Critical-Path-Based Variable Neighborhood Descent for the Joint Scheduling of FJSP and AGVs

Abstract

This study addresses the joint scheduling problem of flexible job shop scheduling and automated guided vehicles with the objective of minimizing the makespan. We propose an efficient optimization approach based on a critical-path-driven variable neighborhood descent. The core contribution lies in the development of a critical path detection mechanism that incorporates transportation processes, along with the design of tailored neighborhood structures. Building on this foundation, a problem-specific variable neighborhood descent search strategy is implemented. Unlike traditional variable neighborhood descent approaches, the proposed critical path analysis accurately identifies bottleneck operations in both processing and transportation stages. The designed neighborhood structures effectively coordinate machine scheduling and automated guided vehicles transportation, enabling synergistic optimization. To enhance overall performance, auxiliary strategies such as an external memory archive and population diversity maintenance are integrated. Experimental results on multiple benchmark datasets demonstrate that the proposed method achieves significant improvements in solution quality compared to existing algorithms. Ablation experiments further confirm the critical role of the critical-path-driven variable neighborhood descent mechanism in enhancing algorithmic performance.