A time-indexed formulation for single-machine scheduling problems : branch-and-cut

In Van den Akker, Van Hoesel, and Savelsbergh [1994], we have studied a time-indexed formulation for single-machine scheduling problems and have presented a complete characterization of all facet inducing inequalities with right-hand sides 1 and 2 of the convex hull of the monotone extension of the set of feasible schedules. In this paper, we discuss the development of a branch-and-cut algorithm based on these facet inducing inequalities. We describe separation algorithms for each class of these inequalities, and elaborate on various other important components of the branch-and-cut algorithm, such as branching strategies, cut generation schemes, and primal heuristics. We present our computational experiences with the algorithm for the problem of minimizing the total weighted completion time on a single machine subject to release dates.