A Fast Taboo Search Algorithm for the Job Shop Problem
Eugeniusz Nowicki, Czeslaw Smutnicki
Management Science · 1996 · Volume 42 · Issue 6
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 × 10 hard benchmark problem within 30 seconds on a personal computer.
Keywords
scheduling, heuristics, job-shop, taboo search
Enable JavaScript for citation tools and additional paper interactions.