Optimal Petri-Net-Based Polynomial-Complexity Deadlock-Avoidance Policies for Automated Manufacturing Systems Export

@article{citeulike:3981326, abstract = {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.}, author = {Xing, Keyi and Zhou, Meng C. and Liu, Huixia and Tian, Feng}, booktitle = {Systems, Man and Cybernetics, Part A, IEEE Transactions on}, citeulike-article-id = {3981326}, citeulike-linkout-0 = {http://dx.doi.org/10.1109/TSMCA.2008.2007947}, citeulike-linkout-1 = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4703275}, doi = {10.1109/TSMCA.2008.2007947}, journal = {Systems, Man and Cybernetics, Part A, IEEE Transactions on}, keywords = {ams, avoidance, complexity, deadlock, flexbile, manufacturing, polynomial, systems}, number = {1}, pages = {188--199}, posted-at = {2009-01-30 11:17:32}, priority = {2}, title = {Optimal Petri-Net-Based Polynomial-Complexity Deadlock-Avoidance Policies for Automated Manufacturing Systems}, url = {http://dx.doi.org/10.1109/TSMCA.2008.2007947}, volume = {39}, year = {2009} }

TY - JOUR ID - citeulike:3981326 L3 - citeulike-article-id:3981326 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. IS - 1 JF - Systems, Man and Cybernetics, Part A, IEEE Transactions on EP - 199 TI - Optimal Petri-Net-Based Polynomial-Complexity Deadlock-Avoidance Policies for Automated Manufacturing Systems VL - 39 T2 - Systems, Man and Cybernetics, Part A, IEEE Transactions on SP - 188 KW - ams KW - avoidance KW - complexity KW - deadlock KW - flexbile KW - manufacturing KW - polynomial KW - systems AU - Xing, Keyi AU - Zhou, Meng AU - Liu, Huixia AU - Tian, Feng PY - 2009/// UR - http://dx.doi.org/10.1109/TSMCA.2008.2007947 ER -