JOB SHOP SCHEDULING BY SIMULATED ANNEALING
成果类型：
Article
署名作者：
VANLAARHOVEN, PJM; AARTS, EHL; LENSTRA, JK
署名单位：
Philips; Philips Research; Eindhoven University of Technology; Centrum Wiskunde & Informatica (CWI)
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.40.1.113
发表日期：
1992
页码：
113-125
关键词：
摘要：
We 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. We prove that our 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 our 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.