Deadlock Prevention Based on Structure Reuse of Petri Net Supervisors for Flexible Manufacturing Systems

Zhiwu Li, Gaiyun Liu, Hans Michael Hanisch, Mengchu Zhou

Research output: Contribution to journalArticlepeer-review

155 Scopus citations


Deadlocks are an undesirable situation in automated flexible manufacturing systems (FMS). Their occurrences often deteriorate the utilization of resources and may lead to catastrophic results. Finding an optimal supervisor is NP-hard. A computationally efficient method often ends up with a suboptimal one. This paper develops a deadlock prevention method that makes a good tradeoff between optimality and computational tractabil-ity for a class of Petri nets, which can model many FMS. The theory of regions guides our efforts toward the development of near-optimal solutions for deadlock prevention. Given a plant net, a minimal initial marking is first decided by structural analysis, and an optimal live controlled system is computed. Then, a set of inequality constraints is derived with respect to the markings of monitors and the places in the model such that no siphon can be insufficiently marked. A method is proposed to identify the redundancy condition for constraints. For a new initial marking of the plant net, a deadlock-free controlled system can be obtained by regulating the markings of the monitors such that the inequality constraints are satisfied, without changing the structure of the controlled system. The near-optimal performance of a controlled net system via the proposed method is shown through several examples.

Original languageEnglish (US)
Pages (from-to)178-191
Number of pages14
JournalIEEE Transactions on Systems, Man, and Cybernetics Part A: Systems and Humans
Issue number1
StatePublished - Jan 1 2012

All Science Journal Classification (ASJC) codes

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


  • Deadlock prevention
  • discrete event system
  • flexible manufacturing system (FMS)
  • petri net
  • the theory of regions


Dive into the research topics of 'Deadlock Prevention Based on Structure Reuse of Petri Net Supervisors for Flexible Manufacturing Systems'. Together they form a unique fingerprint.

Cite this