基于MIP算法的系統(tǒng)Petri網(wǎng)模型中的死鎖預(yù)防.pdf

1、自然世界及工程實(shí)際中的許多現(xiàn)象都可以歸結(jié)為離散事件動態(tài)系統(tǒng)(DEDS),這些系統(tǒng)無一例外的要求具有無阻塞性,及系統(tǒng)運(yùn)行無死鎖.科學(xué)界針對這一問題提出了許多先進(jìn)的控制理論及方法,其中Petri網(wǎng)由于具有離散性,并發(fā)性,隨機(jī)性,可以較好的描述此類系統(tǒng)而得到了廣泛應(yīng)用.傳統(tǒng)的基于Petri網(wǎng)的死鎖預(yù)防策略一般遵循控制系統(tǒng)Petri網(wǎng)模型中的所有嚴(yán)格極小信標(biāo)被清空從而達(dá)到控制整個系統(tǒng)使之無死鎖的這一基本思想.然而,由于系統(tǒng)Petri網(wǎng)模型中的信

2、標(biāo)的個數(shù)隨著網(wǎng)規(guī)模呈指數(shù)增長,基于這一思想的控制策略往往不可行.一種基于基本信標(biāo)的死鎖預(yù)防策略應(yīng)運(yùn)而生,該理論指出只要網(wǎng)系統(tǒng)的基本信標(biāo)得到控制,其他的嚴(yán)格極小信標(biāo)也隨之得到控制,而且與嚴(yán)格極小信標(biāo)不同的是,基本信標(biāo)的個數(shù)是強(qiáng)受限于網(wǎng)系統(tǒng)的規(guī)模的.本文在此研究的基礎(chǔ)上,論證了網(wǎng)系統(tǒng)中的基本信標(biāo)的不唯一性,控制不同的基本信標(biāo)可以得到不同的控制效果,進(jìn)而提出了最優(yōu)基本信標(biāo)的概念并給出了相應(yīng)的計算方法,應(yīng)用這一計算方法可以在多項(xiàng)式時間內(nèi)求得一組

3、最優(yōu)基本信標(biāo),也就是說,控制該組基本信標(biāo)相對于其他的基本信標(biāo)可以使得系統(tǒng)Petri網(wǎng)模型具有最多的可達(dá)狀態(tài),這在實(shí)際中,意味著系統(tǒng)具有更大的靈活性.但是上述理論雖然只需要控制基本信標(biāo)即可以控制整個系統(tǒng),但是由于從屬信標(biāo)滿足一定的可控性條件才能完全受控,這意味著在控制算法的生成過程中所有的信標(biāo)都要參與,從而大大增加了系統(tǒng)控制的復(fù)雜性.本文在基本信標(biāo)理論基礎(chǔ)上,提出了一種基于MIP算法的死鎖預(yù)防策略,該策略指出了一種思路,可以控制基本信標(biāo),