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

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

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

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

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

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

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