TY - JOUR
T1 - A divide-and-conquer strategy to deadlock prevention in flexible manufacturing systems
AU - Li, Zhi Wu
AU - Zhu, Sen
AU - Zhou, Meng Chu
N1 - Funding Information:
Manuscript received November 7, 2007; revised May 2, 2008. Current version published February 25, 2009. This work was supported in part by the National Natural Science Foundation of China under Grant 60474018 and Grant 60773001, by the National Research Foundation for the Doctoral Program of Higher Education, Ministry of Education of China under Grant 20070701013, by the Chang Jiang Scholars Program, Ministry of Education, China, and by the 2007–2008 Technion-Xidian Academic Exchange Program. This paper was recommended by Associate Editor J. Wang.
PY - 2009
Y1 - 2009
N2 - Petri nets are a popular mathematical tool to investigate the deadlock problems in resource allocation systems. As an important problem solution paradigm in computer science, the divide-and-conquer strategy is used in this paper to investigate the deadlock prevention for flexible manufacturing systems (FMSs) that are modeled with Petri nets. Based on the concept of resource circuits, a plant net model is divided into an idle subnet, an autonomous subnet, and a number of small but independent subnets, called toparchies, from the viewpoint of deadlock control. A liveness-enforcing supervisor, called toparch, is designed for each toparchy. If a particular separation condition holds in a plant net model, the computational complexity of toparches is significantly reduced. This research shows that the resultant net, called monarch, by composing the toparches derived for the toparchies can serve as a liveness-enforcing Petri net supervisor for the whole plant model. FMS examples are given to illustrate the proposed method.
AB - Petri nets are a popular mathematical tool to investigate the deadlock problems in resource allocation systems. As an important problem solution paradigm in computer science, the divide-and-conquer strategy is used in this paper to investigate the deadlock prevention for flexible manufacturing systems (FMSs) that are modeled with Petri nets. Based on the concept of resource circuits, a plant net model is divided into an idle subnet, an autonomous subnet, and a number of small but independent subnets, called toparchies, from the viewpoint of deadlock control. A liveness-enforcing supervisor, called toparch, is designed for each toparchy. If a particular separation condition holds in a plant net model, the computational complexity of toparches is significantly reduced. This research shows that the resultant net, called monarch, by composing the toparches derived for the toparchies can serve as a liveness-enforcing Petri net supervisor for the whole plant model. FMS examples are given to illustrate the proposed method.
KW - Deadlock prevention
KW - Divide-and-conquer strategy
KW - Flexible manufacturing system (FMS)
KW - Petri net
KW - Siphon
UR - http://www.scopus.com/inward/record.url?scp=63049128873&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=63049128873&partnerID=8YFLogxK
U2 - 10.1109/TSMCC.2008.2007246
DO - 10.1109/TSMCC.2008.2007246
M3 - Article
AN - SCOPUS:63049128873
SN - 1094-6977
VL - 39
SP - 156
EP - 169
JO - IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews
JF - IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews
IS - 2
ER -