作业车间调度问题的一种改进的转换瓶颈算法  

A Mended Shifting Bottleneck Algorithm for Job Shop Scheduling

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

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

出　　处：《计算机工程与应用》2005年第2期59-62,共4页Computer Engineering and Applications

基　　金：国家973基础研究发展规划项目资助(编号:G1998030600)

摘　　要：描述了一种解决作业车间调度最短完工时间问题有效的启发式算法。该算法是对Adams等人的转换瓶颈算法的改进,算法中用了改进的Calier单机调度方法以克服原Calier算法的不足。从对一组问题基准实例的实验计算结果看,该算法在合理的计算时间内,对多个实例得到比原转换瓶颈算法和Beam搜索算法更好的结果;从实验结果看,算法也优于ISB算法。An effective heuristic algorithm for solving the minimum makespan problem of job shop scheduling is pre-sented in this paper.The algorithm is an improvement of the shifting bottleneck procedure given by Adams et al,and makes use of improved Calier algorithm solving one-machine sequencing problem in order to overcome the drawbacks of Calier 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 shifting bottleneck and beam search al-gorithms.And computational experiments also show that the algorithm get better solutions than ISB.

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

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