Article ID: | iaor20001509 |
Country: | Netherlands |
Volume: | 113 |
Issue: | 1 |
Start Page Number: | 123 |
End Page Number: | 136 |
Publication Date: | Feb 1999 |
Journal: | European Journal of Operational Research |
Authors: | Kolonko M. |
Keywords: | optimization: simulated annealing |
We present two results about heuristic solutions to the job shop scheduling problem (JSP). First, we show that the well-known analytical results on convergence of simulated annealing (SA) do not hold in the application to the JSP. We give a simple counterexample where the SA process converges against a suboptimal schedule. To overcome this problem at least heuristically, we present a new approach that uses a small population of SA runs in a genetic algorithm framework. The novel features are an adaptive temperature control that allows ‘reheating’ of the SA and a new type of time-oriented crossover of schedules. Though the procedure uses only standard properties of the JSP it yields excellent results on the classical test examples.