A Computational Study of Local Search Algorithms for Job Shop Scheduling

TLDR

The study evaluates the computational performance of local search algorithms for job shop scheduling. The authors compare iterative improvement, simulated annealing, threshold accepting, and genetic local search. Simulated annealing yields superior solutions within the same runtime compared to other local search methods, yet tabu search achieves faster runtimes, and it remains best against tailored algorithms only when time is not a constraint. Published in INFORMS Journal on Computing (ISSN 1091‑9856), formerly ORSA Journal on Computing (ISSN 0899‑1499, 1989‑1995).

Abstract

We present a computational performance analysis of local search algorithms for job shop scheduling. The algorithms under Investigation are Iterative improvement, simulated annealing, threshold accepting, and genetic local search. Our study shows that simulated annealing performs best in the sense that it finds better solutions than the other algorithms within the same amount of running time. Compared to more tailored algorithms, simulated annealing still finds the best results but only under the assumption that running time is of no concern. Compared to tabu search, simulated annealing is outperformed especially with respect to running times. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.