考慮不確定因素影響的保障任務(wù)調(diào)度算法

曾 斌，姚 路，胡 煒，楊 光（海軍工程大學(xué)管理工程系信息管理研究室，湖北　武漢430033）

考慮不確定因素影響的保障任務(wù)調(diào)度算法

曾 斌，姚 路，胡 煒，楊 光
（海軍工程大學(xué)管理工程系信息管理研究室，湖北武漢430033）

針對(duì)裝備保障任務(wù)的優(yōu)化調(diào)度問(wèn)題，首先進(jìn)行靜態(tài)建模，提出了一個(gè)新的數(shù)學(xué)規(guī)劃模型，能夠有效描述保障單元的力量配置及與保障對(duì)象的指派關(guān)系等復(fù)雜約束條件；隨后實(shí)施動(dòng)態(tài)建模，利用混合Petri網(wǎng)把數(shù)學(xué)模型轉(zhuǎn)換為流程模型，不僅構(gòu)建了變遷激發(fā)規(guī)則以表達(dá)靜態(tài)數(shù)學(xué)模型的約束條件，而且設(shè)計(jì)了新的子網(wǎng)結(jié)構(gòu)模擬突發(fā)事件及協(xié)同保障的動(dòng)態(tài)過(guò)程。為了求解該規(guī)劃模型，提出了一個(gè)基于退火進(jìn)化的優(yōu)化調(diào)度算法，該算法首先計(jì)算保障單元的分配問(wèn)題，隨后搜索資源分配的優(yōu)先級(jí)列表生成保障任務(wù)的工作順序，算法中利用Petri網(wǎng)過(guò)程模型計(jì)算不確定條件下的目標(biāo)函數(shù)值。仿真實(shí)驗(yàn)表明算法能在較快的收斂速度下提高保障單元的利用率。

任務(wù)調(diào)度；不確定；協(xié)同保障；優(yōu)化算法

網(wǎng)址：www.sys-ele.com

0 引 言

未來(lái)作戰(zhàn)將是多個(gè)戰(zhàn)場(chǎng)同時(shí)存在、互為依托的全方位作戰(zhàn)，這給保障決策指揮帶來(lái)了巨大挑戰(zhàn)：一是保障的地域廣、地點(diǎn)多、可用時(shí)間相對(duì)減少、難度加大；二是作戰(zhàn)單元的戰(zhàn)損是全方位的，需要軍需、物資、油料、裝備、醫(yī)療、衛(wèi)生、通訊、交通等全面的綜合保障才能起到保障作用。為了保障部隊(duì)的作戰(zhàn)行動(dòng)，保障部隊(duì)必須能夠在同一時(shí)間和多種地域遂行多項(xiàng)任務(wù)保障。為此，產(chǎn)生了協(xié)同保障模式，保障部隊(duì)平時(shí)依據(jù)可能擔(dān)負(fù)的任務(wù)，對(duì)所屬裝備器材、專業(yè)人員實(shí)施模塊化管理，將各類具有相同或相近用途的裝備器材進(jìn)行資源整合，把人員按照專業(yè)進(jìn)行編組，建立“專業(yè)化保障單元”。戰(zhàn)時(shí)每一個(gè)保障單元既可獨(dú)立執(zhí)行專項(xiàng)任務(wù)，也可根據(jù)任務(wù)需要靈活調(diào)配組合形成保障單元，協(xié)同使用。因此，一個(gè)完善的保障決策支持系統(tǒng)需要能夠根據(jù)作戰(zhàn)部隊(duì)任務(wù)需求，充分預(yù)見(jiàn)可能發(fā)生的各種情況，制定詳細(xì)的保障力量調(diào)度計(jì)劃，形成可行的保障預(yù)案。目前大多數(shù)研究者把裝備保障任務(wù)調(diào)度問(wèn)題看作車間作業(yè)調(diào)度問(wèn)題的一種典型應(yīng)用［1］，主要研究給定一定數(shù)量作業(yè)線（保障單元），將各個(gè)保障對(duì)象（分布在多個(gè)戰(zhàn)場(chǎng)的作戰(zhàn)單元）的單個(gè)或批量保障工作進(jìn)行重新組合，并形成一個(gè)最優(yōu)任務(wù)序列的過(guò)程。約束條件包括諸如出動(dòng)順序、最大維修保障時(shí)間、保障人員有限等約束條件，調(diào)度的目的是達(dá)到諸如人員利用率最高、費(fèi)用最小、耗費(fèi)時(shí)間最少等。但這些研究存在不足。

（1）沒(méi)有考慮不確定的突發(fā)事件的影響。除經(jīng)典調(diào)度問(wèn)題存在的大規(guī)模、強(qiáng)約束等復(fù)雜因素，保障過(guò)程存在的一些不確定性，例如備品備件的短缺、維修設(shè)備的故障及惡劣天氣的出現(xiàn)等，使得不確定條件下的任務(wù)調(diào)度具有更高的求解難度，是一個(gè)更具挑戰(zhàn)性的復(fù)雜優(yōu)化問(wèn)題。

（2）缺乏對(duì)協(xié)同保障模式的支持?，F(xiàn)有調(diào)度算法一般假設(shè)每個(gè)保障對(duì)象只能占用滿足其要求的保障單元集合中的一個(gè)［2］。但在協(xié)同保障時(shí)應(yīng)該允許多個(gè)保障單元同時(shí)保障同一個(gè)作戰(zhàn)單元。

（3）約束條件較為簡(jiǎn)單。典型的任務(wù)指派問(wèn)題考慮的都是保障力量的數(shù)量約束且假設(shè)每個(gè)保障單元處理能力相同，而實(shí)際由于各保障單元配置不同，工作速度是存在差異性的。

（4）戰(zhàn)時(shí)各保障單元需要服務(wù)的作戰(zhàn)單元不僅數(shù)量多，而且距離遠(yuǎn)，即存在保障地點(diǎn)分散等的限制，需要保障單元花費(fèi)較多時(shí)間才能運(yùn)輸?shù)奖Ｕ系攸c(diǎn)，這也是常規(guī)作業(yè)調(diào)度忽視的問(wèn)題。

非確定條件下的資源分配和任務(wù)調(diào)度問(wèn)題是難以優(yōu)化的，這也是當(dāng)前的一個(gè)研究熱點(diǎn)［3］。例如文獻(xiàn)［4］研究了應(yīng)急保障資源分配時(shí)非確定條件的建模問(wèn)題，并比較了3種分配策略下不同模型的性能。文獻(xiàn)［5］提出了一種基于粒子群的優(yōu)化算法解決任務(wù)分配及資源部署問(wèn)題，并通過(guò)離散事件仿真來(lái)模擬非確定條件的影響。文獻(xiàn)［6］提出了一個(gè)針對(duì)項(xiàng)目管理的資源分配模型，并在模型中引入了非確定影響因子。文獻(xiàn)［7］提出了緊急救援時(shí)保障資源的隨機(jī)規(guī)劃模型，并把保障資源的采辦及運(yùn)輸代價(jià)作為非確定參數(shù)，最后驗(yàn)證了該模型對(duì)于制定救援計(jì)劃的輔助決策能力。文獻(xiàn)［8］提出了一個(gè)基于遺傳算法的隨機(jī)分配算法并把它應(yīng)用到任務(wù)調(diào)度問(wèn)題中，并通過(guò)馬爾可夫鏈驗(yàn)證了算法的收斂性。文獻(xiàn)［9］也提出了一個(gè)二重向量編碼的遺傳算法以解決任務(wù)調(diào)度問(wèn)題。文獻(xiàn)［10］提出了一種基于預(yù)測(cè)算子的仿真優(yōu)化算法，并應(yīng)用于資源配置方案的制定。文獻(xiàn)［11］利用模擬退火算法優(yōu)化并行維修資源的分配，從仿真實(shí)驗(yàn)看算法具有較高的收斂速度。文獻(xiàn)［12］在作業(yè)車間制造系統(tǒng)中提出了一個(gè)混合Petri網(wǎng)與遺傳算法的優(yōu)化調(diào)度策略。文獻(xiàn)［13-14］綜合了混合Petri網(wǎng)的流程建模能力與遺傳算法的搜索能力，分別提出了適用于柔性制造系統(tǒng)的優(yōu)化調(diào)度算法。文獻(xiàn)［15］提出了一個(gè)2階段粒子群優(yōu)化算法，結(jié)合了遺傳算子和退火策略，用以解決大規(guī)模流水線生產(chǎn)調(diào)度問(wèn)題。文獻(xiàn)［16］利用網(wǎng)絡(luò)模型對(duì)復(fù)雜的生產(chǎn)系統(tǒng)進(jìn)行建模，并提出了一個(gè)多階段進(jìn)化算法搜索網(wǎng)絡(luò)模型的最優(yōu)解。文獻(xiàn)［17］提出一個(gè)組合優(yōu)化框架來(lái)對(duì)動(dòng)態(tài)資源分配問(wèn)題進(jìn)行建模與求解。雖然有不少文獻(xiàn)從各自的應(yīng)用方向研究了資源分配及任務(wù)調(diào)度問(wèn)題，但這些方法都有自己的應(yīng)用范圍，難以直接生成裝備維修保障方案，而且也不支持對(duì)地理上分布廣泛的對(duì)象進(jìn)行任務(wù)調(diào)度。

鑒于以前研究方法存在的不足，本文分析裝備保障任務(wù)調(diào)度的特點(diǎn)，建立了一種新的任務(wù)調(diào)度數(shù)學(xué)模型，并鑒于混合Petri網(wǎng)的知識(shí)表達(dá)特點(diǎn)，建立了保障任務(wù)調(diào)度輔助決策模型，把數(shù)學(xué)模型轉(zhuǎn)換為可執(zhí)行的程序模型。模型中通過(guò)約束條件式（1）及對(duì)應(yīng)Petri網(wǎng)結(jié)構(gòu)（見(jiàn)圖2）實(shí)現(xiàn)了對(duì)協(xié)同保障的支持，通過(guò)設(shè)計(jì)混合Petri網(wǎng)結(jié)構(gòu)（見(jiàn)圖3）模擬突發(fā)事件的影響，通過(guò)約束條件式（2）引入的工作量矩陣表達(dá)了保障單元的差異性特點(diǎn)，通過(guò)約束條件式（6）表示了保障地點(diǎn)分散的限制。

最后設(shè)計(jì)了一個(gè)兩階段啟發(fā)式算法。第一階段利用模擬退火算法局部尋優(yōu)效果好的優(yōu)點(diǎn)，對(duì)保障單元進(jìn)行優(yōu)化分配；第二階段利用遺傳算法的啟發(fā)式全局搜索能力，根據(jù)混合Petri網(wǎng)的激活規(guī)則搜索優(yōu)化的調(diào)度方案，確定工序。并通過(guò)仿真計(jì)算對(duì)該算法的數(shù)學(xué)模型和性能進(jìn)行了驗(yàn)證。本文雖然主要考慮不確定條件下保障任務(wù)調(diào)度問(wèn)題，但任務(wù)優(yōu)先級(jí)和保障費(fèi)用等約束稍加修改也能較容易的加入本算法。

1 調(diào)度模型

1.1 問(wèn)題描述及數(shù)學(xué)模型

為了從理論上描述裝備保障的調(diào)度條件，用NF表示保障對(duì)象（作戰(zhàn)單元）的數(shù)量，NW表示保障工作數(shù)量（與戰(zhàn)損裝備有關(guān)），NR表示保障單元的數(shù)量。其他的數(shù)學(xué)符號(hào)表示見(jiàn)表1。其中Iij表示在保障對(duì)象Oi上的保障工作Wj是否執(zhí)行，nij表示Oi上調(diào)度的Wj的工作量（Iij_＞0），可以通過(guò)歷史數(shù)據(jù)統(tǒng)計(jì)或預(yù)測(cè)方式計(jì)算保障工作量［18 19］。如果nij＞0，則Wj將調(diào)度執(zhí)行，否則該工作將不在Oi上執(zhí)行。兩個(gè)保障工作之間的間隔時(shí)間Wij和計(jì)劃保障時(shí)間Pj（s），Pj（e）表示保障單元的一次工作時(shí)間。一般情況下Pj（s）大于Pj-1（s），當(dāng)然保障工作Wj-1和Wj也可以并行開(kāi)展，例如衛(wèi)勤和維修可以同時(shí)執(zhí)行。

表1 數(shù)學(xué)符號(hào)定義

在任務(wù)調(diào)度中，執(zhí)行保障工作Wj的單元至少為1，至多為如果兩個(gè)或以上單元被分配給同一個(gè)保障工作即為協(xié)同保障。保障單元指派關(guān)系可由式（1）約束。

利用保障單元Rk在時(shí)間t內(nèi)完成的工作量nij可由式（2）計(jì)算：

為了保證能按時(shí)完成保障工作，工作開(kāi)始時(shí)刻tiRjk（s）和結(jié)束時(shí)刻還需要引入如下約束條件，其中

對(duì)于有順序要求的保障工作，可以用以下約束來(lái)加以限制，即下一步工作Wj必須在前面工作Wj-1完成后才能開(kāi)始，該條件表述如下：

由于各保障對(duì)象分布區(qū)域不同，保障單元在它們之間運(yùn)輸需要花費(fèi)時(shí)間，所以下一步工作必須在前面所有工作完成后再加上運(yùn)輸時(shí)間后才能開(kāi)展。

基于以上約束條件，調(diào)度問(wèn)題的目標(biāo)函數(shù)可用式（7）表達(dá)：

1.2 混合Petri網(wǎng)模型

離散petri網(wǎng)中庫(kù)所中的令牌用離散數(shù)表示，而連續(xù)Petri網(wǎng)用實(shí)數(shù)令牌表示連續(xù)的工作過(guò)程。在大多數(shù)情況下，工作過(guò)程可以用連續(xù)流來(lái)近似模擬，但保障單元的狀態(tài)是離散的，所以本文利用混合Petri網(wǎng)對(duì)保障過(guò)程進(jìn)行建模?；旌螾etri網(wǎng)由6元組N=＜P，T，Pre，Post，M0，h＞定義，其中P為庫(kù)所的集合，T為變遷的集合，Pre（Post）為表示輸入（輸出）有向弧的關(guān)聯(lián)函數(shù)，M0為表示令牌初始值的函數(shù)，h函數(shù)表示Petri網(wǎng)中某節(jié)點(diǎn)屬于離散或連續(xù)類型。

圖1為任務(wù)調(diào)度Petri網(wǎng)模型的一個(gè)示例。在連續(xù)庫(kù)所Pij中的數(shù)字為令牌數(shù)量，它表示了保障工作量。在Oi中剛開(kāi)始實(shí)施保障工作Wj時(shí)，Pij的值設(shè)置為nij，對(duì)應(yīng)于Oi的其他庫(kù)所的值設(shè)置為0。例如圖1中，初始狀態(tài)時(shí)，庫(kù)所P11，P12，…，P1j，的工作量（令牌）分別設(shè)置為45，0，…，0。連續(xù)變遷用任務(wù)Tijk表示，它表示利用保障單元Rk在保障對(duì)象Oi中實(shí)施的保障工作Wj，即保障任務(wù)。圖中連續(xù)變遷與一個(gè)預(yù)定義的工作時(shí)限［Pj（s），Pj（e）］關(guān)聯(lián)，連續(xù)庫(kù)所與一個(gè)等待時(shí)間Wij關(guān)聯(lián)。

圖1 保障工作調(diào)度的混合Petri網(wǎng)模型

庫(kù)所中令牌分布決定變遷的使能和激發(fā)，變遷激發(fā)又將改變令牌的分布，它將會(huì)從輸入庫(kù)所中消耗令牌，執(zhí)行任務(wù)，然后把一定數(shù)量的令牌放置到輸出庫(kù)所中。在戰(zhàn)時(shí)保障系統(tǒng)模型中，它表示當(dāng)某項(xiàng)工作所需要的條件得到滿足時(shí)，該項(xiàng)保障工作即得到使能，可以執(zhí)行。其中任務(wù)的執(zhí)行時(shí)間對(duì)應(yīng)著連續(xù)變遷的激發(fā)時(shí)間，它由保障單元的工作進(jìn)度決定。當(dāng)某項(xiàng)保障工作結(jié)束后，與其對(duì)應(yīng)的保障對(duì)象將轉(zhuǎn)到新的狀態(tài)，這時(shí)原來(lái)使用的保障單元將會(huì)釋放。

在保障工作的執(zhí)行過(guò)程中，庫(kù)所的令牌分布隨時(shí)間不斷流動(dòng)。因此通過(guò)觀察混合Petri網(wǎng)中令牌矢量的變化情況就可以監(jiān)測(cè)保障對(duì)象及保障單元的工作進(jìn)程和狀態(tài)。

1.3 協(xié)同保障及非確定條件的Petri網(wǎng)模型

協(xié)同保障及非確定條件模型如圖2和圖3所示（圖1的部分模型），在圖2的起始階段，在保障對(duì)象O1上工作的保障單元R1，R2和R3協(xié)同執(zhí)行同一個(gè)保障工作W1，保障單元R1，R2和R3的工作能力分別為6（人·機(jī)），7（人·機(jī)）和8（人·機(jī)）。在不考慮保障設(shè)備故障等非確定條件時(shí)，如果3個(gè)單元協(xié)同工作，保障工作W1的持續(xù)時(shí)間為2.2小時(shí)。如果沒(méi)有令牌賦予庫(kù)所P2和P3，則工作時(shí)間延長(zhǎng)為7.5小時(shí)。

圖2 協(xié)同保障模型

圖3 不確定條件模型

保障設(shè)備故障或者惡劣天氣等非確定情況會(huì)導(dǎo)致保障工作中斷。如果是設(shè)備故障引起工作中斷，對(duì)應(yīng)每一個(gè)保障單元Rk，利用與連續(xù)變遷Tijk相連的離散Petri網(wǎng)表示任務(wù)Tijk的中斷及恢復(fù)狀態(tài)，該離散Petri網(wǎng)包含2個(gè)離散遷移和2個(gè)離散庫(kù)所。如果是天氣原因造成中斷，利用與連續(xù)變遷Tijk相連的1個(gè)庫(kù)所表達(dá)，該庫(kù)所與一個(gè)由外部環(huán)境條件控制的離散變遷相連。不同的非確定條件可以生成相應(yīng)的離散庫(kù)所。其他的約束條件也用可這種方式建模。

例如在圖3中，如果天氣條件允許Tijk的實(shí)施，則在庫(kù)所P3中賦予令牌；否則不賦予令牌。如果盡管P3中存在令牌，但P2中被賦予令牌時(shí)，表示雖然天氣情況允許，但保障設(shè)備發(fā)生故障。在30分鐘后，通過(guò)激發(fā)離散變遷T2可以把令牌轉(zhuǎn)移到庫(kù)所P1，這時(shí)保障工作可以開(kāi)始。由于離散變遷的優(yōu)先級(jí)高于連續(xù)變遷，在120分鐘后通過(guò)激發(fā)變遷T1，可以使系統(tǒng)重新轉(zhuǎn)入設(shè)備故障狀態(tài)。通過(guò)這種方式，如果在建模時(shí)輸入T1和T2的中斷時(shí)間，就可以表達(dá)保障工作中可能遇到的各種中斷情況。

1.4 約束條件的Petri建模

式（1）～式（6）定義的約束條件都可以用混合Petri網(wǎng)的激發(fā)規(guī)則表達(dá)，這些規(guī)則包括以下內(nèi)容。

（1）式（1）表達(dá)了協(xié)同保障的條件，它限制了Oi中Wj所能指派保障單元的最大數(shù)量。由于混合Petri網(wǎng)是動(dòng)態(tài)生成的，所以與連續(xù)變遷連接的離散庫(kù)所的數(shù)量就等于所指派保障單元的數(shù)量。當(dāng)保障單元被調(diào)度后，既可馬上生成Petri網(wǎng)中的連續(xù)庫(kù)所，連續(xù)變遷和離散庫(kù)所，但從連續(xù)變遷到離散庫(kù)所的有向弧需要在工序確定后才能創(chuàng)建。

（2）式（2）的數(shù)學(xué)定義表示必須完成被調(diào)度執(zhí)行的保障工作，即當(dāng)所有保障任務(wù)完成后激發(fā)操作才能停止。

（3）式（4）表示了2個(gè)約束條件，即保障工作必須在預(yù)先規(guī)定的工期內(nèi)完成，而且當(dāng)前一個(gè)工作Wj-1完成后再加上一個(gè)等待時(shí)間（例如人員休整）才能開(kāi)始下一個(gè)工作Wj。

（4）根據(jù)保障工作先后次序要求，前一個(gè)工作Wj-1完成后才能開(kāi)始下一個(gè)工作Wj，這與式（5）對(duì)應(yīng)。例如如果P12的令牌數(shù)量少于45，即使其他條件都滿足，任務(wù)T124和任務(wù)T125也無(wú)法開(kāi)始。

（5）式（6）定義了保障單元在不同保障對(duì)象之間的運(yùn)輸時(shí)間，它也需要在Petri網(wǎng)中得到考慮，該運(yùn)輸時(shí)間與離散變遷關(guān)聯(lián)。

（6）保障工作可能在任意一個(gè)時(shí)刻中斷。該規(guī)則的實(shí)現(xiàn)見(jiàn)1.3節(jié)。

根據(jù)混合Petri網(wǎng)本身的激發(fā)特點(diǎn)，保障工作時(shí)間段之間不會(huì)出現(xiàn)重疊，所以式（3）不需要有專門規(guī)則表達(dá)。從以上描述可看出該P(yáng)etri網(wǎng)模型可以對(duì)保障任務(wù)的調(diào)度過(guò)程進(jìn)行建模。模型中所有的約束條件都由離散庫(kù)所或令牌定義，通過(guò)增加離散庫(kù)所或令牌可以方便的補(bǔ)充新的約束。

2 算法描述

保障工作調(diào)度包括保障單元分配指派和工序安排兩個(gè)步驟，所以調(diào)度算法也包括兩個(gè)階段，先按照模擬退火算法產(chǎn)生保障單元指派方案；隨后嵌套調(diào)用遺傳算法優(yōu)化該方案下的工序安排（通過(guò)一個(gè)優(yōu)先隊(duì)列表示），優(yōu)先隊(duì)列中每一個(gè)工作都賦予一個(gè)優(yōu)先級(jí)；再返回模擬退火算法產(chǎn)生更優(yōu)的指派方案。根據(jù)混合Petri網(wǎng)的激發(fā)規(guī)則，可以通過(guò)最小化保障任務(wù)之間的空閑時(shí)間來(lái)優(yōu)化優(yōu)先隊(duì)列。

2.1 基于模擬退火的保障單元分配

當(dāng)兩個(gè)或兩個(gè)以上的保障工作在執(zhí)行過(guò)程中，因爭(zhēng)奪保障單元而造成互相等待時(shí)，就會(huì)發(fā)生死鎖現(xiàn)象，為此在模擬退火算法中需要引入式（1）約束條件。算法中獨(dú)立變量x表示保障單元的指派方案，x’表示協(xié)同工作時(shí)保障單元指派任務(wù)的備選池，算法偽代碼如下：

1：初始化溫度T，初始化解狀態(tài)空間N

2：初始化方案x，初始化最小適應(yīng)度函數(shù)min

3：調(diào)用第2階段的函數(shù)gaP L（x）計(jì)算適應(yīng)度Fx

4：while不滿足終止條件do

5：fori=0 toN

6：產(chǎn)生新方案x’

7：調(diào)用gaP L（x） 計(jì)算適應(yīng)度Fx’

8：if（Fx’＜Fx）then

9：接受新方案x’ 作為當(dāng)前解，代替x

10：else

11：if（rnd（）＜exp（Fx-Fx’/T））then

12：接受新方案x’作為當(dāng)前解，代替x’

13：end if

14：end if

15：if（Fx’＜min）

16：接受新適應(yīng)值Fx’代替min，存儲(chǔ)x’

17：end if

18：end for

19：計(jì)算（T-T*a）代替T，其中0＜a＜1

20：end while

在這里注意算法中的符號(hào)定義與表1不同。當(dāng)保障單元指派方案確定后，才能得出第2階段遺傳算法的染色體長(zhǎng)度，也才能夠建立起混合Petri網(wǎng)模型中除有向弧之外的所有庫(kù)所和變遷。

2.2 基于遺傳算法的工序安排

利用第1階段產(chǎn)生的保障單元指派方案，第2階段的遺傳算法搜索優(yōu)先級(jí)列表，并根據(jù)Petri網(wǎng)模型產(chǎn)生調(diào)度方案。算法采用了經(jīng)典的單點(diǎn)順序雜交算子，1位反向變異算子和賭盤選擇復(fù)制算子，并引入了精華保留（elite reservation）策略。優(yōu)先級(jí)列表當(dāng)作染色體編碼，其中的保障任務(wù)按照工作Wj分組，只在同一個(gè)保障工作Wj中不同任務(wù)之間進(jìn)行雜交和變異。適應(yīng)度為所有保障任務(wù)之間的空閑時(shí)間和運(yùn)輸時(shí)間之和，它是通過(guò)運(yùn)行混合Petri網(wǎng)模型的活動(dòng)來(lái)計(jì)算的，根據(jù)Petri網(wǎng)的激發(fā)規(guī)則執(zhí)行適應(yīng)度函數(shù)，當(dāng)激發(fā)規(guī)則停止后產(chǎn)生調(diào)度方案，如果該方案具有當(dāng)前最優(yōu)的適應(yīng)度，則把它記錄在優(yōu)先級(jí)列表中。函數(shù)gaPL（x）偽代碼如下所示。

ProceduregaP L（x）

1：按照Wij對(duì)優(yōu)先級(jí)列表染色體排序；

2：從方案x中繼承當(dāng)前最優(yōu)優(yōu)先級(jí)列表；

3：初始化染色體種群c；

4：建立混合Petri網(wǎng)的連續(xù)部分；

5：調(diào)用適應(yīng)度計(jì)算函數(shù)evaluation（c）；

6：while不滿足終止條件do

7：進(jìn)行復(fù)制，雜交和變異；

8：調(diào)用適應(yīng)度計(jì)算函數(shù)evaluation（c）；

9：end while evaluation（c）

1：forr=1 to種群規(guī)模

2：建立混合 Petri網(wǎng)的離散部分；

3：初始化時(shí)間步長(zhǎng)τ，當(dāng)前時(shí)刻t=0；

4：while沒(méi)有完成所有任務(wù)do

5：if滿足激發(fā)條件then

6：激發(fā)變遷并更新對(duì)應(yīng)庫(kù)所的令牌；

7：end if

8：t=t+τ；

9：更新任務(wù)間空閑時(shí)間和運(yùn)輸時(shí)間之和；

10：end while

11：if發(fā)現(xiàn)最優(yōu)適應(yīng)度then

12：更新當(dāng)前適應(yīng)度，優(yōu)先級(jí)和調(diào)度方案；

13：end if

14：end for

2.3 消除死鎖

在常規(guī)優(yōu)化算法中一般通過(guò)檢測(cè)資源占用過(guò)程中是否發(fā)生沖突來(lái)判斷死鎖的產(chǎn)生。例如當(dāng)需要分配某資源給一個(gè)工作時(shí)，首先需要檢查它是否被另一個(gè)工作占用，如果已被占用，算法將一直等待直至該資源被釋放。如果在上述適應(yīng)度函數(shù)中也采用這種常規(guī)的死鎖檢測(cè)方法，將會(huì)增加遺傳算法的計(jì)算時(shí)間。所以本算法中采用先分配保障單元后安排工序的方法，可以有效防止保障單元沖突導(dǎo)致的死鎖。算法中每一項(xiàng)保障單元根據(jù)任務(wù)順序分配給相應(yīng)的工作，而且保障單元之間相互獨(dú)立。另外，第2步算法從第1步算法中繼承優(yōu)先級(jí)列表，而非盲目的從某個(gè)隨機(jī)源點(diǎn)開(kāi)始搜索，這也能較大的提高搜索效率。

3 實(shí)驗(yàn)驗(yàn)證

在這里以一個(gè)包含16個(gè)保障對(duì)象的綜合保障案例來(lái)進(jìn)行實(shí)驗(yàn)驗(yàn)證，該案例包括通信、衛(wèi)勤、油料、維修等6項(xiàng)保障工作，每項(xiàng)工作都設(shè)置了預(yù)定工期和所需保障單元，對(duì)應(yīng)于工作W1，W2，…，W6的所需保障單元數(shù)量分別假定為2，1，1，1，1和3。因?yàn)槟承┕ぷ鞯膶?shí)際完成時(shí)間會(huì)超過(guò)預(yù)定工期，所以它們可能不能滿足式（4），這時(shí)需要把它們對(duì)應(yīng)的適應(yīng)度進(jìn)行適量提高。為了提高算法的通用性，用C語(yǔ)言實(shí)現(xiàn)了調(diào)度算法，并在4 G B內(nèi)存的奔騰4工作站上運(yùn)行，運(yùn)行時(shí)間依賴于模擬退火算法和遺傳算法的參數(shù)設(shè)置以及Petri網(wǎng)的步長(zhǎng)設(shè)置。根據(jù)我們的統(tǒng)計(jì)，當(dāng)模擬退火算法中N=200，α=0.02，遺傳算法中種群規(guī)模=20，進(jìn)化代數(shù)=200，Petri網(wǎng)步長(zhǎng)=10 s時(shí)，調(diào)度算法的收斂時(shí)間約為10 min。

3.1 保障單元指派算法對(duì)性能的影響

圖4表示了在遺傳算法不同代數(shù)的情況下保障單元指派及調(diào)度的優(yōu)化效果。圖中“100代”和“1000代”表示算法中第2階段工序調(diào)度優(yōu)化的遺傳算法進(jìn)化代數(shù)分別設(shè)置為100和1000，這意味在同等計(jì)算時(shí)間內(nèi)，“100代”中第1階段保障單元指派算法的執(zhí)行頻率要高于“1000代”。

圖4 保障單元指派優(yōu)化

從圖4可以看出，在算法進(jìn)化的早期階段，“100代”就能在較短的時(shí)間取得較好的計(jì)算結(jié)果，這也表明增加保障單元指派的優(yōu)化頻率，可以改善算法的收斂度。當(dāng)然提高保障單元指派的優(yōu)化頻率并不就等于削弱第2階段的優(yōu)化效果，因?yàn)榈?階段算法的初始優(yōu)先級(jí)列表是從第1階段算法中直接繼承得到的。

3.2 遺傳算法不同加速策略的比較

因?yàn)楸Ｕ瞎ぷ髦g的等待時(shí)間Wij對(duì)算法結(jié)果的質(zhì)量有較大影響，所以當(dāng)?shù)却龝r(shí)間不同且不考慮其他約束時(shí)，如果把保障任務(wù)按Wij排序就可以得到最佳調(diào)度結(jié)果。圖5顯示了按Wij排序?qū)Y(jié)果質(zhì)量的影響。圖中遺傳算法初始群體所包括的染色體分別為不排序，一次排序和全排序。很明顯圖中“不排序”的曲線收斂速度最慢，而初始群體“全排序”時(shí)能得到較高的收斂速度和算法質(zhì)量。而“一次排序”時(shí)適應(yīng)度會(huì)受到諸如運(yùn)輸時(shí)間等因素的影響，所以它的進(jìn)化速度和算法質(zhì)量要比“全排序”差。從3條曲線的結(jié)果可以看出按照等待時(shí)間對(duì)保障任務(wù)排序可以提高進(jìn)化的收斂速度。

圖5 染色體排序結(jié)果

當(dāng)?shù)?輪調(diào)度優(yōu)化結(jié)束后，意味著針對(duì)每一個(gè)保障單元的工序及對(duì)應(yīng)的優(yōu)先級(jí)列表也得到了優(yōu)化，以當(dāng)前得到的最佳工序?yàn)榛A(chǔ)可以開(kāi)始第2輪的保障單元指派。而對(duì)上輪優(yōu)先級(jí)列表的利用程度不同，產(chǎn)生的計(jì)算結(jié)果也會(huì)不同，圖6比較了不同利用率的影響情況。為了消除染色體排序的影響，本次實(shí)驗(yàn)遺傳算法的初始群體采用“不排序”策略。圖6中，“0%利用率”表示初始染色體全部隨機(jī)生成，“10%利用率”表示初始染色體的10%從上階段保障單元指派中得到的優(yōu)先級(jí)列表中繼承產(chǎn)生，剩余的90%還是隨機(jī)生成。盡管在進(jìn)化的開(kāi)始階段幾條曲線有交叉情況，但最后的最優(yōu)適應(yīng)度還是按照利用率降序排列。該比較結(jié)果證明部分的繼承操作可以改善進(jìn)化速度和算法質(zhì)量。另外所有染色體都繼承產(chǎn)生時(shí)，進(jìn)化速度和算法質(zhì)量是最高的。但從傳統(tǒng)觀點(diǎn)來(lái)看，如果初始染色體缺乏差異性是會(huì)對(duì)算法全局優(yōu)化能力帶來(lái)負(fù)面影響的，不過(guò)由于第1階段的保障單元指派是不斷更新的，在遺傳算法繼承操作之前染色體也是隨機(jī)生成的，所以繼承操作產(chǎn)生的染色體仍然具有一定的差異性。

圖6 不同利用率的影響

3.3 調(diào)度結(jié)果

表2列出了得到最優(yōu)適應(yīng)度時(shí)9個(gè)保障單元調(diào)度統(tǒng)計(jì)信息，其中時(shí)間以min為單位。保障單元R1和R2可用于執(zhí)行工作W1，保障單元R7，R8和R9可執(zhí)行工作W6。本次調(diào)度最后統(tǒng)計(jì)得到協(xié)同保障的次數(shù)為10次，在不考慮運(yùn)輸時(shí)間的情況下，每一個(gè)維修保障單元的平均利用率達(dá)到了93.9%。調(diào)度長(zhǎng)度為627.5 min，它表示第1個(gè)任務(wù)開(kāi)始時(shí)刻到最后一個(gè)任務(wù)結(jié)束時(shí)刻的時(shí)間跨度，由于在裝備保障時(shí)需要騰出時(shí)間應(yīng)付可能發(fā)生的突發(fā)性事件，所以該調(diào)度長(zhǎng)度具有一定的彈性。

表2 調(diào)度結(jié)果的統(tǒng)計(jì)信息

從仿真結(jié)果中還可以發(fā)現(xiàn)調(diào)度算法的優(yōu)勢(shì)。例如，如果把保障的時(shí)間窗口設(shè)置為16 h，則調(diào)度時(shí)間長(zhǎng)度為10.45 h，以便預(yù)留一部分時(shí)間應(yīng)對(duì)非確定情況造成的停工。這時(shí)沒(méi)有調(diào)度保障單元R1和R2的時(shí)間分別為1.3 h和1.1 h，這些沒(méi)有得到調(diào)度的空余時(shí)間用于應(yīng)對(duì)可能發(fā)生的突發(fā)性不確定事件。

4 總 結(jié)

本文針對(duì)協(xié)同保障任務(wù)調(diào)度問(wèn)題提出了一個(gè)兩階段優(yōu)化算法，算法強(qiáng)化保障單元指派優(yōu)化，按照保障工作之間等待時(shí)間排序優(yōu)先級(jí)列表，并在調(diào)度階段繼承保障單元分配階段產(chǎn)生的任務(wù)序列，通過(guò)混合Petri網(wǎng)模型模擬了保障工作的各種約束條件和不確定因素的影響，從仿真實(shí)驗(yàn)結(jié)果看以上手段能夠加快收斂速度并提高優(yōu)化質(zhì)量。最后生成的調(diào)度結(jié)果具有較高的資源利用率，兼顧了協(xié)同保障，運(yùn)輸時(shí)間和保障工作之間等待時(shí)間等諸多因素，對(duì)于建立中短期保障預(yù)案而言算法具有較高的應(yīng)用價(jià)值。特別是有概率分布的非確定情況時(shí)，例如模擬影響保障工作實(shí)施的天氣情況等，在Petri網(wǎng)模型的相應(yīng)遷移上關(guān)聯(lián)一個(gè)概率分布時(shí)間量即可實(shí)現(xiàn)。

當(dāng)前工作重點(diǎn)還是考慮保障任務(wù)的離線調(diào)度問(wèn)題，但當(dāng)保障需求源源不斷到達(dá)時(shí)，則需要在線調(diào)度，可是在線調(diào)度卻由于缺少必要的預(yù)知信息難以取得優(yōu)化解，本文的辦法是把需求工作的到達(dá)也作為不確定量，從而預(yù)留一部分保障單元來(lái)解決保障工作動(dòng)態(tài)到達(dá)問(wèn)題。另外盡管當(dāng)前算法的計(jì)算時(shí)間在可允許范圍之內(nèi)，但還可以通過(guò)并行計(jì)算等方法進(jìn)一步降低算法的時(shí)間復(fù)雜度。

［1］Zhang L M，Peng L，Liu J H，et al.Im proved PS O algorith ms for equipment support mission scheduling problem［J］.Computer Engineering and Design，2012，33（8）：3105-3110.（張立民，彭樂(lè)，劉敬虎，張曉軍.求解裝備保障任務(wù)調(diào)度問(wèn)題的改進(jìn)粒子群算法.計(jì)算機(jī)工程與設(shè)計(jì)［J］.2012，33（8）：3105-3110.）

［2］Zhu L，Song J S，W ang Z Y.Scheduling m odel of the battle equip ment maintenance task based on the m ost support time［J］. Systems Engineering and Electronics，2007，29（11）：1900-1905.（朱昱，宋建社，王正元.一種基于最大保障時(shí)間的戰(zhàn)時(shí)裝備維修任務(wù)調(diào)度［J］.系統(tǒng)工程與電子技術(shù)，2007，29（11）：1900 -1905.）

［3］W ang L，Zheng H Y，Zheng X L.Survey on resource-constrained project scheduling under uncertainty［J］.Control and Decision，2014，29（4）：577-514.（王凌，鄭環(huán)宇，鄭曉龍.不確定資源受限項(xiàng)目調(diào)度研究綜述［J］.控制與決策，2014，29（4）：577-514.）

［4］H uang Y，F(xiàn)an Y.M odeling uncertainties in emergency service resource allocation［J］.Journal of Infrastructure Systems，2011，17（1）：35-41.

［5］Martins M S R，F(xiàn)uchs S C，Pando L U，et al.PSO with path rel inking for resource allocation using simulation optimization［J］. Com puters&Industrial Engineering，2013，65（2）：322-330.

［6］Wolfra m WW，K uhn D，Rustem B.M ulti-resource allocation in stochastic project scheduling［J］.Annals ofO perations Research，2012，193（1）：193-220.

［7］Bozorgi-Amiri A，Jabalameli M S，AleHashem S M J.A multi-objective robust stochastic program ming model for disaster rel ief logistics under uncertainty［J］.O R Spectrum，2013，35（4）：905-933.

［8］Li F C，Xu L D，Jin C X，et al.Rando m assignment method based on genetic algorith ms and its application in resource allocation［J］.ExpertSystems with Applications，2012，39（15）：123-129.

［9］Zheng J，W u J Z，H ao X C，et al.A novel bi-vector encoding genetic algorith m for the simultaneous multiple resources scheduling problem［J］.Journal of Intelligent Manufacturing，2012，23（6）：55-70.

［10］Melouka S H，F(xiàn)ontema B A，Way mireb E，et al.Stochastic resource allocation using a predictor-based heuristic for optimization via simulation［J］.Com puters&Operations Research，2014，46（6）：38-48.

［11］Shivasankarana N，Kumara P S，Nallaku marasam yb G，et al. Repair shop job scheduling with parallel operators and multiple constraints using simulated annealing［J］.International Journal of Com putational Intelligence Systems，2013，6（2）：223-233.

［12］Yao AW L，Pan Y M.A Petri nets and genetic algorithm based optimal scheduling for job shop manufacturing systems［C］∥Proc. of International Conference on System Science and Engineering，2013：99-104.

［13］Sadrieh S A，G haeli M，Bahri P A，et al.A n integrated Petri nets and G A based approach for scheduling of hybrid plants［J］. Com putersin Industry，2007，58（6）：519-530.

［14］Gonzalo M，Carlos M，Cardona J.Petri nets and genetic algorithms for complex manufacturing systems schedul ing［J］.International Journal of Production Research，2012，50（3）：791-803.

［15］Zhang C S，Ning J X，O uyang D T.A hybrid alternate two phases particle swarm optimization algorith m for flowshop scheduling problem［J］.Com puters&Industrial Engineering，2010，58（1）：1-11.

［16］Lin L，H ao X C，Gen M，et al.Network m odeling and evolutionary optimization for scheduling in manufacturing［J］.Journal of Intelligent M anufacturing，2012，23（6）：37-53.

［17］Bertsimas D，G upta S，Lulli G.Dynamic resource allocation：a flexible and tractable m odeling framework［J］.European Journal of O perational Research，2014，236（1）：14-26.

［18］Xu H，Shi Q.Research on equip ment maintenance workload distribution in wartime based on montecarlo method［J］.Science Technology and Engineering，2007，7（20）：27-30.（徐航，石全.基于蒙特卡羅法的戰(zhàn)時(shí)裝備維修工作量分布規(guī)律研究［J］.科學(xué)技術(shù)與工程，2007，7（20）：27-30.）

［19］Wei GQ，Yang YQ.Dispatching model of continuous consumption resources in wartime under insufficient supply［J］. Journal of Systems Engineering and Electronics，2012，34（1）：102-106.（魏國(guó)強(qiáng)，楊永清.供應(yīng)不足條件下戰(zhàn)時(shí)連續(xù)消耗資源調(diào)度模型［J］.系統(tǒng)工程與電子技術(shù)，2012，34（1）：102-106.）

Scheduling algorith m for maintenance tasks under uncertainty

ZENG Bin，Y A O Lu，H U Wei，Y A N G Guang
（Department of Management Engineering，Naval University of Engineering，Wuhan 430033，China）

It is important to schedule the limited maintenance resources efficiently for equipment supportability.In the static modeling stage，a new mathematic description modelis presented considering complex constraints such as power configuration and assignments relationships of maintenance units.In the dynamic stage，a Petri nets modelis established to translate the static mathematic modelinto the dynamic work flow model.In the Petri nets model，a set of firing rules are proposed to implement the constraints of the mathematic model，and the new net structures are designed to simulate the workflow of uncertainties and cooperative process.In order to solve the planning model，an optimization algorithm based on the annealing evolution algorithmis presented in which a simulated annealing algorithm is adopted to solve the maintenance unit assignment problem and a search algorith m is used to generate the schedule results according to the Petri nets model.The simulation results indicates that the algorithm can improve the unit utilization with a high evolution speed.

task scheduling；uncertainty；cooperative maintenance；optimization algorithm

T P 301

A

10.3969/j.issn.1001-506 X.2016.03.19

1001-506 X（2016）03-0595-07

2015-03-23；

2015-07-14；網(wǎng)絡(luò)優(yōu)先出版日期：2015-11-20。

網(wǎng)絡(luò)優(yōu)先出版地址：http：∥w w w.cnki.net/kcms/detail/11.2422.T N.20151120.1758.004.html

國(guó)家自然科學(xué)基金（71201172）資助課題

曾 斌（1970-），男，教授，博士，主要研究方向?yàn)樾畔⒐芾怼?/p>

E-mail：zbtrueice@163.com

姚 路（1979-），男，副教授，博士研究生，主要研究方向?yàn)檠b備管理。

E-mail：yaolu@163.com

胡 煒（1989-），男，碩士研究生，主要研究方向?yàn)樾畔⒐芾怼?/p>

E-mail：majunchao92@163.com

楊 光（1980-），男，講師，博士，主要研究方向?yàn)樾畔⒐芾怼?/p>

E-mail：gavin21st@163.com