S3PR网可达标识数的一种有效估算方法

doi:10.3969/j.issn.1001-2400.2014.03.025

Abstract

Abstract:

This paper proposes a method that deals with an approximate calculation of the number of reachable markings of an S³PR in an algebraic way. Based on combinatorics, we find an upper bound of reachable markings of an S³PR. Then we try to find the number of unreachable markings by extracting siphons with two resource places. The obtained number covers most or even all of the unreachable markings. Finally, we can estimate the number of reachable markings by removing the unreachable ones from the upper bound. Calculations and analyses verify the effectiveness of the proposed method.

Key words: flexible manufacturing system, Petri net, siphon, reachable marking

HONG Liang. On efficient estimation of reachable markings for S³PR[J].J4, 2014, 41(3): 169-173.

References

［1］陈玉峰, 李志武. 安全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.
［2］ Li Z W, Zhou M C. Elementary Siphons of Petri Nets and Their Application to Deadlock Prevention in Flexible Manufacturing Systems ［J］. IEEE Transactions on Systems, Man and Cybernetics: Systems, 2004, 34(1): 38-51.
［3］ Li Z W, Liu G Y, Hanisch H M, et al. Deadlock Prevention Based on Structure Reuse of Petri Net Supervisors for Flexible Manufacturing Systems ［J］. IEEE Transactions on Systems, Man and Cybernetics: Systems, 2012, 42(1): 178-191.
［4］ Li Z W, Zhou M C. Two-stage Method for Synthesizing Liveness-enforcing Supervisors for Flexible Manufacturing Systems Using Petri Nets ［J］. IEEE Transactions on Industrial Informatics, 2006, 2(4): 313-325.
［5］ Wang S G, Wang C Y, Zhou M C, et al. 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 S G, Wang C Y, Zhou M C. Controllability Conditions of Resultant Siphons in a Class of Petri Nets ［J］. IEEE Transactions on Systems, Man and Cybernetics: Systems, 2012, 42(5): 1206-1215.
［7］ Ezpeleta J, Colom J M, Martinez J. Petri Net Based Deadlock Prevention Policy for Flexible Manufacturing Systems ［J］. IEEE Transactions on Robotics and Automation, 1995, 11(2): 173-184.
［8］ Ghaffari A, Rezg N, Xie X L. Design of a Live and Maximally Permissive Petri Net Controller Using the Theory of Regions ［J］. IEEE Transactions on Robotics and Automation, 2003, 19(1): 137-142.
［9］ Uzam M, Zhou M C. An Iterative Synthesis Approach to Petri net-based Deadlock Prevention Policy for Flexible Manufacturing Systems ［J］. IEEE Transactions on Systems, Man and Cybernetics: Systems, 2007, 37(3): 362-371.
［10］ Hong L, Chao D Y. Enumeration of Reachable States for Arbitrary Marked Graphs ［J］. IET Control Theory and Applications, 2012, 6(10): 1536-1543.
［11］ Roberts F S, Tesman B. Applied Combinatorics ［M］. Oxford: Taylor ＆ Francis, 2009.

[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]	MA Ziyue;TONG Yin. Supervisor synthesis in Petri nets based on basis marking graphs [J]. Journal of Xidian University, 2016, 43(6): 68-73.
[3]	JIANG Zhongyuan;ZHANG Xiuyan;MA Ziyue. Capacity optimization for power storage systems in smart grids [J]. J4, 2015, 42(6): 106-112.
[4]	ZHANG Xiuyan;ZHONG Chunfu;JIA Jianyuan. Method to compute the reachability set of S³PR [J]. J4, 2015, 42(5): 105-109.
[5]	ZHANG Li;ZHAO Liangxu;WANG Shouguang;WANG Chengying. Optimal linear constraint transformation method for α-nets [J]. J4, 2015, 42(5): 183-187+212.
[6]	CHEN Xiaoliang;JIANG Zhongyuan;YE Jianhong . Confusion detection and prevention policies for workflow nets [J]. J4, 2015, 42(2): 77-83.
[7]	ZHU Chengcheng;DONG Lida. Concurrency bug test for a class of multithreaded software [J]. J4, 2015, 42(2): 167-173+212.
[8]	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.
[9]	LI Ye;WANG Yinghui;YU Zhenhua. Formal modeling of cyber-physical systems using object-oriented Petri nets [J]. J4, 2014, 41(2): 165-171.
[10]	WANG Qi;WANG Anrong;PU Xuqiang. Computation of special markings of Petri nets of manufacturing systems [J]. J4, 2013, 40(6): 85-91.
[11]	ZHANG Man;DUAN Zhenhua. Synthesis rules of WF-nets and their application in process design [J]. J4, 2012, 39(2): 200-206.
[12]	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.
[13]	. Deadlock prevention approach for a class of timed Petri nets [J]. J4, 2009, 36(5): 902-908.
[14]	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.
[15]	WANG An-rong;LI Zhi-wu. Effective algorithm for obtaining a set of elementary siphons [J]. J4, 2008, 35(4): 632-638.

On efficient estimation of reachable markings for S³PR

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

Recommended 10

On efficient estimation of reachable markings for S3PR

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

Recommended 10

On efficient estimation of reachable markings for S³PR