Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem

François Margot (), Maurice Queyranne () and Yaoguang Wang ()
Additional contact information
François Margot: GSIA, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, Pennsylvania 15213
Maurice Queyranne: Faculty of Commerce, University of British Columbia, Vancouver, British Columbia, Canada
Yaoguang Wang: PeopleSoft, Inc., Pleasanton, California 94566

Operations Research, 2003, vol. 51, issue 6, 981-992

Abstract: We present an in-depth theoretical, algorithmic, and computational study of a linear programming (LP) relaxation to the precedence constrained single-machine scheduling problem 1|prec|(Sigma) j w j C j to minimize a weighted sum of job completion times. On the theoretical side, we study the structure of tight parallel inequalities in the LP relaxation and show that every permutation schedule that is consistent with Sidney's decomposition has total cost no more than twice the optimum. On the algorithmic side, we provide a parametric extension to Sidney's decomposition and show that a finest decomposition can be obtained by essentially solving a parametric minimum-cut problem. Finally, we report results obtained by an algorithm based on these developments on randomly generated instances with up to 2,000 jobs.

Keywords: Network/graphs; flow algorithms: parametric flows and Sidney decompositions; Production/scheduling; approximations: 2-approximation algorithm; Programming; integer; algorithms; relaxation/subgradient: integer formulation (search for similar items in EconPapers)
Date: 2003
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.51.6.981.24912 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:51:y:2003:i:6:p:981-992

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().