Direct minimal empty siphon computation using MIP

被引:33
作者
Chao, Daniel Y. [1 ]
机构
[1] Natl Chengchi Univ, Taipei 11623, Taiwan
关键词
Petri nets; Siphons; Deadlocks; Integer programming; FLEXIBLE MANUFACTURING SYSTEMS; LIVENESS-ENFORCING SUPERVISORS; RESOURCE-ALLOCATION SYSTEMS; DEADLOCK PREVENTION POLICY; PETRI NETS; AVOIDANCE; DESIGN; FMS;
D O I
10.1007/s00170-009-1967-1
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
We propose a revised mixed-integer programming (MIP) method to directly compute unmarked siphons with a minimal number of places. This eliminates the need to deduce a minimal siphon from an unmarked maximal siphon obtained from the traditional MIP method proposed by Chu et al. The revised MIP test reports smaller siphons earlier than larger siphons and adds monitors to basic siphons before compound siphons. This results in adding fewer monitors and reaching more states.
引用
收藏
页码:397 / 405
页数:9
相关论文
共 15 条
[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]   Technical note-reducing mip iterations for deadlock prevention of flexible manufacturing systems [J].
Chao, Daniel Y. .
INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2009, 41 (3-4) :343-346
[3]  
Chao DY, 2007, J INF SCI ENG, V23, P203
[4]   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
[5]   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
[6]  
Huang YS, 2007, J INF SCI ENG, V23, P215
[7]   Design of deadlock prevention supervisors using Petri nets [J].
Huang, Yi-Sheng .
INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2007, 35 (3-4) :349-362
[8]   Design of liveness-enforcing supervisors for flexible manufacturing systems using Petri nets [J].
Li, Zhi Wu ;
Hu, He Suan ;
Wang, An Rong .
IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART C-APPLICATIONS AND REVIEWS, 2007, 37 (04) :517-526
[9]   Deadlock control of flexible manufacturing systems via invariant-controlled elementary siphons of petri nets [J].
Li, Zhiwu ;
Wei, Na .
INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2007, 33 (1-2) :24-35
[10]   On systematic methods to remove redundant monitors from liveness-enforcing net supervisors [J].
Li, ZhiWu ;
Hu, HeSuan .
COMPUTERS & INDUSTRIAL ENGINEERING, 2009, 56 (01) :53-62