Please use this identifier to cite or link to this item:
For citation please use:
Main Title: Resource Constrained Project Scheduling: Computing Lower Bounds by Solving Minimum Cut Problems
Author(s): Möhring, Rolf H.
Schulz, Andreas S.
Stork, Frederik
Uetz, Marc
Type: Research Paper
Abstract: We propose a novel approach to compute 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. Motivated by a known result that this problem can be formulated as a cardinality-constrained stable set problem in comparability graphs, we show how to reduce it to a minimum cut problem in an appropriate directed graph. We then focus on an application of this algorithm to different types of resource-constrained project scheduling problems by using it for the computation of lower bounds on the objective function value via Lagrangian relaxation of these problems. This approach shows to be applicable to various problem settings, and an extensive study based on widely accepted test beds in project scheduling reveals that our algorithm significantly improves upon other fast computable lower bounds at very modest running times. For problems with time windows, we obtain the best known bounds for several instances, and for a class of notoriously hard labor-constrained scheduling problem with time-varying resources, we drastically reduce the time to obtain the lower bounds based on the corresponding LP relaxation. For precedence-constrained scheduling with several resource types, our bounds are again computed very fast, and improve the bounds obtained in reasonable time by all currently known algorithms.
Subject(s): scheduling
project scheduling
Lagrangian relaxation
subgradient optimization
minimum cut
Issue Date: 1998
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 1998, 620
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 180 kB
DownloadShow Preview
Format: Postscript | Size: 422.14 kB

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.