基于混合搜索策略的Job Shop调度研究

目的 提出基于遗传算法和禁忌搜索算法的混合算法，解决单一算法求解JobShop调度问题存在的不足，提高求解质量．方法 采用遗传算法作为全局搜索算法，禁忌搜索算法作为局部搜索算法．根据JobShop调度问题解的特征。提出基于关键工序的邻域选择方法，将基于这种邻域选择方法的禁忌搜索算法作为变异算子，加强了遗传算法邻域解的搜索能力．结果 混合算法在较短时间内，找到了FT10、LA24、LA36等典型benchmarks问题的最优解，得到的makespan的平均值较并行遗传算法（PGA）提高3．84％、较TSAB算法提高4.66％．结论 采用的禁忌搜索算法改善了遗传算法的局部搜索能力，说明提出的混合搜索策略是有效的．

Study on Job Shop Scheduling Based on Search Hybrid Strategy

A hybrid algorithm based on genetic algorithm and taboo search algorithms are proposed to solve the Job Shop scheduling problem and improve the quality of solution used by single algorithms.The hybrid algorithm uses the genetic algorithm as a global search algorithm and adopts taboo search algorithms as a local search algorithm.A new neighborhood search method based on the critical operation is introduced.At the same time,the neighborhood search method is introduced into the mutation operator in order to improve the searching ability of genetic algorithms.This algorithm can solve typical benchmark problems efficiently,such as FT10,LA24,LA36.The hybrid search strategy increases the satisfied solution by 3.84% compared with that of PGA and by 4.66% compared with that of TSAB.The results of computer simulation experiment indicate that the taboo search algorithms improve the ability of local search,which shows that the hybrid search strategy is effective.