TY - JOUR
T1 - Optimal Petri-net-based polynomial-complexity deadlock-avoidance policies for automated manufacturing systems
AU - Xing, Keyi
AU - Zhou, Meng Chu
AU - Liu, Huixia
AU - Tian, Feng
N1 - Funding Information:
Manuscript received March 7, 2007; revised July 19, 2007 and March 12, 2008. Current version published December 17, 2008. This work was partially supported by the National Nature Science Foundation of P. R. China under Grants 60774083, 60773001, and 60574066, and Chang Jiang Scholars program, PRC Ministry of Education. This paper was recommended by Associate Editor H. R. Rao.
PY - 2009
Y1 - 2009
N2 - Even for a simple automated manufacturing system (AMS), such as a general single-unit resource allocation system, the computation of an optimal or maximally permissive deadlock-avoidance policy (DAP) is NP-hard. Based on its Petri-net model, this paper addresses the deadlock-avoidance problem in AMSs, which can be modeled by systems of simple sequential processes with resources. First, deadlock is characterized as a perfect resource-transition circuit that is saturated at a reachable state. Second, for AMSs that do not have one-unit resources shared by two or more perfect resource-transition circuits that do not contain each other, it is proved that there are only two kinds of reachable states: safe states and deadlock. An algorithm for determining the safety of a new state resulting from a safe one is then presented, which has polynomial complexity. Hence, the optimal DAP with polynomial complexity can be obtained by a one-step look-ahead method, and the deadlock-avoidance problem is polynomially solved with Petri nets for the first time. Finally, by reducing a Petri-net model and applying the design of optimal DAP to the reduced one, a suboptimal DAP for a general AMS is synthesized, and its computation is of polynomial complexity.
AB - Even for a simple automated manufacturing system (AMS), such as a general single-unit resource allocation system, the computation of an optimal or maximally permissive deadlock-avoidance policy (DAP) is NP-hard. Based on its Petri-net model, this paper addresses the deadlock-avoidance problem in AMSs, which can be modeled by systems of simple sequential processes with resources. First, deadlock is characterized as a perfect resource-transition circuit that is saturated at a reachable state. Second, for AMSs that do not have one-unit resources shared by two or more perfect resource-transition circuits that do not contain each other, it is proved that there are only two kinds of reachable states: safe states and deadlock. An algorithm for determining the safety of a new state resulting from a safe one is then presented, which has polynomial complexity. Hence, the optimal DAP with polynomial complexity can be obtained by a one-step look-ahead method, and the deadlock-avoidance problem is polynomially solved with Petri nets for the first time. Finally, by reducing a Petri-net model and applying the design of optimal DAP to the reduced one, a suboptimal DAP for a general AMS is synthesized, and its computation is of polynomial complexity.
KW - Automated manufacturing systems (AMSs)
KW - Control policy
KW - Deadlock avoidance
KW - Petri net
KW - Polynomial complexity
UR - http://www.scopus.com/inward/record.url?scp=58149136242&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=58149136242&partnerID=8YFLogxK
U2 - 10.1109/TSMCA.2008.2007947
DO - 10.1109/TSMCA.2008.2007947
M3 - Article
AN - SCOPUS:58149136242
SN - 1083-4427
VL - 39
SP - 188
EP - 199
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 - 1
ER -