Job Shop Scheduling by Simulated Annealing

Peter J. M. van Laarhoven, Emile H. L. Aarts and Jan Karel Lenstra
Additional contact information
Peter J. M. van Laarhoven: Nederlandse Philips Bedrijven, Eindhoven, The Netherlands
Emile H. L. Aarts: Philips Research Laboratories, Eindhoven, The Netherlands, and Eindhoven University of Technology, Eindhoven, The Netherlands
Jan Karel Lenstra: Eindhoven University of Technology, Eindhoven, The Netherlands and CWI, Amsterdam, The Netherlands

Operations Research, 1992, vol. 40, issue 1, 113-125

Abstract: 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.

Keywords: analysis of algorithms; suboptimal algorithms; simulated annealing; production/scheduling; sequencing; deterministic; multiple machine; job shop scheduling (search for similar items in EconPapers)
Date: 1992
References: Add references at CitEc
Citations: View citations in EconPapers (49)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.40.1.113 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:40:y:1992:i:1:p:113-125

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().