Elementary Siphons of Petri Nets and Their Application to Deadlock Prevention in Flexible Manufacturing Systems

Zhi Wu Li, Meng Chu Zhou

Research output: Contribution to journalArticlepeer-review

617 Scopus citations

Abstract

A variety of important Petri net-based methods to prevent deadlocks arising in flexible manufacturing systems (FMS) are to add some control places and related arcs to strict minimal siphons (SMS) such that no siphon can be emptied. Since the number of minimal siphons grows in general exponentially with respect to a Petri net size, their disadvantages lie in that they often add too many additional places to the net, thereby making the resulting net model much more complex than the original one. This paper explores ways to minimize the new additions of places while achieving the same control purpose. It proposes for the first time the concept of elementary siphons that are a special class of siphons. The set of elementary siphons in a Petri net is generally a proper subset of the set of all SMS. Its smaller cardinality becomes evident in large Petri net models. This paper proves that by adding a control place for each elementary siphon to make sure that it is marked, deadlock can be successfully prevented. Compared with the existing methods, the new method requires a much smaller number of control places and, therefore, is suitable for large-scale Petri nets. An FMS example is used to illustrate the proposed concepts and policy, and show the significant advantage over the previous methods.

Original languageEnglish (US)
Pages (from-to)38-51
Number of pages14
JournalIEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans.
Volume34
Issue number1
DOIs
StatePublished - Jan 2004

All Science Journal Classification (ASJC) codes

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

Keywords

  • Deadlock prevention
  • Flexible manufacturing systems
  • Petri nets
  • Siphons

Fingerprint Dive into the research topics of 'Elementary Siphons of Petri Nets and Their Application to Deadlock Prevention in Flexible Manufacturing Systems'. Together they form a unique fingerprint.

Cite this