Deadlock Prevention Based on Structure Reuse of Petri Net Supervisors for Flexible Manufacturing Systems

被引:143
作者
Li, ZhiWu [1 ,2 ]
Liu, GaiYun [1 ]
Hanisch, Hans-Michael [3 ]
Zhou, MengChu [4 ,5 ]
机构
[1] Xidian Univ, Sch Electromech Engn, Xian 710071, Peoples R China
[2] King Saud Univ, FARCAMT, Dept Ind Engn, Coll Engn, Riyadh 11421, Saudi Arabia
[3] Univ Halle Wittenberg, Inst Comp Sci, D-06120 Halle, Germany
[4] New Jersey Inst Technol, Dept Elect & Comp Engn, Newark, NJ 07102 USA
[5] Tongji Univ, Key Lab Embedded Syst & Serv Comp, Minist Educ, Shanghai 200092, Peoples R China
来源
IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART A-SYSTEMS AND HUMANS | 2012年 / 42卷 / 01期
基金
新加坡国家研究基金会; 中国国家自然科学基金;
关键词
Deadlock prevention; discrete event system; flexible manufacturing system (FMS); petri net; the theory of regions; LIVENESS-ENFORCING SUPERVISORS; PERFORMANCE EVALUATION; ELEMENTARY SIPHONS; MERGED NETS; AVOIDANCE; POLICY; DESIGN; RESOURCES; PARALLEL; MODELS;
D O I
10.1109/TSMCA.2011.2147308
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
Deadlocks are an undesirable situation in automated flexible manufacturing systems (FMS). Their occurrences often deteriorate the utilization of resources and may lead to catastrophic results. Finding an optimal supervisor is NP-hard. A computationally efficient method often ends up with a suboptimal one. This paper develops a deadlock prevention method that makes a good tradeoff between optimality and computational tractability for a class of Petri nets, which can model many FMS. The theory of regions guides our efforts toward the development of near-optimal solutions for deadlock prevention. Given a plant net, a minimal initial marking is first decided by structural analysis, and an optimal live controlled system is computed. Then, a set of inequality constraints is derived with respect to the markings of monitors and the places in the model such that no siphon can be insufficiently marked. A method is proposed to identify the redundancy condition for constraints. For a new initial marking of the plant net, a deadlock-free controlled system can be obtained by regulating the markings of the monitors such that the inequality constraints are satisfied, without changing the structure of the controlled system. The near-optimal performance of a controlled net system via the proposed method is shown through several examples.
引用
收藏
页码:178 / 191
页数:14
相关论文
共 62 条
[1]   Deadlock prevention and avoidance in FMS: A Petri net based approach [J].
Abdallah, IB ;
ElMaraghy, HA .
INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 1998, 14 (10) :704-715
[2]  
Barkaoui K, 1997, IEEE SYS MAN CYBERN, P3750, DOI 10.1109/ICSMC.1997.633253
[3]  
BARKAOUI K, 1994, P IEEE INT C SYST MA, V1, P525
[4]  
Barkaoui Kamel, 1996, LECT NOTES COMPUTER, V1091, P57
[5]   Max'-controlled siphons for liveness of S3PGR2 [J].
Chao, D. Y. .
IET CONTROL THEORY AND APPLICATIONS, 2007, 1 (04) :933-936
[6]   Deadlock analysis of Petri nets using siphons and mathematical programming [J].
Chu, F ;
Xie, XL .
IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, 1997, 13 (06) :793-804
[7]   Automatic Modeling for Performance Evaluation of Inventory and Outbound Distribution [J].
de Albuquerque, Gabriel Alves, Jr. ;
Martins Maciel, Paulo Romero ;
Ferreira Lima, Ricardo Massa ;
Zimmermann, Armin .
IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART A-SYSTEMS AND HUMANS, 2010, 40 (05) :1025-1044
[8]  
Ezpeleta J, 1998, LECT NOTES COMPUT SC, V1420, P64
[9]  
Ezpeleta J, 2002, IEEE T ROBOTIC AUTOM, V18, P621, DOI 10.1109/TR A.2002.801048
[10]   A PETRI-NET BASED DEADLOCK PREVENTION POLICY FOR FLEXIBLE MANUFACTURING SYSTEMS [J].
EZPELETA, J ;
COLOM, JM ;
MARTINEZ, J .
IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, 1995, 11 (02) :173-184