S3PR網的嚴格極小信標計算方法

尤 丹， 劉 苗， 吳文慧， 王壽光

(1. 浙江工商大學 信息與電子工程學院，浙江 杭州 310018；2. 西安電子科技大學 機電工程學院，陜西 西安 710071)

作為一個數學建模工具，Petri[1]網能夠描述資源共享、沖突、互斥、并發和不確定性，而且能幫助研究者發現系統潛在的死鎖，并使用相應的控制策略來防止死鎖，因而被廣泛地應用于柔性制造系統死鎖的分析與控制．在眾多Petri 模型中，S3PR 網[2]是學者們研究柔性制造系統死鎖問題時較常用的模型．目前許多學者致力于極小信標相關理論的研究[3-8]，并提出了計算極小信標的算法，但這些算法的計算效率不高．現今，基于信標的死鎖控制問題[9-10]，針對普通Petri網比較成熟，但相對較為復雜的一般Petri網而言，信標研究還處于初期階段．資源環法是目前計算S3PR 網嚴格極小信標最有效的方法之一．針對S3PR 網，文獻[5]提出了基于計算資源環的算法并提出環資源子集的概念以克服資源環法的不足．同時，還提出環資源子集的計算算法以及環資源子集對應的信標是嚴格極小信標的充分必要條件，在此基礎上提出一種快速計算嚴格極小信標的算法．但是文獻[5]沒有分析S3PR網中一類特殊庫所與嚴格極小信標的關系，筆者針對這類特殊庫所進行研究，提出基于環資源計算嚴格極小信標的方法．由于該方法避免環資源子集特征資源子網[5]強連通的判斷，所以與環資源子集法[5]相比，有更高的計算效率．

1 計算嚴格極小信標

Peri網、S3PR網以及資源環的基本定義和相關符號說明參見文獻[1-2, 5]．

在這一部分，筆者針對S3PR網中一類特殊操作庫所和特殊資源庫所進行定義與分析．

在下面的討論中，用Ω來表示S3PR網N=(PA∪P0∪PR，T，F)的一個資源子集，其中Ω= {r1，r2，…，rm}?PR(m≥2)．

定義1 令N=(PA∪P0∪PR，T，F)，是一個S3PR網，Ωi和Ωj是N的資源子集．稱Ωi和Ωj是可組合的，當且僅當Ωi∩Ωj≠?，Ωi?Ωj，Ωj?Ωi．對資源子集Ωi和Ωj的組合操作“°”定義如下:

(1) 若Ωi和Ωj是可組合的，則Ωi°Ωj=Ωi∪Ωj;

(2) 若Ωi和Ωj是不可組合的，則Ωi°Ωj=?．

在下面的討論中，如果Ωi和Ωj是可組合的，用Ωi，j來表示Ωi°Ωj．顯然，Ωi°Ωi=?．

定義3 稱資源子集Ω為組合環資源子集，如果?Ω1，Ω2，…，Ωn∈Θ，使得Ω=Ω1°Ω2° …°Ωn=Ω1∪Ω2∪ …∪Ωn(n≥2)．用Ξ表示N中所有組合環資源子集的集合．

由定義2和定義3得到以下定理．

定理1 在S3PR網N中，?Ω∈，Ω∪(·Ω∩Ω·)從N中導出的子網是強連通的．

定理2 令N=(PA∪P0∪PR，T，F)，是一個S3PR網，Ω= {r1，r2，…，rm}?PR(m≥2) ，是N的資源子集，則SΩ=Ω∪A(·ΩΩ·)，是一個信標[5]．

定理3SΩ是嚴格極小信標SMS當且僅當Ω是環資源子集，且它的特征資源子網NΩ是強連通的[5]．

圖1 S3PR網(N, M0)圖2 S3PR網(N, M0)

推論1 若Ω是L-S3PR網N的環資源子集，則SΩ=Ω∪A(·ΩΩ·) 是嚴格極小信標SMS．

證明 在L-S3PR中，不存在特殊操作庫所，同樣也不存在特殊資源庫所，由引理1或定理4即可得出此推論．

圖3 一個柔性制造系統的Petri網模型

2 實驗結果

下面用一個經典的柔性制造系統實例[2]來說明通過特殊庫所判斷嚴格極小信標的應用．圖3為該柔性制造系統的S3PR網模型．

圖3的簡單環資源子集如表1所示，組合環資源子集如表2所示．圖3共有25個環資源子集，這些環資源子集對應25個信標，但其中有些信標可能不是嚴格極小的．下面通過定理4～6來判斷信標是否為嚴格極小信標．

表1 圖3中的簡單環資源子集

根據定義6～8，可知圖3中操作庫所p6是特殊操作庫所，資源庫所p20是特殊資源庫所，資源庫所p23、p25是特殊資源庫所p20的特殊輸入資源庫所．

根據定理4可得，簡單環資源子集Ω2，Ω4，Ω5，Ω6和組合環資源子集Ω2，4，Ω2，5，Ω4，5，Ω5，6，Ω2，4，5，Ω2，5，6，Ω4，5，6，Ω2，4，5，6所形成的信標中不包含任何特殊資源庫所p20，則這些環資源子集一定可以形成嚴格極小信標SMS．

根據定理5可得，簡單環資源子集Ω3和組合環資源子集Ω3，4，Ω3，5，Ω3，4，5，Ω3，5，6，Ω3，4，5，6所形成的信標中包含所有特殊輸入資源庫所p23和p25，則這些環資源子集一定可以形成嚴格極小信標SMS．

根據定理6可得，簡單環資源子集Ω1和組合環資源子集Ω1，2，Ω1，2，4，Ω1，2，5，Ω1，2，4，5，Ω1，2，5，6，Ω1，2，4，5，6所形成的信標中包含一個特殊輸入資源庫所p23或p25，則這些環資源子集一定不可以形成嚴格極小信標SMS．

綜上所述，可求出圖3所有的嚴格極小信標，共18個．

表2 圖3中的組合環資源子集

3 結 束 語

對于S3PR網，筆者首先定義了特殊操作庫所和特殊資源庫所，通過對其分析，提出通過特殊庫所判定信標是否為嚴格極小信標的判定定理，基于判定定理有效求解出嚴格極小信標．實驗結果表明，采用筆者所提出的方法，可以快速地計算出S3PR網中的嚴格極小信標．與文獻[5]提出的方法相比，筆者提出的基于特殊庫所求解嚴格極小信標的方法避免了對環資源子集特征資源子網是否是強連通的判斷，進而也避免了通過資源子集求其特征資源子網．因此筆者提出的方法將提高計算效率．由于該方法只適用于一類S3PR網，把該方法應用到更大類型網將是以后研究的方向．

[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 S3PR 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.