Job shop scheduling by simulated annealing

Job shop scheduling by simulated annealing

0.00 Avg rating0 Votes
Article ID: iaor19921901
Country: United States
Volume: 40
Issue: 1
Start Page Number: 113
End Page Number: 125
Publication Date: Jan 1992
Journal: Operations Research
Authors: , ,
Keywords: scheduling
Abstract:

The authors describe an approximation algorithm for the problem of finding the minimum makespan in a job shop. The algorithm is based on simulated annealing, a generalization of the well known iterative improvement approach to combinatorial optimization problems. The generalization involves the acceptance of cost-increasing transitions with a nonzero probability to avoid getting stuck in local minima. The authors prove that the present algorithm asymptotically converges in probability to a globally minimal solution, despite the fact that the Markov chains generated by the algorithm are generally not irreducible. Computational experiments show that the algorithm can find shorter makespans than two recent approximation approaches that are more tailored to the job shop scheduling problem. This is, however, at the cost of large running times.

Reviews

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