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

Jill R. Hardin; George L. Nemhauser; Martin W P Savelsbergh

doi:10.1016/j.disopt.2007.10.003

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

Industrial Engineering and Management Sciences

Research output: Contribution to journal › Article › peer-review

13 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 language	English (US)
Pages (from-to)	19-35
Number of pages	17
Journal	Discrete Optimization
Volume	5
Issue number	1
DOIs	https://doi.org/10.1016/j.disopt.2007.10.003
State	Published - 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

Access to Document

10.1016/j.disopt.2007.10.003

Cite this

@article{35225cc3e1974c1d85b3fdceebf23293,

title = "Strong valid inequalities for the resource-constrained scheduling problem with uniform resource requirements",

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.",

keywords = "Lifting, Multiprocessor scheduling, Resource-constrained scheduling, Time-indexed formulation, Valid inequalities",

author = "Hardin, {Jill R.} and Nemhauser, {George L.} and Savelsbergh, {Martin W P}",

year = "2008",

month = feb,

doi = "10.1016/j.disopt.2007.10.003",

language = "English (US)",

volume = "5",

pages = "19--35",

journal = "Discrete Optimization",

issn = "1572-5286",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

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

AU - Hardin, Jill R.

AU - Nemhauser, George L.

AU - Savelsbergh, Martin W P

PY - 2008/2

Y1 - 2008/2

N2 - 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.

AB - 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.

KW - Lifting

KW - Multiprocessor scheduling

KW - Resource-constrained scheduling

KW - Time-indexed formulation

KW - Valid inequalities

UR - http://www.scopus.com/inward/record.url?scp=38749130089&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38749130089&partnerID=8YFLogxK

U2 - 10.1016/j.disopt.2007.10.003

DO - 10.1016/j.disopt.2007.10.003

M3 - Article

AN - SCOPUS:38749130089

SN - 1572-5286

VL - 5

SP - 19

EP - 35

JO - Discrete Optimization

JF - Discrete Optimization

IS - 1

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this