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

提出了一种解决作业车间调度最短完工时间问题的启发式算法．该算法中采用了变禁忌表长度策略的禁忌搜索方法．在禁忌搜索过程中利用完工时间（makespan）的一个下界作为判断一个解好坏的辅助量，由于得到该下界所需的计算量远远小于完工时间的，因此大大地减少了禁忌搜索过程的计算时间．从对一组问题基准实例的实验计算结果看，该算法在合理的计算时间内，得到了比当前没有使用转换瓶颈技术的最好的禁忌搜索算法之一的TSAB算法更好的结果．

An algorithm based on taboo search method for job shop scheduling

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.