Machine Sequencing Via Disjunctive Graphs: An Implicit Enumeration Algorithm

摘要

A disjunctive graph is a generalized graph some of whose arcs are disjunctive. Such graphs translate a variety of scheduling-type problems, like machine sequencing. The latter problem can be reduced to that of finding a minimaximal path (shortest critical path) in a disjunctive PERT network. The present paper describes an implicit enumeration algorithm for finding such a path by solving a sequence of PERT problems. The algorithm finds at an early stage a local optimum; thus one can stop at any moment with a reasonably 'good' feasible solution. The number of PERT problems whose data are to be stored at any given moment cannot exceed the number of disjunctive pairs of arcs. (Author)