一類Petri網(wǎng)中基本信標(biāo)的快速求解算法.pdf

1、柔性制造系統(tǒng)作為一種典型的離散事件系統(tǒng)是Petri網(wǎng)的一個重要應(yīng)用領(lǐng)域。在柔性制造系統(tǒng)中，由于資源的競爭出現(xiàn)死鎖現(xiàn)象。死鎖預(yù)防是基于信標(biāo)的一種死鎖控制方法。系統(tǒng)中被清空的信標(biāo)導(dǎo)致死鎖發(fā)生。理論證明，只要控制住一個系統(tǒng)的基本信標(biāo)，則整個系統(tǒng)不會發(fā)生死鎖。基本信標(biāo)是一類特殊的嚴(yán)格極小信標(biāo)，它的個數(shù)比嚴(yán)格極小信標(biāo)的個數(shù)少得多，并且不會超過網(wǎng)系統(tǒng)的規(guī)模。 現(xiàn)有的方法中，基本信標(biāo)是以已知所有的嚴(yán)格極小信標(biāo)為前提的。但是，一個Petri網(wǎng)中

2、的信標(biāo)的個數(shù)是隨著網(wǎng)的規(guī)模呈指數(shù)增長的。針對一個Petri網(wǎng)子類-S<'3>PR網(wǎng)，本文提出了一種從部分嚴(yán)格極小信標(biāo)中求取基本信標(biāo)的算法。根據(jù)S<'3>PR網(wǎng)的結(jié)構(gòu)特點，一個S<'3>PR網(wǎng)中的資源回路對應(yīng)一個信標(biāo)，在資源回路中不含分支弧的情況下，對應(yīng)一個嚴(yán)格極小信標(biāo)。我們將S3pR網(wǎng)抽象到一個有向資源圖中。本工作中提出了補(bǔ)集矩陣的概念，并且理論證明，基本信標(biāo)是補(bǔ)集矩陣對應(yīng)的信標(biāo)空間的一個基。從一個資源回路中，也可以求出對應(yīng)的嚴(yán)格極小信