一種基于Petri 網(wǎng)的多目標(biāo)無死鎖蟻群調(diào)度算法

惠曉龍，郜振鑫

資源受限的項(xiàng)目調(diào)度問題(Resource Constrained Project Scheduling Problem，RCPSP)屬于NP－h(huán)ard 問題;廣泛存在于制造系統(tǒng)等調(diào)度問題，它通過合理地分配資源，達(dá)到項(xiàng)目執(zhí)行工期最短等優(yōu)化目標(biāo)［1］。在合理分配資源的過程中，死鎖是一個重要的研究課題，目前人們從控制的角度提出了多種死鎖避免控制策略，但是這些策略無法優(yōu)化系統(tǒng)的運(yùn)行性能，因此系統(tǒng)的無死鎖優(yōu)化調(diào)度是一個值得研究的問題［2－5］。傳統(tǒng)的優(yōu)化調(diào)度只有一個優(yōu)化目標(biāo)，而在實(shí)際項(xiàng)目中往往存在多個優(yōu)化調(diào)度目標(biāo)。

本文針對制造系統(tǒng)的賦時Petri 網(wǎng)模型，研究以總工期最短和緊急項(xiàng)目工期最短為優(yōu)化目標(biāo)的無死鎖調(diào)度問題，建立系統(tǒng)的多目標(biāo)無死鎖蟻群調(diào)度算法。蟻群算法采用最大最小螞蟻系統(tǒng)，通過修改狀態(tài)轉(zhuǎn)移概率公式，并給出算法最優(yōu)解的評價函數(shù)，使螞蟻綜合多個優(yōu)化目標(biāo)選擇路徑。單只螞蟻選擇下一步可執(zhí)行的操作時，進(jìn)行死鎖判斷，將死鎖避免控制策略嵌入到算法，實(shí)現(xiàn)無死鎖調(diào)度。仿真結(jié)果驗(yàn)證了本文提出的多目標(biāo)無死鎖蟻群調(diào)度算法的可行性和有效性。

1 系統(tǒng)的Petri 網(wǎng)模型

Petri 網(wǎng)［2］結(jié)構(gòu)是一個三元組N=(P，T，F(xiàn))，其中P和T 都是有限但互不相交的集合。P 是位置(Place)的集合，T 是變遷(Transition)的集合，F(xiàn)?(P×T)∪(T×P)是有向弧(Arc)的集合。

Petri 網(wǎng)N 的一個標(biāo)識或狀態(tài)是一個映射M∶P→Z+，其中Z+={0，1，2，…}。給定標(biāo)記Petri 網(wǎng)N=(P，T，F(xiàn)，M0)，用T*表示T 的所有變遷序列的集合，?a=t0，t1，t2，…，tn∈T*，如果Miti＞Mi+1，i=0，1，2，…，n，則稱a 為在M0下的可行序列，稱Mi(i=1，2，…，n+1)為從M0的可達(dá)標(biāo)識或狀態(tài)。Petri 網(wǎng)N 中的一條路徑是一個序列αuv=(u=x1，x2，…，xk+1=v)，其中xi∈P∪T，(xi，xi+1)∈F，i=1，…，k，k 是α 的長度。

本文采用位置賦時Petri 網(wǎng)模擬系統(tǒng)的特征，模型中一個標(biāo)記必須在位置中經(jīng)過一定時延，記作d(p)，才能進(jìn)入下一個位置。

采用文獻(xiàn)［2，4］給出的制造系統(tǒng)模型，如圖1 所示。系統(tǒng)中有4 類機(jī)器(m1，m2，m3和m4)和3 類機(jī)器人(r1，r2和r3)，把資源集合表示為r={m1，m2，m3，m4，r1，r2，r3}，C(mi)=2，i=1，2，3，4，C(ri)=1，i=1，2，3。系統(tǒng)需要加工處理3 類工件，加工q1類工件的資源順序是r2m2r2，加工q3類工件的資源順序是r3m4r2m3r1，加工q2類工件有兩條路徑，其資源順序分別是r1m1r2m2r3和r1m3r2m4r3。tij和pij中的字母i 代表第i 條路徑，q1類工件的加工路徑為p1st11p11t12p12t13p13t14p1e，q2類工件的加工路徑有兩條分別為p2st21p21t22p22t23p23t24p24t25p25t26p2e和p2st21p21t32p32t33p33t34p34t35p25t26p2e，q3類工件的加工路徑為p4st41p41t42p42t43p43t44p44t45p45t46p4e。3 類工件需要加工的個數(shù)分別為8，12 和8。

圖1 系統(tǒng)的Petri 網(wǎng)模型

2 多目標(biāo)無死鎖蟻群調(diào)度算法

2.1 算法簡介

本文的蟻群算法采用最大最小螞蟻系統(tǒng)(Max－Min Ant System，MMAS)，其主要思想是:僅更新每一代中最好的螞蟻個體所走的路徑上的信息量，加快收斂速度;并將各條路徑上的信息量限制在區(qū)間［τmin，τmax］內(nèi)，避免某條路徑上的信息量遠(yuǎn)大于其他路徑上的信息量，使螞蟻的搜索行為集中到同一條路徑上［6］。

針對制造系統(tǒng)的調(diào)度模型提出蟻群算法的數(shù)學(xué)模型，問題描述如下:針對一個可標(biāo)識的自動制造系統(tǒng)(N，M0)，加工完一定任務(wù)的工件總共需要的操作數(shù)目為，所有加工操作的集合表示為{O1，O2，…，On}，操作Oi的加工時間為t(Oi)(i=1，2，…，n)，算法的任務(wù)就是尋找一個有序的加工路徑或者操作序列，完成所有的加工任務(wù)，優(yōu)化目標(biāo)使系統(tǒng)的加工時間和緊急工件的加工完成時間最短。算法對系統(tǒng)的工件、資源和操作均按順序采用10 進(jìn)制進(jìn)行編碼。

2.2 多目標(biāo)無死鎖蟻群調(diào)度算法

算法中蟻群數(shù)量為m，螞蟻k(k=1，2，…，m)在選擇下一步操作時，根據(jù)文獻(xiàn)［5］中提出的具有多項(xiàng)式復(fù)雜性的死鎖避免控制策略(DAP)，將不會造成死鎖的操作放入集合allowedk中，并從中選擇下一步遍歷操作，從而實(shí)現(xiàn)無死鎖調(diào)度。在遍歷的過程中，根據(jù)各操作之間遺留的信息素來決定下一個操作，同時考慮操作的啟發(fā)式信息和緊急工件的優(yōu)先級信息。Pkij表示第k 只螞蟻由操作Oi轉(zhuǎn)移到操作Oj的狀態(tài)轉(zhuǎn)移概率，由式(1)確定

其中，τij表示操作Oi和Oj之間的信息素，初始時刻為常數(shù);ηj表示在搜索過程中選擇操作Oj的期望值，根據(jù)先驗(yàn)知識可知，本文ηj為操作Oj的最早開始加工時間的導(dǎo)數(shù);ζj表示操作Oj對應(yīng)工件的優(yōu)先級，初始給定為常數(shù)。

α 表示信息素啟發(fā)式因子，反映的是蟻群在遍歷過程中所殘留信息素的相對重要程度;β 表示期望啟發(fā)式因子，反映了對下一個遍歷操作所期望的相對重要程度;γ 表示優(yōu)先級啟發(fā)式因子，反映優(yōu)先級的相對重要程度。如式(1)所示，螞蟻優(yōu)先選擇信息素濃度高、能最早開始加工并且優(yōu)先級高的操作路徑。

算法每一次迭代只更新最優(yōu)解路徑上的信息素，因此給出了評價最優(yōu)解的函數(shù)。假設(shè)系統(tǒng)中只含有一類緊急工件，其他工件都是普通工件，用式(2)的大小作為評價最優(yōu)解α 的標(biāo)準(zhǔn)，其中ω1和ω2分別是系統(tǒng)加工時間t1和緊急工件加工時間t2的權(quán)值。ζ 表示緊急工件的優(yōu)先級，finishtime 表示緊急工件的加工完成時間。

為防止算法過早收斂陷入局部最優(yōu)解，當(dāng)算法收斂時重置信息素模型，重啟調(diào)度。用收斂因子cf描述算法的收斂程度;在初始時刻cf=0，當(dāng)所有的信息素的值都等于τmax或τmin時，cf=1.0，由式(3)求得。

算法實(shí)現(xiàn)步驟:(1)系統(tǒng)初始化。蟻群中螞蟻的總數(shù)，最大循環(huán)迭代次數(shù)，信息素初始化τij=0.5。(2)單只螞蟻調(diào)度。首先根據(jù)死鎖避免控制策略，保證每只螞蟻在選擇下一個操作之前，保證操作不會造成死鎖，然后根據(jù)狀態(tài)轉(zhuǎn)移概率公式選擇下一步操作，直到遍歷完所有操作。(3)所有螞蟻遍歷完形成路徑集合，從中選擇最優(yōu)路徑更新信息素模型。(4)計算收斂因子，如果算法收斂后，重置信息素模型。(5)判斷是否滿足結(jié)束條件，即達(dá)到最大循環(huán)迭代次數(shù)，如果滿足，則輸出算法計算結(jié)果，算法結(jié)束。

3 算法仿真與結(jié)果分析

對圖1 所示的制造系統(tǒng)的調(diào)度問題，采用蟻群算法對其進(jìn)行調(diào)度，采用文獻(xiàn)［7］中給出的加工時間數(shù)據(jù)，加工時間如表1 所示。

表1 制造系統(tǒng)操作加工時間

系統(tǒng)仿真參數(shù)設(shè)置如下。q1，q2，q3這3 類工件的優(yōu)先級分別為(1，2，1)，q2類工件為緊急工件，α=3，β=3，γ=1，ρ=0.01，蟻群數(shù)量為10，迭代次數(shù)800，ω1=0.4，ω2=0.6。圖2 是迭代最優(yōu)解變化情況，圖3是多目標(biāo)全局最優(yōu)解的的變化情況，求得所有工件完成時間428，緊急工件完成時間259，對應(yīng)的最優(yōu)調(diào)度路徑為(t11，t21，t41，t32，t21，t22，t42，t21，t41，t12，t22，t13，t14，t43，t21，t42，t33，t23，t22，t34，t41，t21，t24，t23，t24，t22，t44，t21，t32，t45，t46，t21，t43，t44，t42，t25，t26，t35，t26，t11，t33，t32，t12，t25，t26，t45，t46，t43，t44，t34，t33，t21，t35，t26，t32，t13，t14，t21，t41，t34，t23，t22，t21，t24，t42，t35，t26，t23，t33，t41，t32，t24，t34，t21，t22，t45，t46，t43，t44，t21，t42，t35，t26，t33，t34，t32，t45，t46，t43，t25，t26，t23，t25，t26，t24，t23，t35，t26，t33，t24，t25，t26，t11，t44，t34，t41，t12，t42，t25，t26，t35，t26，t41，t11，t12，t42，t13，t14，t41，t11，t12，t13，t14，t13，t14，t11，t12，t11，t12，t43，t44，t45，t46，t42，t43，t44，t45，t46，t43，t44，t45，t46，t45，t46，t13，t14，t11，t12，t13，t14，t13，t14)。

圖2 蟻群算法迭代最優(yōu)解

圖3 蟻群算法多目標(biāo)調(diào)度最優(yōu)解

從仿真結(jié)果可以看出，蟻群算法在迭代次數(shù)為約360 和705 時收斂，重置信息素模型重啟調(diào)度，以免算法陷入局部最優(yōu)解。算法根據(jù)優(yōu)化目標(biāo)權(quán)值的不同，做出權(quán)衡，選擇最優(yōu)解，從圖中可以看出，算法較好地給出了調(diào)度的最優(yōu)解，是可行、有效的。

4 結(jié)束語

本文針對資源受限項(xiàng)目中的制造系統(tǒng)調(diào)度問題，采用其Petri 網(wǎng)模型，將死鎖避免控制策略嵌入到蟻群算法中，解決系統(tǒng)具有多個加工優(yōu)化目標(biāo)的問題，給出系統(tǒng)的多目標(biāo)無死鎖蟻群調(diào)度算法。蟻群算法采用最大最小螞蟻系統(tǒng)，通過修改狀態(tài)轉(zhuǎn)移概率公式，使螞蟻具有較大的概率優(yōu)先選擇緊急工件的加工操作，算法每次只更新最優(yōu)調(diào)度解對應(yīng)的信息素，給出評價函數(shù)來評價調(diào)度解的優(yōu)劣。通過仿真實(shí)例，證明了算法的可行性和有效性。

［1］ 龐南生，孟俊姣.多目標(biāo)資源受限項(xiàng)目魯棒調(diào)度研究［J］.運(yùn)籌與管理，2012(3):27－32.

［2］ EZPELETA J，COLOM J M，MARTINEZ J.A petri net based deadlock prevention policy for flexible manufacturing systems［J］.IEEE Transactions on Robotics and Automation，1995，11(2):173－184.

［3］ REVELIOTIS S A，LAWLEY M A，F(xiàn)ERREIRA P M.Polynomial－complexity deadlock avoidance policies for sequential resource allocation systems［J］.IEEE Transactions on Automatic Control，1997，42(10):1344－1357.

［4］ XING K Y，ZHOU M C，LIU H X，et al.Optimal petri－net－based polynomial－complexity deadlock－avoidance policies for automated manufacturing systems［J］.IEEE Transactions on Systems，Man and Cybernetics，Part A:Systems and Humans，2009，39(1):188－199.

［5］ 邢科義，田鋒，楊小軍，等.具有多項(xiàng)式時間復(fù)雜性的避免制造系統(tǒng)死鎖控制策略［J］.自動化學(xué)報，2007，33(8):893－896.

［6］ STüTZLE T，HOOS H H.Max－min ant system［J］.Future Generation Computer Systems，2000，16(9):889－914.

［7］ XING K Y，HAN L B，ZHOU M C.Deadlock－free genetic scheduling algorithm for automated manufacturing systems based on deadlock control policy［J］.IEEE Transactions on Systems，Man，and Cybernetics，Part B:Cybernetics，2012，42(3):603－615.