Abstract: Aiming at the Open-shop Scheduling Problem (OSP),an improved Genetic Algorithm (GA) named Diversity Enhancement-based Adaptive Genetic Algorithm (DEAGA) was proposed.Five operators such as diversity enhancement operator,adaptive crossover operator,adaptive mutation operator and multiple tournament selections operator were designed to improve convergence efficiency and evolution quality of GA.The time complexity of each operator in DEAGA was analyzed,and the results proved that the complexity was not increased by comparing with the simple genetic algorithm.An orthogonal design method was used to determine the optimal parameters of the operators.Three experiments were designed to analyze the role of the propose operators,and the result showed that the diversity enhanced operator could improve the solution quality,and the adaptive operator could promote the convergence rate.Based on 60 benchmarks of OSP,the effectiveness and stability of the proposed algorithm were verified by comparing with the existing 5 algorithms.The effect of problem scale on the scheduling performance was analyzed by using 100 cases.

Key words: open shop scheduling, genetic algorithms, diversity enhancement, adaptive genetic operator, complexity analysis, orthogonal design

摘要： 针对开放式车间调度问题,提出了基于多样性增强的自适应遗传算法进行优化求解。设计了多样性判定增强算子、自适应交叉变异算子、多元竞争选择算子等五个算子,以提高遗传算法的进化效率和进化质量;通过分析算法各算子的时间复杂度,发现所提算子并未增加算法复杂度;采用正交试验确定了各算子的最优参数;设计了三组实验,分析了所提算子对算法的影响,结果表明多样性增强算子提高了求解质量,自适应交叉变异算子加快了收敛速度;基于60个标准算例,通过与已有5种算法比较,验证了所提算法的有效性和稳定性。采用100个算例,分析了算例规模对调度性能的影响规律。

关键词: 开放式车间调度, 遗传算法, 多样性增强, 自适应遗传算子, 复杂度分析, 正交试验