基于Petri網(wǎng)的離散事件系統(tǒng)初始資源優(yōu)化配置

郝真鳴,孫丹丹，郝晉淵,陳凡，葛衛(wèi)華,李兵兵,冉寧

(1.河北大學(xué) 電子信息工程學(xué)院，河北 保定 071002；2.河北大學(xué) 中央蘭開夏傳媒與創(chuàng)意學(xué)院，河北 保定 071002)

離散事件系統(tǒng)(discrete event system，DES)是由不規(guī)則時(shí)間間隔出現(xiàn)的事件(離散事件)序列驅(qū)動，并按照一定的運(yùn)行規(guī)則相互作用導(dǎo)致狀態(tài)演化的一種動態(tài)系統(tǒng)[1].大部分人造系統(tǒng)從邏輯層面都可抽象為DES，例如柔性制造系統(tǒng)、通信網(wǎng)絡(luò)系統(tǒng)、交通控制系統(tǒng)等.DES初始資源優(yōu)化配置問題是指使用最少資源成本完成系統(tǒng)生產(chǎn)要求，對于降低生產(chǎn)成本、提高經(jīng)濟(jì)效益具有重要意義[2].因此，DES資源優(yōu)化配置成為近年來的研究熱門問題.

Petri網(wǎng)自20世紀(jì)60年代被提出以來，由于具有強(qiáng)大的建模分析能力以及圖形和數(shù)學(xué)雙重表示、高效分析離散事件系統(tǒng)等優(yōu)點(diǎn)[3]，而被應(yīng)用于故障診斷[4-8]、監(jiān)控器綜合[9-12]、資源優(yōu)化配置的研究.曹蕊等[13]利用Petri網(wǎng)提出了基于業(yè)務(wù)流程模型抽象的流程配置優(yōu)化，對抽象模型添加配置信息，實(shí)現(xiàn)了配置優(yōu)化分析.楊欣等[14]以資源配置混雜Petri網(wǎng)為研究模型，提出了一種適用于混雜系統(tǒng)動態(tài)生產(chǎn)調(diào)度的模型以及優(yōu)化方法，增強(qiáng)了混雜生產(chǎn)過程應(yīng)對突發(fā)事件的能力.廖敏等[15]基于工作流活動，利用在傳統(tǒng)Petri網(wǎng)的基礎(chǔ)上的擴(kuò)展Petri網(wǎng)建立了工作流模型，對制造資源的調(diào)度過程進(jìn)行了仿真，提高了資源的共享效率以及企業(yè)協(xié)作性.宋海翔等[16]基于傳統(tǒng)Petri網(wǎng)改進(jìn)定義了一種帶有資源約束的Petri網(wǎng)，對業(yè)務(wù)流程進(jìn)行了建模和優(yōu)化，對資源配置進(jìn)行了優(yōu)化.Li等[17]提出了一種在已知標(biāo)識Petri網(wǎng)中估計(jì)最小初始標(biāo)識的遞歸算法，并進(jìn)一步討論了具有低復(fù)雜度的啟發(fā)式算法，該算法能有效確定初始化時(shí)執(zhí)行指定任務(wù)所需的最小資源.

經(jīng)過上述分析可發(fā)現(xiàn)，雖然Petri網(wǎng)適合于DES資源優(yōu)化配置問題，但是幾乎所有基于Petri網(wǎng)的方法都需要計(jì)算系統(tǒng)狀態(tài)空間，導(dǎo)致復(fù)雜度較高，難以滿足實(shí)際要求.為了避免計(jì)算系統(tǒng)的狀態(tài)空間，本文基于Petri網(wǎng)提出一種將DES初始資源優(yōu)化配置問題轉(zhuǎn)化為整數(shù)線性規(guī)劃(integer linear programming,ILP)問題[18]的方法.首先，基于Petri網(wǎng)對DES建立數(shù)學(xué)模型，并利用Petri網(wǎng)的結(jié)構(gòu)特性和狀態(tài)方程將初始資源優(yōu)化配置問題轉(zhuǎn)化為ILP問題；其次，利用Lingo求解ILP問題；最后，通過實(shí)例驗(yàn)證提出方法的有效性.實(shí)驗(yàn)結(jié)果表明，提出的算法簡單高效，具有較強(qiáng)的實(shí)用性.

1 Petri網(wǎng)基礎(chǔ)

1.1 基本概念

Petri網(wǎng)的結(jié)構(gòu)表示為N=(P,T,F,W)，其中P={p1,p2,…,pn}表示庫所集合；S={t1,t2,…,tm}表示變遷集合；F?(P×T)∪(T×P)表示流關(guān)系，即庫所與變遷之間的連接關(guān)系；W為權(quán)值函數(shù)，為每一條弧賦予1個正整數(shù)權(quán)值.

令x∈P∪S為一個Petri網(wǎng)的節(jié)點(diǎn).它的輸入集定義為·x={y∈P∪S|(y,x)∈F}；它的輸出集定義為x·={y∈P∪S|(x,y)∈F}.

一個Petri網(wǎng)N的關(guān)聯(lián)矩陣A是以|P|×|S|為序標(biāo)的整數(shù)矩陣,定義為

A(p,t)=W(t,p)-W(p,t)

,

(1)

其物理意義是變遷t發(fā)生后庫所p中托肯數(shù)的變化量.庫所p對應(yīng)的行向量稱為p的關(guān)聯(lián)向量，記作A(p,·)，變遷t對應(yīng)的列向量稱為t的關(guān)聯(lián)向量，記作A(·,t).

一個Petri網(wǎng)的標(biāo)識是一個向量M∶P→B，其中B表示自然數(shù)集合.庫所中的標(biāo)識稱為托肯(token)，M(p)表示庫所p中的托肯數(shù).(N,M0)稱為一個網(wǎng)系統(tǒng)，其中N是Petri網(wǎng)結(jié)構(gòu)，M0是初始標(biāo)識.

一個變遷t∈S在標(biāo)識M下是使能的(enabled)當(dāng)且僅當(dāng)

?p∈·t,M(p)≥W(p,t),

(2)

記M[t〉.M[σ〉表示變遷序列σ=t1t2…tk在標(biāo)識M下是使能的.在初始標(biāo)識M0下使能的所有變遷序列定義為L(N,M0)，即

L(N,M0)={σ∈S*|M0[σ〉}.

(3)

一個Petri網(wǎng)的節(jié)點(diǎn)序列x1x2…xn稱為一條路徑,如果xi+1∈xi·，其中xi∈P∪S,i∈{1,2,…,n-1}.如果從節(jié)點(diǎn)xi到節(jié)點(diǎn)xj之間存在一條路徑，則稱xj可由xi進(jìn)入.如果一條路徑的首節(jié)點(diǎn)就是尾節(jié)點(diǎn)，則該路徑稱為回路.無回路的Petri網(wǎng)稱為無環(huán)Petri網(wǎng).

1.2 狀態(tài)方程

在一個Petri網(wǎng)中，變遷t發(fā)生后，網(wǎng)系統(tǒng)躍遷到另一個狀態(tài),產(chǎn)生一個新標(biāo)識M′,使得?p∈P，M′(p)=M(p)+A(p,t),表示在標(biāo)識M下發(fā)生變遷t到達(dá)標(biāo)識M′,記為M[t〉M′.在Petri網(wǎng)N中從標(biāo)識M出發(fā)能夠到達(dá)的全部標(biāo)識的集合稱為(N,M)的可達(dá)標(biāo)識集，表示為R(N,M).

M′=M0+A·y，

(4)

滿足上述狀態(tài)方程的標(biāo)識集合稱為潛在的可達(dá)標(biāo)識集，記作PR(N,M0).然而，任何一個可達(dá)標(biāo)識都滿足狀態(tài)方程(4)，但滿足方程(4)的標(biāo)識并不一定是可達(dá)的，即R(N,M0)?PR(N,M0).因此狀態(tài)方程僅提供了一個標(biāo)識可由初始標(biāo)識到達(dá)的必要條件.

定理1[19]令N是一個無環(huán)Petri網(wǎng).

2)標(biāo)識M′從M0處可達(dá)當(dāng)且僅當(dāng)存在一個非負(fù)整數(shù)解y滿足狀態(tài)方程M′=M0+A·y，即R(N,M0)=PR(N,M0).

為了避免計(jì)算系統(tǒng)狀態(tài)空間，本文利用狀態(tài)方程法求解初始資源優(yōu)化配置問題，因此根據(jù)定理1做出如下假設(shè)：

假設(shè)1Petri網(wǎng)是無環(huán)的.

2 初始資源優(yōu)化配置算法

本文考慮的初始資源優(yōu)化配置問題可描述為問題1.

問題1給定一個Petri網(wǎng)模型，計(jì)算初始標(biāo)識M0滿足以下2個條件：

1) 變遷ti發(fā)生ki次，其中ki≥0，i=1,2,…，|S|.

例1一個Petri網(wǎng)模型如圖1所示，其中庫所集P={p1,p2,p3,p4}，變遷集S={t1,t2,t3}.

圖1 Petri網(wǎng)模型Fig.1 Model of Petri net

其關(guān)聯(lián)矩陣為

現(xiàn)根據(jù)問題1考慮圖1所示Petri網(wǎng)的初始資源優(yōu)化配置問題.計(jì)算初始標(biāo)識M0滿足以下2個條件：

1)t1、t2各發(fā)生1次，t3無發(fā)生次數(shù)限制.

令xi為庫所pi中的托肯數(shù)，即M0=(x1,x2,x3,x4)T；無發(fā)生次數(shù)限制變遷t3的發(fā)生次數(shù)表示為z3，即y=(1,1,z3)T.根據(jù)條件1)以及Petri網(wǎng)的固有屬性，上述問題包含如下4個約束條件：

2)對于任意p∈P，滿足M0(p)≥0.

(5)

(6)

綜上所述，問題1可由算法1求解.雖然求解ILP的復(fù)雜度在理論上是不確定的，但大量實(shí)驗(yàn)結(jié)果表明現(xiàn)有的Gurobi、Lingo等軟件在求解這類問題上具有良好的計(jì)算效率，本文利用Lingo求解ILP問題.命題1證明了算法1的正確性.

算法1

輸入：Petri網(wǎng)N、問題1.

輸出：初始資源優(yōu)化配置結(jié)果.

步驟1:判斷Petri網(wǎng)是否無環(huán)；若不是，退出算法；若是，執(zhí)行步驟2.

步驟2:令M0=(x1,x2，…,x|P|)T.

步驟3:寫出問題1的目標(biāo)函數(shù)：

步驟4:寫出問題1的約束條件集合：

步驟5:求解上述ILP問題，輸出計(jì)算結(jié)果.

命題1算法1所求的解是問題1的解.

3 實(shí)例分析

圖2 Petri網(wǎng)模型Fig.2 Model of Petri net

圖2為某自動制造系統(tǒng)的Petri網(wǎng)模型，其中庫所集P={p1,p2,p3,p4,p5,p6,p7,p8}，變遷集S={t1,t2,t3,t4,t5,t6,t7}.

其關(guān)聯(lián)矩陣

現(xiàn)根據(jù)問題1考慮該模型的初始資源優(yōu)化配置問題：計(jì)算初始標(biāo)識M0滿足以下2個條件：

1) 變遷t1、t2、t3各發(fā)生1次，t4、t5各發(fā)生2次，其余變遷無發(fā)生次數(shù)限制.

(7)

(8)

圖3 Lingo代碼Fig.3 Code of Lingo

圖4 Lingo計(jì)算結(jié)果Fig.4 Results of Lingo

4 結(jié)論

基于Petri網(wǎng)提出了一種DES初始資源優(yōu)化配置方法.根據(jù)Petri網(wǎng)的結(jié)構(gòu)化特性和狀態(tài)方程，將初始資源優(yōu)化配置問題轉(zhuǎn)化為ILP問題，并利用Lingo軟件求解.實(shí)驗(yàn)結(jié)果表明，提出的算法簡單高效,具有較強(qiáng)的實(shí)用性，可為現(xiàn)實(shí)中DES資源優(yōu)化配置提供理論借鑒.

本文只考慮了可觀事件存在的情況，然而DES中還可能存在不可觀事件.因此，在可觀事件與不可觀事件同時(shí)存在的情況下進(jìn)行資源配置則是未來的研究方向.