Optimal Petri-Net-Based Polynomial-Complexity Deadlock-Avoidance Policies for Automated Manufacturing Systems
Authors:
- Meng Chu ZhouMZMeng Chu Zhou
- Huixia LiuHLHuixia Liu
- Feng TianFTFeng Tian
Top Cited Papers
- 9 December 2008
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans
- Vol. 39 (1) , 188-199
Abstract
Even for a simple automated manufacturing system (AMS), such as a general single-unit resource allocation system, the computation of an optimal or maximally permissive deadlock-avoidance policy (DAP) is NP-hard. Based on its Petri-net model, this paper addresses the deadlock-avoidance problem in AMSs, which can be modeled by systems of simple sequential processes with resources. First, deadlock is characterized as a perfect resource-transition circuit that is saturated at a reachable state. Second, for AMSs that do not have one-unit resources shared by two or more perfect resource-transition circuits that do not contain each other, it is proved that there are only two kinds of reachable states: safe states and deadlock. An algorithm for determining the safety of a new state resulting from a safe one is then presented, which has polynomial complexity. Hence, the optimal DAP with polynomial complexity can be obtained by a one-step look-ahead method, and the deadlock-avoidance problem is polynomially solved with Petri nets for the first time. Finally, by reducing a Petri-net model and applying the design of optimal DAP to the reduced one, a suboptimal DAP for a general AMS is synthesized, and its computation is of polynomial complexity.Keywords
This publication has 42 references indexed in Scilit:
- Resource-Oriented Petri Net for Deadlock Avoidance in Flexible Assembly SystemsIEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 2007
- Deadlock Resolution in Automated Manufacturing Systems With RobotsIEEE Transactions on Automation Science and Engineering, 2007
- Optimal Liveness Petri Net Controllers with Minimal Structures for Automated Manufacturing Systems2006
- Supervisory Control for Deadlock Avoidance in Compound ProcessesIEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 2004
- Iterative synthesis of Petri net based deadlock prevention policy for flexible manufacturing systems2004
- Avoiding deadlock and reducing starvation and blocking in automated manufacturing systemsIEEE Transactions on Robotics and Automation, 2001
- ERCN-merged nets and their analysis using siphonsIEEE Transactions on Robotics and Automation, 1999
- Deadlock avoidance policy for Petri-net modeling of flexible manufacturing systems with shared resourcesIEEE Transactions on Automatic Control, 1996
- Resolution of deadlocks in flexible manufacturing systems: Avoidance and recovery approachesJournal of Manufacturing Systems, 1994
- Deadlock prevention and deadlock avoidance in flexible manufacturing systems using Petri net modelsIEEE Transactions on Robotics and Automation, 1990