Forcing Relations for AND/OR Precedence Constraints

Rolf H. Möhring, Martin Skutella, and Frederik Stork

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]