An Improved Mixed-Integer Programming Method to Compute Emptiable Minimal Siphons in S³PR Nets

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 (S <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> PR). Compared with classical MIP, since MIP' utilizes the structural characteristics of S <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> PR 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 S <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> PR nets to show its superior efficiency.