The relation of time indexed formulations of nonpreemptive single machine scheduling problems to the node packing problem is 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 5-hole inequalities of the convex hull of the set of feasible node packings in this graph respectively.

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

NOBILI, Paolo;
2002

Abstract

The relation of time indexed formulations of nonpreemptive single machine scheduling problems to the node packing problem is 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 5-hole inequalities of the convex hull of the set of feasible node packings in this graph respectively.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11587/107190
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 15
social impact