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

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