S3PR网的严格极小信标计算方法

doi:10.3969/j.issn.1001-2400.2014.04.032

J4 ›› 2014, Vol. 41 ›› Issue (4): 193-197+204.doi: 10.3969/j.issn.1001-2400.2014.04.032

S³PR网的严格极小信标计算方法

尤丹¹;刘苗²;吴文慧¹;王寿光¹

(1. 浙江工商大学信息与电子工程学院，浙江杭州 310018；
2. 西安电子科技大学机电工程学院，陕西西安 710071)

收稿日期:2013-04-18 出版日期:2014-08-20 发布日期:2014-09-25
通讯作者: 尤丹
作者简介:尤丹(1991-)，女，E-mail: youdan000@hotmail.com．
基金资助:
国家自然科学基金资助项目(61100056，61374148)；浙江省自然科学基金资助项目(LY12F03020)；浙江省科技计划资助项目(2013C31111)；浙江省新型网络标准与应用技术重点实验室资助项目(2013E10012)；浙江工商大学校级创新资助项目 (3080XJ2513233)

Method to compute the strict minimal siphon for S³PR

YOU Dan¹;LIU Miao²;WU Wenhui¹;WANG Shouguang¹

(1. School of Information & Electronic Engineering, Zhejiang Gongshang Univ., Hangzhou 310018, China;
2. School of Mechano-electronic Engineering, Xidian Univ., Xi'an 710071, China)

Received:2013-04-18 Online:2014-08-20 Published:2014-09-25
Contact: YOU Dan

摘要/Abstract

摘要：

Petri网作为一种新兴的数学建模工具，被广泛地应用于各类制造系统中．现有的死锁预防控制策略大多采用对极小信标添加控制库所来达到死锁预防的目的．因此，严格极小信标在柔性制造系统的死锁预防中占据极其重要的地位．对于一类含有资源的简单资源顺序进程网(S³PR)，笔者首先定义了一类特殊库所，通过分析特殊库所和环资源子集的关系，提出判定环资源子集对应的信标是否为严格极小信标的定理，基于判定定理有效求解出严格极小信标．实验结果表明，该方法可以快速地计算出S³PR网中的严格极小信标．

关键词: 死锁, 柔性制造系统, Petri网, 严格极小信标

Abstract:

Petri nets are used to model the concurrent execution and the deadlock problem in a flexible manufacturing system (FMS). Strict minimal siphons (SMS) play an important role in the development of deadlock control policies for FMS. In this paper, for a class of Petri nets called Systems of Simple Sequential Processes with Resources (S³PR), we propose a more effective method to compute SMS by analyzing a special class of places in S³PR. First, the concept of special places is proposed. Next, by analyzing the relationship between the special places and the loop resource subsets, some conditions for loop resource subsets to generate SMS are established. Based on those conditions, we can compute SMS effectively. Experimental results show that the proposed method is an effective one when the special places exist in S³PR.

Key words: deadlock, flexible manufacturing systems, Petri net, strict minimal siphons

尤丹;刘苗;吴文慧;王寿光. S³PR网的严格极小信标计算方法[J]. J4, 2014, 41(4): 193-197+204.

YOU Dan;LIU Miao;WU Wenhui;WANG Shouguang. Method to compute the strict minimal siphon for S³PR[J]. J4, 2014, 41(4): 193-197+204.

参考文献

［1］ Murata T. Petri Nets: Properties, Analysis, and Applications［J］. Proceeding of the IEEE, 1989, 77(4): 541-580.
［2］ 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.
［3］王安荣, 李志武. 基本信标计算的一种快速算法［J］. 西安电子科技大学学报, 2008, 35(4): 632-638.
Wang Anrong, Li Zhiwu. Effective Algorithm for Obtaining a Set of Elementary Siphons［J］. Journal of Xidian University, 2008, 35(4): 632-638.
［4］ Wang Shouguang, Zhou Mengchu, Wang Chengying. Extracting All Minimal Siphons from Maximal Unmarked Siphons in Manufacturing-oriented Petri Nets ［C］//IEEE International Conference on Automation Science and Engineering. Piscataway: IEEE, 2011: 399-404.
［5］ Wang Shouguang, Wang Chengying, Zhou Mengchu. A Method to Compute Strict Minimal Siphons in S³PR Based on Loop Resource Subsets ［J］. IEEE Transactions on Systems, Man, and Cybernetics Systems, 2012, 42(1): 226-237.
［6］ Wang Shouguang, Li Yue, Wang Chengying, et al. Computation of All Minimal Siphons in Petri Nets［C］//Proceedings of 9th IEEE Conference on Networking, Sensing and Control. Piscataway: IEEE, 2012: 4651
［7］ Liu Xiangling, Wang Anrong, Li Zhiwu. A Fast Algorithm to Find a Set of Elementary Siphons for a Class of Petri Nets［C］//Proceedings of IEEE International Conference on Automation Science and Engineering. Piscataway: IEEE, 2006: 399-404.
［8］ Xing Keyi, Zhou Mengchu, Wang Feng, et al. Resource Transition Circuits and Siphons for Deadlock Control of Automated Manufacturing Systems［J］. IEEE Transactions on Systems, Man, and Cybernetics Part A: Systems and Humans, 2011, 41(1): 74-84.
［9］ Li Zhiwu, Zhou Mengchu. Control of Elementary and Dependent Siphons in Petri Nets and Their Application［J］. IEEE Transactions on System, Man, and Cybernetics Part A: Systems and Humans, 2008, 38(1): 133-148.
［10］ Li Zhiwu, Zhao Mi. On Controllability of Dependent Siphons for Deadlock Prevention in Generalized Petri Nets ［J］. IEEE Transactions on Systems, Man, and Cybernetics Part A: Systems and Humans, 2008, 38(2): 369-384.

[1]	王祺;陈晓亮. 一种用于柔性制造系统混惑状态估计的算法[J]. 西安电子科技大学学报, 2017, 44(2): 69-74.
[2]	马子玥;童音. 采用基本标识图的Petri网控制策略[J]. 西安电子科技大学学报, 2016, 43(6): 68-73.
[3]	蒋忠远;张秀艳;马子玥. 智能电网中电能存储系统的容量优化[J]. J4, 2015, 42(6): 106-112.
[4]	张秀艳;钟春富;贾建援. S³PR网的可达标识集算法[J]. J4, 2015, 42(5): 105-109.
[5]	张丽;赵良煦;王寿光;汪成英. 针对α网的最优线性约束转换方法[J]. J4, 2015, 42(5): 183-187+212.
[6]	陈晓亮;蒋忠远;叶剑虹 . 工作流网的混或检测和预防策略 [J]. J4, 2015, 42(2): 77-83.
[7]	朱承丞;董利达. 一种多线程软件并发漏洞检测方法 [J]. J4, 2015, 42(2): 167-173+212.
[8]	洪良. S³PR网可达标识数的一种有效估算方法[J]. J4, 2014, 41(3): 169-173.
[9]	李晔;王映辉;于振华. 信息物理融合系统的面向对象Petri网建模[J]. J4, 2014, 41(2): 165-171.
[10]	王祺;王安荣;蒲绪强. 制造系统Petri网特殊标识求解算法[J]. J4, 2013, 40(6): 85-91.
[11]	姚磊;蔡觉平;李赞;张海林;王韶力. 2D-Mesh结构片上网络无虚通道容错路由算法[J]. J4, 2012, 39(6): 26-33.
[12]	张曼;段振华. 工作流网合成规则及其在流程设计中的应用[J]. J4, 2012, 39(2): 200-206.
[13]	陈玉峰;李志武. 安全Petri网事件分离状态的BDD算法[J]. J4, 2010, 37(1): 119-124+141.
[14]	郭金维;李志武. 一种时延Petri网的死锁预防方法[J]. J4, 2009, 36(5): 902-908.
[15]	朱森;李志武. 双航母编队C³I系统Petri网建模与分析研究[J]. J4, 2009, 36(4): 661-668.

S³PR网的严格极小信标计算方法

Method to compute the strict minimal siphon for S³PR

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10