TY - JOUR
T1 - On siphon computation for deadlock control in a class of Petri nets
AU - Li, Zhi Wu
AU - Zhou, Meng Chu
N1 - Funding Information:
Manuscript received March 22, 2006; revised July 30, 2007. This work was supported in part by the Natural Science Foundation of China under Grant 60474018 and Grant 60773001, by the Laboratory Foundation for the Returned Overseas Chinese Scholars, Ministry of Education, PRC, under Grant 030401, by the National Research Foundation for the Doctoral Program of Higher Education, Ministry of Education, PRC, under Grant 20070701013, and the Chang Jiang Scholars Program of Ministry of Education, PRC. This paper was recommended by Associate Editor M. P. Fanti.
PY - 2008/5
Y1 - 2008/5
N2 - As a structural object, siphons are well recognized in the analysis and control of deadlocks in resource allocation systems modeled with Petri nets. Many deadlock prevention policies characterize the deadlock behavior of the systems in terms of siphons and utilize this characterization to avoid deadlocks. This paper develops a novel methodology to find interesting siphons for deadlock control purposes in a class of Petri nets, i.e., a system of simple sequential processes with resources (S3 PR). Resource circuits in an (S3 PR) are first detected, from which, in general, a small portion of emptiable minimal siphons can be derived. The remaining emptiable ones can be found by their composition. A polynomial-time algorithm for finding the set of elementary siphons is proposed, which avoids complete siphon enumeration. It is shown that a dependent siphon can always be controlled by properly supervising its elementary siphons. A computationally efficient deadlock control policy is accordingly developed. Experimental study shows the efficiency of the proposed siphon computation approach.
AB - As a structural object, siphons are well recognized in the analysis and control of deadlocks in resource allocation systems modeled with Petri nets. Many deadlock prevention policies characterize the deadlock behavior of the systems in terms of siphons and utilize this characterization to avoid deadlocks. This paper develops a novel methodology to find interesting siphons for deadlock control purposes in a class of Petri nets, i.e., a system of simple sequential processes with resources (S3 PR). Resource circuits in an (S3 PR) are first detected, from which, in general, a small portion of emptiable minimal siphons can be derived. The remaining emptiable ones can be found by their composition. A polynomial-time algorithm for finding the set of elementary siphons is proposed, which avoids complete siphon enumeration. It is shown that a dependent siphon can always be controlled by properly supervising its elementary siphons. A computationally efficient deadlock control policy is accordingly developed. Experimental study shows the efficiency of the proposed siphon computation approach.
KW - Automated manufacturing system
KW - Deadlock prevention
KW - Elementary siphon
KW - Flexible manufacturing system (FMS)
KW - Petri net
KW - Resource allocation system
KW - Siphon
UR - http://www.scopus.com/inward/record.url?scp=43249102181&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=43249102181&partnerID=8YFLogxK
U2 - 10.1109/TSMCA.2008.918605
DO - 10.1109/TSMCA.2008.918605
M3 - Article
AN - SCOPUS:43249102181
SN - 1083-4427
VL - 38
SP - 667
EP - 679
JO - IEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans
JF - IEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans
IS - 3
ER -