面向Job Shop调度的算法融合方法研究

Study of Algorithm Fusion Method for Job Shop Scheduling

提出一种算法融合方法,解决单一算法求解Job Shop调度问题存在的不足,提高这类问题的求解质量。在融合方法中,采用遗传算法和蚁群算法进行并行搜索;根据Job Shop调度问题解的特征,提出基于关键工序的邻域选择方法,并将基于这种邻域选择方法的禁忌搜索算法作为局部搜索算法,加强了遗传算法和蚁群算法的局部搜索能力。采用算法融合方法构造的优化算法对13个难解的benchmarks问题实例进行求解,在较短的时间内,得到的十次实验结果的makespan最优值和平均值优于并行遗传算法(PGA)和TS算法。采用算法融合方法构造的优化算法具有较强的搜索能力,说明提出的算法融合方法是有效的。

We propose the algorithm fusion method to overcome the deficiencies of the single algorithm in solving job shop scheduling problems. Following the method, we do parallel and asynchronous searches using the genetic algorithm and the ant colony algorithm. According to the characteristics of the solution to a job shop scheduling problem, we propose a new neighborhood search method based on critical operations and use the taboo search algorithm based on the neighborhood search algorithm as the local search algorithm, thus strengthening the local search capacities of genetic algorithm and ant colony algorithm. The practice of seeking solutions for 13 hard benchmark problems with the algorithm fusion method shows that the makespan optimal values and average values obtained from 10 experiments are better than those using the parallel genetic algorithm and the taboo search algorithm. All these indicate that the algorithm fusion method is effective.