Please use this identifier to cite or link to this item:
For citation please use:
Main Title: On the Representation of Resource Constraints in Project Scheduling
Author(s): Stork, Frederik
Uetz, Marc
Type: Research Paper
Abstract: In project scheduling, resource constraints are usually defined via resource consumption and -availability. Many algorithmic approaches, however, are based on the concept of minimal forbidden sets to represent the resource constraints. Jobs of a forbidden set can be scheduled simultaneously with respect to the precedence constraints, however, they consume more resources than available. Forbidden sets are usually not given explicitly, and by definition even the number of inclusion-minimal forbidden sets may be exponential in the number of jobs. In this paper, we propose a simple branch-and-bound type algorithm to efficiently compute and represent all minimal forbidden sets for a given instance. We evaluate the algorithm on well established test sets of the project scheduling problem library PSPLIB. In addition, we exhibit intimite relations between the different representations of resource constraints and threshold hypergraphs.
Subject(s): project scheduling
resource constraints
forbidden sets
threshold hypergraphs
threshold dimension
minmal cover inequalities
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, 693
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: 205.33 kB
DownloadShow Preview
Format: Postscript | Size: 466.9 kB

Item Export Bar

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