洪 良，周 健

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

一類Petri網可達標識數(shù)的有效計算方法

洪 良，周 健

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

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

柔性制造系統(tǒng)；Petri網；信標；可達標識

0 引 言

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

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

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

文中的方法適用于所有S3PR網，可以在很短時間內估算出一個S3PR網的可達標識數(shù)，為可達圖的計算提供幫助.

1 基本定義

Petri網是一個四元組，可表示為N＝（P，T，F(xiàn)，W）.其中，P代表庫所的集合，用圓圈表示；T代表變遷的集合，用方框表示；F?（P×T）∪（T×P）稱為流關系或者有向弧的集合；W：（P×T）∪（T×P）→N是一個映射，稱為Petri網N的權函數(shù)，若f∈F，則W（f）＞0，若f?F，則W（f）＝0.

N的P－向量I是映射：I：P→Z，P－向量是以P為序標的列向量，Z是整數(shù)的集合.P－向量I是Petri網N的P－不變式當且僅當I≠0，且IT［N］＝OT，其中［N］是一個以為序標的整數(shù)矩陣，稱為關聯(lián)矩陣.稱P－不變式I是N的P－半流當且僅當I中的元素均為非負.‖I‖＝｛p｜I（p）≠0｝稱為I的支撐.稱P－不變式I是極小的若其支撐不是N的其他不變式支撐的嚴格超集，且其元素的最大公因子為1.

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

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

2 計算方法

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

2.2 不可達標識的移除

3 算 例

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

圖1 S3PR網例子Fig.1 The S3PR example

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

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

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

4 結束語

基于組合學，給出一種估算S3PR網可達標識數(shù)的方法.首先，計算網的可達標識數(shù)上限.然后，通過含有2個資源庫所的信標確定不可達標識數(shù).兩者的差值即為所求的結果.由于引入了組合學，此方法具有相當?shù)偷挠嬎銖碗s度，可以作為計算可達圖的前期工作.

［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

陜西省自然科學基礎研究計劃資助項目（2015JQ6258）

洪良（1984—），男，河北省唐山市人，西安工程大學講師，研究方向為自動控制理論、Petri理論及應用.E－mail：hongliang20030605＠163.com