A matheuristic and imitation learning-driven evolutionary algorithm for the flexible job shop scheduling benchmark problem with discrete operation sequence flexibility
研究了具有离散工序顺序柔性的柔性作业车间调度问题，提出约束规划模型和数学启发式与模仿学习驱动的进化算法，在110个基准实例上验证了模型和算法能改进现有最优解。
In real-world production, a few operations of a job may do not follow precedence constraints. However, classical flexible job shop scheduling problem (FJSP) typically assume operations sequence is fixed. Therefore, this study investigates the FJSP with discrete operation sequence flexibility (FJSPDS), aiming to minimise the makespan. First, a novel constraint programming (CP) model is proposed to obtain optimal solutions. Then, a matheuristic and imitation learning-driven evolutionary algorithm (MILEA) is developed to effectively solve large-scale instances. The MILEA includes three key components: (1) a matheuristic-based hybrid initialization method that enhances the quality of the initial population by utilising the mathematical model to explore better operation sequencing; (2) an imitation learning-assisted local search mechanism that adaptively selects seven critical path-based operators to refine solutions; and (3) a CP-assisted evolutionary operator that overcomes the limitations of traditional encoding-decoding schemes and broadens the exploration of the solution space. Experiments are performed on 110 benchmark instances, and experimental results show that the proposed CP model proves 60 optimal solutions and improves 86 best-known solutions compared with existing models. Meanwhile, MILEA proves 60 optimal solutions and improves 52 best-known solutions compared with existing state-of-the-art algorithms.