An optimal schedule time of a job shop-like disjunctive graph

✍ Scribed by S. Ashour; K. Y. Chiu; T. E. Moore

• Publisher: John Wiley and Sons
• Year: 1973
• Tongue: English
• Weight: 812 KB
• Volume: 3
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.3230030405

✦ Synopsis

Abstract

This paper considers the shop scheduling problem which involves both job precedence and machine interference constraints. Based on the graph‐theoretical representation of the problem, a branch‐and‐bound algorithm is proposed for implicitly producing an optimal schedule such that the schedule time is minimized. The algorithm utilizes a set of heuristic rules, in addition to a powerful bounding procedure, to guide the search. An upper bound is also employed to recognize an optimal solution in earlier stages. The procedure is illustrated by a sample problem and its rapid convergence is demonstrated by a set of published problems. The proposed algorithm is compared favorably with existing procedures.