Methods for Checking the Consistency of Precedence Constraints

Abstract

Precedence constraints appear in mathematical models from many different fields of application and the problem of determining whether or not a set of such constraints is consistent is of rather general interest. This paper describes a number of different approaches to this problem. For each approach a survey of existing algorithms is given. An efficient algorithm, especially designed for checking the consistency of activity networks, is developed by the combination of recent graph algorithms with ideas published in the early 60's. The time of computation for this algorithm grows linearly with the number of constraints and it is faster than any other published algorithm when applied to digraphs of a certain structure.