蘇析超, 韓　維, 蕭　衛(wèi), 蔣婷婷

(1. 海軍航空工程學(xué)院飛行器工程系, 山東 煙臺 264001; 2. 中國船舶工業(yè)系統(tǒng)工程研究院,北京 100094; 3. 海軍航空工程學(xué)院研究生管理大隊(duì), 山東 煙臺 264001)

?

基于Memetic算法的艦載機(jī)艦面一站式保障調(diào)度

蘇析超1, 韓維1, 蕭衛(wèi)2, 蔣婷婷3

(1. 海軍航空工程學(xué)院飛行器工程系, 山東 煙臺 264001; 2. 中國船舶工業(yè)系統(tǒng)工程研究院,北京 100094; 3. 海軍航空工程學(xué)院研究生管理大隊(duì), 山東 煙臺 264001)

面向艦載機(jī)艦面保障效率和資源利用率等效能指標(biāo),系統(tǒng)分析了一站式保障流程約束和資源約束條件,建立了艦載機(jī)多機(jī)艦面一站式保障調(diào)度的數(shù)學(xué)優(yōu)化模型。針對傳統(tǒng)優(yōu)化算法難以求解大規(guī)模調(diào)度問題,提出了一種Memetic算法。首先,為了使可更新類資源負(fù)載均衡化,采用一種嵌入資源分配策略的串行調(diào)度方案;其次,設(shè)計(jì)了一種基于子拓?fù)浣Y(jié)構(gòu)的自適應(yīng)變異策略以提升算法的探索能力,并引入基于模擬退火機(jī)制的局部搜索方法;最后，基于不同調(diào)度規(guī)模案例的仿真結(jié)果驗(yàn)證了模型和算法的可行性和有效性。

艦載機(jī); 艦面一站式保障;Memetic算法; 優(yōu)化

0　引　言

作為航母作戰(zhàn)編隊(duì)攻防體系的核心,艦載機(jī)承擔(dān)了航母全系統(tǒng)和航母戰(zhàn)斗群的絕大多數(shù)作戰(zhàn)使命,其艦面保障是影響出動架次率乃至航母編隊(duì)作戰(zhàn)效能的關(guān)鍵因素。艦載機(jī)艦面保障涉及復(fù)雜的流程約束、資源約束和環(huán)境約束,隨著艦載機(jī)機(jī)群規(guī)模的增加,傳統(tǒng)的人工調(diào)度已難以滿足其實(shí)時性、魯棒性和優(yōu)化性能。因此,對艦載機(jī)多機(jī)艦面保障流程安排和資源分配進(jìn)行科學(xué)的規(guī)劃和決策具有重要意義[1]。

近年來,艦載機(jī)調(diào)度已成為國內(nèi)外研究的一個新興的熱點(diǎn)。針對艦載機(jī)艦面調(diào)運(yùn)規(guī)劃,文獻(xiàn)[2]提出了基于改進(jìn)A*算法的甲板滑行路徑規(guī)劃方法;文獻(xiàn)[3]在艦載機(jī)運(yùn)動約束模型的基礎(chǔ)上,引入了“凸殼模型”和碰撞檢測以實(shí)現(xiàn)調(diào)運(yùn)的安全性。美國的麻省理工學(xué)院通過對一款名為DCAP(deckoperationcourseofactionplanner)[4]的飛行甲板輔助決策平臺的開發(fā),建立了甲板周期內(nèi)艦載機(jī)調(diào)度的線性整數(shù)規(guī)劃模型,并研究了基于分支定界的精確算法[5]、基于逆向強(qiáng)化學(xué)習(xí)的機(jī)器學(xué)習(xí)方法[6]和基于差分進(jìn)化算法的智能優(yōu)化[7]等方法在艦載機(jī)機(jī)群全流程調(diào)度問題中的應(yīng)用。文獻(xiàn)[8]引入Multi-agent技術(shù)并基于艦載機(jī)作業(yè)流程建立了3層混合控制模型架構(gòu),研究了考慮故障擾動等因素的艦載機(jī)動態(tài)調(diào)度問題。文獻(xiàn)[9]針對單機(jī)機(jī)組保障模式的不足,建立了多機(jī)一體化機(jī)務(wù)保障調(diào)度模型,可有效提升保障人員的利用率。

但是,由于目前航母資源設(shè)置的局限性,無法滿足各停機(jī)位均能供給各類資源,使得艦載機(jī)在航空保障過程中需要頻繁的調(diào)運(yùn)作業(yè),從而降低了保障作業(yè)效率和艦載機(jī)的出動架次率。

為此,本文針對艦載機(jī)一站式保障的發(fā)展趨勢和其技術(shù)特征[10],建立了艦載機(jī)機(jī)群的艦面一站式保障調(diào)度模型,并設(shè)計(jì)了一種基于子拓?fù)渚W(wǎng)局部災(zāi)變策略的Memetic算法,以提升針對中、大規(guī)模調(diào)度問題的求解性能。

1　艦載機(jī)艦面一站式保障問題建模

1.1一站式保障流程分析與問題描述

艦載機(jī)艦面一站式保障是指艦載機(jī)在航空保障流程約束和資源配置約束條件下,不需要往返地調(diào)運(yùn)即可在甲板同一個停機(jī)站位集中完成各項(xiàng)出動前保障作業(yè),從而提升機(jī)群的快速出動能力。一站式保障實(shí)現(xiàn)的前提和關(guān)鍵在于各類保障資源的優(yōu)化配置。根據(jù)資源的性質(zhì)和作用,可將其分解為:可更新資源、消耗類資源、空間資源。

(1) 可更新資源,主要包括保障人員和保障設(shè)備/設(shè)施。其中保障人員按照保障作業(yè)的性質(zhì)可劃分為機(jī)械、軍械、航電、特設(shè)等專業(yè)類型,每一類保障人員均包含若干組保障人員;保障設(shè)備則包括提供電燃?xì)庖旱认念愘Y源的固定站點(diǎn)和移動保障車。與移動保障車的甲板機(jī)動保障不同,固定資源站僅可對以管線長度為半徑的圓域內(nèi)的艦載機(jī)提供保障,圖1為庫茲涅佐夫號航母某類資源站覆蓋的停機(jī)位示意圖。

(2) 消耗類資源,指保障過程中不斷消耗的電燃?xì)庖汉蛷椝幍任镔Y資源。這類資源不僅總量有限制,而且由于航母技術(shù)和空間布局制約,存在任意時刻供應(yīng)量的限制,如額定燃油壓力僅能滿足一定數(shù)量的艦載機(jī)同時進(jìn)行加油作業(yè)。

(3) 空間資源,主要考慮對艦載機(jī)實(shí)施保障作業(yè)所需的諸如座艙、起落架倉等的站位空間。

圖1　庫茲涅佐夫號航母某類資源站覆蓋停機(jī)位示意圖Fig.1　Distribution map of some resource stations on the admiral Kuznetsov aircraft carrier

對任一艦載機(jī)i,其保障工序流程可表示為有向網(wǎng)絡(luò)圖Di=(Vi,Ai),其中,節(jié)點(diǎn)Vi表示保障工序集合,有向弧Ai表示各工序間的緊前緊后約束關(guān)系。本文研究的目的,即在保證流程約束條件下,對各類資源進(jìn)行合理地分配和調(diào)度,以實(shí)現(xiàn)機(jī)群快速保障和保障資源均衡使用,進(jìn)而提升艦載機(jī)多機(jī)的出動效能。

1.2一站式保障調(diào)度數(shù)學(xué)模型

首先定義模型參數(shù)如下:

I={1,2,…,n}為艦載機(jī)集合,其中n為艦載機(jī)數(shù)量；

Ji={1,2,…,|Ji|}為艦載機(jī)i的工序集,其中|Ji|為工序數(shù)；

Kp={1,2,…,|Kp|}為保障專業(yè)種類集合；

Ks={1,2,…,|Ks|}為站位空間種類集合；

Kr={1,2,…,|Kr|}為保障設(shè)備種類集合；

Kw={1,2,…,|Kw|}為消耗性資源種類集合；

Lpk={1,2,…,|Lpk|}為第k(k∈Kp)種專業(yè)保障人員集合；

Lsk={1,2,…,|Lsk|}為第k(k∈Ks)類空間集合；

Lrk={1,2,…,|Lrk|}為第k(k∈Kr)種保障設(shè)備集合；

Rkl為第k(k∈Kr)種第l個保障設(shè)備所覆蓋到的艦載機(jī)集合；

rpijk為艦載機(jī)i的第j道保障工序?qū)Φ趉(k∈Kp)類專業(yè)保障人員的需求量；

rsijk為艦載機(jī)i的第j道保障工序?qū)Φ趉(k∈Ks)類空間站位的需求變量；

rijk為艦載機(jī)i的第j道保障工序?qū)Φ趉(k∈Kr)種保障設(shè)備的需求量；

rwijk為艦載機(jī)i的第j道保障工序?qū)Φ趉(k∈Kw)類消耗性資源的需求量；

Pij為工序Oij的緊前工序集合；

Tij為工序Oij的保障作業(yè)時間；

Sij、Eij分別為第i架艦載機(jī)第j道工序的開始保障時間和結(jié)束保障時間；

Eopk、Eork′分別為第k(k∈Kp)類專業(yè)保障人員和第k′(k′∈Kr)類保障設(shè)備的閑忙比方差；

Bpkl、Brk′l′分別為為第k(k∈Kp)類專業(yè)中第l個保障人員和第k′(k′∈Kr)類第l′個保障設(shè)備的工作時間。

決策變量定義為

根據(jù)艦載機(jī)調(diào)度的指標(biāo)要求,優(yōu)化的目標(biāo)選取分層雙目標(biāo),即在滿足最小化最大保障完工時間的前提下,使得可更新資源的閑忙比方差和最小

(1)

式中,第k類專業(yè)的閑忙比方差

(2)

工作時間Bpkl可表示為

(3)

第k類設(shè)備的閑忙比方差Eork和其第l個設(shè)備的工作時間Brkl可分別參照式(2)和式(3)給出。

約束條件包括

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

表示艦載機(jī)i中同時進(jìn)行保障的不同工序均對某類設(shè)備有需求時,僅需一個設(shè)備即可滿足,如一個供電設(shè)備可滿足若干并行通電作業(yè)工序;式(10)為消耗性資源約束,即任意時刻對某消耗性資源的需求不大于其供給量。

2　Memetic算法設(shè)計(jì)

由上述模型可以看出,艦載機(jī)多機(jī)一站式保障調(diào)度問題本質(zhì)上屬于一類具有非確定性多項(xiàng)式-難(non-deterministicpolynomial-hard,NP-hard)特性的資源受限多項(xiàng)目調(diào)度問題(resource-constrainedmulti-projectschedulingproblem,RCMPSP)[11-12]。若按照各類資源的選擇和工序保障順序逐一編碼,不僅編碼復(fù)雜度高,且求解效率隨著艦載機(jī)保障數(shù)量規(guī)模增大而急劇下降,計(jì)算量耗費(fèi)大。因此,本文借鑒RCMPSP的群智能優(yōu)化求解方法,并嵌入可更新性資源選擇的啟發(fā)式規(guī)則,在確保求解精度的前提下提升了解算的效率。

Memetic算法是一種基于種群的全局搜索和基于個體的局部搜索的混合算法,自1989年由Moscato提出后,已經(jīng)在諸多領(lǐng)域得到了廣泛的應(yīng)用[13],特別是在解決具有多極值特性的調(diào)度問題具有很強(qiáng)的尋優(yōu)能力和普適性[14-15]。本文在求解RCMPSP問題的標(biāo)準(zhǔn)遺傳算法(geneticalgorithm,GA)的基礎(chǔ)上,設(shè)計(jì)了改進(jìn)的Memetic算法如下。

2.1解的編碼

編碼方案是影響算法搜索效果和效率的重要因素,求解RCMPSP問題的主要編碼策略包括任務(wù)列表編碼、優(yōu)先數(shù)編碼和優(yōu)先規(guī)則編碼。其中,任務(wù)列表編碼相對于后兩者具有更有效的搜索空間,因此本文采用任務(wù)列表的編碼策略。染色體個體可表示為滿足流程約束關(guān)系的作業(yè)排列X=[x1,x2,…,xk,…,xnm],其中,xk為二元數(shù)組(i,j)分別表示艦載機(jī)編號及其工序號,nm為所有工序數(shù)總和。

2.2解碼操作

解碼是實(shí)現(xiàn)染色體編碼向調(diào)度方案映射的關(guān)鍵步驟,通過解碼確定各艦載機(jī)工序的保障開始/結(jié)束時間以及資源的分配。然而經(jīng)典的串行調(diào)度生成機(jī)制和并行調(diào)度生成機(jī)制僅考慮任意時刻資源占用量,而不考慮資源的具體分配[16]。為了更均衡地利用各類資源,分別設(shè)計(jì)保障人員和保障設(shè)備的分配規(guī)則:

(2) 基于覆蓋范圍內(nèi)剩余工序作業(yè)時間最少優(yōu)先(minimumtotalprocessingtimeremainingincoveringarea,MTRCA)的保障設(shè)備分配規(guī)則,表示當(dāng)工序Oij需要第k類設(shè)備進(jìn)行保障,則對覆蓋到艦載機(jī)i的所有k類設(shè)備,分別計(jì)算其覆蓋范圍內(nèi)對應(yīng)的艦載機(jī)待保障工序時間和

并選取最小值所對應(yīng)的保障設(shè)備。其中令Sg表示已調(diào)度集合,則覆蓋域內(nèi)待分配工序集

通過MTRCA分配,一方面緩解覆蓋較多艦載機(jī)工序的設(shè)備的使用沖突,使工作負(fù)載均衡;另一方面避免設(shè)備使用過度集中造成保障總時間的延遲。當(dāng)存在待保障工序時間和相同的設(shè)備時,采用MATF規(guī)則進(jìn)行分配。

Initialization:g=1,Sg=?;

While|Sg|

(i*,j*)=xg;

ESi*j*=max{Eij+dij|(i,j)∈Pi*j*};

For?k∈Kp∧rpi*j*k>0

Endfor

For?k∈Kr∧ri*j*k>0

Endfor

Sg+1=Sg∪{(i*,j*)},g=g+1;

End

2.3適應(yīng)度分配與選擇算子

采用基于排序的適應(yīng)度分配法,以避免適應(yīng)度函數(shù)選取不當(dāng)而降低求解的魯棒性。對于規(guī)模為Np的種群,按照個體最大保障完成時間Cmax進(jìn)行排序,即Cmax越小排序越高,設(shè)選擇壓力Π(Π∈[1,2]),表示最佳個體被選中的概率與平均選中概率的比值,pi種群中個體i的位序,則基于線性排序的適應(yīng)度計(jì)算方法可表示為

(12)

根據(jù)式(12)所得適應(yīng)度分配,按照輪盤賭策略選擇個體進(jìn)行種群更新。

2.4交叉算子

2.5基于子拓?fù)涔ば蚓W(wǎng)的自適應(yīng)變異策略

變異策略是增加種群多樣性,避免陷入局部最優(yōu)的重要手段,常規(guī)的基于Insertion或Inerchange的變異策略僅能產(chǎn)生較小的鄰域變換范圍,對于較大規(guī)模的調(diào)度問題則難以跳出局部最優(yōu)。為此,本文針對大規(guī)模的RCMPSP問題特性,設(shè)計(jì)一種新的鄰域結(jié)構(gòu)如下:

(1) 針對染色體個體X根據(jù)概率Pm選擇艦載機(jī)i,并從X中提取其工序排列πi;

(4) 將重排的序列隨機(jī)插入至原染色體X的[dx1,dx2]位置區(qū)間,得到新的染色體Y。

該鄰域結(jié)構(gòu)一方面通過基于子拓?fù)涔ば蚓W(wǎng)的重排實(shí)現(xiàn)艦載機(jī)內(nèi)的工序排序的變動,另一方面通過重插入實(shí)現(xiàn)艦載機(jī)之間的工序變換,從未增大了搜索空間。此外,為了進(jìn)一步增強(qiáng)變異策略在進(jìn)化后期避免陷入局部極值的能力,對變異概率采用自適應(yīng)變化策略

(13)

(14)

2.6基于模擬退火機(jī)制的局部搜索策略

通過引入局部搜索策略可進(jìn)一步引導(dǎo)算法在多局部極值解空間中進(jìn)行高效地深度搜索,增強(qiáng)算法的全局尋優(yōu)能力。在執(zhí)行了交叉和變異的全局搜索后,選取種群中100p%的最優(yōu)個體,并采用基于Inerchange的鄰域結(jié)構(gòu)和模擬退火選擇機(jī)制進(jìn)行局部搜索:

步驟 1對選取的個體Spbest,令k=1。

步驟 2按概率Pl選取基因位xk=(i,j),找到其緊前工序集所在Spbest中的最大基因位xk′=(i,h),h∈Pij。

步驟 5令k=k+1,若k

基于上述各部分算法描述,求解艦載機(jī)一站式保障調(diào)度問題的Memetic算法基本流程圖如圖2所示。

圖2　Memetic算法流程圖Fig.2　Flow diagram of Memetic algorithm

3　仿真分析

以庫茲涅佐夫號航母為實(shí)例分析對象,如圖1所示，某出動任務(wù)想定需要對8架艦載機(jī)進(jìn)行出動前的保障作業(yè)。任一艦載機(jī)i的單機(jī)保障工序流程如圖3所示,其中除編號1和編號19為單機(jī)虛擬開始/結(jié)束工序,其余編號工序右上角括號內(nèi)分別表示需要的保障人員專業(yè)類型和設(shè)備類型,且需求量均為1,虛線連接的工序表示因站位空間的限制而不能同時進(jìn)行。通過添加整體保障任務(wù)的虛擬開始/結(jié)束節(jié)點(diǎn)可將各艦載機(jī)保障工序流程合并為多機(jī)保障網(wǎng)絡(luò)流程。

圖3　艦載機(jī)單機(jī)保障工序流程圖Fig.3　Support process flow chart of single aircraft

各艦載機(jī)工序保障的時間參數(shù)和設(shè)備對艦載機(jī)的保障覆蓋情況分別如表1和表2所示。

表1 保障工序時間參數(shù)表

表2中單元格的數(shù)字集合表示該列設(shè)備類型可覆蓋到該行的艦載機(jī)的設(shè)備集合。此外,參與保障的5類專業(yè)保障人員的數(shù)量分別為|Lp1|=4,|Lp2|=4,|Lp3|=6,|Lp4|=4,|Lp5|=4;5類設(shè)備資源分別對應(yīng)5類可消耗性資源,例如工序Oij需要Kr1類設(shè)備保障的同時也需要Kw1類消耗性資源供給,且各類消耗性資源的供給限制可表示[Nw1,Nw2,…,Nw5]=[6,5,2,4,2],其中Nwk表示第k(k∈Kw)類消耗性資源能同時供給Nwk架艦載機(jī)進(jìn)行保障作業(yè)。

表2　設(shè)備對艦載機(jī)保障覆蓋關(guān)系

將GA、IGA和Memetic算法分別求得的最優(yōu)解進(jìn)化曲線進(jìn)行對比,如圖4所示,并結(jié)合表3的對比分析可以看出,本文所提出的Memetic算法不僅具有較強(qiáng)的全局搜索能力和收斂速度,且算法更穩(wěn)定,魯棒性更強(qiáng);而通過比較基于本文所設(shè)計(jì)變異策略的IGA和標(biāo)準(zhǔn)GA算法,驗(yàn)證了

表3　算法性能對比

圖4　最優(yōu)解收斂對比曲線Fig.4　Comparison diagram of optimal convergence

圖5　最優(yōu)調(diào)度甘特圖Fig.5　Gantt chart of optimal scheduling

為了檢驗(yàn)Memetic算法求解中、大規(guī)模調(diào)度問題的優(yōu)越性,另外分別在相同保障條件下進(jìn)行4機(jī)和12機(jī)出動的仿真對比,算法設(shè)置相同,得到出動保障效率參數(shù)如表4所示。通過仿真可以看出,在保障規(guī)模較小的情況下,3種算法基本上均能以較大概率收斂至最優(yōu)解或次優(yōu)解,而隨著艦載機(jī)規(guī)模的增加,3種算法的求解性能差距拉大,GA和IGA算法往往收斂不到最優(yōu)解,而Memetic算法依然保持較好的收斂性和魯棒性。

表4　不同出動規(guī)模下算法性能對比

4　結(jié)　論

本文針對艦載機(jī)艦面一站式保障調(diào)度問題,通過系統(tǒng)分析艦載機(jī)保障的流程約束和各類資源約束,以優(yōu)化保障時間和可更新資源利用率方差為目標(biāo),建立了問題的數(shù)學(xué)模型。在此基礎(chǔ)上,設(shè)計(jì)了一種基于子拓?fù)浣Y(jié)構(gòu)的變異策略和基于模擬退火機(jī)制局部搜索的Memetic算法求解該模型。通過以庫茲涅佐夫號航母為背景的仿真實(shí)例驗(yàn)證了模型的可行性,以及算法對于中、大規(guī)模保障調(diào)度問題求解的有效性。在今后研究中,將著力研究算法在實(shí)際調(diào)度中的時效性問題。

[1]HanW,WangQG. Conspectus of aircraft carrier and carrier plane[M].Yantai:NavalAeronauticalandAstronauticalUniversityPress, 2009: 37-41. (韓維, 王慶官. 航母與艦載機(jī)概論[M].煙臺: 海軍航空工程學(xué)院出版社, 2009: 37-41.)

[2]WuY,QuXJ.Pathplanningfortaxiofcarrieraircraftlaunching[J].Science China Technological Sciences, 2013, 56(6): 1561-1570.

[3]HanW,SiWC,DingDC,etal.Multi-routesdynamicplanningondeckofcarrierplanebasedonclusteringPSO[J].Journal of Beijing University of Aeronautics and Astronautics, 2013, 39(5): 610-614. (韓維, 司維超, 丁大春, 等. 基于聚類PSO算法的艦載機(jī)艦面多路徑動態(tài)規(guī)劃[J].北京航空航天大學(xué)學(xué)報(bào), 2013, 39(5): 610-614.)

[4]RyanJC,CummingsML,RoyN,etal.Designinganinteractivelocalandglobaldecisionsupportsystemforaircraftcarrierdeckscheduling[C]∥Proc.of the AIAA Infotech@ Aerospace Conference, 2011.

[5]RyanJC,BanerjeeAG,CummingsML,etal.Comparingtheperformanceofexpertuserheuristicsandanintegerlinearprograminaircraftcarrierdeckoperations[J].IEEE Trans. on Cybernetics, 2014, 44(6): 761-773.

[6]MichiniB,JonathanP.Ahuman-interactivecourseofactionplannerforaircraftcarrierdeckoperations[C]∥Proc.of the AIAA Infotech @ Aerospace Conference, 2011.

[7]DastidarRG,FrazzoliE.Aqueueingnetworkbasedapproachtodistributedaircraftcarrierdeckscheduling[C]∥Proc.of the AIAA Infotech @ Aerospace Conference, 2011.

[8]FengQ,ZengSK,KangR.AMAS-basedmodelfordynamicschedulingofcarrieraircraft[J].Acta Aeronautica et Astronautica Sinica,2009,30(11):2119-2125.(馮強(qiáng),曾聲奎,康銳.基于MAS的艦載機(jī)動態(tài)調(diào)度模型[J].航空學(xué)報(bào),2009,30(11):2119-2125.)

[9]HanW,SuXC,ChenJF.Integratedmaintenancesupportschedulingmethodofmulti-carrieraircrafts[J].Systems Engineering and Electronics,2015,37(4):809-816.(韓維,蘇析超,陳俊鋒.艦載機(jī)多機(jī)一體化機(jī)務(wù)保障調(diào)度方法[J].系統(tǒng)工程與電子技術(shù),2015,37(4): 809-816.)

[10]LiuXC.Technicalfeaturesandcriticaltechnologiesforthe“pit-stop”aircraftservicingadoptedbyfordclassaircraftcarriers[J].Chinese Journal of Ship Research, 2013, 8(6): 1-5. (劉相春. 美國“福特”級航母“一站式保障”技術(shù)特征和關(guān)鍵技術(shù)分析[J].中國艦船研究, 2013, 8(6): 1-5.)

[11]HartmannS,BriskornD.Asurveyofvariantsandextensionsoftheresource-constrainedprojectschedulingproblem[J].European Journal of Operational Research, 2014, 207(1): 1-14.

[12]WangL,FangC.Ahybridestimationofdistributionalgorithmforsolvingtheresource-constrainedprojectschedulingproblem[J].Expert Systems with Application, 2012, 39(3): 2451-2460.

[13]NeriF,CottaC.MemeticalgorithmandMemeticcomputingoptimization:aliteraturereview[J].Swarm and Evolutionary Computation, 2012(2): 1-14

[14]GaoL,ZhangGH,ZhangLP,etal.AnefficientMemeticalgorithmforsolvingthejobshopschedulingproblem[J].Computers & Industrial Engineering, 2011, 60(4): 699-705.

[15]ChiangTC,ChengHC,FuLC.NNMA:aneffectiveMemeticalgorithmforsolvingmultiobjectivepermutationflowshopschedulingproblems[J].Expert Systems with Application, 2011, 38(5): 5986-5999.

[16]ShouYY. Resource-constrained multi-project scheduling models and methods[M].Hangzhou:ZhejiangUniversityPress, 2010: 74-80. (壽涌毅. 資源受限多項(xiàng)目調(diào)度的模型與方法[M].杭州:浙江大學(xué)出版社, 2010: 74-80.)

Pit-stop support scheduling on deck of carrier plane based on Memetic algorithm

SU Xi-chao1, HAN Wei1, XIAO Wei2, JIANG Ting-ting3

(1. Department of Airborne Vehicle Engineering, Naval Aeronautical and Astronautical University, Yantai 264001, China;2. System Engineering Research Institute, China State Shipbuilding Corporation, Beijing 100094, China;3. Graduate Student’s Brigade, Naval Aeronautical and Astronautical University, Yantai 264001, China)

Forimprovingtheeffectivenessindexessuchassupportefficiencyandresourcesavailabilityondeckofcarrierplaneseffectively,thepit-stopsupportroutingconstraintsandresourcesconstraintsareanalyzedsystematically,andanoptimizedpit-stopsupportschedulingmathematicmodelondeckofcarrierplanesisestablished.Tosolvelarge-scaleschedulingproblemswhicharedifficultfortraditionaloptimizationmethods,aMemeticalgorithmisproposed.First,tomaketheloadofrenewableresourcesequalized,aserialschedulegenerationschemeembeddedbyresourcesallocationstrategiesisadopted.Second,anewadaptivemutationstrategybasedonthesub-topologystructureisdesignedtoimproveexplorationabilityofthealgorithm,andalocalsearchmethodbasedonsimulatedannealingisintroduced.Finally,thesimulationresultsshowthefeasibilityofthemodelandtheeffectivenessofthealgorithmunderdifferentdispatchscales.

carrierplane;pit-stopsupportschedulingondeck;Memeticalgorithm;optimization

2016-02-29；

2016-04-05；網(wǎng)絡(luò)優(yōu)先出版日期：2016-06-29。

國家自然科學(xué)基金(51375490)；航空科學(xué)基金(20145784010)資助課題

V271.4+92

ADOI:10.3969/j.issn.1001-506X.2016.10.12

蘇析超(1989-),男,博士研究生,主要研究方向?yàn)榕炤d機(jī)技術(shù)研究及應(yīng)用。

E-mail:suiting1012@163.com

韓維(1970-),男,通信作者,教授,博士研究生導(dǎo)師,博士，主要研究方向?yàn)楹娇毡Ｕ瞎こ毯惋w行動力學(xué)。

E-mail:Luckydevilhan@163.com

蕭衛(wèi)(1966-),男,研究員,碩士,主要研究方向?yàn)楹娇障到y(tǒng)工程、流程優(yōu)化。

E-mail:18911990663@189.cn

蔣婷婷(1995-),女,碩士研究生,主要研究方向?yàn)榕炤d機(jī)技術(shù)研究及應(yīng)用。

E-mail:suiting1012@163.com

網(wǎng)絡(luò)優(yōu)先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20160629.1132.002.html