Please use this identifier to cite or link to this item:
For citation please use:
Main Title: Resource-Constrained Project Scheduling: From a Lagrangian Relaxation to Competitive Solutions
Author(s): Stork, Frederik
Uetz, Marc
Type: Research Paper
Abstract: List scheduling belongs to the classical and widely used algorithms for scheduling problems, but for resource-constrained project scheduling problems most standard priority lists do not capture enough of the problem structure, often resulting in poor performance. We use a well-known Lagrangian relaxation to first compute schedules which do not necessarily respect the resource constraints. We then apply list scheduling in the order of so-called α-completion times of jobs. Embedded into a standard subgradient optimization, our computational results show that the schedules compare to those obtained by state-of-the-art local search algorithms. In contrast to purely primal heuristics, however, the Lagrangian relaxation also provides powerful lower bounds, thus the deviation between lower and upper bounds can be drastically reduced by this approach.
Subject(s): scheduling
project scheduling
Lagrangian relaxation
list scheduling
Issue Date: 2000
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: 2000, 661
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: 88.46 kB
DownloadShow Preview
Format: Unknown | Size: 87.32 kB

Item Export Bar

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