A matheuristic and imitation learning-driven evolutionary algorithm for the flexible job shop scheduling benchmark problem with discrete operation sequence flexibility

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.