Knowledge graph-enhanced evolutionary multitasking matheuristic algorithm for job shop scheduling problem with discrete operation sequence flexibility

This work studies job shop scheduling problem with discrete operation sequence flexibility (JSPDS), aiming to minimize the makespan. Unlike traditional scheduling problems, where operations follow a fixed sequence, discrete operation sequence flexibility allows jobs to have multiple processing sequence options, leading to a large solution space. To effectively address JSPDS, we propose a constraint programming (CP) model for small-scale instances to obtain optimal solutions. For large-scale instances, we propose a knowledge graph-enhanced evolutionary multitasking matheuristic algorithm (KG-EMMA). First, a knowledge graph-enhanced evolutionary multitasking optimization framework is designed, which expands search knowledge from a single task to multiple tasks, providing more information than a single evolutionary algorithm. A knowledge graph is used to measure task relatedness, enabling the selection of suitable assisted tasks and avoiding negative knowledge transfer. Next, a dual statistical learning-assisted local search technique is introduced, which controls the application of low-intensity and high-intensity search operators, ensuring the appropriate selection of operators at each stage. Finally, a CP-assisted evolutionary operator as a matheuristic approach to overcome the limitations of traditional encoding and decoding schemes is designed, enabling a comprehensive exploration of the solution space. Experimental results on 20 benchmark instances show that the CP model improves 14 best-known solutions compared with existing MILP models, and KG-EMMA improves 10 best-known solutions compared with state-of-the-art algorithms. These results demonstrate that both the CP model and KG-EMMA are effective in solving JSPDS.