S3PR網(wǎng)的嚴(yán)格極小信標(biāo)計(jì)算方法

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

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

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

1 計(jì)算嚴(yán)格極小信標(biāo)

Peri網(wǎng)、S3PR網(wǎng)以及資源環(huán)的基本定義和相關(guān)符號(hào)說明參見文獻(xiàn)[1-2, 5]．

在這一部分，筆者針對(duì)S3PR網(wǎng)中一類特殊操作庫所和特殊資源庫所進(jìn)行定義與分析．

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

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

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

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

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

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

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

定理1 在S3PR網(wǎng)N中，?Ω∈，Ω∪(·Ω∩Ω·)從N中導(dǎo)出的子網(wǎng)是強(qiáng)連通的．

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

定理3SΩ是嚴(yán)格極小信標(biāo)SMS當(dāng)且僅當(dāng)Ω是環(huán)資源子集，且它的特征資源子網(wǎng)NΩ是強(qiáng)連通的[5]．

圖1 S3PR網(wǎng)(N, M0)圖2 S3PR網(wǎng)(N, M0)

推論1 若Ω是L-S3PR網(wǎng)N的環(huán)資源子集，則SΩ=Ω∪A(·ΩΩ·) 是嚴(yán)格極小信標(biāo)SMS．

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

圖3 一個(gè)柔性制造系統(tǒng)的Petri網(wǎng)模型

2 實(shí)驗(yàn)結(jié)果

下面用一個(gè)經(jīng)典的柔性制造系統(tǒng)實(shí)例[2]來說明通過特殊庫所判斷嚴(yán)格極小信標(biāo)的應(yīng)用．圖3為該柔性制造系統(tǒng)的S3PR網(wǎng)模型．

圖3的簡單環(huán)資源子集如表1所示，組合環(huán)資源子集如表2所示．圖3共有25個(gè)環(huán)資源子集，這些環(huán)資源子集對(duì)應(yīng)25個(gè)信標(biāo)，但其中有些信標(biāo)可能不是嚴(yán)格極小的．下面通過定理4～6來判斷信標(biāo)是否為嚴(yán)格極小信標(biāo)．

表1 圖3中的簡單環(huán)資源子集

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

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

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

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

綜上所述，可求出圖3所有的嚴(yán)格極小信標(biāo)，共18個(gè)．

表2 圖3中的組合環(huán)資源子集

3 結(jié) 束 語

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

[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] 王安榮, 李志武. 基本信標(biāo)計(jì)算的一種快速算法[J]. 西安電子科技大學(xué)學(xué)報(bào), 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.