Machine sequencing: Disjunctive graphs and degree‐constrained subgraphs
作者:
Egon Balas,
期刊:
Naval Research Logistics Quarterly
(WILEY Available online 1970)
卷期:
Volume 17,
issue 1
页码: 1-10
ISSN:0028-1441
年代: 1970
DOI:10.1002/nav.3800170102
出版商: Wiley Subscription Services, Inc., A Wiley Company
数据来源: WILEY
摘要:
AbstractIn two earlier papers, we proposed algorithms for finding an optimal sequence of processingmitems onqmachines, 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
点击下载:
PDF
(577KB)
返 回