Please wait a minute...
J4  2013, Vol. 47 Issue (3): 431-441    DOI: 10.3785/j.issn.1008-973X.2013.03.006
计算机技术     
S4PR网的极小信标计算方法
徐姗姗1,2, 董利达1, 朱丹1, 朱承丞1
1.浙江大学 电子电路与信息系统研究所,浙江 杭州 310027;2.解放军陆军军官学院
管理工程教研室,安徽 合肥 230031
Method to compute minimal siphons in S4PR nets
XU Shan-shan1,2, DONG Li-da1, ZHU Dan1, ZHU Cheng-cheng1
1. Institute of Electronic Circuit and Information System, Zhejiang University, Hangzhou 310027, China;
2.  Department of Management Engineering, Army Officer Academy, PLA,  Hefei 230031, China
 全文: PDF  HTML
摘要:

为了解决S4PR网的信标求解问题,提出了一种计算网中全部极小信标的方法.该方法通过分析资源库所内工作环与资源库所集合之间的关系构建有向图(C-R图),获取强连通的C-R子图集合,而每个C-R子图对应着一个信标,由此得到包含2个及2个以上资源库所的信标集合,将该集合与含有单个资源库所的极小信标集合进行并集运算,形成备选信标集合,通过算法对备选集合进行筛选,删除其中非极小的信标,进而得到网中全部的极小信标.该方法为获取S4PR网中全部的极小信标提供了有效、可行的方案,为下一步设计最优活性控制器奠定了基础.一个可用S4PR网建模的柔性制造系统实例验证了该极小信标计算方法的正确性.

Abstract:

This work proposed a method to find all the minimal siphons for an S4PR net. The method builds up a directed graph based on the relationship among resource places and their inner-working circuits (referred to as C-R graph). It can be used to calculate the strongly connected subgraphs with each of them corresponding to one siphon. Based on these, the siphons having multiple resource places are computed. These siphons are combined with the ones having the single resource place to construct the siphon candidate set. An algorithm was used to do filtering to these siphon candidates and the non-minimal siphons were removed to achieve the set of minimal siphons in the S4PR net. This method provides an effective solution for calculating all the minimal siphons in S4PR nets, and builds a foundation for designing optimal liveness-enforcing supervisor. This method was verified by a flexible manufacturing system (FMS) example which could be modeled by an S4PR net.

出版日期: 2013-03-01
:  TP 278  
基金资助:

国家自然科学基金资助项目(61071062);浙江省自然科学基金资助项目(Y12F02030).

通讯作者: 董利达,男,副教授.     E-mail: lddong2002@163.com
作者简介: 徐姗姗(1981-),女,硕士生,从事Petri网理论研究. E-mail:shanshanxu1981@gmail.com
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章  

引用本文:

徐姗姗, 董利达, 朱丹, 朱承丞. S4PR网的极小信标计算方法[J]. J4, 2013, 47(3): 431-441.

XU Shan-shan, DONG Li-da, ZHU Dan, ZHU Cheng-cheng. Method to compute minimal siphons in S4PR nets. J4, 2013, 47(3): 431-441.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2013.03.006        http://www.zjujournals.com/eng/CN/Y2013/V47/I3/431

[1] LI Z W, ZHANG J, ZHAO M. Liveness-enforcing supervisor design for a class of generalised Petri net models of flexible manufacturing systems [J]. IET Control Theory and Applications, 2007, 1(4): 955-967.
[2] WYSK R A, YANG N S, JOSHI S. Detection of deadlocks in flexible manufacturing cells [J]. IEEE Transactions on Robotics and Automation, 1991, 7(6): 853-859.
[3] PARK J, REVELIOTIS S A. Deadlock avoidance in sequential resource allocation systems with multiple resource acquisitions and flexible routing [J]. IEEE Transactions on Automatic Control, 2001, 46(10): 1572-1583.
[4] ABDALLAH I B, ELMARAGHY H A. Deadlock prevention and avoidance in FMS: a Petri net based approach [J]. International Journal of Advanced Manufacturing Technology, 1998, 14(10): 704-715.
[5] EZPELETA J, COLOM J M, MARTINEZ J. A Petri net based deadlock prevention policy for flexible manufacturing systems [J]. IEEE Transactions on Robotics and Automation, 1995, 11(2):173-184.
[6] TRICAS F, GARCIA V F, COLOM J M, et al. A Petri net structure–based deadlock prevention solution for sequential resource allocation systems[C]∥Proceedings of the 2005 IEEE International Conference on Robotics and Automation. Barcelona: IEEE, 2005:271-277.
[7] LI Zhi-wu, ZHOU Meng-chu. Elementary siphons of Petri nets and their application to deadlock prevention in flexible manufacturing systems [J]. IEEE Transactions on Systems, Man and Cybernetics, Part A, 2004, 34(1): 3851.[8] CHU Feng, XIE Xiao-lan. Deadlock analysis of Petri nets using siphons and mathematical programming [J]. IEEE Transactions on Robotics and Automation, 1997, 13(6):793-804.
[9] HUANG Yi-sheng, JENG M, XIE Xiao-lan, et al. Deadlock prevention policy based on Petri nets and siphons [J]. International Journal of Production Research, 2001, 39(2): 283-305.
[10] LI Zhi-wu, LIU Ding. A correct minimal siphons extraction algorithm form a maximal unmarked siphon of a Petri net [J]. International Journal of Production Research, 2007, 45(9):2161-2165.
[11] LI Zhi-wu, ZHOU Meng-chu. On siphon computation for deadlock control in a class of Petri nets [J]. IEEE Transactions on Systems, Man and Cybernetics, Part A, 2008, 38(3):667-679.
[12] WANG Shou-guang, WANG Cheng-ying, YU Yang-ping. A method of computing strict minimal siphons in an S3PR based on resource circuits [C]∥49th IEEE Conference on Decision and Control. Atlanta: IEEE, 2010: 2785-2790.
[13] CANO E E, ROVETTO C A, COLOM J M. On the computation of the minimal siphons of S4PR nets from a generating family of siphons[C]∥2010 IEEE Conference on Emerging Technologies and Factory Automation. Bilbao: IEEE, 2010:18.
[14] MURATA T. Petri nets: properties, analysis and applications [J]. Proceedings of the IEEE, 1989, 77(4):541-580.
[15] 吴哲辉.Petri网导论[M].北京:机械工业出版社, 2006:141.
[16] IORDACHE M V, MOODY J O, ANTSAKLIS P J. Synthesis of deadlock prevention supervisors using Petri nets [J]. IEEE Transactions on Robotics and Automation, 2002, 18(1): 59-68.
[17] TRICAS F, EZPELETA J. Computing minimal siphons in Petri net models of resource allocation systems: a parallel solution [J]. IEEE Transactions on Systems, Man and Cybernetics, Part A, 2006, 36(3): 532-539.
[18] TRICAS F, COLOM J M, EZPELETA J. A solution to the problem of deadlocks in concurrent systems using Petri nets and integer linear programming [C]∥Proceedings of the 11th European Simulation Symposium. Erlangen: [s. n.], 1999:542-546.
[19] 肖位枢.图论及其算法[M].北京:航空工业出版社,1993,34-37.

[1] 刘爱军, 杨育, 李斐, 邢青松, 陆惠, 张煜东. 混沌模拟退火粒子群优化算法研究及应用[J]. J4, 2013, 47(10): 1722-1730.
[2] 田景红, 潘晓弘, 王正肖. 基于频繁模式挖掘的实时供应链数据分析[J]. J4, 2009, 43(12): 2259-2263.
[3] 叶建芳, 潘晓弘, 王正肖, 等. 基于免疫离散粒子群算法的调度属性选择[J]. J4, 2009, 43(12): 2203-2207.