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

Improved Genetic Algorithm for Solving Multiple Flexible Job Shop Scheduling Problems

摘要: 针对柔性作业车间调度问题，考虑机器预维护的情况，建立了最小化最大完工时间、关键机器负载以及机器总负载为目标的调度模型，并提出一种改进遗传算法进行问题求解。根据问题特点，设计了基于工序和机器的双层编码，并采用三种种群初始化策略来生成初始种群。为了将解转化为可行有效的调度方案，设计了考虑运输时间以及机器预维护的插入式解码。采用不同的个体更新方式，并引入了变邻域搜索来提高算法的局部搜索能力，以避免陷入局部最优解。最后，在对基准算例改造并进行对比实验，验证了所提算法的可行性与有效性。

Abstract: A scheduling model was established to minimize the maximum completion time, critical machine load, and total machine load for the flexible job shop scheduling problem, taking into account ma-chine pre maintenance. An improved genetic algorithm was proposed to solve the problem. Based on the characteristics of the problem, a dual layer encoding based on process and machine was de-signed, and three population initialization strategies were used to generate the initial population. In order to transform the solution into a feasible and effective scheduling scheme, an insertion de-coding method was designed that takes into account transportation time and machine pre mainte-nance. Adopting different individual update methods and introducing variable neighborhood search to improve the algorithm’s local search ability to avoid falling into local optima. Finally, the feasibility and effectiveness of the proposed algorithm were verified by modifying the benchmark calculation example and conducting comparative experiments.