S3PR网的可达标识集算法

doi:10.3969/j.issn.1001-2400.2015.05.018

Abstract

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

CLC Number:

TP271+.8

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

References

［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]	WANG Qi;CHEN Xiaoliang. Algorithm for estimating confusion states of flexible manufacturing systems [J]. Journal of Xidian University, 2017, 44(2): 69-74.
[2]	JIANG Zhongyuan;ZHANG Xiuyan;MA Ziyue. Capacity optimization for power storage systems in smart grids [J]. J4, 2015, 42(6): 106-112.
[3]	ZHANG Li;ZHAO Liangxu;WANG Shouguang;WANG Chengying. Optimal linear constraint transformation method for α-nets [J]. J4, 2015, 42(5): 183-187+212.
[4]	CHEN Xiaoliang;JIANG Zhongyuan;YE Jianhong . Confusion detection and prevention policies for workflow nets [J]. J4, 2015, 42(2): 77-83.
[5]	ZHU Chengcheng;DONG Lida. Concurrency bug test for a class of multithreaded software [J]. J4, 2015, 42(2): 167-173+212.
[6]	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.
[7]	LI Ye;WANG Yinghui;YU Zhenhua. Formal modeling of cyber-physical systems using object-oriented Petri nets [J]. J4, 2014, 41(2): 165-171.
[8]	WANG Qi;WANG Anrong;PU Xuqiang. Computation of special markings of Petri nets of manufacturing systems [J]. J4, 2013, 40(6): 85-91.
[9]	CHEN Yu-feng;LI Zhi-wu. Computation of marking/transition separation instances for safe Petri nets using BDD [J]. J4, 2010, 37(1): 119-124+141.
[10]	. Deadlock prevention approach for a class of timed Petri nets [J]. J4, 2009, 36(5): 902-908.
[11]	ZHU Sen;LI Zhi-wu. On the colored Petri net model of the C³I system of the double aircraft carriers group [J]. J4, 2009, 36(4): 661-668.
[12]	WANG An-rong;DUAN Jiang-tao;LI Zhi-wu;JIA Jian-yuan. On the forbidden state avoidance of resource allocation systems [J]. J4, 2005, 32(5): 742-747.
[13]	MA Yu-xiang;LI Yuan-jun;LIU Yan-ming. A modeling and verification method for ingtelligent networks services with Petri nets [J]. J4, 2004, 31(2): 194-198.
[14]	LI Zhi-wu;WANG An-rong;JIA Jian-yuan. Methods for solving invariants and state equations for Petri nets [J]. J4, 2003, 30(2): 259-263.

Method to compute the reachability set of S³PR

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 14

Metrics

Comments

Recommended 10

Method to compute the reachability set of S3PR

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 14

Metrics

Comments

Recommended 10

Method to compute the reachability set of S³PR