標(biāo)注Petri網(wǎng)的最小代價計劃序列估計

周廣瑞，徐淑琳，郭乙運(yùn)，魯法明，岳 昊+

1.青島大學(xué) 復(fù)雜性科學(xué)研究所，山東 青島 266071

2.山東省工業(yè)控制技術(shù)重點實驗室，山東 青島 266071

3.青島港國際股份有限公司，山東 青島 266011

4.山東科技大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，山東 青島 266590

離散事件系統(tǒng)是由事件序列驅(qū)動的一種動態(tài)系統(tǒng)，可以通過一組狀態(tài)和一些驅(qū)動狀態(tài)改變的事件來描述[1]。典型的離散事件系統(tǒng)有柔性制造系統(tǒng)、交通系統(tǒng)以及通信網(wǎng)絡(luò)系統(tǒng)等。Petri 網(wǎng)[2-3]是系統(tǒng)建模和分析的工具，能夠簡便地描述系統(tǒng)的演化過程。Petri 網(wǎng)作為一種形式化工具被用于解決許多有價值的問題，例如，柔性裝配系統(tǒng)的監(jiān)督控制[4-5]、死鎖控制[6-9]、業(yè)務(wù)流程管理[10-11]等。

文獻(xiàn)[12-13]研究了基于變遷觀測的Petri 網(wǎng)的標(biāo)識估計問題，將觀測信息來源于變遷發(fā)生的Petri 網(wǎng)稱為標(biāo)注Petri 網(wǎng)。在標(biāo)注Petri 網(wǎng)中估計最小初始標(biāo)識，可用于解決制造系統(tǒng)中已知制造流程求解最小資源消耗的最優(yōu)化問題。在制造系統(tǒng)中，規(guī)劃出以最小成本完成任務(wù)的制造流程，轉(zhuǎn)化為標(biāo)注Petri 網(wǎng)中的最小代價計劃序列的估計問題[14-16]。文獻(xiàn)[14]提出了一種用于計算最小代價變遷序列的動態(tài)規(guī)劃算法，并證明了標(biāo)識數(shù)目是關(guān)于標(biāo)注序列長度k的多項式函數(shù)，最小代價變遷序列即為所求的最小代價計劃序列。文獻(xiàn)[16]提出在標(biāo)注Petri 網(wǎng)中可通過構(gòu)建一種特殊可達(dá)圖的方法來尋找最小代價變遷發(fā)生序列。

在現(xiàn)有的文獻(xiàn)中，回溯法作為一種系統(tǒng)化的搜索方法常用于最優(yōu)解的求取問題，通過目標(biāo)函數(shù)和約束條件來避免無效搜索，剔除冗余節(jié)點，減少搜索的節(jié)點數(shù)目[17]。文獻(xiàn)[18]應(yīng)用回溯法求解帶時間窗和同時送取貨的車輛最優(yōu)路徑問題。文獻(xiàn)[19]解決無線傳感器網(wǎng)絡(luò)的確定性調(diào)度問題，基于回溯法能夠獲得近似最優(yōu)調(diào)度解，有效降低計算復(fù)雜度。文獻(xiàn)[20]應(yīng)用回溯法解決云計算中多任務(wù)執(zhí)行不協(xié)調(diào)的問題，節(jié)約了計算時間。文獻(xiàn)[21]應(yīng)用回溯法解決安全業(yè)務(wù)可行性的時間和空間失衡問題，付出的空間代價較小，且具有良好的時間性能。

在制造系統(tǒng)標(biāo)注Petri 網(wǎng)模型中估計最小代價計劃序列，有助于達(dá)到以最小成本完成生產(chǎn)任務(wù)的目的。本文應(yīng)用回溯法對標(biāo)注Petri 網(wǎng)的最小代價計劃序列進(jìn)行估計，達(dá)到減少計算量、提高工作效率的目標(biāo)。應(yīng)用本文方法，當(dāng)觀測到一個標(biāo)注時，優(yōu)先發(fā)生代價小的變遷，根據(jù)深度優(yōu)先搜索的策略能夠獲得一個當(dāng)前最小代價變遷序列。以其作為約束條件，在搜索其他路徑時，能夠避免一些不滿足約束條件的變遷發(fā)生，并剔除搜索路徑中的剩余標(biāo)識，最終通過遍歷解空間樹獲得系統(tǒng)的最小代價變遷序列?；诨厮莘ㄇ蠼鈽?biāo)注Petri 網(wǎng)的最小代價計劃序列估計問題，能夠剔除冗余標(biāo)識，進(jìn)而刪除多余搜索標(biāo)識路徑。現(xiàn)有文獻(xiàn)中的動態(tài)規(guī)劃法僅能夠合并相同標(biāo)識，不能剔除標(biāo)識，因此回溯法的計算量更小。針對同一實例分別采用回溯法與動態(tài)規(guī)劃法進(jìn)行運(yùn)算，由實驗運(yùn)行結(jié)果可知，本文方法具有更高的工作效率。

1 基本概念

N=(P,T;A,W) 為一個Petri 網(wǎng)，其中P={p1,p2,…,pn} 是有限庫所集，T={t1,t2,…,tm} 是有限變遷集，A?(P×T)?(T×P)是流關(guān)系集合，W:A→{1,2,…}是弧上的權(quán)重函數(shù)。在Petri 網(wǎng)模型示意圖中，空心圓圈代表庫所，庫所中的托肯用實心圓點表示，黑色實線代表變遷，有向箭頭代表流關(guān)系。

以圖1 所示的標(biāo)注Petri 網(wǎng)模型為例，庫所集P={p1,p2,…,p9}；變遷集T={t1,t2,…,t7}；標(biāo)注集Σ={a,b,c,d,e}；標(biāo)注函數(shù)為L(t1)=a，L(t2)=L(t3)=b，L(t4)=L(t5)=c，L(t6)=d，L(t7)=e；變遷代價為C(t1)=C(t2)=C(t5)=C(t6)=C(t7)=1，C(t3)=2，C(t4)=3。p1與p9中的托肯分別表示待加工原材料和成品，p2～p8中的托肯表示半成品，變遷t1與t7分別表示拆卸和組裝。變遷t2～t8表示半成品的加工，其中一個加工過程表示為p2t2p4t4p6t6p8。

Fig.1 A labeled Petri net model圖1 一個標(biāo)注Petri網(wǎng)模型

給定一個長度為2 的標(biāo)注序列ω=a b，根據(jù)ω可獲得變遷發(fā)生序列σ1=t1t2和σ2=t1t3，代價分別為C(σ1)=2 和C(σ2)=3。由C(σ1)

由圖1 中的Petri 網(wǎng)實例可知，標(biāo)注序列ω=a b對應(yīng)的最小代價變遷發(fā)生序列為σ1=t1t2，標(biāo)注序列ω=a b c對應(yīng)的最小代價變遷發(fā)生序列為σ2=t1t3t5，即標(biāo)注序列ω=a b c前兩個標(biāo)注對應(yīng)的最小代價變遷發(fā)生序列將被替代。當(dāng)標(biāo)注序列發(fā)生改變時，其對應(yīng)的最小代價變遷發(fā)生序列也可能發(fā)生改變，因此需要計算每條搜索路徑中變遷發(fā)生序列的總代價。

2 基于回溯法求取最小代價變遷序列

2.1 解空間樹的構(gòu)建

復(fù)雜問題通常有較多的可行解，它們構(gòu)成了問題的解空間。若沒有確定正確的解空間就開始搜索，可能會產(chǎn)生較多滿足約束條件的重復(fù)可行解或者錯誤解。解空間用如圖2 所示的解空間樹來表示。根節(jié)點作為初始狀態(tài)位于解空間樹的第一層，根據(jù)不同的約束條件對根節(jié)點做出選擇后得到的葉子節(jié)點位于第二層。以此類推，解空間樹的一個可行解為從樹的根節(jié)點到葉子節(jié)點的路徑[17]。

Fig.2 Model of solution-space tree圖2 解空間樹模型

2.2 最小代價變遷序列的獲取

基于回溯法估計標(biāo)注Petri 網(wǎng)的最小代價計劃序列，剔除其他路徑中不滿足約束條件的標(biāo)識，而非直接剪掉一條路徑。設(shè)lc是當(dāng)前最小總代價，當(dāng)搜索到一個標(biāo)識M后，滿足，存在以下兩種情況：

（1）若C(σ)≤lc，則該標(biāo)識是構(gòu)成搜索路徑的部分解，且繼續(xù)搜索下一個標(biāo)識。

（2）若C(σ)>lc，則該標(biāo)識不是構(gòu)成搜索路徑的部分解，結(jié)束該路徑的搜索。

在圖3 所示的標(biāo)識路徑搜索空間示意圖中，給定標(biāo)注序列ω=l1l2…lk，假設(shè)成立，且C(t1)lc，則回溯至祖先標(biāo)識并搜索其他路徑，反之繼續(xù)搜索該路徑。由于同一個標(biāo)識可能出現(xiàn)在多條搜索路徑上，為了清楚地顯示每條路徑的情況，因此不合并搜索路徑中的相同標(biāo)識。

Fig.3 Schematic diagram of evolution of marking paths圖3 標(biāo)識路徑演化示意圖

2.3 算法

給定一個長度為k的標(biāo)注序列ω=l1l2…lk(lj∈Σ,j=1,2,…,k)，觀測到標(biāo)注lj，j∈{1,2,…,k}，集合Vj包含所有與標(biāo)注lj相關(guān)的節(jié)點v。四元組節(jié)點v=(level,marking,sequence,cost)，其中l(wèi)evel為節(jié)點層次的序號；marking為節(jié)點相關(guān)標(biāo)識；sequence為對應(yīng)的變遷發(fā)生序列；cost為變遷序列的代價。若后繼需考慮節(jié)點v，則flag(v)=0；反之flag(v)=1。

算法1計算最小代價變遷序列

輸入：一個標(biāo)注Petri 網(wǎng)Nl=(N,M0,Σ,L)，一個長度為k的標(biāo)注序列ω=l1l2…lk(lj∈Σ,j=1,2,…,k)。

輸出：包含所有最小代價變遷序列的集合S和最小代價lc。

觀測到標(biāo)注lj，j∈{1,2,…,k}，若標(biāo)注lj對應(yīng)多個變遷，則選擇代價較小的變遷優(yōu)先發(fā)生。創(chuàng)建一個節(jié)點v之后，當(dāng)v.cost≤lc時，若集合Vj中不存在節(jié)點v1，使得v1.marking=v.marking，則flag(v)=0，節(jié)點v進(jìn)棧S，更新集合Vj=Vj∪{v}；若集合Vj中存在節(jié)點v1，使得v1.marking=v.marking，則需考慮以下三種情況：

（1）若v.cost

（2）若v.cost>v1.cost，則flag(v)=1，節(jié)點v不進(jìn)棧S；

（3）若v.cost>v1.cost，則flag(v)=0，節(jié)點v進(jìn)棧S，更新集合Vj=Vj∪{v}。

當(dāng)j=k時，若v.cost

算法1 首先通過棧S獲得節(jié)點?，根據(jù)棧的性質(zhì)，可以直接得到代價較小的變遷，避免發(fā)生代價較大的變遷。其次，通過比較發(fā)生節(jié)點變遷代價的大小，能夠確保該節(jié)點通過最小代價變遷發(fā)生獲得。最后，能夠避免在搜索路徑中出現(xiàn)大于當(dāng)前最小總代價的變遷序列，從而使得算法1 能夠避免無效搜索，減少搜索的節(jié)點數(shù)目。

3 應(yīng)用實例與結(jié)果分析

3.1 應(yīng)用實例

以圖4 所示文獻(xiàn)[14]中的一個包含兩臺并聯(lián)機(jī)器的制造系統(tǒng)標(biāo)注Petri 網(wǎng)模型為例，標(biāo)注集Σ={a,b,c,d,e,f,g,h} ；庫所集P={p1,p2,…,p10} ；變遷集T={t1,t2,…,t12} ；初始標(biāo)識為M0=[1 1 0 2 0 0 2 0 0 0]T；標(biāo)注函數(shù)為L(t3)=L(t5)=a，L(t4)=L(t6)=b，L(t7)=L(t9)=c，L(t8)=L(t10)=d，L(t1)=e，L(t2)=f，L(t11)=g，L(t12)=h；變遷代價為C(t1)=C(t2)=C(t4)=C(t5)=C(t9)=5，C(t3)=C(t7)=C(t8)=C(t10)=10，C(t6)=C(t11)=C(t12)=15。

Fig.4 Labeled Petri net model for manufacturing system圖4 一個制造系統(tǒng)的標(biāo)注Petri網(wǎng)模型

給定長度為10 的標(biāo)注序列ω=e e f f a a b c c d，根據(jù)這個序列，可得圖5 所示的Petri網(wǎng)模型的標(biāo)識解空間示意圖。應(yīng)用算法1，基于回溯法求取最小代價計劃序列的標(biāo)識路徑搜索空間如圖6 所示。表1 總結(jié)了每條標(biāo)識路徑中變遷發(fā)生的信息，每條路徑的標(biāo)識序列和標(biāo)識剔除情況如表2 所示。在圖6 所示的標(biāo)識路徑搜索空間中，路徑①的標(biāo)識集合Z(ω)={M1,M2,M3,M4,M51,M61,M71,M81,M91,M10}，最小代價為lc=55。圖5 所示的標(biāo)識解空間中存在多條路徑，回溯至祖先標(biāo)識M51并搜索路徑②。路徑②的標(biāo)識集合為Z(ω)={M1,M2,M3,M4,M51,M62,M72,M82,M91,M10}，當(dāng)變遷發(fā)生序列為σ2=t1t1t2t2t5t3t4t9t7時，C(σ2)=55，若繼續(xù)發(fā)生變遷t8，則C(σ2)=65，由于C(σ2)>lc，標(biāo)注d對應(yīng)的變遷t8不應(yīng)發(fā)生，此時剔除標(biāo)識M10。以同樣的方式搜索剩余路徑，獲得最小代價變遷序列集合S={t1t1t2t2t5t5t4t9t9t8}，最小代價為lc=55。

Table 1 Information about firing of transitions in marking paths表1 標(biāo)識路徑上的變遷發(fā)生信息

Fig.5 Marking solution space established according to labeled sequence ω=eeffa a b ccd圖5 根據(jù)標(biāo)注序列ω=eeffa a b ccd 構(gòu)建的標(biāo)識解空間

Table 2 Marking sequences and the number of eliminated markings表2 標(biāo)識序列與標(biāo)識剔除數(shù)目

3.2 結(jié)果分析

在上述包含兩臺并聯(lián)機(jī)器的制造系統(tǒng)標(biāo)注Petri網(wǎng)模型中，基于回溯法與動態(tài)規(guī)劃法構(gòu)建的標(biāo)識解空間規(guī)模相同，因此僅給出基于回溯法構(gòu)建的標(biāo)識解空間。在標(biāo)識路徑搜索空間中不合并相同的標(biāo)識，由表2 可知，應(yīng)用回溯法搜索的標(biāo)識數(shù)目比應(yīng)用動態(tài)規(guī)劃法搜索的標(biāo)識數(shù)目減少約17%。對于給定的標(biāo)注序列ω=e e f f a a b c c d，當(dāng)觀測到的標(biāo)注序列長度小于等于4 時，標(biāo)注e和f僅對應(yīng)一個變遷，即只存在一條搜索路徑，因此應(yīng)用回溯法與動態(tài)規(guī)劃法搜索的標(biāo)識數(shù)目相同；當(dāng)標(biāo)注序列長度大于4時，可以剔除路徑中不滿足約束條件的標(biāo)識，合并相同的標(biāo)識后，回溯法比動態(tài)規(guī)劃法減少搜索的標(biāo)識數(shù)目由表3 給出。根據(jù)兩種方法處理該實例的結(jié)果可知，基于回溯法估計標(biāo)注Petri 網(wǎng)的最小代價計劃序列可以減少計算量。

本文提出一種方法，基于回溯法估計標(biāo)注Petri網(wǎng)的最小代價計劃序列。雖然沒有從理論上降低蠻力窮舉方法與文獻(xiàn)[14]所提方法的計算復(fù)雜度，但是本文方法在搜索標(biāo)識的過程中，通過深度優(yōu)先策略可以避免不滿足約束條件的變遷發(fā)生，從而減少了搜索的標(biāo)識數(shù)目，提高了工作效率。

Fig.6 Searching-space of marking paths圖6 標(biāo)識路徑搜索空間

Table 3 Comparative analysis of number of markings表3 標(biāo)識數(shù)目對比分析

4 結(jié)束語

本文研究制造系統(tǒng)標(biāo)注Petri 網(wǎng)模型的最小代價計劃序列估計問題，提出了一種基于回溯法求取最小代價變遷序列的算法。根據(jù)深度優(yōu)先搜索策略可以獲得標(biāo)注Petri 網(wǎng)的一個當(dāng)前最小代價變遷序列，以該序列的代價作為其他路徑搜索部分解的約束條件，滿足約束條件的一條完整路徑即對應(yīng)問題的一個解。實例結(jié)果表明，本文算法能夠剔除冗余標(biāo)識，縮小搜索空間規(guī)模，提高工作效率。后續(xù)工作將結(jié)合本文方法，在含有不可觀測變遷的標(biāo)注Petri 網(wǎng)中估計最小代價計劃序列。