Time-Indexed Formulation for Single-Machine Scheduling Problems: Branch-and-Cut

摘要

In Van den Akker, Van Hoesel, and Savelsbergh (1994), the authors have studied atime-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 the paper, the authors discuss the development of a branch-and-cut algorithm based on these facet inducing inequalities.