direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 646-1999

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Forcing Relations for AND/OR Precedence Constraints
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'00), pp. 235-236
not available
not available
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.
Download as [PDF] [ps.gz]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe