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

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

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

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

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

1 Petri網(wǎng)基礎

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)表示流關系，即庫所與變遷之間的連接關系；W為權值函數(shù)，為每一條弧賦予1個正整數(shù)權值.

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

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

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

,

(1)

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

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

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

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

(2)

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

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

(3)

一個Petri網(wǎng)的節(jié)點序列x1x2…xn稱為一條路徑,如果xi+1∈xi·，其中xi∈P∪S,i∈{1,2,…,n-1}.如果從節(jié)點xi到節(jié)點xj之間存在一條路徑，則稱xj可由xi進入.如果一條路徑的首節(jié)點就是尾節(jié)點，則該路徑稱為回路.無回路的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)生一個新標識M′,使得?p∈P，M′(p)=M(p)+A(p,t),表示在標識M下發(fā)生變遷t到達標識M′,記為M[t〉M′.在Petri網(wǎng)N中從標識M出發(fā)能夠到達的全部標識的集合稱為(N,M)的可達標識集，表示為R(N,M).

M′=M0+A·y，

(4)

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

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

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

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

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

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

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

問題1給定一個Petri網(wǎng)模型，計算初始標識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

其關聯(lián)矩陣為

現(xiàn)根據(jù)問題1考慮圖1所示Petri網(wǎng)的初始資源優(yōu)化配置問題.計算初始標識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的復雜度在理論上是不確定的，但大量實驗結(jié)果表明現(xiàn)有的Gurobi、Lingo等軟件在求解這類問題上具有良好的計算效率，本文利用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的目標函數(shù)：

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

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

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

3 實例分析

圖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}.

其關聯(lián)矩陣

現(xiàn)根據(jù)問題1考慮該模型的初始資源優(yōu)化配置問題：計算初始標識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計算結(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軟件求解.實驗結(jié)果表明，提出的算法簡單高效,具有較強的實用性，可為現(xiàn)實中DES資源優(yōu)化配置提供理論借鑒.

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