用佩特里网解决可拆卸异构AGV系统的死锁调度问题。
Petri Net Modeling and Deadlock-Free Scheduling of Attachable Heterogeneous AGV Systems
- 基于佩特里网建模任务协同过程，实现动态调度与死锁预判。
- 在真实与合成数据上显著提升求解效率，优于现有策略和算法。
- 适合智能制造中需灵活协作的自动化物流系统设计者。
随着柔性自动化需求增长，异构自动导引车（AGV）系统得到广泛应用。本文研究一种由可连接/断开的载具与穿梭车组成的物料运输系统，其通过灵活耦合完成协同任务。这种耦合虽提升效率，却导致系统高度耦合并易发生死锁。为此，提出将佩特里网（PN）集成于自适应大邻域搜索（ALNS）算法中的无死锁调度框架。佩特里网将静态任务序列映射为动态协作流程，通过状态演化评估性能，并利用结构分析实现主动死锁预防。在真实世界与合成实例上的大量实验表明，该框架显著提升计算效率，所开发的ALNS优于当前现场策略、精确求解器及前沿元启发式算法。最后的敏感性分析提供了车队规模优化的管理启示。
原文摘要 · Abstract (English)
The increasing demand for flexible automation has accelerated the adoption of heterogeneous automated guided vehicles (AGVs). This work investigates a new scheduling problem in a material transportation system consisting of attachable heterogeneous AGVs, including carriers and shuttles, that flexibly attach and detach for cooperative task execution. While such collaboration enhances operational efficiency, the attachment-induced synchronization renders the system highly coupled and susceptible to deadlocks. To address this, we propose a Petri net (PN)-based deadlock-free scheduling framework integrated into an adaptive large neighborhood search (ALNS) algorithm. The PN is introduced to map candidate solutions from static permutations into dynamic collaborative processes, enabling performance evaluation via state evolution and proactive deadlock prevention through structural analysis. Extensive experiments on real-world and synthetic instances demonstrate that the proposed framework significantly improves computational efficiency, with the developed ALNS outperforming the current on-site policy, exact solvers, and state-of-the-art metaheuristics. Finally, sensitivity analysis yields managerial insights for optimal fleet sizing.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。