Optimal Petri-net-based polynomial-complexity deadlock-avoidance policies for automated manufacturing systems

Keyi Xing, Meng Chu Zhou, Huixia Liu, Feng Tian

Research output: Contribution to journalArticlepeer-review

182 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)188-199
Number of pages12
JournalIEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans
Issue number1
StatePublished - 2009

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Human-Computer Interaction
  • Electrical and Electronic Engineering
  • Control and Systems Engineering
  • Computer Science Applications


  • Automated manufacturing systems (AMSs)
  • Control policy
  • Deadlock avoidance
  • Petri net
  • Polynomial complexity


Dive into the research topics of 'Optimal Petri-net-based polynomial-complexity deadlock-avoidance policies for automated manufacturing systems'. Together they form a unique fingerprint.

Cite this