崔建國(guó)，謝建文，于明月，蔣麗英，徐曉宇，王瑞凱

(1.沈陽航空航天大學(xué) 自動(dòng)化學(xué)院，沈陽 110136； 2.中航工業(yè)上海航空測(cè)控技術(shù)研究所 故障診斷與健康管理技術(shù)航空科技重點(diǎn)實(shí)驗(yàn)室，上海 201601； 3.沈陽飛機(jī)設(shè)計(jì)研究所 綜合后勤保障部，沈陽 110035)

?

飛機(jī)再次出動(dòng)保障任務(wù)優(yōu)化方法

崔建國(guó)1,2，謝建文1，于明月1，蔣麗英1，徐曉宇3，王瑞凱3

(1.沈陽航空航天大學(xué) 自動(dòng)化學(xué)院，沈陽 110136； 2.中航工業(yè)上海航空測(cè)控技術(shù)研究所 故障診斷與健康管理技術(shù)航空科技重點(diǎn)實(shí)驗(yàn)室，上海 201601； 3.沈陽飛機(jī)設(shè)計(jì)研究所 綜合后勤保障部，沈陽 110035)

軍用飛機(jī)的再次出動(dòng)保障活動(dòng)時(shí)間的長(zhǎng)短，對(duì)飛機(jī)作戰(zhàn)效能的發(fā)揮起到至關(guān)重要的作用。針對(duì)軍用飛機(jī)在多資源約束條件下再次出動(dòng)保障活動(dòng)要求達(dá)到最快捷的實(shí)際軍事需求，以軍用飛機(jī)再次出動(dòng)的部分任務(wù)為研究對(duì)象，提出了一種基于啟發(fā)式優(yōu)先規(guī)則與遺傳算法相結(jié)合的保障任務(wù)優(yōu)化新方法。首先，根據(jù)優(yōu)先規(guī)則確定對(duì)任務(wù)活動(dòng)次序進(jìn)行優(yōu)先規(guī)則編碼。根據(jù)合格節(jié)點(diǎn)判據(jù)，實(shí)現(xiàn)完整的拓?fù)渑判?。然后利用遺傳算法對(duì)任務(wù)需求進(jìn)行初始化，根據(jù)優(yōu)先規(guī)則得到的編碼進(jìn)行遺傳算法的復(fù)制、交叉、變異。從而得到軍用飛機(jī)再次出動(dòng)準(zhǔn)備的最優(yōu)時(shí)間。最終通過提取軍用飛機(jī)再次出動(dòng)的七個(gè)任務(wù)進(jìn)行了試驗(yàn)驗(yàn)證，并且將結(jié)果與人工繪制的結(jié)果進(jìn)行對(duì)比。結(jié)果表明，基于啟發(fā)式的遺傳算法能夠滿足軍用飛機(jī)再次出動(dòng)準(zhǔn)備時(shí)間在多資源約束條件下，時(shí)間最短，具有很高的實(shí)用價(jià)值。

多資源約束；準(zhǔn)備時(shí)間；啟發(fā)式算法；遺傳算法；拓?fù)渑判颍粌?yōu)先規(guī)則

軍用飛機(jī)再次出動(dòng)保障任務(wù)優(yōu)化研究實(shí)質(zhì)上是一個(gè)項(xiàng)目調(diào)度問題。但由于軍用飛機(jī)再次出動(dòng)必須同時(shí)處理活動(dòng)的前后邏輯關(guān)系約束和多資源約束，使得它比一般的進(jìn)度優(yōu)化問題更加難以解決，在理論上屬于NP難問題。軍用飛機(jī)再次出動(dòng)保障任務(wù)優(yōu)化研究是指在滿足各任務(wù)的資源限量約束和緊前緊后關(guān)系的順序約束下，對(duì)飛機(jī)進(jìn)行保障優(yōu)化，給出合適的工作安排次序，使得任務(wù)總工期達(dá)到最短。軍用飛機(jī)再次出動(dòng)保障任務(wù)分析，可為實(shí)際保障工作提供理論參考和指導(dǎo)，是保障飛機(jī)再次出動(dòng)高效完成的基礎(chǔ)，關(guān)系著整個(gè)航空部隊(duì)的快速反應(yīng)能力、出動(dòng)強(qiáng)度和持續(xù)高強(qiáng)度作戰(zhàn)能力，在一定程度上決定著戰(zhàn)斗的勝負(fù)，具有重要的研究?jī)r(jià)值和軍事意義[1]。

目前，軍用飛機(jī)再次出動(dòng)保障任務(wù)優(yōu)化問題在實(shí)際工程中尚缺乏有效的解決方法。文獻(xiàn)[8]介紹了一種多目標(biāo)的優(yōu)化問題，對(duì)資源約束項(xiàng)目調(diào)度的研究只考慮到把不同任務(wù)在不同時(shí)間分配到不同設(shè)備上時(shí)的設(shè)備資源約束，當(dāng)軍用飛機(jī)再次出動(dòng)碰到由于其它輔助資源的短缺而造成的資源約束時(shí)，這種方法就不再有效[3,7]。

本文介紹了一種基于啟發(fā)式優(yōu)先規(guī)則與遺傳算法相結(jié)合的時(shí)間優(yōu)化新方法求解多資源約束的保障任務(wù)優(yōu)化問題。

1 再次出動(dòng)保障任務(wù)優(yōu)化的理論基礎(chǔ)

1.1 啟發(fā)式算法

相對(duì)于精確算法提出來的啟發(fā)式算法。啟發(fā)式算法的求解具有操作簡(jiǎn)單，效率高的優(yōu)點(diǎn)，啟發(fā)式算法的難點(diǎn)在于每一個(gè)待求解問題都需要找出其特有的啟發(fā)式規(guī)則。

啟發(fā)式算法主要包括局部搜索技術(shù)、元啟發(fā)式算法、優(yōu)先規(guī)則的啟發(fā)式算法。本文采用的是基于優(yōu)先規(guī)則的啟發(fā)式算法。優(yōu)先規(guī)則是根據(jù)資源約束相關(guān)或緊前緊后相關(guān)的啟發(fā)式規(guī)則給出在資源限量范圍內(nèi)的各個(gè)活動(dòng)的先后順序。進(jìn)度生成機(jī)制和優(yōu)先規(guī)則是優(yōu)先規(guī)則的調(diào)度的兩要素。進(jìn)度生成機(jī)制從零開始逐步擴(kuò)展局部進(jìn)度，計(jì)劃生成一個(gè)完整的可行方案。進(jìn)度生成機(jī)制主要包括：串行調(diào)度方案和并行調(diào)度方案。優(yōu)先規(guī)則的原則就是在進(jìn)度生成的時(shí)候給與每個(gè)任務(wù)相應(yīng)的優(yōu)先權(quán)，在對(duì)每個(gè)任務(wù)進(jìn)行安排時(shí)算法會(huì)按照給出的任務(wù)優(yōu)先權(quán)來決定任務(wù)的次序及任務(wù)的開始時(shí)間。

1.2 遺傳算法的原理

遺傳算法是受生物進(jìn)化論“適者生存”啟發(fā)提出的一種優(yōu)化的算法，將問題轉(zhuǎn)化為對(duì)染色體編碼，將編碼后的染色體通過復(fù)制、交叉、變異進(jìn)行一代代的進(jìn)化，將最適應(yīng)的個(gè)體保留，得到問題的最優(yōu)解。

(1)遺傳編碼解碼

在利用遺傳算法求解問題之前，首先要把實(shí)際問題表示為染色體位串結(jié)構(gòu)，即對(duì)實(shí)際問題進(jìn)行編碼和解碼運(yùn)算。將問題空間映射到GA編碼空間稱作編碼，而由編碼空間映射問題空間稱為解碼運(yùn)算[15]。

(2)適應(yīng)度函數(shù)

通過遺傳編碼將實(shí)際問題表示為染色體位串結(jié)構(gòu)，根據(jù)適者生存的原則，對(duì)得到的染色體位串進(jìn)行適應(yīng)性評(píng)價(jià)。為了能夠選擇出生存力比較強(qiáng)的個(gè)體引入適應(yīng)度函數(shù)。適應(yīng)度函數(shù)就構(gòu)成個(gè)體的生存環(huán)境。個(gè)體的生存能力由適應(yīng)度函數(shù)值決定。在用遺傳算法進(jìn)行優(yōu)化設(shè)計(jì)的時(shí)，評(píng)價(jià)個(gè)體性能優(yōu)劣的唯一指標(biāo)是適應(yīng)值的相對(duì)大小。適應(yīng)值都是正數(shù)，不可取負(fù)數(shù)，適應(yīng)值是進(jìn)行遺傳操作的主要判斷根據(jù)。在種群中，遺傳個(gè)體的適應(yīng)值越大，則其性能越好，生存的幾率越大。

(3)遺傳算子

遺傳算法的操作算子的三種基本形式是選擇和復(fù)制、交叉、變異。其中遺傳算法的核心就是選擇和復(fù)制、交叉、變異，它們是模擬自然遺傳進(jìn)化過程中的繁殖、雜交和突變現(xiàn)象的主要載體。選擇是指依據(jù)適應(yīng)度從種群中選取個(gè)體操作的過程，復(fù)制是指子代繼承父代的過程，交叉是指在產(chǎn)生子代的過程中染色體之間進(jìn)行了重組，變異是指在子代繼承父代的過程中復(fù)制出現(xiàn)差錯(cuò)產(chǎn)生新的染色體，使子代具有了新的特性[11]。

2 再次出動(dòng)保障任務(wù)優(yōu)化方法

結(jié)合啟發(fā)式算法的優(yōu)先規(guī)則與遺傳算法的優(yōu)點(diǎn)，本文提出的飛機(jī)再次出動(dòng)保障任務(wù)的具體優(yōu)化過程如圖1所示。

圖1所示為再次出動(dòng)保障任務(wù)優(yōu)化方法，為了有效產(chǎn)生能夠處理前后約束的編碼方式，采用一種基于優(yōu)先編碼的方法。根據(jù)編碼產(chǎn)生n個(gè)個(gè)體的初始化種群，對(duì)初始化的種群進(jìn)行評(píng)價(jià)，對(duì)于評(píng)價(jià)結(jié)果判斷是否滿足任務(wù)需求的約束條件。對(duì)于滿足條件的利用遺傳算法，根據(jù)適應(yīng)度函數(shù)確定父代個(gè)體，首先從父代中選取兩個(gè)個(gè)體進(jìn)行復(fù)制，根據(jù)交叉概率產(chǎn)生需要交叉的父代個(gè)體，然后根據(jù)變異原則對(duì)父代個(gè)體變異產(chǎn)生新的個(gè)體。根據(jù)遺傳代數(shù)判斷是否中止，從而完成對(duì)飛機(jī)的再次出動(dòng)時(shí)間進(jìn)行優(yōu)化。

圖1 再次出動(dòng)保障任務(wù)優(yōu)化方法

3 再次出動(dòng)保障任務(wù)優(yōu)化實(shí)例分析

以軍用飛機(jī)再次出動(dòng)所需的常見7個(gè)保障任務(wù)為例，對(duì)以上提出的飛機(jī)再次出動(dòng)保障任務(wù)優(yōu)化方法進(jìn)行實(shí)例分析。

常見的7個(gè)保障任務(wù)分別為機(jī)械外觀檢查、吊艙外觀檢查、導(dǎo)彈自檢、掛架充氮?dú)狻⒄{(diào)倉加水、裝干擾彈、更換發(fā)射裝置，分別對(duì)其編號(hào)為1、2、3、4、5、6、7。活動(dòng)之間受緊前、緊后條件的約束，每一個(gè)活動(dòng)都需要軍械員及電抗員兩類人員，分別用資源1、2代替，每類人員的最大限量為5?，F(xiàn)有如下表1所示的任務(wù)需求。

表1 任務(wù)需求表

活動(dòng)緊前緊后工期(d)資源1、2需求12、3、431、221542、231643、141622、252754、163、4722、375、642、0

為了使任務(wù)需求更加直觀且便于分析研究將其轉(zhuǎn)化為網(wǎng)絡(luò)計(jì)劃任務(wù)圖，如圖2所示。

圖2 網(wǎng)絡(luò)計(jì)劃任務(wù)圖

目標(biāo)函數(shù)如式(1)所示。

minfn

(1)

約束函數(shù)如式(2)所示。

fj-fi≥djall(i,j)∈H

(2)

(3)

式中：n—網(wǎng)絡(luò)計(jì)劃中最后一個(gè)活動(dòng)；fj—活動(dòng)j的完成時(shí)間，j=1,2,…,n；H—相鄰兩個(gè)活動(dòng)邏輯關(guān)系的集合；st—在時(shí)刻t正在進(jìn)行的活動(dòng)；rik—活動(dòng)i對(duì)第k種資源的需求量；bk—第k種資源的總供給量；K—資源總的種類。

式(1)是目標(biāo)函數(shù)，表示最后一項(xiàng)任務(wù)最早的完成時(shí)間，也即活動(dòng)任務(wù)的最短工期；式(2)是邏輯關(guān)系約束即活動(dòng)任務(wù)的先后順序，即任何活動(dòng)在開始之前都必須先完成其所有緊前活動(dòng)；式(3)是資源約束，即不能超出資源限量，在活動(dòng)過程中的任意時(shí)刻所用的某種資源的總量應(yīng)在資源的供應(yīng)量的范圍內(nèi)。

3.1 基于優(yōu)先權(quán)的編碼

一個(gè)活動(dòng)的ID用位置表示，活動(dòng)的優(yōu)先權(quán)用基因的值來表示，如下表2所示?；虻闹凳且粋€(gè)惟一的正整數(shù)，活動(dòng)的優(yōu)先權(quán)由基因的值決定，基因的值越大活動(dòng)的優(yōu)先權(quán)越高。

表2 基于優(yōu)先權(quán)的編碼

位置：活動(dòng)ID1234567值：活動(dòng)優(yōu)先權(quán)3716452

采用一次通過過程即由染色體產(chǎn)生拓?fù)渑判颍匆淮涡缘貜淖蟮接掖_定活動(dòng)。當(dāng)進(jìn)行一個(gè)位置決策時(shí)，若干活動(dòng)可能就這一位置進(jìn)行競(jìng)爭(zhēng)，具有最高優(yōu)先權(quán)的一個(gè)贏得該位置。優(yōu)先權(quán)的任何改變通常導(dǎo)致不同的拓?fù)渑判?，因此這種編碼本質(zhì)上能夠表示給定DAG所有可能的拓?fù)渑判颉?/p>

3.2 拓?fù)渑判?/p>

第一步：初始化

1→t(迭代下標(biāo))

1→PS[t](初始化拓?fù)渑判?

Q1→St(初始化優(yōu)先隊(duì)列)

1→CUT[i],i屬于Q1(初始化割集中邊的數(shù)量)

1→CUT[i],i屬于V-Q1

第二步：執(zhí)行終止測(cè)試。如果PS[t]=n,進(jìn)入第六步，否則t=t+1，繼續(xù)。

第三步：固定第t個(gè)節(jié)點(diǎn)，從優(yōu)先隊(duì)列St中移除具有最高優(yōu)先權(quán)的節(jié)點(diǎn)i*并將其放入向量PS[t]。

第四步：執(zhí)行割集更新CUT[i]= CUT[i]+1,?i∈Qi*

第五步：更新合格節(jié)點(diǎn)集合。對(duì)于?i∈Qi*，如果CUT[i]=dIN(i),將i放入優(yōu)先隊(duì)列St，返回第二步。

第六步：返回完整的拓?fù)渑判騊S[·]。

可得到如圖3所示的拓?fù)渑判颉?/p>

圖3 DAG的拓?fù)渑判?/p>

3.3 優(yōu)化過程與結(jié)果

首先利用項(xiàng)目管理軟件對(duì)任務(wù)需求進(jìn)行分配，結(jié)果如圖4所示。

圖4 項(xiàng)目管理排列的結(jié)果

優(yōu)化前自動(dòng)排列的結(jié)果可以看出資源超限。

圖5 項(xiàng)目管理資源1的使用情況

按照項(xiàng)目管理排列任務(wù)工期為16天，有資源超出限制的情況。由圖5、6可以看出資源1在第八天，資源2在第三四天都有超出資源最大限量的情況。

圖6 項(xiàng)目管理資源2的使用情況

將遺傳算法的遺傳代數(shù)固定為100，雜交率設(shè)為0.3，變異率設(shè)為0.1，種群規(guī)模為30。為了使輸出結(jié)果更加直觀，經(jīng)遺傳算法改進(jìn)后項(xiàng)目管理排列的輸出結(jié)果如圖7所示。

圖7 改進(jìn)后項(xiàng)目管理排列結(jié)果

圖8 遺傳算法資源1的使用情況

圖9 遺傳算法資源2的使用情況

人工繪制的結(jié)果與遺傳算法優(yōu)化后的所用的天使相等，都可以滿足資源約束條件的限制。

以表格的形式對(duì)比三種方法的優(yōu)化情況。

遺傳算法優(yōu)化后的結(jié)果滿足資源約束的條件，最短的工期是18天。而project繪制不能滿足資源限量約束條件，人工繪制優(yōu)化時(shí)間比較耗時(shí)。

表3 遺傳算法與其他方法的對(duì)比

遺傳算法項(xiàng)目管理軟件人工繪制優(yōu)化時(shí)間/天181618資源限量滿足不滿足滿足緊前緊后滿足滿足滿足運(yùn)算時(shí)間快快耗時(shí)

4 結(jié)論

對(duì)比表3中不同方法可知，遺傳算法能夠在同時(shí)滿足“資源限量”和“緊前緊后”的約束條件下得到最優(yōu)的結(jié)果。盡管人工繪制的優(yōu)化時(shí)間與遺傳算法的優(yōu)化時(shí)間都是18天，但由于遺傳算法所需的“運(yùn)算時(shí)間”短，而人工繪制需要的“運(yùn)算時(shí)間”長(zhǎng)，所以，應(yīng)采用基于啟發(fā)式遺傳算法的優(yōu)化方案并可應(yīng)用于飛機(jī)再次出動(dòng)保障任務(wù)優(yōu)化工作中。

[1]李海濤.基于遺傳算法的工程項(xiàng)目多資源均衡優(yōu)化研究[D].大連:大連理工大學(xué)，2012.

[2]MARSZALEK M,SCHMID C.Spatial weighting for bag-of-features[C].2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition,New York,2006:2118-2125.

[3]LAZEBNIK S,SCHMID C,PONCE J.Beyond bags of features:spatial pyramid matching for recognizing natural scene categories[C].2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition,New York,2006.

[4]CHUM O,ZISSERMAN,A.An exemplar model for learning object classes[C].2007 IEEE Computer Society Conference on Computer Vision and Pattern Recognition,Minneapolis ,2007.

[5]玄光男,程潤(rùn)偉.遺傳算法與工程優(yōu)化[M].北京:清華大學(xué)出版社,2004.

[6]黎詠梅.基于小生境遺傳算法的風(fēng)火電節(jié)能調(diào)度研究[J].機(jī)電一體化,2013,19(2):51-54.

[7]柳青紅,袁逸萍,李曉娟.基于改進(jìn)遺傳算法的作業(yè)車間調(diào)度[J].機(jī)械工程與自動(dòng)化,2014(6):1-3.

[8]方紅雨,崔遜學(xué).基于遺傳算法的調(diào)度問題研究[J].電腦與信息技術(shù),2001,9(2):1-5.

[9]劉淳安.動(dòng)態(tài)多目標(biāo)優(yōu)化進(jìn)化算法及其應(yīng)用[M].北京:科學(xué)出版社,2011.

[10]萬敏,唐敦兵,王雷,等.求解車間調(diào)度問題的改進(jìn)型自適應(yīng)遺傳算法[J].機(jī)械科學(xué)與技術(shù),2011,30(1):39-42.

[11]王秋芬,楊澤平,梁道雷.一種改進(jìn)的車間調(diào)度問題算法[J].科學(xué)技術(shù)與工程,2013,13(11):2997-3001.

[12]王宏,林丹,李敏強(qiáng).一種求解多目標(biāo)資源受限項(xiàng)目調(diào)度的遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(7):1-46.

[13]許繼影.矩形件優(yōu)化排樣的混合啟發(fā)式方法[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(13):234-239.

[14]黃可坤.改進(jìn)遺傳算法求解流水車間調(diào)度問題[J].嘉應(yīng)學(xué)院學(xué)報(bào)，2012,30(5):8-12.

[15]趙詩奎.基于遺傳算法的柔性資源調(diào)度優(yōu)化方法研究[D].浙江：浙江大學(xué)，2013.

(責(zé)任編輯：劉劃 英文審校：齊義文)

Time optimization method of military aircraft turnaround operations

CUI Jian-guo1,2,XIE Jian-wen1,YU Ming-yue1,JIANG Li-ying1,XU Xiao-yu3,WANG Rui-kai3

(1.College of Automation,Shenyang Aerospace University,Shenyang 110136，China; 2.Aviation Key Laboratory of Science and Technology on Fault Diagnosis and Health Management，Shanghai Aero Measurement & Control Technology Research Institute,Shanghai 201601,China;3.Integrated Logistics Support Department,Shenyang Aircraft Design & Research Institute,Shenyang 110035，China)

The preparation time of military aircraft operations plays a vital role in the combat effectiveness of aircraft.To achieve the actual military requirements,a new method based on the combination of heuristic priority rules and genetic algorithm was proposed in this paper ,and a part task of military aircraft turnaround was regarded as research objects. First,the task order was encoded in terms of the priority rules.According to the eligibility criteria,the complete topological sort was implemented.Then,the genetic algorithm was used to initialize the task requirements.The replication,crossover and mutation of genetic algorithm were conducted based on the codes obtained from the priority rules.Thus,the optimal time for the military aircraft turnaround was obtained. Finally,simulation validation was performed using seven tasks of military aircraft and the results were compared with those of the drawings.The results show that the heuristic genetic algorithm can achieve the shortest preparation time of military aircraft turnaround under multi-resource constraintsand and a high practical value.

ultiple resource constraints;preparation time;heuristic algorithm;genetic algorithm;topological sort;priority rules

2015-10-28

國(guó)家自然科學(xué)基金(項(xiàng)目編號(hào)：51605309)；國(guó)防預(yù)研項(xiàng)目(項(xiàng)目編號(hào)：A0520110023)；國(guó)防基礎(chǔ)科研項(xiàng)目(項(xiàng)目編號(hào)：Z052012B002)；遼寧省自然科學(xué)基金聯(lián)合封閉基金(項(xiàng)目編號(hào)：2014024003)；航空科學(xué)基金(項(xiàng)目編號(hào)：20153354005)。

崔建國(guó)(1963-)，男，遼寧本溪人，教授，主要研究方向：飛行器綜合健康管理，E-mail:gordon_cjg@163.com。

信息科學(xué)與工程

2095-1248(2016)05-0043-06

V19

A

10.3969/j.issn.2095-1248.2016.05.009