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

考慮不確定因素影響的保障任務調度算法

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

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

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

網址：www.sys-ele.com

0 引 言

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

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

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

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

（4）戰(zhàn)時各保障單元需要服務的作戰(zhàn)單元不僅數量多，而且距離遠，即存在保障地點分散等的限制，需要保障單元花費較多時間才能運輸到保障地點，這也是常規(guī)作業(yè)調度忽視的問題。

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

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

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

1 調度模型

1.1 問題描述及數學模型

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

表1 數學符號定義

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

利用保障單元Rk在時間t內完成的工作量nij可由式（2）計算：

為了保證能按時完成保障工作，工作開始時刻tiRjk（s）和結束時刻還需要引入如下約束條件，其中

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

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

基于以上約束條件，調度問題的目標函數可用式（7）表達：

1.2 混合Petri網模型

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

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

圖1 保障工作調度的混合Petri網模型

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

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

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

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

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

圖3 不確定條件模型

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

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

1.4 約束條件的Petri建模

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

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

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

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

（4）根據保障工作先后次序要求，前一個工作Wj-1完成后才能開始下一個工作Wj，這與式（5）對應。例如如果P12的令牌數量少于45，即使其他條件都滿足，任務T124和任務T125也無法開始。

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

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

根據混合Petri網本身的激發(fā)特點，保障工作時間段之間不會出現重疊，所以式（3）不需要有專門規(guī)則表達。從以上描述可看出該Petri網模型可以對保障任務的調度過程進行建模。模型中所有的約束條件都由離散庫所或令牌定義，通過增加離散庫所或令牌可以方便的補充新的約束。

2 算法描述

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

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

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

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

2：初始化方案x，初始化最小適應度函數min

3：調用第2階段的函數gaP L（x）計算適應度Fx

4：while不滿足終止條件do

5：fori=0 toN

6：產生新方案x’

7：調用gaP L（x） 計算適應度Fx’

8：if（Fx’＜Fx）then

9：接受新方案x’ 作為當前解，代替x

10：else

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

12：接受新方案x’作為當前解，代替x’

13：end if

14：end if

15：if（Fx’＜min）

16：接受新適應值Fx’代替min，存儲x’

17：end if

18：end for

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

20：end while

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

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

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

ProceduregaP L（x）

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

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

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

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

5：調用適應度計算函數evaluation（c）；

6：while不滿足終止條件do

7：進行復制，雜交和變異；

8：調用適應度計算函數evaluation（c）；

9：end while evaluation（c）

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

2：建立混合 Petri網的離散部分；

3：初始化時間步長τ，當前時刻t=0；

4：while沒有完成所有任務do

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

6：激發(fā)變遷并更新對應庫所的令牌；

7：end if

8：t=t+τ；

9：更新任務間空閑時間和運輸時間之和；

10：end while

11：if發(fā)現最優(yōu)適應度then

12：更新當前適應度，優(yōu)先級和調度方案；

13：end if

14：end for

2.3 消除死鎖

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

3 實驗驗證

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

3.1 保障單元指派算法對性能的影響

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

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

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

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

因為保障工作之間的等待時間Wij對算法結果的質量有較大影響，所以當等待時間不同且不考慮其他約束時，如果把保障任務按Wij排序就可以得到最佳調度結果。圖5顯示了按Wij排序對結果質量的影響。圖中遺傳算法初始群體所包括的染色體分別為不排序，一次排序和全排序。很明顯圖中“不排序”的曲線收斂速度最慢，而初始群體“全排序”時能得到較高的收斂速度和算法質量。而“一次排序”時適應度會受到諸如運輸時間等因素的影響，所以它的進化速度和算法質量要比“全排序”差。從3條曲線的結果可以看出按照等待時間對保障任務排序可以提高進化的收斂速度。

圖5 染色體排序結果

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

圖6 不同利用率的影響

3.3 調度結果

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

表2 調度結果的統(tǒng)計信息

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

4 總 結

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

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

［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.（張立民，彭樂，劉敬虎，張曉軍.求解裝備保障任務調度問題的改進粒子群算法.計算機工程與設計［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.（朱昱，宋建社，王正元.一種基于最大保障時間的戰(zhàn)時裝備維修任務調度［J］.系統(tǒng)工程與電子技術，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)宇，鄭曉龍.不確定資源受限項目調度研究綜述［J］.控制與決策，2014，29（4）：577-514.）

［4］H uang Y，Fan Y.M odeling uncertainties in emergency service resource allocation［J］.Journal of Infrastructure Systems，2011，17（1）：35-41.

［5］Martins M S R，Fuchs 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，Fontema 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)時裝備維修工作量分布規(guī)律研究［J］.科學技術與工程，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.（魏國強，楊永清.供應不足條件下戰(zhàn)時連續(xù)消耗資源調度模型［J］.系統(tǒng)工程與電子技術，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；網絡優(yōu)先出版日期：2015-11-20。

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

國家自然科學基金（71201172）資助課題

曾 斌（1970-），男，教授，博士，主要研究方向為信息管理。

E-mail：zbtrueice@163.com

姚 路（1979-），男，副教授，博士研究生，主要研究方向為裝備管理。

E-mail：yaolu@163.com

胡 煒（1989-），男，碩士研究生，主要研究方向為信息管理。

E-mail：majunchao92@163.com

楊 光（1980-），男，講師，博士，主要研究方向為信息管理。

E-mail：gavin21st@163.com