Resource-constrained project scheduling: computing lower bounds by solving minimum cut problems

Rolf H. Möhring; Andreas S. Schulz; Frederik Stork; Marc Uetz

doi:10.1007/3-540-48481-7_13

Resource-constrained project scheduling: computing lower bounds by solving minimum cut problems

Rolf H. Möhring, Andreas S. Schulz, Frederik Stork, Marc Uetz

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

18 Citations (Scopus)

11 Downloads (Pure)

Abstract

We present a novel approach to compute Lagrangian lower bounds on the objective function value of a wide class of resource-constrained project scheduling problems. The basis is a polynomial-time algorithm to solve the following scheduling problem: Given a set of activities with start-time dependent costs and temporal constraints in the form of time windows, find a feasible schedule of minimum total cost. In fact, we show that any instance of this problem can be solved by a minimum cut computation in a certain directed graph. We then discuss the performance of the proposed Lagrangian approach when applied to various types of resource-constrained project scheduling problems. An extensive computational study based on different established test beds in project scheduling shows that it can significantly improve upon the quality of other comparably fast computable lower bounds.

Original language	English
Title of host publication	Algorithms - ESA’ 99
Subtitle of host publication	7th Annual European Symposium Prague, Czech Republic, July 16–18, 1999 Proceedings
Editors	Jaroslav Nešetřil
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	139-150
Number of pages	12
ISBN (Electronic)	978-3-540-48481-3
ISBN (Print)	978-3-540-66251-8
DOIs	https://doi.org/10.1007/3-540-48481-7_13
Publication status	Published - 1999
Event	7th Annual European Symposium on Algorithms, ESA 1999 - Prague, Czech Republic Duration: 16 Jul 1999 → 18 Jul 1999 Conference number: 7

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	1643
ISSN (Print)	0302-9743

Conference

Conference	7th Annual European Symposium on Algorithms, ESA 1999
Abbreviated title	ESA
Country/Territory	Czech Republic
City	Prague
Period	16/07/99 → 18/07/99

Keywords

Precedence constraints
Temporal constraint
Project schedule
Lagrangian relaxation
Project schedule problem

Access to Document

10.1007/3-540-48481-7_13

Cite this

Möhring, R. H., Schulz, A. S., Stork, F., & Uetz, M. (1999). Resource-constrained project scheduling: computing lower bounds by solving minimum cut problems. In J. Nešetřil (Ed.), Algorithms - ESA’ 99: 7th Annual European Symposium Prague, Czech Republic, July 16–18, 1999 Proceedings (pp. 139-150). (Lecture Notes in Computer Science; Vol. 1643). Springer. https://doi.org/10.1007/3-540-48481-7_13

Möhring, Rolf H. ; Schulz, Andreas S. ; Stork, Frederik et al. / Resource-constrained project scheduling : computing lower bounds by solving minimum cut problems. Algorithms - ESA’ 99: 7th Annual European Symposium Prague, Czech Republic, July 16–18, 1999 Proceedings. editor / Jaroslav Nešetřil. Berlin, Heidelberg : Springer, 1999. pp. 139-150 (Lecture Notes in Computer Science).

@inproceedings{a85cd7a7ff8e41759a75898fb614f431,

title = "Resource-constrained project scheduling: computing lower bounds by solving minimum cut problems",

abstract = "We present a novel approach to compute Lagrangian lower bounds on the objective function value of a wide class of resource-constrained project scheduling problems. The basis is a polynomial-time algorithm to solve the following scheduling problem: Given a set of activities with start-time dependent costs and temporal constraints in the form of time windows, find a feasible schedule of minimum total cost. In fact, we show that any instance of this problem can be solved by a minimum cut computation in a certain directed graph. We then discuss the performance of the proposed Lagrangian approach when applied to various types of resource-constrained project scheduling problems. An extensive computational study based on different established test beds in project scheduling shows that it can significantly improve upon the quality of other comparably fast computable lower bounds.",

keywords = "Precedence constraints, Temporal constraint, Project schedule, Lagrangian relaxation, Project schedule problem",

author = "M{\"o}hring, {Rolf H.} and Schulz, {Andreas S.} and Frederik Stork and Marc Uetz",

year = "1999",

doi = "10.1007/3-540-48481-7_13",

language = "English",

isbn = "978-3-540-66251-8",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "139--150",

editor = "Jaroslav Ne{\v s}et{\v r}il",

booktitle = "Algorithms - ESA{\textquoteright} 99",

address = "Germany",

note = "7th Annual European Symposium on Algorithms, ESA 1999, ESA ; Conference date: 16-07-1999 Through 18-07-1999",

}

Möhring, RH, Schulz, AS, Stork, F & Uetz, M 1999, Resource-constrained project scheduling: computing lower bounds by solving minimum cut problems. in J Nešetřil (ed.), Algorithms - ESA’ 99: 7th Annual European Symposium Prague, Czech Republic, July 16–18, 1999 Proceedings. Lecture Notes in Computer Science, vol. 1643, Springer, Berlin, Heidelberg, pp. 139-150, 7th Annual European Symposium on Algorithms, ESA 1999, Prague, Czech Republic, 16/07/99. https://doi.org/10.1007/3-540-48481-7_13

Resource-constrained project scheduling: computing lower bounds by solving minimum cut problems. / Möhring, Rolf H.; Schulz, Andreas S.; Stork, Frederik et al.
Algorithms - ESA’ 99: 7th Annual European Symposium Prague, Czech Republic, July 16–18, 1999 Proceedings. ed. / Jaroslav Nešetřil. Berlin, Heidelberg: Springer, 1999. p. 139-150 (Lecture Notes in Computer Science; Vol. 1643).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Resource-constrained project scheduling

T2 - 7th Annual European Symposium on Algorithms, ESA 1999

AU - Möhring, Rolf H.

AU - Schulz, Andreas S.

AU - Stork, Frederik

AU - Uetz, Marc

N1 - Conference code: 7

PY - 1999

Y1 - 1999

N2 - We present a novel approach to compute Lagrangian lower bounds on the objective function value of a wide class of resource-constrained project scheduling problems. The basis is a polynomial-time algorithm to solve the following scheduling problem: Given a set of activities with start-time dependent costs and temporal constraints in the form of time windows, find a feasible schedule of minimum total cost. In fact, we show that any instance of this problem can be solved by a minimum cut computation in a certain directed graph. We then discuss the performance of the proposed Lagrangian approach when applied to various types of resource-constrained project scheduling problems. An extensive computational study based on different established test beds in project scheduling shows that it can significantly improve upon the quality of other comparably fast computable lower bounds.

AB - We present a novel approach to compute Lagrangian lower bounds on the objective function value of a wide class of resource-constrained project scheduling problems. The basis is a polynomial-time algorithm to solve the following scheduling problem: Given a set of activities with start-time dependent costs and temporal constraints in the form of time windows, find a feasible schedule of minimum total cost. In fact, we show that any instance of this problem can be solved by a minimum cut computation in a certain directed graph. We then discuss the performance of the proposed Lagrangian approach when applied to various types of resource-constrained project scheduling problems. An extensive computational study based on different established test beds in project scheduling shows that it can significantly improve upon the quality of other comparably fast computable lower bounds.

KW - Precedence constraints

KW - Temporal constraint

KW - Project schedule

KW - Lagrangian relaxation

KW - Project schedule problem

U2 - 10.1007/3-540-48481-7_13

DO - 10.1007/3-540-48481-7_13

M3 - Conference contribution

SN - 978-3-540-66251-8

T3 - Lecture Notes in Computer Science

SP - 139

EP - 150

BT - Algorithms - ESA’ 99

A2 - Nešetřil, Jaroslav

PB - Springer

CY - Berlin, Heidelberg

Y2 - 16 July 1999 through 18 July 1999

ER -

Möhring RH, Schulz AS, Stork F, Uetz M. Resource-constrained project scheduling: computing lower bounds by solving minimum cut problems. In Nešetřil J, editor, Algorithms - ESA’ 99: 7th Annual European Symposium Prague, Czech Republic, July 16–18, 1999 Proceedings. Berlin, Heidelberg: Springer. 1999. p. 139-150. (Lecture Notes in Computer Science). doi: 10.1007/3-540-48481-7_13

Resource-constrained project scheduling: computing lower bounds by solving minimum cut problems

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this