Decompositions, network flows, and a precedence constrained single-machine scheduling problem

• 成果类型: Article
• 署名作者: Margot, F; Queyranne, M; Wang, YG
• 署名单位: Carnegie Mellon University; University of British Columbia
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.51.6.981.24912
• 发表日期: 2003
• 页码: 981-992
• 关键词: network/graphs; flow algorithms : parametric flows and Sidney decompositions production/scheduling; approximations : 2-approximation; algorithm; programming; integer; algorithms; relaxation/subgradient : integer formulation

摘要

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.