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

洪 良

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

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

洪 良

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

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

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

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

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

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

1 基本定義

Petri網(wǎng)是一個四元組,可表示為N=(P,T,F,W),其中,P代表庫所的集合,用圓圈表示;T代表變遷的集合,用方框表示;F?(P×T)∪(T×P),稱為流關(guān)系或者有向弧的集合;W:(P×T)∪(T×P)→N,是一個映射,稱為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是一個以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)識M是一個從P到N的映射,N是自然數(shù)集,(N,m0)稱為網(wǎng)系統(tǒng),m0稱為N的初始標(biāo)識.從m0可達的所有標(biāo)識的集合稱為(N,m0)的可達集,記為R(N,m0).令X是一個矩陣,它的每一列都是N的一個P半流,表示(N,m0)的不變式標(biāo)識的集合.標(biāo)識可以表示為多集形式.

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

2 計算方法

2.1 可達標(biāo)識數(shù)上限的計算

引理1將k個相同元素放到m個不同容器的組合數(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)的一個子網(wǎng),其中NI=0是一個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)識的集合表示該子網(wǎng)不變式標(biāo)識的數(shù)量.

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

證明 由引理1引出.

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

2.2 不可達標(biāo)識的移除

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

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

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

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

或者

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

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

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

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

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

3 算 例

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

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

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

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

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

4 結(jié)束語

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

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

時間:2013-11-22

國家自然科學(xué)基金資助項目(61074035);中央高校基本科研業(yè)務(wù)費資助項目(JY10000904001);教育部高等學(xué)校博士點基金資助項目(20090203110009)

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

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