Premium
An optimal schedule time of a job shop‐like disjunctive graph
Author(s) -
Ashour S.,
Chiu K. Y.,
Moore T. E.
Publication year - 1973
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230030405
Subject(s) - bounding overwatch , mathematical optimization , computer science , job shop scheduling , schedule , job shop , upper and lower bounds , scheduling (production processes) , heuristic , graph , branch and bound , algorithm , flow shop scheduling , mathematics , theoretical computer science , artificial intelligence , mathematical analysis , operating system
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.