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

Ismael Regis de Farias, Hongxia Zhao, Ming Zhao

Research output: Contribution to journalArticlepeer-review

16 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)1610-1614
Number of pages5
JournalComputers and Operations Research
Volume37
Issue number9
DOIs
StatePublished - Sep 2010

Keywords

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

Fingerprint Dive into the research topics of 'A family of inequalities valid for the robust single machine scheduling polyhedron'. Together they form a unique fingerprint.

Cite this