A Fast Taboo Search Algorithm for the Job Shop Problem

Eugeniusz Nowicki and Czeslaw Smutnicki
Additional contact information
Eugeniusz Nowicki: Technical University of Wroc{\l}aw, Institute of Engineering Cybernetics, ul. Janiszewskiego 11/17, 50-372 Wroc{\l}aw, Poland
Czeslaw Smutnicki: Technical University of Wroc{\l}aw, Institute of Engineering Cybernetics, ul. Janiszewskiego 11/17, 50-372 Wroc{\l}aw, Poland

Management Science, 1996, vol. 42, issue 6, 797-813

Abstract: A fast and easily implementable approximation algorithm for the problem of finding a minimum makespan in a job shop is presented. The algorithm is based on a taboo search technique with a specific neighborhood definition which employs a critical path and blocks of operations notions. Computational experiments (up to 2,000 operations) show that the algorithm not only finds shorter makespans than the best approximation approaches but also runs in shorter time. It solves the well-known 10 \times 10 hard benchmark problem within 30 seconds on a personal computer.

Keywords: scheduling; heuristics; job-shop; taboo search (search for similar items in EconPapers)
Date: 1996
References: Add references at CitEc
Citations: View citations in EconPapers (92)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.42.6.797 (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:ormnsc:v:42:y:1996:i:6:p:797-813

Access Statistics for this article

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