Machine Sequencing Via Disjunctive Graphs: An Implicit Enumeration Algorithm

One formulation of the machine sequencing problem is that of finding a mini-maximal path in a disjunctive graph. This paper describes an implicit enumeration procedure that solves the problem by generating a sequence of circuit-free graphs and solving a slightly amended critical-path problem for each graph in the sequence. Each new term of the sequence is generated from an earlier one by complementing one disjunctive arc. The search tree is drastically cut down by the fact that the only disjunctive arcs that have to be considered for being complemented are those on a critical path. An evaluation of these candidates is used to direct the search at each stage. The procedure can start with any feasible schedule (like the one actually used in production, or generated by some heuristics), and gradually improve it. Thus one can possibly stop short of the optimum, with a reasonably “good” feasible schedule. Storage requirements are limited to the data pertinent to the current node of the search tree.