A fast taboo search algorithm for the job shop problem

• 成果类型: Article
• 署名作者: Nowicki, E; Smutnicki, C
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.42.6.797
• 发表日期: 1996
• 页码: 797-813
• 关键词: scheduling; heuristics; job-shop; taboo search

摘要

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 x 10 hard benchmark problem within 30 seconds on a personal computer.