A Fast Taboo Search Algorithm for the Job Shop Problem

作者：Eugeniusz Nowicki, Czesław Smutnicki · 发表于：Management Science · 年份：1996 · DOI：10.1287/mnsc.42.6.797 · 被引用次数：979 · 研究领域：Scheduling and Optimization Algorithms、Advanced Manufacturing and Logistics Optimization、Optimization and Packing Problems

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.