摘要： 为了解决单一算法求解Job Shop调度问题存在的不足，该文提出了一种混合算法，将蚁群算法用于全局搜索。针对蚁群算法易于陷入局部最优的情况，提出了一种基于关键工序的邻域搜索方法，将使用此邻域搜索方法的TS算法作为局部搜索策略。利用TS算法较强的局部搜索能力，提高了蚁群算法的优化能力，达到改善Job Shop调度问题解的质量。实验结果表明，混合算法在较短的时间内，找到了FT10、LA24、LA36等典型benchmarks问题的最优解，得到的makespan的平均值较并行遗传算法(PGA)和TSAB算法均有所提高。

关键词: 蚁群算法, 禁忌搜索, 混合算法, Job Shop调度

Abstract: It is hard to get solutions in job shop schedule problem using by single algorithms. This paper proposes a hybrid algorithm for job shop schedule. The ant colony algorithm which plunges the local situation easily is used as a global search algorithm. In addition it proposes taboo search algorithm based on a new neighborhood search method, and the TS algorithms in the method are used as local search algorithm. Because the TS algorithms have the stronger local search ability, and it can overcome the disadvantages of ant colony algorithms, so it gets satisfied solutions for job shop scheduling. The experimental results show that this algorithm can solve typical benchmarks problems efficiently, such as FT10, LA24, LA3 efficiently. The hybrid algorithm gets higher the average agreement compared with TSAB and PGA.

Key words: Ant colony algorithm, Taboo search, Hybrid algorithm, Job shop schedule