S3PR网的可达标识集算法

doi:10.3969/j.issn.1001-2400.2015.05.018

J4 ›› 2015, Vol. 42 ›› Issue (5): 105-109.doi: 10.3969/j.issn.1001-2400.2015.05.018

S³PR网的可达标识集算法

张秀艳;钟春富;贾建援

(西安电子科技大学机电工程学院，陕西西安 710071)

收稿日期:2014-04-29 出版日期:2015-10-20 发布日期:2015-12-03
通讯作者: 张秀艳
作者简介:张秀艳(1981-)，女，讲师，西安电子科技大学博士研究生，E-mail: xiuyan0224@163.com．
基金资助:
国家自然科学基金资助项目(51305325)；中央高校基本科研业务费专项资金资助项目(XJS15039)

Method to compute the reachability set of S³PR

ZHANG Xiuyan;ZHONG Chunfu;JIA Jianyuan

(School of Mechano-electronic Engineering, Xidian Univ., Xi'an 710071, China)

Received:2014-04-29 Online:2015-10-20 Published:2015-12-03
Contact: ZHANG Xiuyan

摘要/Abstract

摘要：

针对具有特定资源库所的S³PR网，提出了一种基于P不变式和严格极小信标的计算可达标识集的新方法．首先计算出由P不变式所确定的不变式标识集，再通过分析严格极小信标中相应库所的托肯数与其界的关系，提出判定标识是否为伪标识的判定定理，并基于判定定理有效求解伪标识集，最终通过剔除不变式标识集中的伪标识来获得可达标识集．实验结果表明，采用所提的方法，可以快速有效地计算出S³PR网中的可达标识集．

关键词: Petri网, 严格极小信标, P不变式, 可达标识集, 死锁控制

Abstract:

This paper proposes a novel approach to computing the reachability set by using place invariants and strict minimal siphons for S³PR with specific resource places. First, the set of invariant markings is enumerated. Then a necessary and sufficient condition is developed to decide whether a marking is spurious by analyzing the relationship between the number of tokens in the corresponding places of any strict minimal siphon and their bounds. In addition, the spurious markings are calculated. Finally, the reachability set of the net is generated by removing all the spurious markings from the set of invariant markings. Experimental results show the efficiency of the proposed method.

Key words: Petri nets, strict minimal siphons, place invariants, reachability set, deadlock control

中图分类号:

TP271+.8

张秀艳;钟春富;贾建援. S³PR网的可达标识集算法[J]. J4, 2015, 42(5): 105-109.

ZHANG Xiuyan;ZHONG Chunfu;JIA Jianyuan. Method to compute the reachability set of S³PR[J]. J4, 2015, 42(5): 105-109.

参考文献

［1］ Murata T. Petri Nets: Properties, Analysis, and Applications［J］. Proceedings of the IEEE, 1989, 77(4): 541-580.
［2］ Ezpeleta J, Colom J M, Martinez J. A Petri Net Based Dead Lock Prevention Policy for Flexible Manufacturing Systems［J］. IEEE Transactions on Robotics and Automation, 1995, 11(2): 173-184.
［3］陈玉峰, 李志武. 安全Petri网事件分离状态的BDD算法［J］. 西安电子科技大学学报, 2010, 37(1): 119-124.
Chen Yufeng, Li Zhiwu. Computation of Marking/Transition Separation Instances for Safe Petri Nets Using BDD［J］. Journal of Xidian University, 2010, 37(1): 119-124.
［4］ Chen Y F, Li Z W, Barkaoui K. Maximally Permissive Liveness-enforcing Supervisor with Lowest Implementation Cost for Flexible Manufacturing Systems［J］. Information Science, 2014, 256: 74-90.
［5］ Xing K Y, Zhou M C, Wang F, 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.
［6］ Liu D, Li Z W, Zhou M C. A Parameterized Liveness and Ratio-enforcing Supervisor for a Class of Generalized Petri Nets ［J］. Automatica, 2013, 49(11): 3167-3179.
［7］ Li Z W, Zhou M C. Control of Elementary and Dependent Siphons in Petri Nets and Their Application［J］. IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, 2008, 38(1): 133-148.
［8］李志武, 周孟初. 自动制造系统建模、分析与死锁控制［M］. 北京: 科学出版社, 2009.
［9］ Zhang X Y, Li Z W, Zhong C F, et al. Reachability Analysis of a Class of Petri Nets Using Place Invariants and Siphons ［J］. Maejo International Journal of Science and Technology, 2013, 7(2): 278-290.
［10］ Wu N Q, Zhou M C. Avoiding Deadlock and Reducing Starvation and Blocking in Automated Manufacturing Systems［J］. IEEE Transactions on Robotics and Automation, 2001, 17(5): 658-669.
［11］ Chao D Y. Recursive Solution of Number of Reachable States of a Simple Subclass of FMS［J］. International Journal of Systems Science, 2014, 45(3): 702-710.

[1]	王祺;陈晓亮. 一种用于柔性制造系统混惑状态估计的算法[J]. 西安电子科技大学学报, 2017, 44(2): 69-74.
[2]	马子玥;童音. 采用基本标识图的Petri网控制策略[J]. 西安电子科技大学学报, 2016, 43(6): 68-73.
[3]	蒋忠远;张秀艳;马子玥. 智能电网中电能存储系统的容量优化[J]. J4, 2015, 42(6): 106-112.
[4]	张丽;赵良煦;王寿光;汪成英. 针对α网的最优线性约束转换方法[J]. J4, 2015, 42(5): 183-187+212.
[5]	陈晓亮;蒋忠远;叶剑虹 . 工作流网的混或检测和预防策略 [J]. J4, 2015, 42(2): 77-83.
[6]	朱承丞;董利达. 一种多线程软件并发漏洞检测方法 [J]. J4, 2015, 42(2): 167-173+212.
[7]	尤丹;刘苗;吴文慧;王寿光. S³PR网的严格极小信标计算方法[J]. J4, 2014, 41(4): 193-197+204.
[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]	张曼;段振华. 工作流网合成规则及其在流程设计中的应用[J]. J4, 2012, 39(2): 200-206.
[12]	陈玉峰;李志武. 安全Petri网事件分离状态的BDD算法[J]. J4, 2010, 37(1): 119-124+141.
[13]	郭金维;李志武. 一种时延Petri网的死锁预防方法[J]. J4, 2009, 36(5): 902-908.
[14]	朱森;李志武. 双航母编队C³I系统Petri网建模与分析研究[J]. J4, 2009, 36(4): 661-668.
[15]	王安荣;李志武. 基本信标计算的一种快速算法[J]. J4, 2008, 35(4): 632-638.

S³PR网的可达标识集算法

Method to compute the reachability set of S³PR

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10