Some new results on simulated annealing applied to the job shop scheduling problem |
| |
Affiliation: | 1. School of Mathematical and Physical Sciences, University of Technology Sydney, Australia;2. PolyU Business School, The Hong Kong Polytechnic University, Hong Kong |
| |
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 (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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|