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

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

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

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

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

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

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