An improved mixed-integer programming method to compute emptiable minimal siphons in S3PR Nets

Mengdi Gan, Shouguang Wang, Zhijun Ding, Mengchu Zhou, Wenhui Wu

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

Emptiable minimal siphons (EMSs) play a key role in the development of many deadlock control policies for resource allocation systems modeled with Petri nets. Recent research results show that siphon-based deadlock prevention methods can avoid complete siphon enumeration by using mixed-integer programming (MIP). This brief proposes a novel MIP approach, called MIP′ for short, to compute EMSs for deadlock control in a class of Petri nets, i.e., a system of simple sequential processes with resources (S3PR). Compared with classical MIP, since MIP′ utilizes the structural characteristics of S3PR nets to compute EMSs and more constraints are included in it, its solution space is drastically narrowed. As a result, the number of iterations to solve the MIP′ problem is significantly reduced, and the computational efficiency is considerably improved. Comparisons are provided on several S3PR nets to show its superior efficiency.

Original languageEnglish (US)
Article number8068939
Pages (from-to)2135-2140
Number of pages6
JournalIEEE Transactions on Control Systems Technology
Volume26
Issue number6
DOIs
StatePublished - Nov 2018

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Electrical and Electronic Engineering

Keywords

  • Deadlocks
  • Petri nets
  • liveness
  • mixed-integer programming (MIP)
  • siphons

Fingerprint

Dive into the research topics of 'An improved mixed-integer programming method to compute emptiable minimal siphons in S3PR Nets'. Together they form a unique fingerprint.

Cite this