Publication | Closed Access
A Computational Study of the Job-Shop Scheduling Problem
890
Citations
0
References
1991
Year
Mathematical ProgrammingBranch-and-bound AlgorithmEngineeringIndustrial EngineeringComputational ComplexityJob-shop Scheduling ProblemOperations ResearchSun Sparcstation 1LogisticsSystems EngineeringParallel ComputingCombinatorial OptimizationJob SchedulerHeuristic MethodCombinatorial ProblemComputer EngineeringComputer ScienceSupply Chain ManagementInteger ProgrammingScheduling ProblemProduction SchedulingBusinessScheduling (Production Processes)Parallel ProgrammingBranch And Bound
The job‑shop scheduling problem is a notoriously difficult combinatorial optimization problem, with even modest instances remaining computationally intractable, though recent algorithmic advances have been made. We designed and implemented a new heuristic procedure for finding schedules, a cutting‑plane method for lower bounds, and a combinatorial branch‑and‑bound algorithm. Our combined procedure solved the well‑known 10×10 problem of Muth and Thomson in under seven minutes on a Sun Sparcstation 1. INFORMS Journal on Computing (ISSN 1091‑9856) was published as ORSA Journal on Computing from 1989 to 1995 (ISSN 0899‑1499).
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×10 problem of J. F. Muth and G. L. Thomson in under 7 minutes of computation time on a Sun Sparcstation 1. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.