Strong valid inequalities for the resource-constrained scheduling problem with uniform resource requirements

Jill R. Hardin*, George L. Nemhauser, Martin W P Savelsbergh

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

We consider the resource-constrained scheduling problem when each job's resource requirements remain constant over its processing time. We study a time-indexed formulation of the problem, providing facet-defining inequalities for a projection of the resulting polyhedron that exploit the resource limitations inherent in the problem. Lifting procedures are then provided for obtaining strong valid inequalities for the original polyhedron. Computational results are presented to demonstrate the strength of these inequalities.

Original languageEnglish (US)
Pages (from-to)19-35
Number of pages17
JournalDiscrete Optimization
Volume5
Issue number1
DOIs
StatePublished - Feb 2008

Keywords

  • Lifting
  • Multiprocessor scheduling
  • Resource-constrained scheduling
  • Time-indexed formulation
  • Valid inequalities

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Strong valid inequalities for the resource-constrained scheduling problem with uniform resource requirements'. Together they form a unique fingerprint.

Cite this