Abstract:

Aiming at single-objective Flexible Job Shop Scheduling Problem（FJSP）with the objective of optimizing the maximum completion time, a hybrid algorithm incorporating genetic algorithm, variable neighborhood search and elite protection strategy is proposed. Firstly, the mathematical model is established and the overall flow of the algorithm is presented. Then, the genetic operator is improved and the improved memory base is added to protect the elite individuals. Secondly, based on the critical operations adjustment, three neighborhood structures are designed to enhance the local search ability, which are same-machine moving operation, cross-machine moving operation and double operations adjustment. Finally, the benchmark examples and numerical experiments are used to test and verify the effectiveness of the proposed method.

Key words: Flexible Job Shop Scheduling Problem（FJSP）, genetic algorithm, variable neighborhood search, elite protection strategy

摘要：

针对单目标柔性作业车间调度问题，以最大完工时间为优化目标，将遗传算法、变邻域搜索算法与精英保护策略相结合，提出一种运算效率和求解性能均较好的混合算法。首先建立数学模型，阐述算法的整体流程。对遗传算子进行改进，并添加改良的保优记忆库对精英个体进行保护。基于关键工序调整，设计了“同机器工序调整”“变机器工序调整”“双工序调整”三种邻域结构，增强了局部搜索能力，并给出一种高效的关键工序寻找法则。通过对基准算例及数值实验的测试，验证了该算法的有效性和可行性。

关键词: 柔性作业车间调度（FJSP）, 遗传算法, 变邻域搜索, 精英保护策略