TY - JOUR
T1 - Computation of an emptiable minimal siphon in a subclass of Petri nets using mixed-integer programming
AU - Wang, Shouguang
AU - Duo, Wenli
AU - Guo, Xin
AU - Jiang, Xiaoning
AU - You, Dan
AU - Barkaoui, Kamel
AU - Zhou, Mengchu
N1 - Publisher Copyright:
© 2014 Chinese Association of Automation.
PY - 2021/1
Y1 - 2021/1
N2 - Deadlock resolution strategies based on siphon control are widely investigated. Their computational efficiency largely depends on siphon computation. Mixed-integer programming MIP can be utilized for the computation of an emptiable siphon in a Petri net PN . Based on it, deadlock resolution strategies can be designed without requiring complete siphon enumeration that has exponential complexity. Due to this reason, various MIP methods are proposed for various subclasses of PNs. This work proposes an innovative MIP method to compute an emptiable minimal siphon EMS for a subclass of PNs named S4PR. In particular, many particular structural characteristics of EMS in S4PR are formalized as constraints, which greatly reduces the solution space. Experimental results show that the proposed MIP method has higher computational efficiency. Furthermore, the proposed method allows one to determine the liveness of an ordinary S4PR.
AB - Deadlock resolution strategies based on siphon control are widely investigated. Their computational efficiency largely depends on siphon computation. Mixed-integer programming MIP can be utilized for the computation of an emptiable siphon in a Petri net PN . Based on it, deadlock resolution strategies can be designed without requiring complete siphon enumeration that has exponential complexity. Due to this reason, various MIP methods are proposed for various subclasses of PNs. This work proposes an innovative MIP method to compute an emptiable minimal siphon EMS for a subclass of PNs named S4PR. In particular, many particular structural characteristics of EMS in S4PR are formalized as constraints, which greatly reduces the solution space. Experimental results show that the proposed MIP method has higher computational efficiency. Furthermore, the proposed method allows one to determine the liveness of an ordinary S4PR.
UR - http://www.scopus.com/inward/record.url?scp=85086260111&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85086260111&partnerID=8YFLogxK
U2 - 10.1109/JAS.2020.1003210
DO - 10.1109/JAS.2020.1003210
M3 - Article
AN - SCOPUS:85086260111
SN - 2329-9266
VL - 8
SP - 219
EP - 226
JO - IEEE/CAA Journal of Automatica Sinica
JF - IEEE/CAA Journal of Automatica Sinica
IS - 1
M1 - 9106877
ER -