Loading…
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 agains...
Saved in:
Published in: | European journal of operational research 1999-02, Vol.113 (1), p.123-136 |
---|---|
Main Author: | |
Format: | Article |
Language: | English |
Subjects: | |
Citations: | Items that this one cites Items that cite this one |
Online Access: | Get full text |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Summary: | 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. |
---|---|
ISSN: | 0377-2217 1872-6860 |
DOI: | 10.1016/S0377-2217(97)00420-7 |