A divide-and-conquer strategy to deadlock prevention in flexible manufacturing systems

Zhi Wu Li, Sen Zhu, Meng Chu Zhou

Research output: Contribution to journalArticlepeer-review

51 Scopus citations


Petri nets are a popular mathematical tool to investigate the deadlock problems in resource allocation systems. As an important problem solution paradigm in computer science, the divide-and-conquer strategy is used in this paper to investigate the deadlock prevention for flexible manufacturing systems (FMSs) that are modeled with Petri nets. Based on the concept of resource circuits, a plant net model is divided into an idle subnet, an autonomous subnet, and a number of small but independent subnets, called toparchies, from the viewpoint of deadlock control. A liveness-enforcing supervisor, called toparch, is designed for each toparchy. If a particular separation condition holds in a plant net model, the computational complexity of toparches is significantly reduced. This research shows that the resultant net, called monarch, by composing the toparches derived for the toparchies can serve as a liveness-enforcing Petri net supervisor for the whole plant model. FMS examples are given to illustrate the proposed method.

Original languageEnglish (US)
Pages (from-to)156-169
Number of pages14
JournalIEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews
Issue number2
StatePublished - 2009

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
  • Divide-and-conquer strategy
  • Flexible manufacturing system (FMS)
  • Petri net
  • Siphon


Dive into the research topics of 'A divide-and-conquer strategy to deadlock prevention in flexible manufacturing systems'. Together they form a unique fingerprint.

Cite this