Petri網(wǎng)系統(tǒng)活性保持的充分與必要條件

蔡曉霞，郭承軍，陳鶴峰

（廣東工業(yè)大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，廣東 廣州 510520）

1 引言

活性作為Petri網(wǎng)的重要特性之一，活性問題的研究一直是Petri網(wǎng)理論的重要課題.

目前，已有許多文獻(xiàn)研究了狀態(tài)機(jī)（State Machine），標(biāo)識(shí)圖（Marked Graph），自由選擇網(wǎng)（Free Choice）等Petri網(wǎng)特殊子類的活性問題[1-6].對(duì)于普通網(wǎng)（弧上的權(quán)重皆為1），文獻(xiàn)[7]給出了其保持活性的充分與必要條件.然而對(duì)通用Petri網(wǎng)系統(tǒng)的研究是較少的.Barkaoui利用結(jié)構(gòu)分析方法，通過定義受控Siphon，分別給出了Petri網(wǎng)系統(tǒng)活性的必要條件與充分條件[8].文獻(xiàn)[9]借助于可覆蓋圖得到了無關(guān)聯(lián)-ω?cái)?shù)網(wǎng)系統(tǒng)的活性判定方法.

本文對(duì)Petri網(wǎng)系統(tǒng)活性的充分條件與必要條件進(jìn)行研究.提出了非前阻塞Siphon的概念，得到了Petri網(wǎng)活性的一個(gè)必要條件.在討論通用Petri網(wǎng)的活性的判定問題時(shí)，借助于Petri網(wǎng)系統(tǒng)的狀態(tài)方程和線性方程組理論，對(duì)弱活性加以“齊次線性方程組僅有正整數(shù)解”這一限制，得到了Petri網(wǎng)活性的充分條件，并通過構(gòu)造增廣Petri網(wǎng)得到了一種新的活性判定方法，對(duì)豐富和發(fā)展Petri理論有一定的意義.

本文的安排如下：第2、3節(jié)給出了一些相關(guān)的Petri網(wǎng)基本概念及結(jié)論，并定義了Siphon非前阻塞的概念.第4節(jié)給出了Petri網(wǎng)活性的必要條件.在第5節(jié)中，以一類簡(jiǎn)單網(wǎng)為例，利用線性規(guī)劃方法判定Siphon是非前阻塞的，降低了計(jì)算復(fù)雜度.第6節(jié)借助Petri網(wǎng)的結(jié)構(gòu)特征及線性方程組的理論知識(shí)，找到了判別Petri網(wǎng)活性的充分條件，并在下一節(jié)中，通過構(gòu)造增廣Petri網(wǎng)得到了活性判定的方法.最后，第8節(jié)總結(jié)了本文的工作，并對(duì)后續(xù)可研究?jī)?nèi)容進(jìn)行展望.

2 Petri網(wǎng)的基本概念

本節(jié)中，簡(jiǎn)要闡述需要用到的有關(guān)Petri網(wǎng)理論定義，常用的記號(hào)以及基本結(jié)論. 詳細(xì)內(nèi)容可參考文獻(xiàn)[10].

（1）P與T分別稱為庫所集合與變遷集合，而且|P|=m<∞，|T|=n<∞，P≠?，T≠?，P∩T=?.|*|為集合*的基數(shù).

（2）F?(P×T)∪(T×P)是有向弧的集合.

（3）W:F→N+為映射，它給所有的有向弧分配權(quán)重值.其中，①整數(shù)集合記為Z，非負(fù)整數(shù)集記為N，正整數(shù)集記為N+=N{0}.不超過k的非負(fù)整數(shù)記為Nk={0,1,2…,k}，不超過k的正整數(shù)記為=Nk{0}..

3 Petri網(wǎng)的相關(guān)結(jié)論

4 Petri網(wǎng)活性必要條件

當(dāng)Petri網(wǎng)是活的時(shí)候，它具有某些特定的行為特性，這些行為特征就是Petri網(wǎng)保持活性的必要條件.如果存在某算法，它能驗(yàn)證上述某些必要條件不成立，并且該算法的復(fù)雜度是網(wǎng)規(guī)模的多項(xiàng)式函數(shù)，那么，該算法能有效地判定Petri網(wǎng)是非活的.

5 非前阻塞的判定

定理5.2 如果線性規(guī)劃(2)的最優(yōu)值w*<0，則定理5.1中的SiphonS是非前阻塞的.

注:由上述推理過程，定理顯然成立，詳細(xì)過程略去.

圖1 例1的Petri網(wǎng)系統(tǒng)

圖2 例1中由x生成的子系統(tǒng)

代入線性規(guī)劃（2）求解，可得其最優(yōu)值*w=?∞，為無界解.由此，定理5.2的條件成立，從而SiphonS1是非前阻塞的.同樣的方法，可以判定S2也是非前阻塞的.

對(duì)于有匯合的Petri網(wǎng)的無阻塞的判定，限于篇幅關(guān)系，本文不再詳細(xì)闡述，是后續(xù)研究?jī)?nèi)容.

6 Petri網(wǎng)活性充分條件

Petri網(wǎng)能否保持活性，是Petri網(wǎng)理論研究及其應(yīng)用系統(tǒng)建模聚焦的核心問題.對(duì)于規(guī)模（網(wǎng)節(jié)點(diǎn)數(shù)，有向弧的條數(shù)，token數(shù)目）較大的網(wǎng)，由于系統(tǒng)演化過程中，狀態(tài)呈爆炸式的增長(zhǎng)，采用可達(dá)圖分析的方法，需存貯可達(dá)狀態(tài)及狀態(tài)轉(zhuǎn)化過程，計(jì)算復(fù)雜度過高.本節(jié)借助Petri網(wǎng)結(jié)構(gòu)特征及線性方程組理論來尋求Petri網(wǎng)活性的充分條件，避免遍歷可達(dá)圖，有效地降低計(jì)算復(fù)雜度.

圖3 例2的Petri網(wǎng)系統(tǒng)

7 Petri網(wǎng)活性的判定

對(duì)于關(guān)聯(lián)矩陣增加的行[?1,1,0,0]，[0,0,?1,1]，在有界時(shí)確保增廣網(wǎng)系統(tǒng)有界，向關(guān)聯(lián)矩陣再添加一行[1,?1,0,0]，[0,0,1,?1]，得到矩陣，相當(dāng)于在原Petri網(wǎng)系統(tǒng)中增加庫所p4,p5,p6,p7，所示如圖4.此時(shí)，矩陣A1與等價(jià).

圖4 例3的Petri網(wǎng)系統(tǒng)

8 結(jié)論

本文基于Petri網(wǎng)的狀態(tài)轉(zhuǎn)移方程，討論了確保Petri網(wǎng)活性的充分條件與必要條件，并且將討論的范圍拓廣至通用的Petri網(wǎng)，不限定網(wǎng)具有特殊結(jié)構(gòu).對(duì)于普通網(wǎng)（弧上的權(quán)重皆為1）成立的活性的充分與必要條件，對(duì)于通用網(wǎng)來說，大多數(shù)都不再成立.Siphon是一個(gè)與Petri網(wǎng)活性相關(guān)的關(guān)鍵結(jié)構(gòu).相較于大多數(shù)學(xué)者提出的可控Siphon的概念，文中提出了非前阻塞Siphon的概念，在驗(yàn)證活性滿足的條件時(shí)，可降低計(jì)算復(fù)雜度.當(dāng)Siphon生成的子網(wǎng)是無匯合時(shí)，提供了一個(gè)線性規(guī)劃方法來判定Siphon是非前阻塞的，進(jìn)一步降低了計(jì)算復(fù)雜性.在討論保持活性的充分條件時(shí)，給弱活性添加某些約束（數(shù)學(xué)上表示為齊次線性方程組僅有正整數(shù)解），以確保Petri網(wǎng)是活的.最后，增加庫所構(gòu)造Petri網(wǎng)的增廣網(wǎng)，通過增廣網(wǎng)的行為逼近原網(wǎng)的行為，從而判定原網(wǎng)的活性.在此要求增廣網(wǎng)的活性容易驗(yàn)證.弱活的判定可借助于非前阻塞Siphon來完成.

據(jù)作者所知，當(dāng)前文獻(xiàn)中提出的Petri網(wǎng)活性判定方法有：不變量控制、Trap控制、最大最小可控Siphon等.在這些常用方法失效后，本文提出的方法仍然適用，有興趣的讀者嘗試文中的例3.因此，理論上，本文提供了另外一條途徑處理Petri網(wǎng)活性問題.

本文還有一些未完成的工作.在判定非前阻塞的時(shí)候，限定了子網(wǎng)是無匯合.對(duì)于有匯合的子網(wǎng)還未能給出判定方法.理論上，我們只要求滿足條件的增廣網(wǎng)存在即可，但基于原網(wǎng)構(gòu)造增廣網(wǎng)方法也具有技巧性.這些成為我們下一步的工作.