A family of inequalities valid for the robust single machine scheduling polyhedron

作者：de Farias Ismael Regis Jr^*; Zhao Hongxia; Zhao Ming

来源：Computers & Operations Research, 2010, 37(9): 1610-1614.

DOI：10.1016/j.cor.2009.12.001

• Single machine scheduling
• Branch-and-cut
• Mixed-integer programming
• Robust optimization

We consider the problem of sequencing a set of jobs in a single machine to minimize the maximum of the total weighted completion time of the jobs over a number of scenarios, each corresponding to a set of job processing times. We give a large family of inequalities that are valid for the convex hull of the set of feasible schedules. We then present computational experience in which some of the inequalities are added to the original formulation. We demonstrate through the computational results that their addition to the formulation can substantially improve, among other things, the time required to solve difficult instances of the problem through branch-and-cut.

• 出版日期2010-9