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

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

17 Citations (Scopus)

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 languageEnglish
Title of host publicationAlgorithms - ESA’ 99
Subtitle of host publication7th Annual European Symposium Prague, Czech Republic, July 16–18, 1999 Proceedings
EditorsJaroslav Nešetřil
Place of PublicationBerlin, Heidelberg
PublisherSpringer
Pages139-150
Number of pages12
ISBN (Electronic)978-3-540-48481-3
ISBN (Print)978-3-540-66251-8
DOIs
Publication statusPublished - 1999
Event7th Annual European Symposium on Algorithms, ESA 1999 - Prague, Czech Republic
Duration: 16 Jul 199918 Jul 1999
Conference number: 7

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume1643
ISSN (Print)0302-9743

Conference

Conference7th Annual European Symposium on Algorithms, ESA 1999
Abbreviated titleESA
CountryCzech Republic
CityPrague
Period16/07/9918/07/99

Keywords

  • Precedence constraints
  • Temporal constraint
  • Project schedule
  • Lagrangian relaxation
  • Project schedule problem

Fingerprint Dive into the research topics of 'Resource-constrained project scheduling: computing lower bounds by solving minimum cut problems'. Together they form a unique fingerprint.

Cite this