A polyhedral approach to single-machine scheduling problems

A polyhedral approach to single-machine scheduling problems

0.00 Avg rating0 Votes
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: , ,
Keywords: programming: branch and bound
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.

Reviews

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