Machine sequencing: Disjunctive graphs and degree‐constrained subgraphs

Egon Balas

Naval Research Logistics Quarterly, 1970, vol. 17, issue 1, 1-10

Abstract: 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.

Date: 1970
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/nav.3800170102

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navlog:v:17:y:1970:i:1:p:1-10

Access Statistics for this article

More articles in Naval Research Logistics Quarterly from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().