韓 維，蘇析超，陳俊鋒

（1．海軍航空工程學(xué)院飛行器工程系，山東煙臺(tái)264001；2．海軍航空工程學(xué)院研究生管理大隊(duì)，山東煙臺(tái)264001）

艦載機(jī)多機(jī)一體化機(jī)務(wù)保障調(diào)度方法

韓 維1，蘇析超2，陳俊鋒2

（1．海軍航空工程學(xué)院飛行器工程系，山東煙臺(tái)264001；2．海軍航空工程學(xué)院研究生管理大隊(duì)，山東煙臺(tái)264001）

為了有效提升艦載機(jī)多機(jī)機(jī)務(wù)保障的效率和保障人員的利用率，根據(jù)單機(jī)機(jī)務(wù)保障流程約束特性，建立了基于多計(jì)劃評(píng)審技術(shù)網(wǎng)絡(luò)的多目標(biāo)多機(jī)一體化機(jī)務(wù)保障調(diào)度模型。針對(duì)問(wèn)題的求解，提出了一種自適應(yīng)混合差分進(jìn)化算法。首先根據(jù)調(diào)度的網(wǎng)絡(luò)化排隊(duì)過(guò)程，設(shè)計(jì)了基于事件調(diào)度策略的解碼方法。其次為了協(xié)調(diào)算法“探索”與“開發(fā)”的能力，引入了自適應(yīng)的變異操作和交叉、變異參數(shù)控制。再次，針對(duì)工序塊的平行組合排列特征，提出了4種鄰域結(jié)構(gòu)，進(jìn)而在算法框架中嵌入了一種自適應(yīng)多鄰域局部搜索策略。最后通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了模型和算法的可行性和有效性。

艦載機(jī)機(jī)務(wù)保障；多目標(biāo)優(yōu)化；差分進(jìn)化算法；局部搜索

0 引 言

作為現(xiàn)代戰(zhàn)場(chǎng)上的“海上霸王”，航空母艦及其艦載機(jī)航空兵擺脫了海面的二維限制，一直占據(jù)著軍事大國(guó)海軍裝備序列中的核心地位。在航母編隊(duì)中，艦載機(jī)是最關(guān)鍵的組成部分，航母全系統(tǒng)和航母戰(zhàn)斗群的絕大多數(shù)作戰(zhàn)使命都需要并且只能由艦載機(jī)來(lái)承擔(dān)和完成［1］。其中，艦載機(jī)艦面保障作業(yè)調(diào)度時(shí)間跨度長(zhǎng)，涉及面廣，約束條件復(fù)雜，如何對(duì)其提供合理的規(guī)劃或優(yōu)化對(duì)提升艦載機(jī)作戰(zhàn)效能具有重要作用。

目前國(guó)內(nèi)外對(duì)艦載機(jī)調(diào)度方法的研究主要集中在人工智能領(lǐng)域。文獻(xiàn)［2］針對(duì)艦載機(jī)甲板布列出動(dòng)問(wèn)題建立了布列調(diào)度多目標(biāo)優(yōu)化模型，并利用改進(jìn)的混合粒子群優(yōu)化（hybrid particle swarm optimization，HPSO）算法和遺傳算法（genetic algorithm，GA）進(jìn)行求解和對(duì)比。文獻(xiàn)［3］采用多智能體技術(shù)，將艦載機(jī)維修保障過(guò)程建立為三層多智能體系統(tǒng)模型，并成功運(yùn)用于保障人員配置問(wèn)題的求解。文獻(xiàn)［4］通過(guò)對(duì)一款名為甲板運(yùn)作行動(dòng)過(guò)程規(guī)劃者（deck operation course of action planner，DCAP）的輔助飛行甲板管理軟件的開發(fā)，研究了反向強(qiáng)化學(xué)習(xí)方法［5］和基于排隊(duì)網(wǎng)絡(luò)的策略優(yōu)化［6］在艦載機(jī)自適應(yīng)多階段調(diào)度問(wèn)題中的應(yīng)用，并通過(guò)甲板作業(yè)仿真，將基于線性整數(shù)規(guī)劃模型的優(yōu)化算法與傳統(tǒng)的專家啟發(fā)式規(guī)則進(jìn)行調(diào)度性能上的對(duì)比［7］。文獻(xiàn)［8］根據(jù)所建立的艦載機(jī)運(yùn)動(dòng)約束模型采用改進(jìn)A*算法求解，具有規(guī)劃路徑平滑且響應(yīng)速度快等特點(diǎn)。航空機(jī)務(wù)保障方面，陸基機(jī)務(wù)保障主要采取固定機(jī)組制模式，存在人員利用率不高、保障缺乏彈性等特點(diǎn)，若應(yīng)用于空間有限的艦面多機(jī)保障或?qū)?dǎo)致人員擁擠和危險(xiǎn)系數(shù)增高等后果，因此，研究基于任務(wù)的艦載機(jī)多機(jī)一體化機(jī)務(wù)保障調(diào)度具有較強(qiáng)的現(xiàn)實(shí)意義。文獻(xiàn)［9］和文獻(xiàn)［10］分別將多機(jī)機(jī)務(wù)保障問(wèn)題抽象為柔性開放車間和柔性流水車間問(wèn)題，但均是基于工序串行約束的簡(jiǎn)化模型，這與艦載機(jī)保障工序復(fù)雜網(wǎng)絡(luò)化約束的實(shí)際不符。

為此本文按照艦載機(jī)保障流程約束特性，以最小化保障時(shí)間和保障主體負(fù)載均衡為目標(biāo)，建立基于多計(jì)劃評(píng)審技術(shù)（multiple program evaluation and review technique，Multi-PERT）網(wǎng)絡(luò)的多機(jī)一體化機(jī)務(wù)保障模型。設(shè)計(jì)了一種嵌入多鄰域結(jié)構(gòu)局部搜索的自適應(yīng)混合差分進(jìn)化（self-adaptive hybrid differential evolution，SaHDE）算法求解該模型。通過(guò)實(shí)例仿真和與其他調(diào)度算法的對(duì)比驗(yàn)證了算法的可行性和有效性。

1 艦載機(jī)多機(jī)一體化機(jī)務(wù)保障調(diào)度問(wèn)題模型

1.1 保障作業(yè)流程分析與問(wèn)題描述

艦載機(jī)多機(jī)一體化機(jī)務(wù)保障調(diào)度是指在單機(jī)保障流程約束下，通過(guò)合理調(diào)度保障單元，對(duì)多機(jī)型機(jī)群同時(shí)進(jìn)行保障，以達(dá)到較優(yōu)的出動(dòng)效能和較高的保障資源利用率。在一體化保障模式下，保障單元可以擺脫固定機(jī)組模式的束縛，實(shí)現(xiàn)在不同艦載機(jī)之間的轉(zhuǎn)換和保障。納入一體化保障模式的艦載機(jī)可包含戰(zhàn)斗機(jī)、攻擊機(jī)、預(yù)警機(jī)、反潛機(jī)、電子戰(zhàn)飛機(jī)等固定翼艦載機(jī)，且不同艦載機(jī)由于任務(wù)的區(qū)別而導(dǎo)致保障作業(yè)時(shí)間上的差異。艦載機(jī)單機(jī)保障作業(yè)根據(jù)保障的內(nèi)容和性質(zhì)劃分為不同的專業(yè)類別，每一專業(yè)類別的工序由與之對(duì)應(yīng)的若干組保障單元負(fù)責(zé)保障，而每個(gè)保障單元可由若干保障人員組成，如掛彈單元（可由2～4人組成）主要負(fù)責(zé)軍械外觀檢查、掛架準(zhǔn)備、填充炮彈和掛載導(dǎo)彈等軍械類保障工序。且出于安全性和空間限制的考慮，不同工序間存在串、并行的約束關(guān)系。因此，本文通過(guò)構(gòu)建Multi-PERT多機(jī)保障網(wǎng)絡(luò)對(duì)多機(jī)一體化機(jī)務(wù)保障調(diào)度進(jìn)行描述。圖1所示為某波次出動(dòng)簡(jiǎn)化的Multi-PERT多機(jī)保障網(wǎng)絡(luò)圖。

圖1 Multi-PERT多機(jī)保障網(wǎng)絡(luò)圖

圖1 中Oij為艦載機(jī)i的第j項(xiàng)工序表示工序Oij由MA類保障單元負(fù)責(zé)，且由于保障單元的技能經(jīng)驗(yàn)、協(xié)作能力等的差異，其保障時(shí)間的取值范圍為S和E分別為合成保障過(guò)程的虛擬開始和虛擬結(jié)束作業(yè)，Si為第i架艦載機(jī)的入場(chǎng)保障起始虛工序，Si之間的虛線表示入場(chǎng)保障的前后時(shí)間約束，Oi7之間的虛線則表示各艦載機(jī)保障結(jié)束時(shí)間的優(yōu)先級(jí)約束。

在此基礎(chǔ)上，為建立艦載機(jī)多機(jī)一體化機(jī)務(wù)保障調(diào)度優(yōu)化問(wèn)題模型，進(jìn)行如下假設(shè)：①同一時(shí)刻某一工序只能接受一個(gè)保障單元保障；②保障單元在保障某工序的過(guò)程不可中斷，且只能在上一道工序完成后才能進(jìn)行下一道工序保障；③各艦載機(jī)保障項(xiàng)目之間除共享保障單元外，相互獨(dú)立；④艦載機(jī)在各站位均能接受油電氣液等“一站式”資源保障，無(wú)需中途轉(zhuǎn)運(yùn)；⑤不考慮突發(fā)故障和其他干擾因素。

根據(jù)上述分析可以看出，艦載機(jī)多機(jī)一體化機(jī)務(wù)保障調(diào)度優(yōu)化問(wèn)題本質(zhì)上屬于資源約束條件下多項(xiàng)目調(diào)度優(yōu)化問(wèn)題［1112］，但主要存在兩個(gè)方面的不同，一是本文的Multi-PERT多機(jī)保障模型是基于相同的單機(jī)PERT保障模型而建立的，即各項(xiàng)目（單機(jī)保障工序集合）具有相同保障流程；二是本文的調(diào)度問(wèn)題不僅包括各項(xiàng)目工序的優(yōu)先排序，還包括各項(xiàng)目工序在資源（保障單元）上的選擇分配，問(wèn)題的復(fù)雜性更高。

1.2 調(diào)度模型參數(shù)及決策變量定義

模型中各參數(shù)定義如下：

I＝｛1，2，…，n｝為參與保障的艦載機(jī)集合，其中，n為艦載機(jī)數(shù)量。

M＝｛1，2，…，｜M｜｝為保障單元集合，其中，｜M｜為保障單元數(shù)量。

Ji＝｛1，2，…，m｝為艦載機(jī)i的工序集，其中，m為單機(jī)工序數(shù)。

Mj為可對(duì)工序Oij進(jìn)行保障的一類保障單元集合，且Mj?M。

Sij為艦載機(jī)i的第j道工序保障開始時(shí)間。TSi為艦載機(jī)i的入場(chǎng)保障起始時(shí)間。

Eij為艦載機(jī)i的第j道工序保障結(jié)束時(shí)間。

Tijk為艦載機(jī)i的第j道工序在第k（k∈Mj）個(gè)保障單元上的作業(yè)時(shí)間。

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

HSi為虛工序Si的緊后工序集合。

Ci為艦載機(jī)i最后一道工序的保障結(jié)束時(shí)間。

Cmax為各艦載機(jī)的最大保障結(jié)束時(shí)間。

Cijeg為保障單元從艦載機(jī)i的第j道工序保障結(jié)束至艦載機(jī)e的第g道工序開始保障的轉(zhuǎn)換時(shí)間。

ObVk為第k（k∈Mj）個(gè)保障組的閑忙比，即整個(gè)保障過(guò)程空閑時(shí)間與工作時(shí)間的比值。Eob為保障單元的閑忙比方差。決策變量定義為

1.3 調(diào)度模型的建立

根據(jù)艦載機(jī)保障調(diào)度的實(shí)際需求，調(diào)度優(yōu)化的目的首先要提升保障效率，使得保障活動(dòng)在最短的時(shí)間內(nèi)完成；在保證保障時(shí)間最短的前提下，其次是使得保障單元的工作負(fù)載均衡化。因此選取最大保障完工時(shí)間Cmax＝max（Ci）和閑忙比方差Eob兩個(gè)指標(biāo)作為優(yōu)化目標(biāo)。根據(jù)定義可得

其中，保障單元k的閑忙比為

工作時(shí)間bVk可表示為保障時(shí)間和轉(zhuǎn)移時(shí)間之和，即

綜合考慮保障的目標(biāo)及各類約束，建立艦載機(jī)多機(jī)一體化機(jī)務(wù)保障調(diào)度優(yōu)化模型為

其中，式（4）表示調(diào)度的目標(biāo)，即在保證最小化最大保障完工時(shí)間的前提下，使得各保障單元閑忙比更為均衡；式（5）表示每架艦載機(jī)的任一工序只能在一個(gè)保障單元上保障；式（6）表示任一艦載機(jī)工序保障開始時(shí)間與結(jié)束時(shí)間的關(guān)系；式（7）表示作業(yè)的緊前關(guān)系約束，一個(gè)工序的開始必須保證所有緊前工序均保障結(jié)束；式（8）表示艦載機(jī)在入場(chǎng)系留后才能開始保障；（9）表示不同工序不能同時(shí)由同一保障單元保障，且保障按優(yōu)先級(jí)進(jìn)行，式中BM為足夠大實(shí)數(shù)，確保不等式恒成立；式（10）表示決策變量的0－1屬性約束。

2 基于SaHDE算法的問(wèn)題求解

艦載機(jī)多機(jī)一體化機(jī)務(wù)保障調(diào)度問(wèn)題是一類具有高度復(fù)雜性、多約束性和多目標(biāo)性的NP-hard問(wèn)題。艦載機(jī)保障工序眾多，且隨著艦載機(jī)保障數(shù)量的增加，問(wèn)題的規(guī)模急劇增大，導(dǎo)致在問(wèn)題的求解過(guò)程中容易陷入局部極值而找不到全局最優(yōu)解。通過(guò)增大搜索空間和種群規(guī)?？稍谝欢ǔ潭壬显黾拥玫饺肿顑?yōu)解的概率，但無(wú)疑將耗費(fèi)更大的計(jì)算量，降低搜索的效率。差分進(jìn)化算法（differential evolution，DE）由Storn和Price提出后，便被證明是最強(qiáng)大的隨機(jī)實(shí)參數(shù)優(yōu)化算法之一［13］，在解決實(shí)際調(diào)度問(wèn)題具有很強(qiáng)的適應(yīng)性和普遍性［14-15］，并在諸如本文的多極值問(wèn)題方面具有更優(yōu)秀的求解能力［16］。本節(jié)在標(biāo)準(zhǔn)DE算法［17］的基礎(chǔ)上，設(shè)計(jì)了改進(jìn)的SaHDE算法。

2.1 染色體編碼

經(jīng)典資源受限多項(xiàng)目調(diào)度問(wèn)題的求解常采用離散作業(yè)列表編碼方式和隨機(jī)數(shù)編碼。若采用作業(yè)列表編碼方式，則只能表示各艦載機(jī)作業(yè)的保障順序，針對(duì)每道工序所選擇的保障單元?jiǎng)t還需增加一層編碼列表加以表示。為降低編碼的冗雜性，克服作業(yè)列表編碼方式在進(jìn)化操作中產(chǎn)生非法解的不足，本文采用基于矩陣的實(shí)數(shù)編碼方式［14］。

式中，個(gè)體An×m，行表示艦載機(jī)編號(hào)，列表示工序號(hào)，任一元素aij為區(qū)間（1，Mj＋1）上的一個(gè)隨機(jī)實(shí)數(shù)。其中，整數(shù)部分Int（aij）表示艦載機(jī)i的第j道工序在第Int（aij）個(gè)保障單元上作業(yè)，小數(shù)部分Dec（aij）表示多個(gè)工序在同一保障單元上沖突時(shí)的優(yōu)先排序，Dec（aij）越大代表優(yōu)先級(jí)越高。將矩陣編碼的每一列構(gòu)成一小段，形成的染色體可以表示為一個(gè)長(zhǎng)度為n×m的字符串：［a11，a21，…，an1，a12，a22，…，anm］。

2.2解碼操作

解碼過(guò)程是實(shí)現(xiàn)染色體向調(diào)度方案映射的過(guò)程，每一次解碼都是對(duì)調(diào)度系統(tǒng)的一次仿真。根據(jù)Multi-PERT多機(jī)保障網(wǎng)絡(luò)圖可以看出，解碼的每一步不僅取決于染色體上的信息，還需對(duì)工序的緊前緊后約束進(jìn)行判斷。不妨將艦載機(jī)多機(jī)機(jī)務(wù)保障調(diào)度看作是包含多種平行保障單元的網(wǎng)絡(luò)化排隊(duì)保障過(guò)程，任一道工序在滿足緊前約束條件下釋放到所選擇的保障單元上，并根據(jù)優(yōu)先級(jí)進(jìn)行排隊(duì)保障。本文采用離散事件仿真中的事件調(diào)度策略，通過(guò)基于最早發(fā)生事件的時(shí)鐘推進(jìn)機(jī)制，得到各個(gè)工序保障的起止時(shí)間等調(diào)度信息。

因此首先定義3類事件歷程：E1-艦載機(jī)入場(chǎng)，E2-工序保障開始，E3-工序保障結(jié)束，每種事件分別設(shè)置相對(duì)應(yīng)的未來(lái)事件表FEL1、FEL2和FEL3。記仿真時(shí)鐘為TIME，第k個(gè)保障單元的等待保障工序隊(duì)列集為Wk，執(zhí)行保障工序集為Ak，已完成保障工序集為Ck。調(diào)度的每一步時(shí)鐘推進(jìn)到3類未來(lái)事件表中最早發(fā)生的時(shí)間，并處理對(duì)應(yīng)的事件歷程：

事件1 艦載機(jī)i入場(chǎng)，并將虛工序Si的緊后工序集HSi中的工序按照Int（aij）釋放至對(duì)應(yīng)的保障單元隊(duì)列Wk，并更新FEL1。

事件2 第k個(gè)保障單元上的工序Oij保障開始，記錄Sij并更新FEL2和FEL3。

事件3 第k個(gè)保障單元上的工序Oij保障結(jié)束，記錄Eij，將Ak中元素轉(zhuǎn)移至Ck，并判斷Oij緊后工序的緊前工序集PHij是否均已保障結(jié)束，若是，則釋放緊后工序集Hij至對(duì)應(yīng)的保障單元隊(duì)列。根據(jù)Dec（aij）選取Wk中下一保障工序，并將其轉(zhuǎn)移至Ak，并更新FEL2和FEL3。

基于事件調(diào)度策略的解碼（decoding algorithm based on event scheduling，DAES）算法描述如表1所示。

表1 DAES算法的偽代碼

續(xù)表

2.3 自適應(yīng)變異操作

基于種群的智能優(yōu)化算法實(shí)現(xiàn)良好搜索性能的關(guān)鍵在于尋找“探索”與“開發(fā)”上的平衡，前者意味著算法“探索”或者“搜索”可行解空間各個(gè)區(qū)域的能力，后者則表示算法盡快收斂于近似最優(yōu)解的能力。在常見的5種變異算子中［17］，DE／rand／1和DE／rand／2變異策略以種群中的隨機(jī)個(gè)體作為基本向量，有利于保持種群的多樣性，但進(jìn)化方向缺乏集中性，收斂速度慢；DE／best／1和DE／best／2變異策略以父代最優(yōu)個(gè)體作引導(dǎo)，局部搜索能力強(qiáng)，精度高，但容易陷入局部最優(yōu)而出現(xiàn)早熟；而DE／current-to-best／1變異策略采取本地個(gè)體與最優(yōu)個(gè)體加權(quán)求和作為基本向量，在一定程度上平衡了全局尋優(yōu)能力和收斂速度，但權(quán)重系數(shù)僅取決于縮放因子F，無(wú)法根據(jù)進(jìn)化信息進(jìn)行自適應(yīng)調(diào)節(jié)。

受文獻(xiàn)［18］的啟發(fā)，本文在DE／current-to-best／1變異策略的基礎(chǔ)上提出如下的改進(jìn)：

式中，Xpbest，G是從當(dāng)前種群的100p%的最優(yōu)子種群中隨機(jī)選取的個(gè)體；ωt為Xpbest，G與Xi，G的權(quán)重系數(shù)，為使得算法在前期執(zhí)行階段更注重“探索”，而在后偏向“開發(fā)”，加快收斂速度，對(duì)ωt采用非線性sigmoid遞增函數(shù)

式中，t為當(dāng)前迭代次數(shù)；T為最大迭代次數(shù)；參數(shù)A控制曲線曲率大小，A越小，則ωt越接近于直線增長(zhǎng)；參數(shù)b控制由“探索”轉(zhuǎn)向“開發(fā)”的時(shí)機(jī)，當(dāng)b＝0.5時(shí)，ωt隨t的增加呈“S”型曲線增長(zhǎng)，且在t＝T／2處ωt＝0.5。b值越小，說(shuō)明由Xi，G為主導(dǎo)的搜索占總搜索過(guò)程的比例則越少，由探索轉(zhuǎn)入開發(fā)的時(shí)機(jī)越早。因此可通過(guò)對(duì)參數(shù)A和b的控制，整體把握 “探索”與“開發(fā)”上的平衡。

2.4 自適應(yīng)參數(shù)控制

除變異策略外，縮放因子F和交叉概率CR同樣對(duì)搜索的性能起到重要作用。為了更好地利用種群信息以提升F與CR在迭代過(guò)程中的自適應(yīng)性，本文采用種群多樣性測(cè)試函數(shù)定義為

式中，Ns為種群規(guī)模；nm為染色體長(zhǎng)度；ˉxtj表示第t次迭代時(shí)群體平均中心位置的第j維分量。Dt越小，則個(gè)體內(nèi)特征差異值越小，種群的多樣性越低。通過(guò)對(duì)式（13）的變換，本文設(shè)計(jì)了一種基于種群多樣性的參數(shù)自適應(yīng)變化策略，表示為

式中，Dmax＝max｛Dt′，t′＝1，2，…，t｝；Fl、Fu、CRl、CRu分別為縮放因子和交叉概率的最小、最大邊界，擾動(dòng)項(xiàng)采用范圍更廣的柯西分布；σ為人為給定的分布標(biāo)準(zhǔn)差，按經(jīng)驗(yàn)取為0.1。在進(jìn)化過(guò)程中，縮放因子和交叉概率隨著種群多樣性的變化而自適應(yīng)變化，當(dāng)種群多樣性較高時(shí)，F(xiàn)i和CRi縮小，增強(qiáng)種群的開發(fā)能力，加快收斂；反之當(dāng)種群多樣性較低，F(xiàn)i和CRi增大，以增強(qiáng)種群跳出局部極值的能力，避免早熟收斂。基于柯西分布的擾動(dòng)項(xiàng)一方面增加了參數(shù)的多樣性，另一方面其相對(duì)于正態(tài)分布具有更強(qiáng)的兩翼性，從而加大了尋優(yōu)范圍和跳出局部最優(yōu)點(diǎn)的能力。

2.5 基于自適應(yīng)多鄰域結(jié)構(gòu)的局部搜索

針對(duì)調(diào)度問(wèn)題解空間的多極值性質(zhì)，通過(guò)引入局部搜索可有助于引導(dǎo)算法高效到達(dá)存在眾多局部極小的峽谷底部，并進(jìn)行徹底的搜索［19］。而局部搜索的性能取決于所使用的鄰域結(jié)構(gòu)。

首先根據(jù)染色體中aij對(duì)應(yīng)的Int（aij）值將所有工序分配至各保障單元，再根據(jù)Dec（aij）值對(duì)保障單元內(nèi)的工序隊(duì)列按照由小到大排列得到πk＝｛Oij｜（k＝Int（aij））∧（k∈Mj）｝。由此，對(duì)?i∈I的第j道工序集，均可對(duì)應(yīng)｜Mj｜個(gè)排序πk（k∈Mj）。針對(duì)上述平行工序排序，定義基于工序塊的4種鄰域結(jié)構(gòu)如下：

（1）縱向交換鄰域Interchange_V（πk1，u，πk2）：表示對(duì)?k1，k2∈Mj（k1≠k2），將πk1中第u位工序與πk2中各個(gè)工序依次交換位置。

（2）橫向交換鄰域Interchange_L（πk，u）：表示對(duì)?k∈Mj，將πk中第u位工序與πk中其他位工序依次交換。

（3）縱向插入鄰域Insert_V（πk1，u，πk2）：表示對(duì)?k1，k2∈Mj（k1≠k2），將πk1中第u位工序取出，并依次插入至πk2中各個(gè)可插入位置。

（4）橫向插入鄰域Insert_L（πk，u）：表示對(duì)?k∈Mj，將πk中第u位工序取出，并依次分別插入πk中其他可插入位置。

其中，針對(duì)具體的交換和插入操作，可假設(shè)第u位工序Oij，第v位工序Oej和第v＋1位工序Ofj。若令工序Oij與工序Oej交換，則令aij值與aej值互換；若令工序Oij插入至第v位和第v＋1之間的空位，則令aij＝aej＋（afj－aej）· rand（0，1）。

顯然，不同的鄰域結(jié)構(gòu)具有不同的局部搜索效果。橫向交換鄰域與橫向插入鄰域是通過(guò)改變單個(gè)保障單元內(nèi)工序順序進(jìn)行局部搜索，而縱向插入鄰域與縱向交換鄰域則通過(guò)改變平行保障單元間工序位置進(jìn)行局部搜索，且縱向插入鄰域可改變保障單元內(nèi)工序數(shù)量，對(duì)搜索前期起到平衡保障單元負(fù)載的作用，縱向交換鄰域則不會(huì)改變保障單元內(nèi)工序數(shù)量，這在搜索后期保障單元負(fù)載較均衡的情況下將發(fā)揮更大作用。

為了更有效地利用各種鄰域結(jié)構(gòu)的特點(diǎn)，借鑒文獻(xiàn)［20］中SaDE算法的自適應(yīng)變異策略，以上述定義的4種鄰域結(jié)構(gòu)作為局部搜索的選擇對(duì)象，根據(jù)算法搜索過(guò)程中各鄰域的貢獻(xiàn)動(dòng)態(tài)改變其使用率，進(jìn)而達(dá)到自學(xué)習(xí)的搜索效果。具體算法過(guò)程描述如下：

步驟1 令pl（l＝1，2，3，4）表示第l種鄰域結(jié)構(gòu)的選擇概率和分別表示第t（t＞LP）次迭代時(shí)之前LP代中第l種鄰域結(jié)構(gòu)搜索產(chǎn)生個(gè)體進(jìn)入下一代的成功或是失敗的數(shù)目表示第l種鄰域結(jié)構(gòu)搜索進(jìn)入下一代的個(gè)體的成功率，初始化pl（l＝1，2，3，4）＝1／4，令j＝1。

步驟2 選取染色體個(gè)體S內(nèi)工序j的基因段Sj＝（a1j，a2j，…，anj），將其轉(zhuǎn)換為平行保障單元Mj上的工序排列。

步驟3 采取輪盤賭方式選擇一種鄰域結(jié)構(gòu)L，并隨機(jī)選取πk1、u和πk2（k2≠k1）。

步驟4 若L＝Interchange_V，則Snew＝Interchange_ V（πk1，u，πk2）；若f（Snew）＜f（S），則，且S＝ Snew，否則

步驟5 若L＝Interchange_L，則Snew＝Interchange_L（πk1，u）；若f（Snew）＜f（S），則且S＝Snew，否則

步驟6 若L＝Insert_V，則Snew＝Insert_V（πk1，u， πk2）；若f（Snew）＜f（S），則，且S＝Snew，否則

步驟7 若L＝Insert_L，則Snew＝Insert_L（πk1，u）；若f（Snew）＜f（S），則且S＝Snew，否則

步驟8 按式（17）和式（18）更新各鄰域的選擇概率。

式中，ε為一個(gè)較小的值，其作用是控制Stl非零，本文取ε＝0.01。在搜索初期，若t＜LP，則令LP＝t。

步驟9 令j＝j(luò)＋1，若j≤m，則轉(zhuǎn)到步驟2；否則，輸出最優(yōu)解Snew。

2.6 SaHDE算法流程

基于本文Sa HDE算法求解艦載機(jī)多機(jī)一體化機(jī)務(wù)保障調(diào)度問(wèn)題的具體步驟描述如下：

步驟1 初始化種群規(guī)模Ns，最優(yōu)子種群比例p，最大迭代次數(shù)T，縮放因子和交叉概率的最小最大邊界Fl、Fu、CRl、CRu，自適應(yīng)控制參數(shù)A、b、b1、b2，保障艦載機(jī)數(shù)量n及各艦載機(jī)工序數(shù)m。記種群基因位aij的取值下界lower（aij）＝1，上界upper（aij）＝｜Mj｜＋1，對(duì)種群各染色體基因位按aij＝1＋｜Mj｜·rand（0，1）進(jìn)行初始化。

步驟2 按第2.2節(jié)DAES算法解碼得到調(diào)度方案及種群個(gè)體適應(yīng)度。

步驟3 根據(jù)式（14）計(jì)算種群多樣性，并根據(jù)式（15）求得縮放因子Fi。

步驟4 選取100p%的最優(yōu)子種群，按式（12）執(zhí)行變異操作。若aij＜lower（aij），則aij＝2·lower（aij）－aij；若aij＞up per（aij），則aij＝2·up per（aij）－aij。

步驟5 根據(jù)式（16）求得交叉概率CRi，并進(jìn)行二項(xiàng)交叉操作。

步驟6 對(duì)新種群進(jìn)行解碼，采取貪婪選擇方式生成新種群。

步驟7 選取100p%的最優(yōu)子種群，執(zhí)行基于自適應(yīng)多鄰域結(jié)構(gòu)的局部搜索。

步驟8 判斷是否達(dá)到最大循環(huán)代數(shù)，若是，則輸出最優(yōu)調(diào)度方案；若否，則轉(zhuǎn)入步驟2循環(huán)計(jì)算。

3 仿真分析

為驗(yàn)證本文模型的可行性和算法的有效性，結(jié)合保障的約束條件，建立一般化艦載機(jī)單機(jī)機(jī)務(wù)保障流程如圖2所示。進(jìn)一步簡(jiǎn)化，對(duì)單機(jī)機(jī)務(wù)保障網(wǎng)絡(luò)流程中的串行工序進(jìn)行合并，例如可將飛機(jī)下部機(jī)械檢查和飛機(jī)上部機(jī)械檢查合并為機(jī)械外觀檢查工序，最終可得到如圖1所示的Multi-PERT多機(jī)保障網(wǎng)絡(luò)圖，其中包含4類平行保障單元。

圖2 艦載機(jī)單機(jī)機(jī)務(wù)保障流程圖

以俄羅斯庫(kù)茲涅佐夫號(hào)航母為仿真背景，任務(wù)想定A需要保障12架艦載機(jī)，并給出各架艦載機(jī)完成任務(wù)所需的掛彈加油等工序保障的需求量，參與保障的各類保障單元數(shù)量為｜MA｜＝3，｜MB｜＝3，｜MC｜＝4，｜MD｜＝5。各架艦載機(jī)通過(guò)機(jī)庫(kù)和甲板上的調(diào)運(yùn)計(jì)劃得到的入場(chǎng)時(shí)間和布列站位如圖3所示，其中未標(biāo)明入場(chǎng)時(shí)間的艦載機(jī)表示TSi＝0。

圖3 艦載機(jī)站位及入場(chǎng)時(shí)序示意圖

利用Matlab8.1軟件編制仿真程序，參數(shù)設(shè)置為：種群規(guī)模Ns＝50，最優(yōu)子種群比例p＝0.1，最大迭代次數(shù)T＝400，縮放因子和交叉概率的最小最大邊界Fl＝0.3，F(xiàn)u＝0.6，CRl＝0.6，CRu＝0.9，自適應(yīng)控制參數(shù)A＝10，b＝0.2，b1＝b2＝0.5，學(xué)習(xí)周期LP＝30。

定義自適應(yīng)差分進(jìn)化算法（adaptive differential evolution algorithm，ADE）為在本文SaHDE算法基礎(chǔ)上不采用局部搜索機(jī)制，DE1算法為采用DE／best／1／bin模式的標(biāo)準(zhǔn)DE算法，DE2算法為采用DE／rand／1／bin模式的標(biāo)準(zhǔn)DE算法，且DE1和DE2設(shè)置參數(shù)為F＝0.5，CR＝0．9。分別采用本文的SaHDE算法、GA算法、ADE算法、DE1和DE2進(jìn)行30次獨(dú)立運(yùn)算，得到的結(jié)果如表1所示，其中，BST，AST，BOB和AOB分別表示30次運(yùn)行結(jié)果所得的最優(yōu)保障完工時(shí)間、平均保障完工時(shí)間、最小閑忙比方差和平均閑忙比方差。

表2 算法性能對(duì)比

圖4為DE1、DE2和ADE算法求得的保障時(shí)間最優(yōu)解收斂對(duì)比曲線，圖5為SaHDE算法、ADE算法和GA求得的保障時(shí)間最優(yōu)解收斂對(duì)比曲線。

圖4 DE1、DE2和ADE算法最優(yōu)解收斂對(duì)比曲線

圖5 GA、ADE和SaHDE算法最優(yōu)解收斂對(duì)比曲線

結(jié)合表1、圖4和圖5可以看出：①在求解本文的多峰值問(wèn)題的標(biāo)準(zhǔn)算法中，DE1的性能優(yōu)于DE2和GA，收斂速度快，但易于陷入局部極值。②ADE通過(guò)引入自適應(yīng)的變異策略和參數(shù)控制策略，結(jié)合了DE1的“探索”和DE2與“開發(fā)”的優(yōu)勢(shì)，性能較DE1和DE2均有所提升。③Sa HDE算法在ADE算法的基礎(chǔ)上，引入自適應(yīng)多鄰域的局部搜索，進(jìn)一步增強(qiáng)了算法跳出局部極值、避免早熟收斂的能力，同時(shí)具備較強(qiáng)的魯棒性。

通過(guò)Sa HDE算法獲得的一個(gè)最優(yōu)調(diào)度甘特圖如圖6所示，其每一個(gè)條狀框圖中的前一個(gè)字母下標(biāo)的數(shù)字表示正在保障的艦載機(jī)i（1≤i≤12），后一個(gè)數(shù)字表示艦載機(jī)的第j（1≤j≤7）道工序；陰影部分代表保障單元的轉(zhuǎn)移時(shí)間；坐標(biāo)縱軸對(duì)應(yīng)保障單元，如表示A類保障單元中的第一組。所求得最優(yōu)目標(biāo)值Cmax＝114.8min，Eob＝8.174 ×10－3。

圖6 最優(yōu)調(diào)度甘特圖

4 結(jié) 論

本文在分析艦載機(jī)單機(jī)機(jī)務(wù)保障流程的基礎(chǔ)上，以最小化保障時(shí)間和保障主體負(fù)載均衡為目標(biāo)，建立基于Multi-PERT網(wǎng)絡(luò)的多機(jī)一體化機(jī)務(wù)保障模型。設(shè)計(jì)了一種嵌入多鄰域結(jié)構(gòu)局部搜索的自適應(yīng)混合差分進(jìn)化算法Sa HDE求解該模型。最后通過(guò)實(shí)例仿真和對(duì)比，驗(yàn)證了模型的可行性與所提出算法的優(yōu)越性，對(duì)航母上的多機(jī)機(jī)務(wù)保障調(diào)度提供了新的思路和決策參考。

［1］Han W，Wang Q G．Conspectus of aircraft carrier and carrier plane［M］．Yantai：Naval Aeronautical and Astronautical University Press，2009：37- 41．（韓維，王慶官．航母與艦載機(jī)概論［M］．煙臺(tái)：海軍航空工程學(xué)院出版社，2009：37- 41．）

［2］Si W C，Han W，Shi W W．Comparison of deck-disposed methods for shipboard aircraft based on HPSO and GA［J］．Systems Engineering and Electronic，2013，35（2）：338- 344．（司維超，韓維，史瑋韋．基于HPSO和GA算法的艦載機(jī)甲板布放方法比較［J］．系統(tǒng)工程與電子技術(shù)，2013，35（2）：338- 344．）

［3］Feng Q，Li S J，Sun B．A multi-agent based intelligent configuration method for aircraft fleet maintenance personnel［J］．Chinese Journal of Aeronautics，2014，27（2）：280- 290．

［4］Ryan J C，Cummings M L，Roy N，et al．Designing an interactive local and global decision support system for aircraft carrier deck scheduling［C］∥Proc.of the AIAA Infotech＠Aerospace Conference，2011：1516．

［5］Michini B，Jonathan P．A human-interactive course of action planner for aircraft carrier deck operations［C］∥Proc.of the AIAA Infotech＠Aerospace Conference，2011：1515．

［6］Dastidar R G，F(xiàn)razzoli E．A queueing network based approach to distributed aircraft carrier deck scheduling［C］∥Proc.of the AIAA Infotech＠Aerospace Conference，2011：1514．

［7］Ryan J C，Banerjee A G，Cummings M L，et al．Comparing the performance of expert user heuristics and an integer linear program in aircraft carrier deck operations［J］．IEEE Trans.on Cybernetics，2014，44（6）：761- 773．

［8］Wu Y，Qu X J．Path planning for taxi of carrier aircraft launching［J］．Science China Technological Sciences，2013，56（6）：1561- 1570．

［9］Luan X F，Xie J．Research on multi-aircrafts preparation process based on simulation optimization［J］．Computer and Digital Engineering，2010，38（12）：50- 53．（欒孝豐，謝君．基于仿真優(yōu)化的多機(jī)機(jī)務(wù)準(zhǔn)備流程研究［J］．計(jì)算機(jī)與數(shù)字工程，2010，38（12）：50- 53．）

［10］Wei C Q，Chen C L，Wang B R．Study of aircraft support scheduling of aircraft on carrier based on space restriction［J］．Control Engineering of China，2013，20（4）：699- 702．（魏昌全，陳春良，王保乳．基于空間約束的艦載機(jī)航空保障調(diào)度研究［J］．控制工程，2013，20（4）：699- 702．）

［11］Wang L，F(xiàn)ang C．A hybrid estimation of distribution algorithm for solving the resource-constrained project scheduling problem［J］．Expert Systems with Application，2012，39（3）：2451- 2460．

［12］Wang W X，Wang X，Ge X L，et al．Multi-objective optimization for multi-project scheduling on critical chain［J］．Advance in Engineering Software，2014，68（2）：33- 39．

［13］Zhao Y X，Yang X S，Liu L Q．Newly emerging meta-heuristic optimization methods［M］．Beijing：Science Press，2013：220- 225．（趙玉新，劉利強(qiáng)．新興元啟發(fā)式優(yōu)化方法［M］．北京：科學(xué)出版社，2013：220- 225．）

［14］Tang L X，Yue Z，Liu J Y．An improved differential evolution algorithm for practical dynamic scheduling in steelmaking-continuous casting production［J］．IEEE Trans.on Evolutionary Computation，2014，18（2）：209- 225．

［15］Yuan Y，Xu H．Flexible job shop scheduling using hybrid differential evolution algorithms［J］．Computers&Industrial Engineering，2013，65（2）：246- 260．

［16］Das S，Suganthan P N．Differential evolution：a survey of the state-of-the-art［J］．IEEE Trans.on Evolutionary Computation，2011，15（1）：4- 31．

［17］Su H J，Yang Y P，Wang Y J．Research on differential evolution algorithm：a survey［J］．Systems Engineering and Electronic，2008，30（9）：1793- 1797．（蘇海軍，楊煜普，王宇嘉．微分進(jìn)化算法的研究綜述［J］．系統(tǒng)工程與電子技術(shù)，2008，30（9）：1793- 1797．）

［18］Ghosh P，Das S，Zafar H．Adaptive-differential-evolution-based design of two-channel quadrature mirror filter banks for subband coding and data transmission［J］．IEEE Trans.on Systems，Man，and Cybernetics—Part C：Application and Reviews，2012，42（6）：1613- 1623．

［19］Wang H Y，Zhao Y W，Wang W L，et al．New parallel algorithm based on DE for batch splitting job shop scheduling under multiple-resource constraints［J］．Control and Decision，2010，25（11）：1635- 1644．（王海燕，趙燕偉，王萬(wàn)良，等．兩級(jí)差分進(jìn)化算法求解多資源作業(yè)車間批量調(diào)度問(wèn)題［J］．控制與決策，2010，25（11）：1635- 1644．）

［20］Qin A K，Huang V L，Suganthan P N．Differential evolution algorithm with strategy adaptation for global numerical optimization［J］．IEEE Trans.on Evolutionary Computation，2009，13（2）：398- 417．

Integrated maintenance support scheduling method of multi-carrier aircrafts

HAN Wei1，SU Xi-chao2，CHEN Jun-feng2
（1.Department of Airborne Vehicle Engineering，Naval Aeronautical and Astronautical University，Yantai 264001，China；2.Graduate Student’s Brigade，Naval Aeronautical and Astronautical University，Yantai 264001，China）

In order to improve the maintenance support efficiency and support personnel availability of multi-carrier aircrafts effectively，according to the constraint characteristics of maintenance support process for single-carrier aircraft，a multi-objective integrated maintenance support scheduling model of multi-carrier aircrafts based on multiple program evaluation and review technique networks is established．To solve the problem，a self-adaptive hybrid differential evolution algorithm is presented．First，a decoding method based on event scheduling is designed according to networked queuing process of scheduling．Second，for coordinating the exploration and exploitation in algorithm，a self-adaptive mutation operation，an adaptive control strategy of crossover and mutation parameters are introduced．Third，in view of the characteristics of parallel-arrangement of process blocks，four kinds of neighborhood structure are defined，and then a novel local search based on the newly defined neighborhoods is presented and imbedded in the Sa HDE algorithm．The simulation results show the feasibility of the model and the effectiveness of the algorithm．

carrier aircraft maintenance support；multi-objective optimization；differential evolution algorithm；local search

TP 301

A

10．3969／j．issn．1001-506X．2015．04．14

韓 維（1970-），教授，博士研究生導(dǎo)師，博士，主要研究方向?yàn)楹娇沼詈娇茖W(xué)與技術(shù)。E-mail：Luckydevilhan＠163．com

1001-506X（2015）04-0809-08

2014- 05- 19；

2014- 07- 04；網(wǎng)絡(luò)優(yōu)先出版日期：2014- 09- 28。

網(wǎng)絡(luò)優(yōu)先出版地址：http：／／w ww．cnki．net／kcms／detail／11．2422．TN．20140928．1625．016．html

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

蘇析超（1989-），通訊作者，博士研究生，主要研究方向?yàn)榕炤d機(jī)技術(shù)研究及應(yīng)用。E-mail：381410529＠qq．com

陳俊鋒（1988-），博士研究生，主要研究方向?yàn)榕炤d機(jī)技術(shù)研究及應(yīng)用。E-mail：cjf053221＠126．com