Some new results on simulated annealing applied to the job shop scheduling problem

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 (GA) 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. (C) 1999 Elsevier Science B.V. All rights reserved.