Article ID: | iaor20002087 |
Country: | Germany |
Volume: | 85 |
Issue: | 3 |
Start Page Number: | 541 |
End Page Number: | 572 |
Publication Date: | Jan 1999 |
Journal: | Mathematical Programming |
Authors: | Savelsbergh M.W.P., Hoesel C.P.M. van, Akker J.M. van den |
Keywords: | programming: branch and bound |
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