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

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

0.00 Avg rating0 Votes
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:
Keywords: optimization: simulated annealing
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.