×

A computational study of the job-shop scheduling problem. (English) Zbl 0755.90039

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.

MSC:

90B35 Deterministic scheduling theory in operations research
90-08 Computational methods for problems pertaining to operations research and mathematical programming

Software:

JOBSHOP
PDFBibTeX XMLCite
Full Text: DOI