Novel CP Models and CP-Assisted Meta-Heuristic Algorithm for Flexible Job Shop Scheduling Benchmark Problem With Multi-AGV
Leilei Meng, Weiyao Cheng, Chaoyong Zhang, Kaizhou Gao, Biao Zhang, Yaping Ren
Abstract
This article studies the flexible job shop scheduling problem with a certain number of automatic guided vehicles (FJSP-AGVs), aiming to minimize the makespan. First, a novel constraint programming (CP) model is formulated to obtain optimal solutions. Specifically, the proposed CP model addresses the shortcomings of the existing CP model, which cannot solve instances with a machine processing two consecutive operations of the same job. Additionally, redundant and symmetry-breaking constraints are designed to accelerate constraint propagation and break problem symmetry, respectively. Then, to more effectively solve FJSP-AGVs, a CP-assisted meta-heuristic algorithm framework is designed, with a CP-assisted dual-population collaborative genetic algorithm (DCGA-CP) being developed as an example. Finally, experiments are performed on benchmark instances to demonstrate the effectiveness and superiority of the proposed CP model and DCGA-CP. Experimental results show that the proposed CP models first prove 29 new optimal solutions and improve 27 best-known solutions. Meanwhile, DCGA-CP first proves 29 new optimal solutions and improves 32 best-known solutions for benchmark instances.