The relation of time indexed formulations of single machine scheduling problems to the node packing problem |
| |
Authors: | H Waterer E L Johnson P Nobili MWP Savelsbergh |
| |
Institution: | (1) Center for Operations Research and Econometrics, Université Catholique de Louvain, 34 Voie du Roman Pays, 1348 Louvain-la-Neuve, Belgium, e-mail: waterer@core.ucl.ac.be, BE;(2) School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205, USA, e-mail: ejohnson@isye.gatech.edu, US;(3) Istituto di Analisi dei Sistemi ed Informatica, Consiglio Nazionale delle Ricerche, Viale Manzoni 30, 00185 Roma, Italy, e-mail: nobili@iasi.rm.cnr.it, IT;(4) School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205, USA, e-mail: msavelsbergh@isye.gatech.edu, US |
| |
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, 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.
Received: September 10, 2000 / Accepted: April 20, 2002 Published online: September 27, 2002
Key words. scheduling – node packing – polyhedral methods – facet defining graphs – lifted valid inequalities – facet inducing inequalities} |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|