一种求解柔性作业车间调度问题的改进DRSGA

Improved DRSGA for flexible job shop scheduling

为了解决柔性作业车间调度问题中权重难以确定导致调度效率低的问题,该文提出了1种改进的动态随机搜索遗传算法（DRSGA）。用功效系数法将所有工件完成时间和机器的总负载转化为单一的最小化目标。基于工序和机器分配2种交叉操作,采用1种双层染色体编码方案进行编码。采用1种可变影响空间评价方法,在保证非劣解均匀分布的同时维护了种群多样性。采用动态随机搜索（DRS）和擂台赛法则调整关键路径中工序的排序,得到最优调度方案。将改进DRSGA与向量评估遗传算法、改进遗传算法和混合遗传算法运行结果进行比较,仿真实验结果表明,改进DRSGA求最优解所用平均时间比3种对比算法缩短了41～257 s。

To solve the problems of flexible job shop scheduling that it is difficult to determine the weight and the scheduling efficiency is poor ,an improved dynamic random search genetic algorithm （ DRSGA） is proposed here .All minimized job completing time and total machine loading are translated into single minimized objective by the efficiency coefficient method .A double-layer chromosome encoding scheme is adopted based on sequence crossover and machine allocation crossover .A variable influence space evaluation method is used to guarantee the uniform distribution＆amp;nbsp;of non-inferior solutions , and the diversity of population is maintained .A dynamic random search （ DRS） method and contest rules are employed to adjust key process orders and obtain the optimal scheduling scheme .The improved DRSGA is compared with the vector evaluated genetic algorithm （VEGA）,the improved genetic algorithm （IMGA） and the hybrid genetic algorithm （HGA）.The simulation results indicate that the average time of the optimal solution of the improved DRSGA is shorter than the other three algorithms for 41~257 s.