TY - JOUR
T1 - A family of inequalities valid for the robust single machine scheduling polyhedron
AU - de Farias, Ismael Regis
AU - Zhao, Hongxia
AU - Zhao, Ming
N1 - Copyright:
Copyright 2010 Elsevier B.V., All rights reserved.
PY - 2010/9
Y1 - 2010/9
N2 - 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.
AB - 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.
KW - Branch-and-cut
KW - Mixed-integer programming
KW - Robust optimization
KW - Single machine scheduling
UR - http://www.scopus.com/inward/record.url?scp=75449111777&partnerID=8YFLogxK
U2 - 10.1016/j.cor.2009.12.001
DO - 10.1016/j.cor.2009.12.001
M3 - Article
AN - SCOPUS:75449111777
VL - 37
SP - 1610
EP - 1614
JO - Computers and Operations Research
JF - Computers and Operations Research
SN - 0305-0548
IS - 9
ER -