TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)1999

COGA 5-Wheel

Page Content

to Navigation

Preprints 1999

Forcing Relations for AND/OR Precedence Constraints
Citation key Report-646-1999
Author Rolf H. Möhring and Martin Skutella and Frederik Stork
Year 1999
Number 646
Note Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'00), pp. 235-236
Institution Technische Universität Berlin, Institut für Mathematik
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.
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe