hide
Free keywords:
-
Abstract:
In many scheduling applications it is required that the processing
of some job must be postponed until some other job, which can be
chosen from a pre-given set of alternatives, has been completed. The
traditional concept of precedence constraints fails to model such
restrictions. Therefore, the concept has been generalized to
so-called AND/OR precedence constraints which can cope with
this kind of requirement.
In the context of traditional precedence constraints, feasibility,
transitivity, as well as the computation of earliest start times for
jobs are fundamental, well-studied problems. The purpose of this
paper is to provide efficient algorithms for these tasks for the
more general and complex model of AND/OR precedence constraints. We
show that feasibility as well as many questions related to
transitivity can be solved by applying essentially the same
linear-time algorithm. In order to compute earliest start times we
propose two polynomial-time algorithms to cope with different
classes of time distances between jobs.
