Applegate, David; Cook, William A computational study of the job-shop scheduling problem. (English) Zbl 0755.90039 ORSA J. Comput. 3, No. 2, 149-156 (1991). Summary: The job-shop scheduling problem is a notoriously difficult problem in combinatorial optimization. Although even modest sized instances remain computationally intractable, a number of important algorithmic advances have been made in recent years by J. Adams, E. Balas and D. Zawack; J. Carlier and E. Pinson; B. J. Lageweg, J. K. Lenstra and A. H.G. Rinnooy Kan; and others. Making use of a number of these advances, we have designed and implemented a new heuristic procedure for finding schedules, a cutting-plane method for obtaining lower bounds, and a combinatorial branch and bound algorithm. Our optimization procedure, combining the heuristic method and the combinatorial branch and bound algorithm, solved the well-known \(10\times 10\) problem of J. F. Muth and G. L. Thomson in under 7 minutes of computation time on a Sun Sparcstation 1. Cited in 1 ReviewCited in 118 Documents MSC: 90B35 Deterministic scheduling theory in operations research 90-08 Computational methods for problems pertaining to operations research and mathematical programming Keywords:job-shop scheduling; heuristic procedure; cutting-plane method; lower bounds; branch and bound Software:JOBSHOP PDFBibTeX XMLCite \textit{D. Applegate} and \textit{W. Cook}, ORSA J. Comput. 3, No. 2, 149--156 (1991; Zbl 0755.90039) Full Text: DOI