Imitation Learning and Constraint Programming-assisted Evolutionary Algorithm for Resource-Constrained Flexible Job Shop Scheduling Problem with Sequence-Dependent Setup Times 

The flexible job shop scheduling problem with sequence-dependent setup times (FJSP-SDST) is a critical issue in intelligent manufacturing industries. Existing research on FJSP-SDST typically assumes that setup times are autonomously managed by machines, which limits its applicability. This paper addresses this gap by exploring the resource-constrained FJSP-SDST (RFJSP-SDST), which considers setup times that are conducted by external resources, such as robots or humans.  As an NP-hard problem, it consists of four subproblems: operation sequencing, machine selection and setup task assignment, and resource allocation, making it challenging to solve efficiently. To tackle this complexity, this paper proposes an imitation learning and constraint programming-assisted evolutionary algorithm (ILCPEA) to effectively solve the RFJSP-SDST, focusing on minimizing the makespan. The ILCPEA incorporates a hybrid decoding strategy with combining basic, matheuristic, and imitation learning-assisted methods, which ensures diversity, optimal resource allocation, and a balance between computational resources and performance during the evolution process. To enhance the local search effectively, the disjunctive graph model is used to identify critical paths and four neighborhood structures are designed to improve algorithm convergence. Additionally, a CP-based mathematical evolution operator is introduced to explore the full solution space. Experimental results demonstrate that ILCPEA efficiently generates competitive solutions, outperforms other existing advanced algorithms and demonstrates its practicality in addressing real workshop problems.