Novel CP model and CP-assisted meta-heuristic algorithm for flexible job shop scheduling with preventive maintenance

The research investigates the flexible job shop scheduling problem with preventive maintenance (FJSP-PM) by considering two maintenance strategies namely fixed preventive maintenance (FJSP-FPM) and periodic preventive maintenance (FJSP-PPM). The objective is minimizing the makespan. We first propose two novel constraint programming (CP) models for FJSP-FPM and FJSP-PPM to obtain optimal solutions. Then, we design a CP-assisted meta-heuristic framework, and develop a CP-assisted Q-learning-based collaborative variable neighborhood search algorithm (CVNSQ-CP) as a representative example to effectively address large-scale instances. Finally, the experimental evaluation on benchmark instances validates the capability of the CP model and CVNSQ-CP. Specifically, compared with existing mathematical models, the proposed CP model proves 3 new optimal solutions and improves 11 current best-known solutions for FJSP-FPM, and it improves 13 current best-known solutions for FJSP-PPM. Meanwhile, CVNSQ-CP outperforms current state-of-the-art methods by improving 9 current best-known solutions for FJSP-FPM and 3 current best-known solutions for FJSP-PPM.