洪 良

(西安電子科技大學(xué)機(jī)電工程學(xué)院,陜西西安 710071)

S3PR網(wǎng)可達(dá)標(biāo)識(shí)數(shù)的一種有效估算方法

洪 良

(西安電子科技大學(xué)機(jī)電工程學(xué)院,陜西西安 710071)

提出一種近似計(jì)算S3PR網(wǎng)可達(dá)標(biāo)識(shí)數(shù)的代數(shù)方法.首先,基于組合學(xué),可以找到一個(gè)S3PR網(wǎng)可達(dá)標(biāo)識(shí)數(shù)的上限;然后,通過(guò)計(jì)算包含兩個(gè)資源庫(kù)所的信標(biāo),找到大部分甚至全部不可達(dá)標(biāo)識(shí)的數(shù)量.這樣,可達(dá)標(biāo)識(shí)數(shù)上限減去不可達(dá)標(biāo)識(shí)的數(shù)量就是估算的可達(dá)標(biāo)識(shí)數(shù).

柔性制造系統(tǒng);Petri網(wǎng);信標(biāo);可達(dá)標(biāo)識(shí)

Petri網(wǎng)作為一種強(qiáng)有力的建模與分析工具,廣泛地應(yīng)用于資源分配系統(tǒng)中.在一個(gè)柔性制造系統(tǒng)中,原料通過(guò)不同的加工進(jìn)程進(jìn)入系統(tǒng),并按照需求進(jìn)行下一步的加工.事實(shí)上,一種資源往往被不同的加工進(jìn)程所共用,因此形成的循環(huán)等待使系統(tǒng)陷入死鎖狀態(tài).死鎖問(wèn)題是柔性制造系統(tǒng)中一個(gè)不可回避的問(wèn)題.

人們基于Petri網(wǎng)研究了許多方法來(lái)處理柔性制造系統(tǒng)中的死鎖問(wèn)題[1-6].S3PR網(wǎng)是Petri網(wǎng)的一個(gè)子類,最早由Ezepeleta[7]提出,用于建模每一個(gè)工序只需要一種資源的生產(chǎn)系統(tǒng).許可標(biāo)識(shí)數(shù)是檢驗(yàn)一個(gè)監(jiān)督控制器的重要指標(biāo).在離散事件系統(tǒng)的監(jiān)督控制中,區(qū)域法[8]成為一種重要的方法.Uzam和Zhou[9]通過(guò)對(duì)一個(gè)S3PR網(wǎng)進(jìn)行區(qū)域分析,得到一個(gè)最大許可的監(jiān)督控制器.但是,他們的方法需要可達(dá)圖.計(jì)算可達(dá)圖是一個(gè)極其耗費(fèi)時(shí)間與資源的工作.當(dāng)研究一個(gè)規(guī)模較大的網(wǎng)時(shí),由于內(nèi)存耗盡,研究者往往在計(jì)算機(jī)前守候數(shù)天、數(shù)周甚至數(shù)月卻得不到任何結(jié)果.

因此,在計(jì)算可達(dá)圖之前,最好預(yù)先知道待計(jì)算網(wǎng)的可達(dá)標(biāo)識(shí)數(shù),然后基于當(dāng)前的計(jì)算能力再判斷能否得到結(jié)果或者權(quán)衡是否有進(jìn)行計(jì)算的必要性.基于組合學(xué),筆者等在之前的工作[10]中計(jì)算了標(biāo)識(shí)圖的可達(dá)標(biāo)識(shí)數(shù).S3PR網(wǎng)是一種比標(biāo)識(shí)圖更加復(fù)雜的網(wǎng).作為之前工作的一個(gè)延伸,筆者下面提出的方法可以在很短的時(shí)間內(nèi)估算出一個(gè)S3PR網(wǎng)的可達(dá)標(biāo)識(shí)數(shù),為可達(dá)圖的計(jì)算提供幫助.

1 基本定義

Petri網(wǎng)是一個(gè)四元組,可表示為N=(P,T,F,W),其中,P代表庫(kù)所的集合,用圓圈表示;T代表變遷的集合,用方框表示;F?(P×T)∪(T×P),稱為流關(guān)系或者有向弧的集合;W:(P×T)∪(T×P)→N,是一個(gè)映射,稱為Petri網(wǎng)N的權(quán)函數(shù).若f∈F,則W(f)＞0;若f?F,則W(f)=0.

N的P向量I是映射:I:P→Z,P向量是以P為序標(biāo)的列向量,Z是整數(shù)集.P向量I是Petri網(wǎng)N的P不變式當(dāng)且僅當(dāng)I≠0,且ITN=0T,其中N是一個(gè)以P×T為序標(biāo)的整數(shù)矩陣,稱為關(guān)聯(lián)矩陣.P不變式可以表示為多集形式.P不變式I是N的P半流當(dāng)且僅當(dāng)I中的元素均為非負(fù).稱為I的支撐.稱P不變式I是極小的若其支撐不是N的其他不變式支撐的嚴(yán)格超集,且其元素的最大公因子為1.

Petri網(wǎng)N=(P,T,F,W)的標(biāo)識(shí)M是一個(gè)從P到N的映射,N是自然數(shù)集,(N,m0)稱為網(wǎng)系統(tǒng),m0稱為N的初始標(biāo)識(shí).從m0可達(dá)的所有標(biāo)識(shí)的集合稱為(N,m0)的可達(dá)集,記為R(N,m0).令X是一個(gè)矩陣,它的每一列都是N的一個(gè)P半流,表示(N,m0)的不變式標(biāo)識(shí)的集合.標(biāo)識(shí)可以表示為多集形式.

S3PR網(wǎng)是Petri網(wǎng)的一個(gè)子類,其特點(diǎn)是每一個(gè)工序只需要一種資源參與,一個(gè)資源不能連續(xù)參與兩個(gè)工序的加工.S3PR網(wǎng)的具體定義請(qǐng)參見(jiàn)文獻(xiàn)[7].由于S3PR網(wǎng)是普通網(wǎng),一個(gè)S3PR網(wǎng)可表示為N= (pA∪P0∪pR,T,F),其中pA代表工序庫(kù)所的集合,P0代表閑置庫(kù)所的集合,pR代表資源庫(kù)所的集合.使用資源庫(kù)所r的工序庫(kù)所集合H(r)=··r∩pA,稱為r的持有者.令S是N的嚴(yán)格極小信標(biāo),[S]稱為信標(biāo)S的補(bǔ)集,其中,SR=S∩P R.極小P半流I稱為極小資源P半流或極小P r半流若其支撐僅包含一個(gè)資源庫(kù)所r以及r的持有者,也就是說(shuō)此時(shí)I表示為ir.

2 計(jì)算方法

2.1 可達(dá)標(biāo)識(shí)數(shù)上限的計(jì)算

引理1將k個(gè)相同元素放到m個(gè)不同容器的組合數(shù)是C(m+k-1,k)=(m+k-1)! (k!(m-1)!).[11]

定義1令I(lǐng)是S3PR網(wǎng)(N,m0)的P半流,其中是由Y=生成的(N,M)的一個(gè)子網(wǎng),其中NI=0是一個(gè)pI到N的映射,m0(p)·p是它的多集形式,其中,pI=這樣的子網(wǎng)稱為由I導(dǎo)出的(N,m0)的子網(wǎng).

定義2令是由I導(dǎo)出的S3PR網(wǎng)(N,m0)的子網(wǎng).NI的P向量IΔ是映射pI到Z的映射的列向量,其中pI=Z是整數(shù)集.iIΔ表示的?不變式標(biāo)識(shí)的集合表示該子網(wǎng)不變式標(biāo)識(shí)的數(shù)量.

定理1令是由I導(dǎo)出的S3PR網(wǎng)(N,m0)的子網(wǎng).假定NI擁有m個(gè)庫(kù)所并且在其初始標(biāo)識(shí)下有k個(gè)托肯,則

證明 由引理1引出.

性質(zhì)1基于組合學(xué)的乘法法則,一個(gè)S3PR網(wǎng)(N,m0)的不變式標(biāo)識(shí)數(shù)是它所含有的所有極小pr半流ir導(dǎo)出的子網(wǎng)不變式標(biāo)識(shí)數(shù)的乘積,表示為

2.2 不可達(dá)標(biāo)識(shí)的移除

定義3令iX(N,m0)和R(N,m0)分別表示S3PR網(wǎng)(N,m0)的不變式標(biāo)識(shí)的集合和可達(dá)標(biāo)識(shí)的集合.(N,m0)的一個(gè)不可達(dá)標(biāo)識(shí)是一個(gè)屬于iX(N,m0)但不屬于R(N,M)的標(biāo)識(shí).(N,m0)的不可達(dá)標(biāo)識(shí)的集合可表示為U(N,m0)={M|M∈iX(N,m0)∧M?R(N,m0)}.

定義4令irm和irn是一個(gè)S3PR網(wǎng)的兩個(gè)極小pr半流.G=irm+irn,稱為一個(gè)結(jié)構(gòu)體若存在一個(gè)嚴(yán)格極小信標(biāo)S包含資源庫(kù)所rm和rn并且

定理2令G=ir+ir,是S3PR網(wǎng)(N,m0)的一個(gè)結(jié)構(gòu)體,ri和rj是它的兩個(gè)資源庫(kù)所,ij是由G導(dǎo)出的子網(wǎng).假定NG在初始標(biāo)識(shí)下的托肯均在資源庫(kù)所中,則·pi+m0(rj)·pj,是(NG,的一個(gè)不可達(dá)標(biāo)識(shí),其中pi∈{p|p∈H(ri),?pk∈··p∩pA,pk∈H(rj)}和pj∈{p|p∈ H(rj),?pk∈··p∩pA,pk∈H(ri)}.的不可達(dá)標(biāo)識(shí)的集合記為

證明 應(yīng)用反證法,假設(shè)iri和ir是結(jié)構(gòu)體j的兩個(gè)極小P r半流;分別是iri和ir中的資源庫(kù)所.假設(shè)j是的一個(gè)可達(dá)狀態(tài),那么它之前的狀態(tài)一定是

或者

其中,Pi={p|p∈··pi∩pA},Pj={p|p∈··pj∩pA}.假如從m1可達(dá),根據(jù)定義有?p∈Pi, p∈H(rj),此時(shí)中的托肯數(shù)必定大于m0(rj),這與ir是一個(gè)P不變式,其支撐中的托肯數(shù)是恒定的事實(shí)j相矛盾.因此,不可能從m1到達(dá).同理,同樣不能從M 2到達(dá).所以,是的一個(gè)不可達(dá)標(biāo)識(shí).

定義5令G是S3PR網(wǎng)(N,m0)的一個(gè)結(jié)構(gòu)體,是由G導(dǎo)出的(N,m0)的子網(wǎng). UG(N,m0)={M∈iX(N,m0)稱為由G導(dǎo)出的(N,m0)的不可達(dá)標(biāo)識(shí)的集合,其元素?cái)?shù)量記為

性質(zhì)2令(N,m0)是一個(gè)含有n(n≥3)個(gè)資源庫(kù)所的S3PR網(wǎng),其中N=(P0∪pA∪pR,T,F),G是(N,m0)的一個(gè)結(jié)構(gòu)體,RO={r|r∈pR∧r?G}.那么,有

定理3令Gi和Gj是S3PR網(wǎng)(N,m0)中的兩個(gè)結(jié)構(gòu)體.若存在資源庫(kù)所也就是說(shuō)r是Gi和Gj的共享資源,則有(N,m0)∩UGj(N,m0)=?.反之,若不存在共享資源,則有:

(2)若沒(méi)有共享資源,說(shuō)明兩個(gè)結(jié)構(gòu)體是一個(gè)網(wǎng)中兩個(gè)獨(dú)立的部分,類似于性質(zhì)2,可以得到

3 算 例

圖1所示的網(wǎng)是一個(gè)典型的S3PR網(wǎng).應(yīng)用筆者提出的方法來(lái)計(jì)算此網(wǎng)的可達(dá)標(biāo)識(shí)數(shù).此網(wǎng)包含7個(gè)極小pr半流.首先,根據(jù)定理1分別找到這7個(gè)pr半流導(dǎo)出的子網(wǎng)的不變式標(biāo)識(shí)數(shù),進(jìn)而通過(guò)性質(zhì)1得到此網(wǎng)的不變式標(biāo)識(shí)數(shù)為34 992個(gè).接著,可以找到4個(gè)包含兩個(gè)資源庫(kù)所的嚴(yán)格極小信標(biāo),并找到這4個(gè)嚴(yán)格極小信標(biāo)對(duì)應(yīng)的結(jié)構(gòu)體,進(jìn)而根據(jù)定理2可分別計(jì)算出這4個(gè)結(jié)構(gòu)體導(dǎo)出的不可達(dá)標(biāo)識(shí)數(shù).這些不可達(dá)標(biāo)識(shí)數(shù)的總和為4 860.通過(guò)分析發(fā)現(xiàn),這些結(jié)構(gòu)體中有兩對(duì)結(jié)構(gòu)體是沒(méi)有共享資源庫(kù)所的,根據(jù)定理3可以得到這些結(jié)構(gòu)體聯(lián)合導(dǎo)出的不可達(dá)標(biāo)識(shí)的數(shù)量總共是108個(gè).這樣,得出此網(wǎng)的不可達(dá)標(biāo)識(shí)數(shù)是4 752個(gè).最后,從此網(wǎng)的不變式標(biāo)識(shí)數(shù)中減掉不可達(dá)標(biāo)識(shí)數(shù),得出此網(wǎng)的可達(dá)標(biāo)識(shí)數(shù)總共是30 240個(gè).而實(shí)際上,此網(wǎng)的可達(dá)標(biāo)識(shí)數(shù)是26 750個(gè).因此,筆者估算出來(lái)的結(jié)果跟實(shí)際結(jié)果是接近的.

接下來(lái)通過(guò)表1表現(xiàn)筆者提出的方法計(jì)算可達(dá)標(biāo)識(shí)數(shù)的準(zhǔn)確率.表1分析了10個(gè)S3PR網(wǎng)的例子,計(jì)算出了每個(gè)例子的實(shí)際可達(dá)標(biāo)識(shí)數(shù)和通過(guò)筆者提出的方法計(jì)算出來(lái)的可達(dá)標(biāo)識(shí)數(shù),并給出了筆者提出的方法計(jì)算可達(dá)狀態(tài)數(shù)的準(zhǔn)確率(準(zhǔn)確率是實(shí)際可達(dá)標(biāo)識(shí)數(shù)與筆者提出的方法計(jì)算的可達(dá)標(biāo)識(shí)數(shù)的比值).

圖1 一個(gè)S3PR網(wǎng)例子

表1 筆者提出的方法計(jì)算可達(dá)標(biāo)識(shí)數(shù)的性能分析

從表1可以看出,通過(guò)對(duì)這10個(gè)例子的分析,由筆者提出的方法計(jì)算的可達(dá)狀態(tài)數(shù)的準(zhǔn)確率還是比較高的.但是,此文找出的不可達(dá)狀態(tài)并不包括所有的不可達(dá)狀態(tài),也就是說(shuō)有一部分的不可達(dá)狀態(tài)可能沒(méi)有找出來(lái),所以結(jié)果只能是一個(gè)估算值.從理論上講,此文找到的可達(dá)狀態(tài)數(shù)肯定是大于或者等于準(zhǔn)確的可達(dá)狀態(tài)數(shù).盡管如此,筆者提出的方法的時(shí)間優(yōu)勢(shì)還是顯而易見(jiàn)的.通過(guò)算例分析,鑒于INA計(jì)算可達(dá)標(biāo)識(shí)能力的有限性,可以應(yīng)用筆者提出的方法來(lái)估算一個(gè)S3PR網(wǎng)的可達(dá)標(biāo)識(shí)數(shù),進(jìn)而判定是否有必要通過(guò)INA來(lái)計(jì)算該網(wǎng)的可達(dá)圖.

4 結(jié)束語(yǔ)

基于組合學(xué),給出一種估算S3PR網(wǎng)可達(dá)標(biāo)識(shí)數(shù)的方法.首先,計(jì)算網(wǎng)的不變式標(biāo)識(shí)數(shù);然后,通過(guò)含有兩個(gè)資源庫(kù)所的信標(biāo)確定不可達(dá)標(biāo)識(shí)數(shù),兩者的差值即為所求的結(jié)果.由于引入了組合學(xué),此方法具有相當(dāng)?shù)偷挠?jì)算復(fù)雜度,可以作為計(jì)算可達(dá)圖或者其他工作的前期工作.

[1] 陳玉峰,李志武.安全Petri網(wǎng)事件分離狀態(tài)的BDD算法[J].西安電子科技大學(xué)學(xué)報(bào),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 S3PR 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.

(編輯:郭 華)

On efficient estimation of reachable markings for S3PR

HONG Liang
(School of Mechano-electronic Engineering,Xidian Univ.,Xi’an 710071,China)

This paper proposes a method that deals with an approximate calculation of the number of reachable markings of an S3PR in an algebraic way.Based on combinatorics,we find an upper bound of reachable markings of an S3PR.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.

flexible manufacturing system;Petri net;siphon;reachable marking

TP13

A

1001-2400(2014)03-0169-05

10.3969/j.issn.1001-2400.2014.03.025

2013-01-31< class="emphasis_bold">網(wǎng)絡(luò)出版時(shí)間:

時(shí)間:2013-11-22

國(guó)家自然科學(xué)基金資助項(xiàng)目(61074035);中央高?；究蒲袠I(yè)務(wù)費(fèi)資助項(xiàng)目(JY10000904001);教育部高等學(xué)校博士點(diǎn)基金資助項(xiàng)目(20090203110009)

洪 良(1984-),男,博士,E-mail:hongliang20030605@163.com.

http://www.cnki.net/kcms/detail/61.1076.TN.20131122.1628.201403.182_020.html