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

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

0.00 Avg rating0 Votes
Article ID: iaor20073271
Country: United States
Volume: 51
Issue: 6
Start Page Number: 981
End Page Number: 992
Publication Date: Nov 2003
Journal: Operations Research
Authors: , ,
Keywords: networks: flow, programming: integer
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|jwjCj 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.

Reviews

Required fields are marked *. Your email address will not be published.