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

Algorithm Based on Taboo Search for Job Shop Scheduling

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

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

出　　处：《小型微型计算机系统》2005年第2期222-225,共4页Journal of Chinese Computer Systems

基　　金：国家"九七三"重点基础研究规划项目 (19980 3 0 60 0 )资助 .

摘　　要：描述了一种解决作业车间调度最短完工时间问题的有效的启发式算法 .该算法基于禁忌搜索技术 .算法中利用了新的禁忌搜索方法 .从对一组问题基准实例的实验计算结果看 ,该算法在合理的计算时间内 ,对多个实例得到比当前没有用转换瓶颈技术的禁忌搜索中最好的算法之一的 TSAB算法更好的结果.An effective heuristic algorithm for solving the minimum makespan problem of job shop scheduling is presented in this paper. The algorithm is based on taboo search technique. A new developed taboo search method is used in the algorithm. Computational experiments on a set of benchmark problem instances show 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 algorithm of those not using shifting bottleneck technique.

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

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