An Improved Branch-and bound Algorithm for the Job-shop Scheduling Problem of Minimising Makespan

  1. Lookup NU author(s)
Author(s)Waller L
Series Editor(s)Shaw B
Publication type Report
Series TitleComputing Laboratory Technical Report Series
DateDecember 1972
Report Number40
Full text is available for this publication:
An improved algorithm for determining an optimimum solution to a job-shop scheduling problem is presented. The algorithm utilises a backtracking branch-and-bound search but a slightly different branching process from that suggested by Lomnicki (2) has been employed and has resulted in the calculation of more realistic lower bounds. The modifications to the algorithm were discovered in interactive investigations into the problem and in such investigations optimal solutions to the scheduling of up to 30 jons upon 5 machines have been acheived within a modest amount (2-3 minutes) of computation.
InstitutionComputing Laboratory, The University of Newcastle upon Tyne
Place PublishedNewcastle upon Tyne
ActionsLink to this publication