Algorithm Based on Taboo Search and Shifting Bottleneck for Job Shop Scheduling  

作　　者：Wen-QiHuang ZhiHuang 

机构地区：[1]CollegeofComputerScience,HuazhongUniversityofScienceandTechnology,Wuhan430074,P.R.China

出　　处：《Journal of Computer Science & Technology》2004年第6期776-781,共6页计算机科学技术学报（英文版）

基　　金：国家重点基础研究发展计划(973计划)

摘　　要：In this paper, a computational effective heuristic method for solving the minimum makespan problem of job shop scheduling is presented. It is based on taboo search procedure and on the shifting bottleneck procedure used to jump out of the trap of the taboo search procedure. A key point of the algorithm is that in the taboo search procedure two taboo lists are used to forbid two kinds of reversals of arcs, which is a new and effective way in taboo search methods for job shop scheduling. Computational experiments on a set of benchmark problem instances show that, in several cases, the approach, in reasonable time, yields better solutions than the other heuristic procedures discussed in the literature.In this paper, a computational effective heuristic method for solving the minimum makespan problem of job shop scheduling is presented. It is based on taboo search procedure and on the shifting bottleneck procedure used to jump out of the trap of the taboo search procedure. A key point of the algorithm is that in the taboo search procedure two taboo lists are used to forbid two kinds of reversals of arcs, which is a new and effective way in taboo search methods for job shop scheduling. Computational experiments on a set of benchmark problem instances show that, in several cases, the approach, in reasonable time, yields better solutions than the other heuristic procedures discussed in the literature.

关 键 词：SCHEDULING job shop NP-HARD HEURISTIC taboo search 

分 类 号：TP311.1[自动化与计算机技术—计算机软件与理论]