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

R.H. Möhring, J. Nesetril (Editor), A.S. Schulz, F. Stork, Marc Jochen Uetz

  • 15 Citations

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 languageUndefined
Pages139-150
Number of pages12
DOIs
StatePublished - 1999

Fingerprint

Scheduling problem
Resource-constrained project scheduling
Lower bound
Costs
Minimum cut
Project scheduling
Temporal constraints
Time windows
Testbed
Directed graph
Polynomial-time algorithm
Schedule
Objective function

Keywords

  • EWI-12244
  • IR-62242

Cite this

Möhring, R.H.; Nesetril, J. (Editor); Schulz, A.S.; Stork, F.; Uetz, Marc Jochen / Resource-constrained project scheduling: computing lower bounds by solving minimum cut problems.

1999. 139-150.

Research output: Scientific - peer-reviewPaper

@misc{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 = "EWI-12244, IR-62242",
author = "R.H. Möhring and J. Nesetril and A.S. Schulz and F. Stork and Uetz, {Marc Jochen}",
year = "1999",
doi = "10.1007/3-540-48481-7_13",
pages = "139--150",

}

Resource-constrained project scheduling: computing lower bounds by solving minimum cut problems. / Möhring, R.H.; Nesetril, J. (Editor); Schulz, A.S.; Stork, F.; Uetz, Marc Jochen.

1999. 139-150.

Research output: Scientific - peer-reviewPaper

TY - CONF

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

AU - Möhring,R.H.

AU - Schulz,A.S.

AU - Stork,F.

AU - Uetz,Marc Jochen

A2 - Nesetril,J.

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 - EWI-12244

KW - IR-62242

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

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

M3 - Paper

SP - 139

EP - 150

ER -