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.
