洪 良，周 健

（西安工程大學(xué)電子信息學(xué)院，陜西西安 710048）

一類Petri網(wǎng)可達(dá)標(biāo)識數(shù)的有效計(jì)算方法

洪 良，周 健

（西安工程大學(xué)電子信息學(xué)院，陜西西安 710048）

S3PR網(wǎng)是Petri網(wǎng)的一個子類，基于組合學(xué)提出一種計(jì)算S3PR網(wǎng)可達(dá)標(biāo)識數(shù)的代數(shù)方法.首先，通過組合學(xué)計(jì)算S3PR網(wǎng)可達(dá)標(biāo)識數(shù)的上限.然后，基于資源回路理論，計(jì)算包含2個以及3個資源庫所的信標(biāo)，進(jìn)而找到大部分甚至全部不可達(dá)標(biāo)識的數(shù)量.最后，由可達(dá)標(biāo)識數(shù)上限減去不可達(dá)標(biāo)識，得到估算的可達(dá)標(biāo)識數(shù).該方法的性能通過例子計(jì)算與分析進(jìn)行了驗(yàn)證.結(jié)果顯示該方法可以在較短時(shí)間內(nèi)計(jì)算出S3PR網(wǎng)的可達(dá)標(biāo)識數(shù)，有助于可達(dá)圖的生成.

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

0 引 言

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

人們基于Petri網(wǎng)研究了很多方法來處理柔性制造系統(tǒng)中的死鎖問題［1－2］.文獻(xiàn)［3］提出S3PR網(wǎng)是Petri網(wǎng)的一個子類，用于建模每一個工序只需要一種資源的生產(chǎn)系統(tǒng)；許可標(biāo)識數(shù)是檢驗(yàn)一個監(jiān)督控制器的重要指標(biāo)，文獻(xiàn)［4－5］中基于信標(biāo)的控制器設(shè)計(jì)方案計(jì)算復(fù)雜度低，但通常情況下得不到最優(yōu)控制，也就是許可標(biāo)識數(shù)最大；在離散事件系統(tǒng)的監(jiān)督控制中，區(qū)域法成為一種重要的方法［6］；文獻(xiàn)［7］通過對一個S3PR網(wǎng)進(jìn)行區(qū)域分析，可以得到一個最大許可的監(jiān)督控制器，但是，他們的方法需要可達(dá)圖.計(jì)算可達(dá)圖是一個極其耗費(fèi)時(shí)間與資源的工作，當(dāng)研究一個規(guī)模較大的網(wǎng)時(shí)，由于內(nèi)存耗盡，研究者往往在計(jì)算機(jī)前守候數(shù)天、數(shù)周甚至數(shù)月卻得不到任何結(jié)果［8］.

因此，在計(jì)算可達(dá)圖之前，最好預(yù)先知道待計(jì)算網(wǎng)的可達(dá)標(biāo)識數(shù)，然后基于當(dāng)前的計(jì)算能力再判斷能否得到結(jié)果或者權(quán)衡是否有進(jìn)行計(jì)算的必要性.文獻(xiàn)［9－11］基于組合學(xué)找出了部分S3PR網(wǎng)可達(dá)標(biāo)識的數(shù)量，但他們的方法并不適用于所有的S3PR網(wǎng).

文中的方法適用于所有S3PR網(wǎng)，可以在很短時(shí)間內(nèi)估算出一個S3PR網(wǎng)的可達(dá)標(biāo)識數(shù)，為可達(dá)圖的計(jì)算提供幫助.

1 基本定義

Petri網(wǎng)是一個四元組，可表示為N＝（P，T，F(xiàn)，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，且IT［N］＝OT，其中［N］是一個以為序標(biāo)的整數(shù)矩陣，稱為關(guān)聯(lián)矩陣.稱P－不變式I是N的P－半流當(dāng)且僅當(dāng)I中的元素均為非負(fù).‖I‖＝｛p｜I（p）≠0｝稱為I的支撐.稱P－不變式I是極小的若其支撐不是N的其他不變式支撐的嚴(yán)格超集，且其元素的最大公因子為1.

Petri網(wǎng)N＝（P，T，F(xiàn)，W）的標(biāo)識M是一個從P到N的映射，（N，M0）稱為網(wǎng)系統(tǒng)，M0稱為N的初始標(biāo)識.從M0可達(dá)的所有標(biāo)識的集合稱為（N，M0）的可達(dá)集，記為R（N，M0）.令X是一個矩陣，它的每一列都是N的一個P－半流，Ix（N，M0）＝｛M∈N｜p｜／XTM＝XTM0｝表示（N，M0）的不變式標(biāo)識的集合.文中，標(biāo)識跟不變式可以表示為多集形式.

S3PR網(wǎng)是Petri網(wǎng)的一個子類，其特點(diǎn)是每一個工序只需要一種資源的參與，一個資源不能連續(xù)參與兩個工序的加工.由于S3PR網(wǎng)是普通網(wǎng)，一個S3PR網(wǎng)可表示為N＝（PA∪P0∪PR，T，F(xiàn)），其中PA代表工序庫所的集合，P0代表閑置庫所的集合，PR代表資源庫所的集合.使用資源庫所r的工序庫所集合稱為r的持有者.令S是N的嚴(yán)格極小信標(biāo)，稱為信標(biāo)S的補(bǔ)集，其中，SR＝S∩PR.極小P－半流I稱為極小資源P－半流或極小Pr－半流若其支撐僅包含一個資源庫所r以及r的持有者，也就是說，‖I‖＝｛r｝∪H（r），此時(shí)I表示為Ir.

2 計(jì)算方法

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

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

3 算 例

如圖1所示是一個典型的S3PR網(wǎng).應(yīng)用所提出的方法，通過計(jì)算此網(wǎng)的不變式標(biāo)識數(shù)，可知此網(wǎng)包含7個Pr－半流，分別找到這7個Pr－半流導(dǎo)出的標(biāo)識子網(wǎng)的不變式標(biāo)識數(shù)，進(jìn)而得到此網(wǎng)狀態(tài)數(shù)的上限為675 000.可以找到4個包含2個資源庫所的嚴(yán)格極小信標(biāo)，并找到這4個嚴(yán)格極小信標(biāo)對應(yīng)的2－configuration，進(jìn)而分別找到這4個2－configuration導(dǎo)出的此網(wǎng)的不可達(dá)標(biāo)識數(shù).這些不可達(dá)狀態(tài)相加起來一共是54 000個.通過分析，可知其中有兩對2－configuration是沒有共享的資源庫所的，重疊的個數(shù)一共是360個.這樣得到計(jì)算的不可達(dá)狀態(tài)數(shù)是53 640個.可以找到6個包含3個資源庫所得嚴(yán)格極小信標(biāo)，其中，只有一個信標(biāo)中的資源庫所不包含其他嚴(yán)格極小信標(biāo)的資源庫所，根據(jù)性質(zhì)3，可以得到不可達(dá)狀態(tài)為2 500個，重疊的個數(shù)一共是225個，最終的不可達(dá)狀態(tài)數(shù)為2 275個.因此，總共的不可達(dá)狀態(tài)數(shù)為55 915個.從此網(wǎng)的不變式標(biāo)識數(shù)減掉不可達(dá)狀態(tài)的數(shù)量最后得到，估算的此網(wǎng)的狀態(tài)數(shù)一共是619 085個.而實(shí)際上，此網(wǎng)的可達(dá)狀態(tài)數(shù)是600 424.因此，估算出來的結(jié)果跟實(shí)際結(jié)果是很接近的.

圖1 S3PR網(wǎng)例子Fig.1 The S3PR example

表1顯示了分別應(yīng)用INA和文K方法于圖1中的網(wǎng)，隨初始標(biāo)識改變，而求得的可達(dá)狀態(tài)數(shù)與所耗費(fèi)時(shí)間.其中，表格中“－”表示計(jì)算機(jī)內(nèi)存耗盡，已無法計(jì)算出可達(dá)狀態(tài).從表1中可以看出，此網(wǎng)的可達(dá)狀態(tài)隨初始標(biāo)識的增大而迅速增加.應(yīng)用INA求得狀態(tài)所需的時(shí)間也是迅速增加，甚至在標(biāo)識5下已無法找到最終的可達(dá)圖.而結(jié)果顯示，應(yīng)用文中方法，計(jì)算時(shí)間對初始標(biāo)識的改變并不敏感，而是基本保持恒定，圖2清晰地顯示了這一點(diǎn).因?yàn)镮NA的計(jì)算可達(dá)狀態(tài)的能力是有一個上限的，通過結(jié)果分析，知道可以通過應(yīng)用此文方法來估計(jì)一個S3PR網(wǎng)的可達(dá)狀態(tài)數(shù)，來判定是否有必要通過INA來計(jì)算此網(wǎng)的可達(dá)圖.

通過INA可以計(jì)算一個網(wǎng)的可達(dá)圖.一個網(wǎng)的可達(dá)圖規(guī)模跟網(wǎng)的節(jié)點(diǎn)數(shù)和初始標(biāo)識的大小成指數(shù)關(guān)系.可見，INA的計(jì)算能力對初始標(biāo)識的大小敏感.接下來，通過調(diào)整圖1中S3PR網(wǎng)的初始標(biāo)識來檢驗(yàn)此文方法對一個網(wǎng)初始標(biāo)識的敏感性.以下的計(jì)算是在Windows XP操作系統(tǒng)下，用Pentium（R）Dual－Core CPU 2.6GHz，內(nèi)存為3G的計(jì)算機(jī)下進(jìn)行的.隨著圖1中網(wǎng)初始標(biāo)識的改變，分別應(yīng)用INA和此文方法來計(jì)算可達(dá)狀態(tài)數(shù).

表1 INA與本文方法性能對比Table 1 Comparison between INA and the proposed method

4 結(jié)束語

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

［1］ LI Z W，ZHOU M C.Elementary siphons of Petri nets and their application to deadlock prevention in flexible manufacturing systems［J］.IEEE Trans on Systems，Man and Cybernetics，Part A，2004，34（1）：38－51.

［2］ LI Z W，ZHOU M C.Two－stage method for synthesizing liveness－enforcing supervisors for flexible manufacturing systems using Petri nets［J］.IEEE Trans on Industrial Informatics，2006，2（4）：313－325.

［3］ EZPELETA J，COLOM J M，MARTINEZ J.A Petri net based deadlock prevention policy for flexible manufacturing systems［J］.IEEE Trans on Robotics and Automation，1995，11（2）：173－184.

［4］ 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 Trans on Systems，Man and Cybernetics，Part A，2012，42（1）：226－237.

［5］ 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 ＆Cybernetics，Part A，2012，42（5）：1206－1215.

［6］ 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.

［7］ 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 ＆Cybernetics，Part A，2007，37（3）：362－371.

［8］ HONG L，CHAO D Y.Enumeration of reachable states for arbitrary marked graphs［J］.IET Control Theory and Applications，2012，6（10）：1536－1543.

［9］ CHAO D Y，YU T H.Enumeration of reachable（forbidden，live，and deadlock）states of top k－th order system（with a non－sharing resource place）of Petri nets［C］／／Industrial Electronics Society，IECON 2013－39th Annual Conference of the IEEE.Vienna：IEEE，2013：3517－3523.

［10］ CHAO D Y，YU T H，WU S C.Closed form formula construction to enumerate control related states of K－th order S3PR system（with a Top Left side non－sharing resource place）of Petri nets［C］／／Networking，Sensing and Control（ICNSC），2014IEEE 11th International Conference on.Miami：IEEE，2014：132－137.

［11］ CHAO D Y，YU T H，CHEN T Y.Computation of control related states of middle k－th order system（with a nonsharing resource place）of Petri nets［C］／／Computer，Consumer and Control（IS3C），2014International Symposium on.Washington：IEEE，2014：244－247.

［12］ ROBERTS F S，TESMAN B.Applied combinatorics［M］.Oxford：Taylor ＆Francis，2009.

編輯、校對：孟 超

Effective enumeration of reachable markings for a class of Petri Nets

HONG Liang，ZHOU Jian
（School of Electronics and Information，Xi′an Polytechnic University，Xi′an 710048，China）

An S3PR is a class of Petri Nets.This work proposes a combinatorics based method that deals with an approximate calculation of the number of reachable markings of an S3PR in an algebraic way.First，an upper bound of reachable markings of an S3PR can be found by combinatorics.Second，the number of most even all unreachable markings can be obtained by extracting siphons with two and three resource places from resource circuits.Finally，the number of reachable markings can be estimated by removing the unreachable ones from the upper bound.Example calculations and analyses show the performance of the proposed method.The result shows that the number of reachable markings of an S3PR can be calculated by the proposed method in a short period of time，which contributes to the generation of reachability graphs.

flexible manufacturing system；Petri Net；siphon；reachable markings

TP 13

A

1674－649X（2015）05－0606－05

10.13338／j.issn.1674－649x.2015.05.016

2015－06－10

陜西省自然科學(xué)基礎(chǔ)研究計(jì)劃資助項(xiàng)目（2015JQ6258）

洪良（1984—），男，河北省唐山市人，西安工程大學(xué)講師，研究方向?yàn)樽詣涌刂评碚?、Petri理論及應(yīng)用.E－mail：hongliang20030605＠163.com