An Improved Mixed-Integer Programming Method to Compute Emptiable Minimal Siphons in S3PR Nets
MengDi Gan, Shouguang Wang, Zhijun Ding, MengChu Zhou, Wenhui Wu · IEEE Transactions on Control Systems Technology · 2017
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.