Abstract:

In order to improve the diversity of initial population and consider the operation sequence constraints of the same artifact at the same time, the stack was used to storage all operations in the view of the FJSP machine selection problem, in which the makespan was the optimization objective. Global random initialization method based on the key operation was proposed to solve the machine selection problem of FJSP, in which the key operation containing the only optional machine can directly affect the total load machine and processing time. To avoid the basic genetic algorithm trapped in local optimum when solving FJSP, re-activation mechanism was added to the GA algorithm, by which the diversity of population can be increased. Finally, in the view of the FJSP benchmark examples, the effectiveness of the GRS initialization mechanism and the reliability of the proposed improved algorithm were verified respectively by analyzing the performance comparison of the initial machine selection parts and the experimental results of solving FJSP by the genetic algorithm with different initializations.

Key words: flexible job-shop scheduling, optimization, species diversity, machine selection, GRS initialization mechanism, re-activation mechanism, genetic algorithm, numerical analysis

摘要：

以FJSP的最大完工时间作为优化目标，在考虑同一工件的工序顺序约束的同时，为提高初始种群的多样性，针对FJSP的机器选择问题采用堆栈方式存储工序。P-FJSP中只有一台机器可选的关键工序能直接影响机器总负荷和工件加工时间，进而提出了一种基于关键工序的全局随机选择（GRS）初始化方法。为了避免基本遗传算法在求解FJSP时陷入局部极优而停滞，在GA算法中加入再激活（re-activation）机制，旨在重新激活种群，增加种群的多样性。最后，针对FJSP基准测试算例进行数值分析，通过初始机器选择部分的性能对比实验、不同初始方式下遗传算法求解FJSP对比实验分别验证了GRS初始化机制的有效性和所提改进算法的可靠性。

关键词: 柔性作业车间调度, 优化, 种群多样性, 机器选择, GRS初始化机制, 再激活机制, 遗传算法, 数值分析