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

✍ Scribed by M. Kolonko

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 256 KB
• Volume: 113
• Category: Article
• ISSN: 0377-2217
• DOI: 10.1016/s0377-2217(97)00420-7

✦ Synopsis

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.