求解作业车间调度问题的改进遗传算法  

Improved Genetic Algorithm for Job Shop Scheduling Problem

作　　者：陈金广[1] 马玲叶 马丽丽[1] CHEN Jin-Guang;MA Ling-Ye;MA Li-Li(School of Computer Science,Xi’an Polytechnic University,Xi’an 710048,China)

机构地区：[1]西安工程大学计算机科学学院,西安710048

出　　处：《计算机系统应用》2021年第5期190-195,共6页Computer Systems & Applications

基　　金：陕西省教育厅科研计划(18JK0349)。

摘　　要：使用遗传算法求解作业车间调度问题时,为了获得最优解,提高算法的收敛速度,提出了改进遗传算法.算法以最小化最大完工时间为优化目标,初始化时将种群规模扩大为原来的两倍以增加种群多样性;迭代时使用新的适应度函数让染色体间更易区分;通过轮盘赌法完成染色体选择;用POX(Precedence Operation Crossover)交叉算子完成交叉操作;用互换法完成变异操作;通过具有自我调节能力的交叉和变异概率不断地调整概率值来提高算法寻优能力和收敛速度.仿真结果表明,改进后的遗传算法收敛速度快,寻优能力强,获得的最优解优于标准遗传算法,更适用于作业车间的加工生产.When a genetic algorithm is used to solve job shop scheduling,in order to obtain the optimal solution and increase the convergence speed of the algorithm,we propose an improved genetic algorithm in this study.The goal of the algorithm is to minimize the maximum completion time.First,the population size is doubled during the initialization to increase the diversity of the population and a new fitness function is adopted to make chromosome distinguishing easier in the iteration.Then,chromosomes are selected via roulette.Furthermore,crossover is completed by Precedence Operation Crossover(POX)and mutation by Reciprocal Exchange Mutation(REM).Finally,the optimization ability and convergence speed of the proposed algorithm are improved by adjusting the crossover and mutation probability with selfregulation.The simulation results show that the improved genetic algorithm has faster convergence,stronger optimization ability,and better optimal solution than the traditional one and thus it is more suitable for the processing and production in job shops.

关 键 词：遗传算法 作业车间调度 改进 轮盘赌 自适应概率 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]