Constraint-Enhanced Scheduling: A CP–Meta-Heuristic Synthesis for Multi-AGV Flexible Job Shops

The flexible job shop scheduling problem (FJSP) is an important model for understanding how manufacturing systems coordinate diverse machines, varied process routes, and jobs composed of multiple interdependent operations. However, recently the rise of automated material-handling technologies has changed things and modern workshops increasingly rely on automated guided vehicles (AGVs) to move workpieces between spatially distributed machines, which can cause transportation delays, vehicle conflicts, and travel routes to become as consequential as machining decisions themselves. With these systems evolve, the classical FJSP no longer captures the full set of decisions a scheduler must confront. The expanded problem—now referred to as FJSP with AGVs (FJSP-AGVs) requires the simultaneous determination of machine assignments, AGV allocations, and the sequencing rules governing both kinds of resources. Its difficulty derives from the coupling between machining and transportation: every chosen machine influences the AGV needed for the next move, and the availability of an AGV may in turn affect which machine becomes preferable for processing the subsequent operation.  Although researchers have approached this problem from various directions, exact optimization remains challenging. Mixed-integer linear programming formulations tend to lose efficiency as soon as machines, jobs, or AGVs expand in number, while meta-heuristic algorithms, though often fast, cannot guarantee solution optimality. Constraint programming (CP) has emerged as a promising alternative because of its ability to represent timing relationships, sequencing constraints, and resource conflicts through interval variables and propagation rules. Earlier CP models for FJSP-AGVs demonstrated that this approach can outperform traditional exact algorithms, particularly when determining globally optimal makespans. However, these earlier models were incomplete in one important respect which is they could not correctly handle situations in which a machine processes two consecutive operations of the same job. When this occurs, no transport should be required, but previous CP formulations forced an AGV assignment regardless, introducing artificial conflicts and rendering certain feasible schedules unsolvable. This structural limitation restricted the range of instances that CP techniques could address.

To this account, new research paper published in IEEE Transactions on Systems Man and Cybernetics Systems and led by Associate Professor Leilei Meng from the School of Computer Science at Liaocheng University together with Mr. Weiyao Cheng; Professor Chaoyong Zhang; Assistant Professor Kaizhou Gao; Associate Professor Biao Zhang; and Associate Professor Yaping Ren, researchers developed a revised CP model that resolves the long-standing MPTCOJ issue by introducing a virtual AGV to correctly represent zero-transport operations. They also constructed a CP-assisted dual-population genetic algorithm that uses exploratory search to provide high-quality warm starts for the CP solver. The research team evaluated the performance of the proposed scheduling framework and combined the new CP model with their dual-population collaborative genetic algorithm (DCGA). They designed testing strategy around several publicly available benchmark datasets that capture a wide range of system scales, job configurations, and AGV-to-machine ratios. These datasets include instances with modest numbers of jobs, as well as larger and more intricate cases where transportation delays and machine flexibility compete strongly with each other. The experiments also incorporated a real production scenario to examine how the approach behaves under practical spatial layouts and movement constraints. Each instance was solved under a fixed computational time allowance, ensuring fair comparisons against existing methods.

The first part of the evaluation focused on the four variants of the CP model: the baseline formulation (CP-N), a version enhanced with redundant constraints (CP-R), another with symmetry-breaking constraints (CP-B), and a combined version incorporating both enhancements (CP-RB). These variants were tested independently to assess how each modification influences solver performance. The results show an immediate benefit from incorporating redundancy and symmetry-breaking. In most instances, CP-RB achieved faster convergence and proved optimality for more cases than the other three variants. The redundant constraints appear to strengthen propagation by reducing the ambiguity in operation precedence, while the symmetry-breaking constraint eliminates equivalent AGV assignments that would otherwise inflate the search space.

Afterward, the authors in the second phase evaluated the hybrid DCGA-CP method where they first allowed the meta-heuristic to explore the solution space and generate candidate schedules. Once a promising solution emerged, it was passed to the CP solver as a warm start. This cooperative process consistently amplified the strengths of both components. The authors found that on numerous benchmark instances, the hybrid method reached the best-known solutions and proved many of them to be optimal for the first time. Moreover, across all datasets, the hybrid approach either outperformed or matched the strongest standalone CP model. Its most notable success was in larger or transportation-heavy instances, where the warm start enabled the CP solver to bypass unproductive regions of the search space and refine solutions more efficiently.  In the real industrial case, the proposed methods delivered competitive schedules within negligible computation time, substantially faster than previously published mathematical programming approaches. The only instance that remained unresolved in terms of proving optimality was a case with numerous near-equivalent sequences, which suggest that the absence of a unique dominant schedule can make certification more difficult, even when good solutions are found instantly.

In conclusion, Professor Leilei Meng and colleagues developed four models and formed a cooperative framework that improves solution quality, accelerates convergence, and establishes new optimal schedules across benchmark datasets. The hybrid nature of their method gives it both the flexibility of a meta-heuristic and the rigor of an exact CP engine. Indeed, the CP model’s refinement especially its treatment of consecutive operations on the same machine removes a structural bottleneck that had quietly restrained previous researchers. Once this limitation was eliminated, a clearer picture emerged: CP techniques remain powerful for FJSP-AGVs, but they need carefully curated starting points when dealing with high-dimensional or heavily intertwined constraints. We also believe the meta-heuristic contribution reported in the new study is equally substantive and by using two encoding schemes, the DCGA explores machine–operation–AGV assignments in ways that single-layer encodings typically miss. The frequent rejuvenation of subpopulations prevents the search from drifting into narrow regions of the solution space. Yet, the meta-heuristic is not burdened with the responsibility of certifying optimality. Instead, it performs the role it excels at—rapid exploration—and hands over its best findings to a CP engine that can perform the precise, deterministic refinement needed to close the remaining gaps. This division of labor is both elegant and practical.

Additionally, the extensive benchmarking results dramatize the importance of such cooperation. Many scheduling papers propose hybrid methods, but few demonstrate improvements across dozens of long-standing benchmark instances, and even fewer establish new optimal solutions. The fact that DCGA-CP proves 35 new optimal schedules and improves 32 best-known ones suggests not only algorithmic strength but a re-evaluation of what is computationally reachable in the FJSP-AGV landscape. These contributions also hint at broader consequences. As manufacturing systems become increasingly modular and transportation-dependent, AGV coordination is becoming central to realistic planning. Models unable to capture such interactions will eventually diverge from industry needs. The authors’ CP formulation integrates these behaviors in a flexible way and thus may serve as a foundation for future extensions involving setup times, lot streaming, energy costs, and even Petri-net-boostered decompositions, all proposed in the paper’s concluding remarks. In a nutshell, the authors successfully constructed a search process that is both grounded and adaptive, capable of solving instances once considered too complex for exact verification. The study therefore contributes to advancing approach in intelligent manufacturing systems that acknowledges the heterogeneity of computational tools and leverages their complementarities.