Authors 
: 

Document type 
: 
Document de travail (Working Paper) 
Abstract 
: 
The relation of time indexed formulations of nonpreemptive single machine scheduling
problems to the node packing problem is formally established and then used to
provide simple and intuitive alternate proofs of validity and maximality for previously
known results on the facial structure of the scheduling problem. Previous work on the
facial structure has focused on describing the convex hull of the set of feasible partial
schedules, i.e. schedules in which not all jobs have to be started. The equivalence
between the characteristic vectors of this set and those of the set of feasible node
packings in a graph whose structure is determined by the parameters of the scheduling
problem is established. The main contribution of this paper is to show that the facet
inducing inequalities for the convex hull of the set of feasible partial schedules that
have integral coefficients and right hand side 1 or 2 are the maximal clique inequalities
and the maximally and sequentially lifted 5hole inequalities of the convex hull of the
set of feasible node packings in this graph respectively. 
Access type 
: 
Accès libre

Publication date 
: 
2002 
Collection 
: 
CORE Discussion Papers  2002/09 
Affiliation 
: 
UCL
 CORE  Center for Operations Research and Econometrics

Keywords 
: 
Scheduling ; Node packing ; Polyhedral methods ; Facet defining graphs ; Lifted valid inequalities ; Facet inducing inequalities

Links 
: 
