Deadlock control policy for a class of petri nets without complete siphon enumeration

Z. Li, M. Zhou, M. Uzam

Research output: Contribution to journalArticlepeer-review

26 Scopus citations


Siphons are special structures of a Petri net. Their number grows exponentially with the net size. Hence, the traditional siphon-based deadlock control policies have two problems, that is, generating very structurally complex supervisory controllers and requiring intractable computation efforts. This paper intends to use the newly proposed concept, elementary siphons, and a mixed integer programming (MIP) method to design structurally simple supervisory controllers and reduce the computational burden. This method is applicable to a class of Petri nets, System of Simple Sequential Processes with Resources that can well model a wide class of discrete manufacturing systems. Siphons are divided into elementary and dependent ones. The proposed policy consists of three stages: siphon control, control-induced siphon control, and the elimination of control-redundant monitors. First, a monitor (control place) is added for each elementary siphon such that it is invariant-controlled. Because of the addition of monitors to the plant model, control-induced siphons are possibly generated in the augmented net. Next, monitors are added to make control-induced siphons in the augmented net always marked sufficiently without generating new problematic siphons. A MIP technique is used to guarantee that no siphon is insufficiently marked. Finally, we systematically remove control-redundant monitors. Compared with previous work in the literature, the deadlock prevention policy developed in this paper can lead to a structurally simple liveness-enforcing Petri net supervisor with more permissive behaviour by adding only a small number of monitors and arcs. Moreover, complete siphon enumeration is avoided. A manufacturing system example is utilised to illustrate the proposed methods.

Original languageEnglish (US)
Pages (from-to)1594-1605
Number of pages12
JournalIET Control Theory and Applications
Issue number6
StatePublished - 2007

All Science Journal Classification (ASJC) codes

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


Dive into the research topics of 'Deadlock control policy for a class of petri nets without complete siphon enumeration'. Together they form a unique fingerprint.

Cite this