Deadlock avoidance in sequential resource allocation systems with multiple resource acquisitions and flexible routings

@article{ParkReveliotis01, abstract = {Considers the deadlock avoidance problem for the class of conjunctive/disjunctive (sequential) resource allocation systems (C/D-RAS), which allows for multiple resource acquisitions and flexible routings. First, a siphon-based characterization for the liveness of Petri nets (PNs) modeling C/D-RAS is developed, and subsequently, this characterization facilitates the development of a polynomial-complexity deadlock avoidance policy (DAP) that is appropriate for the considered RAS class. The resulting policy is characterized as C/D-RUN. The last part of the paper exploits the aforementioned siphon-based characterization of C/D-RAS liveness, in order to develop a sufficiency condition for C/D-RAS liveness that takes the convenient form of a mixed integer programming (MIP) formulation. The availability of this MIP formulation subsequently allows the “automatic” correctness verification of any tentative C/D-RAS DAP for which the controlled system behavior remains in the class of PNs modeling C/D-RAS, and the effective flexibility enhancement of the aforementioned C/D-RUN DAP implementations. Finally, we notice that, in addition to extending and complementing the current theory on deadlock-free sequential resource allocation to the most powerful class of C/D-RAS, the presented results also (i) nontrivially generalize important concepts and techniques of ordinary PN structural analysis to the broader class of nonordinary PNs, while (ii) from a practical standpoint, they can find direct application in the (work-) flow management of modern production, service and/or transportation environments}, author = {Park, Jonghun and Reveliotis, S. A. }, citeulike-article-id = {832216}, journal = {Automatic Control, IEEE Transactions on}, keywords = {citas, deadlock, supervisory}, number = {10}, pages = {1572--1583}, posted-at = {2006-09-06 12:02:45}, priority = {2}, title = {Deadlock avoidance in sequential resource allocation systems with multiple resource acquisitions and flexible routings}, url = {http://ieeexplore.ieee.org/xpls/abs\_all.jsp?arnumber=956052}, volume = {46}, year = {2001} }

TY - JOUR ID - ParkReveliotis01 L3 - citeulike-article-id:832216 TI - Deadlock avoidance in sequential resource allocation systems with multiple resource acquisitions and flexible routings JF - Automatic Control, IEEE Transactions on VL - 46 IS - 10 SP - 1572 EP - 1583 N2 - Considers the deadlock avoidance problem for the class of conjunctive/disjunctive (sequential) resource allocation systems (C/D-RAS), which allows for multiple resource acquisitions and flexible routings. First, a siphon-based characterization for the liveness of Petri nets (PNs) modeling C/D-RAS is developed, and subsequently, this characterization facilitates the development of a polynomial-complexity deadlock avoidance policy (DAP) that is appropriate for the considered RAS class. The resulting policy is characterized as C/D-RUN. The last part of the paper exploits the aforementioned siphon-based characterization of C/D-RAS liveness, in order to develop a sufficiency condition for C/D-RAS liveness that takes the convenient form of a mixed integer programming (MIP) formulation. The availability of this MIP formulation subsequently allows the “automatic” correctness verification of any tentative C/D-RAS DAP for which the controlled system behavior remains in the class of PNs modeling C/D-RAS, and the effective flexibility enhancement of the aforementioned C/D-RUN DAP implementations. Finally, we notice that, in addition to extending and complementing the current theory on deadlock-free sequential resource allocation to the most powerful class of C/D-RAS, the presented results also (i) nontrivially generalize important concepts and techniques of ordinary PN structural analysis to the broader class of nonordinary PNs, while (ii) from a practical standpoint, they can find direct application in the (work-) flow management of modern production, service and/or transportation environments KW - citas KW - deadlock KW - supervisory AU - Park, Jonghun AU - Reveliotis, SA PY - 2001/// UR - http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=956052 ER -