Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14708
For citation please use:
Main Title: Forcing Relations for AND/OR Precedence Constraints
Author(s): Möhring, Rolf H.
Skutella, Martin
Stork, Frederik
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15935
http://dx.doi.org/10.14279/depositonce-14708
License: http://rightsstatements.org/vocab/InC/1.0/
Abstract: A natural generalization of ordinary precedence constraints are so-called AND/ OR precedence constraints. In an AND constraint, a job must wait for all its predecessors while in an OR constraint, a job has to wait for at least one of its predecessors. We provide a linear-time algorithm for deducing additional AND/ OR precedence constraints that are implied by the given ones. We show that this algorithm can also be used to verify feasibility of the given constraints. Besides their theoretical value, these results have significant impact in practical applications such as scheduling and assembly sequencing; we show how to use our algorithm to improve solution procedures for resource-constrained project scheduling problems. Finally, we prove that for a related, more general model, the problems under consideration are strongly NP-complete.
Subject(s): precedence constraints
AND/OR
relations
AND constraint
OR constraints
Issue Date: 1999
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: 1999, 646
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-646-1999.pdf
Format: Adobe PDF | Size: 166.57 kB
DownloadShow Preview
Thumbnail
Report-646-1999.ps.gz
Format: Unknown | Size: 68.15 kB
Download

Item Export Bar

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