Forcing relations for AND/OR precedence constraints
Rolf H. Möhring, Martin Skutella, Frederik Stork · 2000
. 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 signicant 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. Introduction. For a set V of activities or jobs, precedence constraints are usually given by a set E of ordered pairs (i; j), i 6= j 2 V , inducing an ac...