Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14732
For citation please use:
Main Title: Solving Project Scheduling Problems by Minimum Cut Computations
Author(s): Möhring, Rolf H.
Schulz, Andreas S.
Stork, Frederik
Uetz, Marc
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15959
http://dx.doi.org/10.14279/depositonce-14732
License: http://rightsstatements.org/vocab/InC/1.0/
Abstract: In project scheduling, a set of precedence-constrained jobs has to be scheduled so as to minimize a given objective. In resource-constrained project scheduling, the jobs additionally compete for scarce resources. Due to its universality, the latter problem has a variety of applications in manufacturing, production planning, project management, and elsewhere. It is one of the most intractable problems in operations research, and has therefore become a popular playground for the latest optimization techniques, including virtually all local search paradigms. We show that a somewhat more classical mathematical programming approach leads to both competitive feasible solutions and strong lower bounds, within quite reasonable computation times. The basic ingredients of our approach are the Lagrangian relaxation of a time-indexed integer programming formulation and relaxation-based list scheduling, enriched with a useful idea from recent approximation algorithms for machine scheduling problems. The efficiency of the algorithm results from the insight that the relaxed problem can be solved by computing a minimum cut in an appropriately defined directed graph. Our computational study covers different types of resource-constrained project scheduling problems, based on several, notoriously hard test sets, including practical problem instances from chemical production planning.
Subject(s): project scheduling
Lagrangian relaxation
lower bounds
minimum cuts
ordering heuristics
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, 680
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:
Report-680-2000.pdf
Format: Adobe PDF | Size: 211.51 kB
DownloadShow Preview
Thumbnail
Report-680-2000.ps.gz
Format: Unknown | Size: 94.83 kB
Download
Report-680-2000.ps
Format: Postscript | Size: 311.01 kB
Download

Item Export Bar

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