一种基于禁忌搜索方法的作业车间调度  

An algorithm based on taboo search method for job shop scheduling

作　　者：黄志[1] 黄文奇[1] 

机构地区：[1]华中科技大学计算机科学与技术学院,湖北武汉430074

出　　处：《华中科技大学学报（自然科学版）》2005年第12期109-111,共3页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：国家重点基础研究发展计划资助项目(G1998030600)

摘　　要：提出了一种解决作业车间调度最短完工时间问题的启发式算法.该算法中采用了变禁忌表长度策略的禁忌搜索方法.在禁忌搜索过程中利用完工时间(makespan)的一个下界作为判断一个解好坏的辅助量,由于得到该下界所需的计算量远远小于完工时间的,因此大大地减少了禁忌搜索过程的计算时间.从对一组问题基准实例的实验计算结果看,该算法在合理的计算时间内,得到了比当前没有使用转换瓶颈技术的最好的禁忌搜索算法之一的TSAB算法更好的结果.An effective heuristic algorithm for solving the minimum makespan of job shop scheduling was presented in this paper. The taboo search method based on variable length of taboo list was applied in the algorithm. In the taboo search procedure, the lower bound of the completion time （makespan） was utilized as the secondary evaluation of solutions. The computations for achieving the lower bound is much less than those for achieving the completion time, therefore the computational time of the procedure is reduced greatly. The computational experiments on a set of benchmark problem instances showed that, in several cases, the approach, in a reasonable amount of computing time, yields better results than TSAB, which is one of best taboo search algorithms of those not using shifting bottleneck technique.

关 键 词：NP-难问题 作业车间调度 启发式 禁忌搜索 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]