尤 丹, 劉 苗, 吳文慧, 王壽光
(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ì)算效率.
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)模型
下面用一個(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)資源子集
對(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.