作业车间调度问题的一种混合式算法  

Hybrid Algorithm for Job Shop Scheduling

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

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

出　　处：《小型微型计算机系统》2006年第1期97-100,共4页Journal of Chinese Computer Systems

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

摘　　要：描述了一种解决作业车间调度最短完工时间问题的混合式算法.该算法基于禁忌搜索和转换瓶颈技术.算法中利用了多种禁忌搜索方法.为了得到更好的结果,算法中还引入了倒转技术.从对一组问题基准实例的实验计算结果看,该算法在合理的计算时间内,对多个实例得到比当前解决该问题的最高效的启发式算法之一的TSSB算法更好的结果.A hybrid algorithm for solving the minimum makespan problem of job shop scheduling is presented in this paper. The algorithm is based on taboo search and shifting bottleneck technique. Several taboo search methods are utilized in the algorithm. To get some improvement, the reverse technique is applied in the algorithm. Computational experiments on a set of benchmark problem instances show that, in several eases, the approach, in a reasonable amount of computing time, yields better results than TSSB,which is one of most efficient heuristic algorithms for the problem.

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]