Novel Hybrid Algorithm of Cooperative Evolutionary Algorithm and Constraint Programming for Dual Resource Constrained Flexible Job Shop Scheduling Problems

In real production, machines are operated by workers, and the constraints of worker flexibility should be considered. The flexible job shop scheduling problem with both machine and worker resources (DRCFJSP) has become a research hotspot in recent years. In this paper, DRCFJSP with the objective of minimizing the makespan is studied, and it should solve three sub-problems: machine allocation, worker allocation and operations sequencing. To solve DRCFJSP, a novel hybrid algorithm (CEAM-CP) of cooperative evolutionary algorithm with multiple populations (CEAM) and constraint programming (CP) is proposed. Specifically, the CEAM-CP algorithm is comprised of two main stages. In the first stage, CEAM is used based on three-layer encoding and full active decoding. Moreover, CEAM has three populations, each of which corresponds to one layer encoding and determines one sub-problem. Moreover, each population evolves cooperatively by multiple cross operations. To further improve the solution quality obtained by CEAM, CP is adopted in the second stage. Experiments are conducted on 13 benchmark instances to assess the effectiveness of multiple crossover operations, CP and CEAM-CP. Most importantly, the proposed CEAM-CP improves 9 best-known solutions out of 13 benchmark instances.