A polyhedral approach to single-machine scheduling problems |
| |
| Authors: | J.M. van den Akker C.P.M. van Hoesel M.W.P. Savelsbergh |
| |
| Affiliation: | (1) Information and Communication Technology Division, National Aerospace Laboratory NLR, P.O.Box 90502, 1006 BM Amsterdam, The Netherlands, e-mail: vdakker@nlr.nl., NL;(2) Department of Quantitative Economics, University of Limburg, P.O.Box 616, 6200 MD Maastricht, The Netherlands, e-mail: s.vanhoesel@ke.unimaas.nl, NL;(3) School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205, USA, e-mail: mwps@akula.isye.gatech.edu, US |
| |
| Abstract: | We report new results for a time-indexed formulation of nonpreemptive single-machine scheduling problems. We give complete characterizations of all facet inducing inequalities with integral coefficients and right-hand side 1 or 2 for the convex hull of the set of feasible partial schedules, i.e., schedules in which not all jobs have to be started. Furthermore, we identify conditions under which these facet inducing inequalities are also facet inducing for the original polytope, which is the convex hull of the set of feasible complete schedules, i.e., schedules in which all jobs have to be started. To obtain insight in the effectiveness of these classes of facet-inducing inequalities, we develop a branch-and-cut algorithm based on them. We evaluate its performance on the strongly NP-hard single machine scheduling problem of minimizing the weighted sum of the job completion times subject to release dates. Received March 24, 1994 / Revised version received February 13, 1997 Published online June 28, 1999 |
| |
| Keywords: | : scheduling – polyhedral methods – facet inducing inequalities – separation – branch-and-cut |
| 本文献已被 SpringerLink 等数据库收录！ |
|
