The relation of time indexed formulations of single machine scheduling problems to the node packing problem

The relation of time indexed formulations of nonpreemptive single machine schedulingproblems to the node packing problem is formally established and then used toprovide simple and intuitive alternate proofs of validity and maximality for previouslyknown results on the facial structure of the scheduling problem. Previous work on thefacial structure has focused on describing the convex hull of the set of feasible partialschedules, i.e. schedules in which not all jobs have to be started. The equivalencebetween the characteristic vectors of this set and those of the set of feasible nodepackings in a graph whose structure is determined by the parameters of the schedulingproblem is established. The main contribution of this paper is to show that the facetinducing inequalities for the convex hull of the set of feasible partial schedules thathave integral coefficients and right hand side 1 or 2 are the maximal clique inequalitiesand the maximally and sequentially lifted 5-hole inequalities of the convex hull of theset of feasible node packings in this graph respectively.