Machine Sequencing Via Disjunctive Graphs: An Implicit Enumeration Algorithm

TLDR

Machine sequencing can be framed as finding a mini‑maximal path in a disjunctive graph. The paper proposes an implicit enumeration algorithm that solves machine sequencing by generating a sequence of circuit‑free graphs and solving an amended critical‑path problem for each. The method iteratively complements a disjunctive arc on a critical path to generate new circuit‑free graphs, evaluates candidates to steer the search, can start from any feasible schedule, and stores only data for the current node, thereby cutting the search tree. The algorithm can terminate before reaching the optimum, yielding a reasonably good feasible schedule.

Abstract

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.