基于信標(biāo)迭代控制的Petri網(wǎng)死鎖預(yù)防策略.pdf

1、在對(duì)離散事件動(dòng)態(tài)系統(tǒng)(discrete event dynamic system，DEDS)的建模、分析、性能評(píng)價(jià)及其控制設(shè)計(jì)中，Petri網(wǎng)作為一種數(shù)學(xué)的方法，得到了廣泛的應(yīng)用。柔性制造系統(tǒng)(flexible manufacturing system，F(xiàn)Ms)作為一類典型的離散事件動(dòng)態(tài)系統(tǒng)，一直是Petri網(wǎng)研究的重要對(duì)象和應(yīng)用領(lǐng)域。由于競(jìng)爭(zhēng)FMS中的有限共享資源(如機(jī)器人、機(jī)床、夾具、緩沖存貯器和傳送帶等)，死鎖(deadlock)

2、經(jīng)常發(fā)生，導(dǎo)致部分或整個(gè)系統(tǒng)的運(yùn)行停頓，直接降低了FMS的生產(chǎn)效率，甚至可能造成災(zāi)難性的后果和重大的經(jīng)濟(jì)損失。人們基于Petri網(wǎng)已經(jīng)研究了許多方法來解決死鎖問題，主要有死鎖的檢測(cè)與恢復(fù)方法、死鎖避免方法和死鎖預(yù)防方法。其中，死鎖預(yù)防方法是將死鎖問題解決在系統(tǒng)的設(shè)計(jì)階段而非運(yùn)行階段，無需在線決策，因此在實(shí)際應(yīng)用中得到了廣泛關(guān)注。
　　 由于建模Petri網(wǎng)中的死鎖問題與Petri網(wǎng)中的一種特殊結(jié)構(gòu)-信標(biāo)(siphon)具有強(qiáng)相關(guān)

3、性，即，信標(biāo)一旦在某個(gè)標(biāo)識(shí)下被清空，則永久地在這個(gè)標(biāo)識(shí)的所有后繼標(biāo)識(shí)下保持清空狀態(tài)，阻止了相關(guān)變遷的發(fā)射，從而導(dǎo)致死鎖的發(fā)生。因此，通過對(duì)信標(biāo)的控制就能夠消除死鎖，實(shí)現(xiàn)死鎖預(yù)防的目的。對(duì)于普通Petri網(wǎng)(ordinary Petri net，OPN)中被清空的信標(biāo)，基于P-不變式的性質(zhì)，添加控制庫所(control place，CP)使其可控：對(duì)于一般Petri網(wǎng)(generalized Petri net，GPN)中導(dǎo)致死鎖的信標(biāo)，

4、依據(jù)最大受控信標(biāo)的概念，添加控制庫所使其滿足最大可控性。所以，對(duì)存在死鎖的Petri網(wǎng)，添加控制庫所的方法能夠確保引起死鎖的信標(biāo)可控，使得受控的Petri網(wǎng)系統(tǒng)滿足活性的需求。如何求取導(dǎo)致死鎖的信標(biāo)和添加控制庫所是獲取活性Petri網(wǎng)控制器的重要步驟，也是設(shè)計(jì)死鎖預(yù)防控制策略的關(guān)鍵。衡量一個(gè)活性Petri網(wǎng)控制器性能的標(biāo)準(zhǔn)是計(jì)算復(fù)雜性、結(jié)構(gòu)復(fù)雜性和行為許可性。針對(duì)基于Petri網(wǎng)建模的FMS中的死鎖問題，本文的目標(biāo)是設(shè)計(jì)有效的死鎖預(yù)防策

5、略。通過部分枚舉計(jì)算法求解出引起死鎖的信標(biāo)，根據(jù)其補(bǔ)集。添加合適的控制庫所使得求解出的信標(biāo)可控，獲取活性Petri網(wǎng)控制器。并且進(jìn)一步化簡(jiǎn)活的受控Petri網(wǎng)系統(tǒng)的結(jié)構(gòu)，降低控制實(shí)現(xiàn)的難度和經(jīng)濟(jì)成本。本文的主要研究成果如下：
　　 1.應(yīng)用文獻(xiàn)[9]中的混合整數(shù)規(guī)劃(mixed integer programming，MIP)方法，針對(duì)一個(gè)普通Petri網(wǎng)的子類S3PR(system of simple sequential p

6、rocess with resource)網(wǎng)的信標(biāo)求解問題，提出了其基本信標(biāo)(elementary siphon，ES)集合的迭代式求解算法。在迭代求解的過程中，每個(gè)MIP問題的可行解對(duì)應(yīng)著一個(gè)最大的空信標(biāo)。通過信標(biāo)的提取和最小化信標(biāo)中資源庫所的數(shù)目，得到相應(yīng)的基本信標(biāo)。進(jìn)而添加該基本信標(biāo)補(bǔ)集的標(biāo)識(shí)約束，使得迭代求解依次進(jìn)行，直至網(wǎng)系統(tǒng)中無最大的空信標(biāo)存在，得到了一個(gè)基本信標(biāo)的集合。它避免了完全枚舉所有的嚴(yán)格極小信標(biāo)，從中計(jì)算出基本信標(biāo)

7、集合的作法，提高了計(jì)算效率。
　　 2.針對(duì)普通Petri網(wǎng)和一般Petri網(wǎng)的一個(gè)子類S4R(systems of sequential systemswith shared resources)網(wǎng)的死鎖問題，提出了庫所分類(place classification)和必需信標(biāo)(necessary siphon，NS)的概念以及相應(yīng)的死鎖預(yù)防策略。在死鎖控制的迭代過程中，應(yīng)用MIP方法求解出最大的死標(biāo)識(shí)信標(biāo)[24]。通過庫所分

8、類，得到了相應(yīng)的必需信標(biāo)。根據(jù)必需信標(biāo)的補(bǔ)集，引入兩類(普通和一般)控制庫所，予以恰當(dāng)?shù)靥砑?，使得迭代過程依次進(jìn)行。當(dāng)MIP問題的最優(yōu)解出現(xiàn)時(shí)，表明受控網(wǎng)系統(tǒng)中無最大的死標(biāo)識(shí)信標(biāo)存在。獲取了活性受控Petri網(wǎng)系統(tǒng)。它部分枚舉那些導(dǎo)致死鎖的必需信標(biāo)，進(jìn)而予以控制，能夠一定程度地化簡(jiǎn)活性受控Petri網(wǎng)系統(tǒng)的結(jié)構(gòu)。實(shí)現(xiàn)了消除死鎖的目的。
　　 3.通過修改文獻(xiàn)[24]中MIP方法的目標(biāo)函數(shù)并且添加新的約束條件，得到了改進(jìn)的MIP方

9、法(revised MIP，RMIP)。應(yīng)用RMIP方法能夠求解出靈巧信標(biāo)(smart siphon)，即，包含著資源庫所數(shù)目和總的庫所數(shù)目均最少的信標(biāo)。相比以往的部分枚舉求解信標(biāo)的做法，即，先求解出最大的空(或死標(biāo)識(shí))信標(biāo)，進(jìn)而提取出相應(yīng)的最小信標(biāo)。RMIP方法減少了信標(biāo)求解的步驟。并且提出了基于靈巧信標(biāo)控制的死鎖預(yù)防策略，得到了結(jié)構(gòu)相對(duì)簡(jiǎn)化和較多許可行為的活性受控Petri網(wǎng)系統(tǒng)。
　　 4.由于在滿足受控的Petri網(wǎng)系統(tǒng)

10、活性的前提下，目前許多采用添加控制庫所的死鎖預(yù)防策略往往導(dǎo)致了冗余控制庫所的存在。針對(duì)此問題，提出了一種迭代式的鑒別和刪除活性受控Petri網(wǎng)系統(tǒng)(N*，M*)中冗余控制庫所的算法。在鑒別和刪除冗余控制庫所的迭代進(jìn)程中，依次選取每個(gè)控制庫所，并將它和相關(guān)連接弧從(N*，M*)移除。若移除某個(gè)控制庫所后，MIP的最優(yōu)解[24]等于剩余的所有庫所的數(shù)目，則表明該控制庫所是冗余的，可以將其從(N*，M*)中刪除且并不改變化簡(jiǎn)網(wǎng)的活性。否則，表