Meta-heuristics for the Job Shop Scheduling Problem [PDF]
M. Ventresca and B.M. Ombuki, December 2003.
Meta-heuristics have been shown to provide effective approximate solutions for difficult NP-hard combinatorial optimization problems. This paper, presents a comparative study of a genetic algorithm (introduced in previous works), with simulated annealing (SA), tabu search (TS), and hybrid methods for the job-shop scheduling problem (JSSP). The approaches are tested on some well-known job shop benchmark problems. We show that the SA and TS outperform the GA. However, neither simulated annealing nor tabu search is uniformly superior over the other. Hybridization of genetic algorithm with tabu is shown to present the most promising solution quality for the JSSP problem instances investigated here.