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 
摘要：

为了解决S4PR网的信标求解问题,提出了一种计算网中全部极小信标的方法.该方法通过分析资源库所内工作环与资源库所集合之间的关系构建有向图（C-R图）,获取强连通的C-R子图集合,而每个C-R子图对应着一个信标,由此得到包含2个及2个以上资源库所的信标集合,将该集合与含有单个资源库所的极小信标集合进行并集运算,形成备选信标集合,通过算法对备选集合进行筛选,删除其中非极小的信标,进而得到网中全部的极小信标.该方法为获取S4PR网中全部的极小信标提供了有效、可行的方案,为下一步设计最优活性控制器奠定了基础.一个可用S4PR网建模的柔性制造系统实例验证了该极小信标计算方法的正确性.
关键词： Petri网;  柔性制造系统;  信标;  死锁预防    
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．
Key words: Petri net    FMS    siphon    deadlock prevention
出版日期: 2013-04-10
:  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/xueshu/eng/CN/10.3785/j.issn.1008-973X.2013.03.006    或    http://www.zjujournals.com/xueshu/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] 许荣斌, 石军, 张鹏飞, 谢莹. Petri网的映射变迁关系相似性度量[J]. 浙江大学学报(工学版), 2017, 51(6): 1205-1213.
[2] 王青, 温李庆, 李江雄, 柯映林, 李涛, 张世炯. 基于Petri网的飞机总装配生产线建模及优化方法[J]. 浙江大学学报(工学版), 2015, 49(7): 1224-1231.
[3] 王成龙,李诚,冯毅萍,荣冈. 作业车间调度规则的挖掘方法研究[J]. 浙江大学学报(工学版), 2015, 49(3): 421-429.
[4] 罗继亮, 王飞,邵辉,赵良煦. 基于约束转换的Petri网最优监控器设计[J]. J4, 2013, 47(11): 2051-2056.
[5] 刘晓健,张树有,徐敬华. 基于网络流Petri网模型的设计更改技术[J]. J4, 2011, 45(1): 37-44.
[6] 董利达, 程曦浩, 郑寒. 基于工作流的安全库所替换网特性研究[J]. J4, 2010, 44(9): 1711-1718.
[7] 周晓慧, 陈纯, 谢作豪. 印染生产过程的仿真和优化[J]. J4, 2010, 44(7): 1377-1381.
[8] 董利达, 郑寒, 程曦浩. 一类含T-图环结构受控网显式控制器设计[J]. J4, 2010, 44(6): 1057-1066.
[9] 卢燕俊 戴华平. 城市交通网络的混杂Petri网建模[J]. J4, 2007, 41(6): 930-934.
[10] 张瑶瑶 颜钢锋 张森林 刘妹琴. 含有不可控变迁的Parikh约束的Petri网控制器综合[J]. J4, 2006, 40(7): 1123-1126.
[11] 沈斌 姚敏 易文晟 原博. 基于分层Petri网的面向服务需求求精[J]. J4, 2006, 40(6): 1045-1050.
[12] 戴华平. 混杂时间事件图的最小初始标志计算方法[J]. J4, 2006, 40(2): 226-229.
[13] 阮连法 张贤明 刘涛涛. 基于有色Petri网的项目投资决策仿真分析[J]. J4, 2005, 39(5): 734-737.
[14] 王笑蓉 吴铁军. 基于Petri网仿真的柔性生产调度--蚁群-遗传递阶进化优化方法[J]. J4, 2004, 38(3): 286-291.