An effective algorithm to find elementary siphons in a class of petri nets

An Rong Wang, Zhi Wu Li, Jian Yuan Jia, Meng Chu Zhou

Research output: Contribution to journalArticlepeer-review

76 Scopus citations

Abstract

As a structural object of Petri nets, siphons play a key role in the development of deadlock prevention policies for resource allocation systems. Elementary siphons are a novel concept in net theory. Based on graph theory, this paper proposes an effective algorithm with polynomial complexity to find a set of elementary siphons for a linear system of simple sequential processes with resources (LS3PR), a subclass of Petri nets, which can model many flexible manufacturing systems. The algorithm is established through the use of a resource directed graph and complementary sets of strict minimal siphons (SMS) of the net. The upper bound of the number of SMS in such a net is identified. A running example is used to demonstrate the proposed method.

Original languageEnglish (US)
Pages (from-to)912-923
Number of pages12
JournalIEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans
Volume39
Issue number4
DOIs
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

Keywords

  • Automated manufacturing system
  • Digraph
  • Discrete event system
  • Elementary siphon
  • Flexible manufacturing system
  • Petri net

Fingerprint

Dive into the research topics of 'An effective algorithm to find elementary siphons in a class of petri nets'. Together they form a unique fingerprint.

Cite this