Machine sequencing: Disjunctive graphs and degree‐constrained subgraphs

In two earlier papers, we proposed algorithms for finding an optimal sequence of processing m items on q machines, by finding a minimaximal path in a disjunctive network. In a third paper, this latter model was generalized (from 2‐state to 3‐state disjunctive graphs) so as to accommodate project scheduling with resource constraints. In this paper, we discuss another algorithm for the (2‐state) disjunctive network problem, closely related to those mentioned above. To make the paper self‐contained, section 2 briefly describes the problem. Section 3 introduces a class of constraints which forms the basis of the algorithm discussed in section 4. The constraints have only 1, −1, or 0 as coefficients on the left‐hand side, integers on the right‐hand side. The whole procedure of generating these constraints and finding a feasible solution whenever a new constraint is added, can be interpreted (section 5) as a process of generating a graph with degree‐constraints on its nodes, and then finding a subgraph satisfying the degree‐constraints. The nodes of the graph are generated by solving a critical‐path‐problem, the feasible subgraphs are found by implicit enumeration.