Constraint Programming for AGV and Machine Integrated Scheduling Problem in Flexible Manufacturing System
Youjie Yao, Qihao Liu, Xinyu Li, Liang Gao
Abstract
The finite resources of automated guided vehicles (AGVs) and machines in a flexible manufacturing system necessitate the integrated scheduling of production and transportation tasks to minimize delays in the production process. Constraint programming (CP) has demonstrated strong solving capabilities in complex shop scheduling problems. However, existing CP models exhibit significant limitations, typically yielding suboptimal solutions in specific scenarios. To address these challenges, this paper introduces a novel CP model that consistently delivers correct optimal solutions across all scenarios. First, the interrelationships among the four key decision sub-problems in AGV and machine integrated scheduling for flexible manufacturing systems are thoroughly analyzed. Next, based on the above analysis and leveraging the presence of transportation tasks, a new CP model is proposed to efficiently handle special cases where jobs do not require transportation. Finally, the model is benchmarked against state-of-the-art methods across three benchmarks and validated through a real-world case study. The results show that the proposed model outperforms existing approaches in both solution quality and efficiency. Notably, the proposed model updates the best-known solutions for the EX72 and EX84 instances, and proves the optimality of all EX instances for the first time.