Petri網(wǎng)基本信標(biāo)的求取算法及死鎖避免策略研究.pdf

1、在諸如柔性制造系統(tǒng)、半導(dǎo)體生產(chǎn)線等這樣的典型離散事件系統(tǒng)中，由于資源的分配不合理會導(dǎo)致死鎖的產(chǎn)生.死鎖不僅會導(dǎo)致生產(chǎn)率的下降，而且可能會造成災(zāi)難性的后果.Petri網(wǎng)是對離散事件系統(tǒng)進(jìn)行建模和分析的主要數(shù)學(xué)工具之一.死鎖預(yù)防和死鎖避免是近二十年來死鎖控制方法中的兩個主要研究方向.死鎖預(yù)防是一種離線的資源分配機(jī)制，而死鎖避免是一種在線決策算法.傳統(tǒng)的死鎖預(yù)防方法對系統(tǒng)Petri網(wǎng)模型中的每個可被清空的極小信標(biāo)添加一個控制庫所和多條控制弧，

2、從而達(dá)到死鎖控制的目的.由于信標(biāo)是Petri網(wǎng)的一個結(jié)構(gòu)特性，在理論上，信標(biāo)的數(shù)量與Petri網(wǎng)的規(guī)模呈指數(shù)關(guān)系，所以規(guī)模較大Petri網(wǎng)的控制器結(jié)構(gòu)過于復(fù)雜.基本信標(biāo)理論已從理論上證明可以得到與Petri網(wǎng)規(guī)模呈線性關(guān)系的受控Petri網(wǎng)模型，但在確定一組基本信標(biāo)時同樣受到枚舉Petri網(wǎng)中所有信標(biāo)問題的困擾.傳統(tǒng)的死鎖避免策略采用在線計算的方式，保證系統(tǒng)不要演化到死鎖狀態(tài)，從而達(dá)到死鎖控制的目的，但是這種方法受到狀態(tài)組合爆炸問題的嚴(yán)

3、重制約.通常情況下，網(wǎng)的整個可達(dá)標(biāo)識需要事先知道且存儲到內(nèi)存中。 本論文針對以上兩種死鎖控制策略中的瓶頸問題展開研究，取得的主要研究結(jié)論如下。 第一，通過對Petri網(wǎng)的子類S3PR網(wǎng)的結(jié)構(gòu)分析，得出該類Petri網(wǎng)的補(bǔ)集矩陣的秩等于基本信標(biāo)數(shù)目的結(jié)論.結(jié)合Petri網(wǎng)理論和圖論，分別給出了LS3PR和S3PR網(wǎng)的資源有向圖的概念，分別證明了在資源有向圖和有效資源有向圖中的強(qiáng)連通塊對應(yīng)LS3PR和S3PR網(wǎng)中的一個嚴(yán)格極

4、小信標(biāo)的結(jié)論.對于LS3PR網(wǎng)給出了一種確定基本信標(biāo)數(shù)目的算法，并且證明該算法的計算時間復(fù)雜度為LS3PR網(wǎng)中資源庫所數(shù)目的多項式時間復(fù)雜度.基于以上結(jié)論，提出了一種確定S3PR網(wǎng)中基本信標(biāo)數(shù)目的算法，并且證明最壞情況下該算法的計算時間復(fù)雜度為S3PR網(wǎng)中資源庫所數(shù)目的指數(shù)時間復(fù)雜度.值得慶幸的是，在特殊情況下，該算法依然是S3PR網(wǎng)中資源庫所數(shù)目的一個多項式算法， 第二，在已知Petri網(wǎng)中部分或全部嚴(yán)格極小信標(biāo)的條件下，提出

5、了一種基于二分法原理確定一組基本信標(biāo)的快速算法。 第三，通過對ES3PR子類的結(jié)構(gòu)分析，提出擴(kuò)展補(bǔ)集和擴(kuò)展補(bǔ)集矩陣的概念，同時證明了擴(kuò)展補(bǔ)集矩陣的秩等于基本信標(biāo)數(shù)目的結(jié)論.在這些概念的基礎(chǔ)上，給出了ELS3PR網(wǎng)資源有向圖的概念，證明了ELS3PR網(wǎng)資源有向圖中的一個強(qiáng)連通塊對應(yīng)網(wǎng)中的一個信標(biāo)的結(jié)論，進(jìn)而給出了基于資源有向圖的求取ELS3PR網(wǎng)中所有嚴(yán)格極小信標(biāo)的算法。 第四，給出了一種分兩步走的死鎖避免策略，該策略中首

6、先離線計算出網(wǎng)系統(tǒng)中的特殊標(biāo)識，包括死標(biāo)識、壞標(biāo)識和危險標(biāo)識，然后在線控制時，僅保證系統(tǒng)不要到達(dá)禁止標(biāo)識，包括死標(biāo)識和壞標(biāo)識.相對于現(xiàn)有的大多數(shù)死鎖避免策略而言，本文給出的策略適于控制大的系統(tǒng)，控制器的許可行為最大，而且成功避免了對系統(tǒng)的Petri網(wǎng)模型的整個可達(dá)圖的計算。 基本信標(biāo)理論在簡化活性Petri控制器結(jié)構(gòu)方面的作用正在日益深入地得到了解和認(rèn)識.本文的研究工作對于Petri網(wǎng)理論以及以Petri網(wǎng)為分析工具的離散事件監(jiān)