基于HTLBO算法的艦載機(jī)機(jī)群機(jī)庫維修任務(wù)調(diào)度

張 勇, 李常久, 蘇析超,*, 崔榮偉

(1. 海軍航空大學(xué)航空作戰(zhàn)勤務(wù)學(xué)院, 山東 煙臺 264001; 2. 海軍航空大學(xué)航空基礎(chǔ)學(xué)院, 山東 煙臺 264001)

0 引 言

艦載機(jī)作為航母編隊的核心作戰(zhàn)單位,在海上戰(zhàn)場爭奪制空權(quán)、空對潛防御、電子對抗和對艦打擊等方面發(fā)揮著重要作用。維修對艦載機(jī)的安全性和可靠性起著至關(guān)重要的作用,可顯著影響機(jī)群持續(xù)作戰(zhàn)能力,且隨著作戰(zhàn)或訓(xùn)練強(qiáng)度的提升,維修能力的制約影響顯得更為突出。

為提高艦載機(jī)機(jī)群的出動效率,縮短艦載機(jī)的維修保障時間,要求形成高效的維修保障任務(wù)規(guī)劃。但相較于陸基修理廠,航母機(jī)庫內(nèi)空間小、環(huán)境復(fù)雜,對維修人員協(xié)同程度要求高，維修人員編制、設(shè)施設(shè)備等資源受限且對維修時限要求嚴(yán)格,給維修任務(wù)調(diào)度帶來了挑戰(zhàn)?；诤侥笝C(jī)庫的環(huán)境特點,科學(xué)地對機(jī)庫內(nèi)維修人員和設(shè)施設(shè)備進(jìn)行調(diào)度時序規(guī)劃和資源分配,縮短作業(yè)時間,提高資源的利用率,是提高機(jī)庫內(nèi)機(jī)群維修效率的關(guān)鍵,這對艦載機(jī)機(jī)群盡快恢復(fù)可用狀態(tài)并形成戰(zhàn)斗力具有重要的意義。

當(dāng)前,針對航母艦載機(jī)維修方面的研究尚處于起步階段。曾斌等[1]提出了一種考慮定期計劃和隨機(jī)保障時間的綜合可用度約束模型,并用啟發(fā)式求解算法生成了艦載機(jī)保障作業(yè)調(diào)度方案和裝備計劃性維護(hù)時間安排;紀(jì)云飛等[2]根據(jù)艦載機(jī)維修特性中人員、環(huán)境、設(shè)備等的實際情況,依據(jù)業(yè)務(wù)流程重組理念將艦載機(jī)艦面維修工作流程進(jìn)行了剔除、調(diào)整、并行和簡化,實現(xiàn)了理論流程向?qū)嶋H工作的流程優(yōu)化;Feng等[3]利用Multi-agent技術(shù)對艦載機(jī)綜合保障過程進(jìn)行建模,針對艦載機(jī)故障與維修的擾動影響,構(gòu)建了艦載機(jī)作業(yè)動態(tài)仿真模型,并將其應(yīng)用于維修人員配置優(yōu)化。

在與艦載機(jī)維修密切相關(guān)的裝備維修保障任務(wù)調(diào)度和飛機(jī)維修調(diào)度領(lǐng)域,國內(nèi)外學(xué)者開展了諸多卓有成效的研究。面向裝備維修任務(wù)調(diào)度領(lǐng)域,昝翔等[4]構(gòu)建了一種考慮時間不確定的性戰(zhàn)時裝備維修任務(wù)調(diào)度模型,以修復(fù)裝備重要度之和最大為目標(biāo),并采用一種改進(jìn)最大-最小螞蟻啟發(fā)式系統(tǒng)求解;曾斌等[5]使用將啟發(fā)式算法與混合Petri網(wǎng)相結(jié)合的求解方式,建立了預(yù)留空余停工時間的不確定性調(diào)度模型,提高了調(diào)度應(yīng)對突發(fā)事件的能力;萬明等[6]基于維修效益最大化的目標(biāo)建立了戰(zhàn)時裝備維修任務(wù)調(diào)度模型,設(shè)計了兩套優(yōu)化目標(biāo)不同的調(diào)度算法,有效地解決了計算最大保障時間和維修效益、維修負(fù)載均衡性的問題。面向飛機(jī)維修調(diào)度,Safaei等[7]圍繞軍用機(jī)群維修計劃案例建立了混合整數(shù)數(shù)學(xué)規(guī)劃模型,詳細(xì)描述了維修任務(wù)中勞動力的資源約束,并使用經(jīng)典分支定界的方法求解;Lin等[8]提出了一種受酵母繁殖過程啟發(fā)的求解算法,以最小化維修完工時間和平衡機(jī)庫資源數(shù)量機(jī)群的維護(hù)成本為目標(biāo),建立基于機(jī)群維修決策模型的保障模型;De等[9]使用仿真與優(yōu)化相結(jié)合的模型增強(qiáng)啟發(fā)式算法求解混合整數(shù)線性規(guī)劃模型,使完工需求時間到達(dá)最小且最小化維修人員總勞動力成本。

從以上研究可以看出,在解決此類維修調(diào)度問題上,模型抽象方法的研究視角經(jīng)歷了由車輛路徑模型[10]、項目調(diào)度模型[11]、流水車間模型[12]向資源受限項目調(diào)度模型[13]不斷深化的過程;模型約束條件由理想化向現(xiàn)實化轉(zhuǎn)變,模型更加精細(xì)復(fù)雜;模型求解方法經(jīng)歷了由精確式解法[7]向啟發(fā)式算法[8-9]的轉(zhuǎn)變。

綜上,這些研究為艦載機(jī)機(jī)群機(jī)庫維修調(diào)度提供了理論參考,但在實際應(yīng)用中仍存在以下幾個方面的不足:一是現(xiàn)階段對于機(jī)群機(jī)庫維修保障任務(wù)的優(yōu)化研究目標(biāo)大多集中在最小化維修完工時間,尚缺乏對于機(jī)群波次出動的可用度需求的考慮;二是維修任務(wù)單一,尚未考慮故障維修和定檢維護(hù)等多模式混合情況;三是對維修保障范圍、維修可并行容量、維修工位空間等現(xiàn)實約束考慮不全面。

針對以上不足,本文以艦載機(jī)機(jī)群機(jī)庫維修任務(wù)調(diào)度問題(maintenance task scheduling problem of aircraft in hangar, MTSPAH)為研究對象,針對艦載機(jī)波次出動的實際需求,結(jié)合維修作業(yè)的約束特征構(gòu)建MTSPAH模型,并設(shè)計了混合教與學(xué)算法(hybrid teaching-learning-based optimization, HTLBO)用于模型求解,以優(yōu)化機(jī)群的波次可用度和維修資源負(fù)載的均衡性。

1 問題描述

艦?zāi)笝C(jī)庫的機(jī)群維護(hù)對保障艦載機(jī)的安全性和可靠性起著至關(guān)重要的作用。航母艦載機(jī)在執(zhí)行飛行任務(wù)前后都需要進(jìn)行故障檢測,如檢測出重大故障,則會將其回收至機(jī)庫,入位系留后排隊等待維修。除了計劃外的隨機(jī)性故障維修工作,還需完成計劃內(nèi)的預(yù)防性定期檢查維護(hù),通常包括25 h、50 h、100 h定檢維護(hù)等。機(jī)庫需完成廣泛的維修任務(wù)和定檢工作,以保持高水平的機(jī)群可用性。機(jī)群可用性還取決于機(jī)庫的維修定檢吞吐效率,因此對相關(guān)維修人員和設(shè)施設(shè)備進(jìn)行科學(xué)的時序規(guī)劃和資源分配是MTSPAH的關(guān)鍵。圖1是庫茲涅佐夫號航母機(jī)庫維修資源環(huán)境的綜合態(tài)勢,其中涉及的特定約束包括以下4個方面。

1.1 作業(yè)流程

針對作業(yè)流程的前后序約束關(guān)系,可采用節(jié)點活動式(activity on node, AON)有向網(wǎng)絡(luò)圖來描述。針對故障維修任務(wù),各維修工序之間為串行關(guān)系:故障定位—故障維修—復(fù)檢;而針對定檢維護(hù)任務(wù),維修工序之間為網(wǎng)絡(luò)化的前后序關(guān)系,即任意工序的緊前工序集不唯一。圖2左側(cè)為多機(jī)保障流程網(wǎng)絡(luò)圖,Oij表示待維修機(jī)群中的第i架艦載機(jī)的第j道工序,OS和OE分別表示虛擬開始和虛擬結(jié)束工序,虛擬工序不需要消耗任何保障資源,工期為0,其作用是將所有定檢維修流程工序整合在一起。

1.2 維修人員與技能

1.3 維修設(shè)備/車間

1.4 維修工位空間

針對維修工位空間約束,令rsijk表示維修工序Oij對第k類(k∈Ks)工位的對應(yīng)關(guān)系,rsijk=1表示占用該類工位,否則rsijk=0。艦載機(jī)維修中的部分工位,諸如座艙等保障工位，由于空間受限,僅可容納一定人數(shù)nsik進(jìn)行并行保障作業(yè)。

2 模型建立

本節(jié)將在模型假設(shè)的基礎(chǔ)上結(jié)合模型的約束條件建立MTSPAH的數(shù)學(xué)優(yōu)化模型。

2.1 模型假設(shè)

為建立MTSPAH模型,提出如下假設(shè):

(1) 固定類維修資源儲備充足,機(jī)庫內(nèi)轉(zhuǎn)運時間相對于維修時間可忽略;

(2) 對任意維修工序,具備所需技能的維修人員使用對應(yīng)技能進(jìn)行保障;

(3) 不考慮任務(wù)變更等突發(fā)因素的干擾,維修工序一旦開始不可中斷;

(4) 采用一體化聯(lián)合維修模式,維修人員對同機(jī)型各艦載機(jī)均可保障。

2.2 模型的變量與約束條件

MTSPAH模型的其余所需變量定義如下:

I:待維修艦載機(jī)集合,I={1,2,…,Nm};

pi:第i架艦載機(jī)的維修停機(jī)位;

Ji:第i架艦載機(jī)維修工序集,Ji={1,2,…,|Ji|};

J:機(jī)群的維修總工序集,J={(i,j)|i∈I,j∈Ji};

At:機(jī)群在t時刻處于執(zhí)行狀態(tài)的所有維修工序集;

Ait:第i架艦載機(jī)在t時刻處于執(zhí)行狀態(tài)的維修工序集;

Psij:工序Oij的緊前工序集合;

Exi:第i架艦載機(jī)入位系留完畢時間;

dij:工序Oij的維修作業(yè)工時;

Ks:工位空間類別集合,Ks={1,2,…,|Ks|};

nsik:第i架艦載機(jī)第k類工位容納的人員數(shù)量;

Smij:維修工序的保障開始時間;

Emij:維修工序Oij的保障結(jié)束時間。

決策變量如下:

約束條件包括:

Smi1≥Exi, ?i∈I

(1)

Smij≥Smi h+di h, ?(i,h)∈Psij; ?(i,j)∈J

(2)

Smij+dij≤Smeg+BM·(1-Ypijeg), ?(i,j),(e,g)∈J

(3)

Smij≤Smeg+BM·(1-Yeijeg), ?(i,j),(e,g)∈J

(4)

(5)

(6)

(7)

(8)

(9)

(10)

Xpijkl,Xeijk′l′,Ypijeg,Yeijeg∈{0,1},
?k∈Kc; ?l∈Lp; ?k′∈Ke;
?l′∈Lek′; ?(i,j),(e,g)∈J

(11)

式(1)表示單機(jī)開始維修的入位時序約束;式(2)表示各艦載機(jī)的維修工序需按照既定維修流程的前后序依次開展;式(3)表示維修人員沖突的優(yōu)先序約束,其中BM為足夠大實數(shù),確保不等式恒成立;式(4)表示維修設(shè)備/車間沖突的優(yōu)先序約束;式(5)表示任意工序?qū)寄艿男枨罅繎?yīng)與分配至該工序且選擇本技能的維修人員數(shù)量相匹配;式(6)表示任意工序?qū)Ω黝惥S修設(shè)備/車間的需求與分配至該工序的資源相匹配;式(7)表示每位維修人員對任意維修工序進(jìn)行維修作業(yè)最多使用其中一項技能;式(8)表示供電站等固定類保障設(shè)備受供給管路長度的限制;式(9)表示工位空間資源約束;式(10)表示維修車間可并行作業(yè);式(11)表示決策變量Xpijkl、Xeijk′l′、Ypijeg和Yeijeg均為0-1決策變量。

2.3 目標(biāo)函數(shù)

面向艦載機(jī)機(jī)群機(jī)庫維修任務(wù)需求,分別構(gòu)建機(jī)群波次可用度和維修人員負(fù)載均衡性兩類優(yōu)化目標(biāo)。一般維修任務(wù)的目標(biāo)設(shè)置為完成時間最小化,而由于艦載機(jī)通常以集中機(jī)群發(fā)起攻擊,這使得艦載機(jī)的出動方式多以波次出動為主,最大化出動計劃中可用機(jī)群數(shù)量是前提。在接到艦載機(jī)機(jī)群出動作戰(zhàn)的指令后,若現(xiàn)存功能完好的艦載機(jī)數(shù)量不足本波次所需數(shù)量,即存在維修或定檢任務(wù)未完成的艦載機(jī)，無法進(jìn)行補充,這將導(dǎo)致該波次出動中機(jī)群數(shù)量不足。針對波次出動作戰(zhàn)需求,本文定義波次可用度表示待維修機(jī)群在后續(xù)各個出動波次準(zhǔn)備時刻的加權(quán)可用度,波次可用度越大,表示維修作業(yè)為各波次提供的完好艦載機(jī)越多,越能滿足波次出動數(shù)量的要求。其次，是使得維修人員的負(fù)載方差最小化,以增加維修作業(yè)的可持續(xù)性。

(1) 最大化機(jī)群波次可用度

(12)

式中:W為出動波次集合;SWw為波次w的出動準(zhǔn)備開始時刻;vw表示對波次可用度的傾向權(quán)值,越靠前的波次對戰(zhàn)局影響越重要,所取權(quán)重越大;ETi表示艦載機(jī)i的維修完工時間;函數(shù)sgn(x)為階躍函數(shù),當(dāng)且僅當(dāng)x≥0時，sgn(x)=1,否則為0;WA定義了機(jī)群維修開始后續(xù)出動波次的平均可用度,WA的目標(biāo)是最大化出動波次集合中的加權(quán)可用度之和。

(2) 最小化維修人員負(fù)載方差

(13)

3 HTLBO算法設(shè)計

基于以上MTSPAH模型的特點分析,將機(jī)庫內(nèi)艦載機(jī)機(jī)群維修任務(wù)調(diào)度劃分為資源受限項目調(diào)度問題(resource constrained project scheduling problem, RCPSP)。由于RCPSP已被證明是一種Np難問題,在可接受的時間內(nèi),現(xiàn)有的精確式解法只能解決小規(guī)模的問題。在面對大規(guī)模調(diào)度問題時,使用啟發(fā)式算法求解引起了人們的關(guān)注,并可以高效求得接近最優(yōu)的解決方案。

通過對RCPSP的深入研究,將經(jīng)典的RCPSP與實際機(jī)庫維修調(diào)度任務(wù)相結(jié)合,特別是在維修人員或多功能機(jī)器等資源的調(diào)度過程中,每種資源掌握幾種不同的技能。基于這一特點,將MTSPAH定義為多技能資源受限項目調(diào)度問題(multi-skill resource-constrained project scheduling problem, MS-RCPSP)[13]以使其更接近實際機(jī)群機(jī)庫維修情況。MS-RCPSP研究從時間和資源上合理安排調(diào)度,在技能與資源最優(yōu)利用的同時實現(xiàn)既定目標(biāo)的最優(yōu)化。

針對上述問題建模,啟發(fā)式算法可實現(xiàn)優(yōu)化性能和計算效率的平衡[13-15],可借鑒成果較為豐富。與粒子群優(yōu)化(particle swarm optimization, PSO)算法、遺傳算法(genetic algorithm, GA)和差分進(jìn)化(differential evolution, DE)算法等類似,教與學(xué)優(yōu)化(teaching-learning-based optimization, TLBO)算法也是一種基于種群的啟發(fā)式算法,它提供了一個模仿課堂上教師與學(xué)生教學(xué)過程的優(yōu)化模型,優(yōu)化過程包含教師的教學(xué)階段和學(xué)生們的互相學(xué)習(xí)階段[16-18],來實現(xiàn)全局最優(yōu)結(jié)果的求解。TLBO算法與其他算法的不同之處在于其不需要任何特定于算法的參數(shù)設(shè)定[18],避免了因參數(shù)的設(shè)定不同而導(dǎo)致算法的優(yōu)化效果不同。該算法在流水車間調(diào)度[19]、作業(yè)車間調(diào)度[20]、煉鋼-連鑄調(diào)度[21]等問題上均有較成功的應(yīng)用,具備良好的優(yōu)化性能和問題適應(yīng)性。

本文在標(biāo)準(zhǔn)TLBO算法[18]的基礎(chǔ)上,針對MTSPAH模型的特點,設(shè)計了一種HTLBO算法,算法流程如圖3所示。

算法具體的執(zhí)行步驟如下:

步驟 1初始化階段。首先根據(jù)機(jī)群機(jī)庫維修任務(wù),隨機(jī)初始化規(guī)模為Np的種群,并基于解碼策略求解種群對應(yīng)適應(yīng)度值;進(jìn)而擇優(yōu)選擇規(guī)模為Nt的精英教師群體,令迭代次數(shù)G=1。

步驟 2教師教學(xué)階段。隨機(jī)從精英教師群體中選取任意教師,選取任意學(xué)生個體采用面向精英教師的DE變異策略進(jìn)行個體更新,隨后將新個體與原個體進(jìn)行二項交叉,并基于貪婪選擇更新學(xué)生和精英教師群體。

步驟 3學(xué)生學(xué)習(xí)階段。對任意學(xué)生個體,從剩余學(xué)生群體中隨機(jī)挑選學(xué)習(xí)對象,采用峰值交叉[22]機(jī)制互相學(xué)習(xí),并基于貪婪選擇更新學(xué)生和精英教師群體。

步驟 4強(qiáng)化學(xué)習(xí)階段。從精英教師群體中隨機(jī)抽取教師個體,執(zhí)行學(xué)習(xí)自動機(jī)的自適應(yīng)鄰域搜索(learning automata-adaptive neighborhood search, LA-AVNS)操作。

步驟 5令G=G+1,判斷是否達(dá)到迭代終止條件,若是,則迭代終止,并輸出最優(yōu)教師個體對應(yīng)的維修調(diào)度方案和資源分配方案;否則,轉(zhuǎn)入步驟2繼續(xù)教與學(xué)優(yōu)化迭代。

HTLBO的主要改進(jìn)點體現(xiàn)在以下3個方面:

(1) 在教師教學(xué)階段,引入基于精英種群的DE算子進(jìn)行種群的更新;

(2) 在學(xué)生學(xué)習(xí)階段,引入峰值交叉算子進(jìn)行種群個體間的交叉學(xué)習(xí);

(3) 在強(qiáng)化學(xué)習(xí)階段,引入LA-AVNS操作對精英種群進(jìn)行局部增強(qiáng)搜索。

3.1 編碼操作

編碼策略是影響算法搜索效果和效率的重要因素。求解RCPSP問題的主要編碼策略包括任務(wù)列表編碼、優(yōu)先數(shù)編碼和優(yōu)先規(guī)則編碼[23]。由于調(diào)度過程中工序之間的優(yōu)先級關(guān)系,采用任務(wù)列表和優(yōu)先規(guī)則的編碼形式可能在后續(xù)的交叉和變異中獲得不符合實際調(diào)度規(guī)則的工序組合,因此采用基于維修作業(yè)時序修正的優(yōu)先數(shù)編碼,即x=[S11,S12,…,S1|J1|,S21,…,SNm|JNm|],以避免在后續(xù)的操作中產(chǎn)生非法的子代。

3.2 解碼操作

解碼機(jī)制包括串行調(diào)度生成機(jī)制(serial scheduling generation scheme, SSGS)和并行調(diào)度生成機(jī)制(parallel scheduling generation scheme, PSGS)兩類[24]。文獻(xiàn)[25]研究表明PSGS相比SSGS在更小的解空間中搜索結(jié)果,在大種群及資源受限的情況下,PSGS的解空間可能不包含最優(yōu)解。因此,對于機(jī)群機(jī)庫維修調(diào)度這種非常規(guī)性能指標(biāo)計算的條件,選擇SSGS生成維修作業(yè)時序方案具有搜索效果和效率的優(yōu)越性。與常規(guī)SSGS不同,HTLBO針對任一待調(diào)度工序Oij,在可滿足各類約束的時序推進(jìn)搜索過程中,嵌入任務(wù)技能對維修人員的匹配滿足性進(jìn)行判斷,即在時序調(diào)度過程中同步進(jìn)行維修人員的分配和技能的選擇?？紤]到多技能維修人員的柔性更大,在對維修人員進(jìn)行分配時,優(yōu)先選擇技能數(shù)較少的維修人員進(jìn)行分配,確保后續(xù)維修工序有更多柔性維修人員可分配;在同等技能數(shù)條件下,則優(yōu)先選擇累計維修時間最少的維修人員,以增強(qiáng)維修人員的負(fù)載均衡性;在維修設(shè)備分配方面,采用基于覆蓋范圍內(nèi)剩余工序作業(yè)時間最少優(yōu)先規(guī)則;在維修車間分配方面,依照盡量集中資源的原則,將維修人員分配至當(dāng)前作業(yè)數(shù)最多的車間。

定義已完成調(diào)度工序集Sg,可調(diào)度工序集Dg,解碼調(diào)度過程是從Dg中按工序優(yōu)先級選取工序,并安排在最早可開工時刻,分配人員、設(shè)備資源,并加入集合Sg這一循環(huán)迭代過程。解碼調(diào)度執(zhí)行流程圖如圖4所示。

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

為便于算法進(jìn)行個體適應(yīng)度比較,將字典序分層目標(biāo)通過賦予權(quán)重組合為單目標(biāo),并定義個體適應(yīng)度為

f=(1-WA)+αLBM

(14)

式中:α(0<α?1)為維修人員負(fù)載方差的權(quán)重系數(shù),維修調(diào)度指揮員可根據(jù)保障需求進(jìn)行權(quán)重調(diào)節(jié),鑒于艦載機(jī)機(jī)群機(jī)庫維修任務(wù)的需求為優(yōu)先保證提供完好的滿足波次需求數(shù)量的艦載機(jī),故可將權(quán)重系數(shù)取為小量。

3.4 教師教學(xué)階段

這一階段利用精英個體(教師)來引導(dǎo)種群個體(學(xué)生)的學(xué)習(xí)以提升整個班級的水平。對此,面向精英的DE操作具備更好的引導(dǎo)作用。在標(biāo)準(zhǔn)DE算法中,面向精英的變異機(jī)制一般以最優(yōu)解作為引導(dǎo),為模仿教師教學(xué)過程,并增強(qiáng)教學(xué)階段的多樣性,借鑒文獻(xiàn)[26]中“DE/target-to-best/1”策略,提出面向精英教師群體的教學(xué)引導(dǎo)機(jī)制:

(15)

3.5 學(xué)生學(xué)習(xí)階段

這一階段學(xué)生通過相互學(xué)習(xí)來提升各自的水平,同時可增加班級群體的學(xué)生多樣性以避免陷入教師教學(xué)階段可能出現(xiàn)的局部極值。對此,采用GA中的峰值交叉[22]來實現(xiàn)學(xué)生間的相互學(xué)習(xí)作用。在峰值交叉中,采用資源利用率作為引導(dǎo)因子,資源利用率較高的峰值區(qū)間往往隱藏著作業(yè)的瓶頸,以此時段作為交叉區(qū)間,從而實現(xiàn)個體之間的優(yōu)勢互補。

首先,給定維修方案S,t時刻的瞬時資源利用率(Instantaneous resource utilization rate, IRUR)定義為

(16)

(17)

進(jìn)一步地,基于TIRU定義,綜合資源利用率最高的峰值區(qū)間可表示為[tp1(S),tp2(S)],且長度為l的峰值區(qū)間起始時刻可由下式計算得出:

(18)

鑒于峰值區(qū)間包含了個體的優(yōu)良基因,算法采用兩點交叉進(jìn)行峰值區(qū)間的優(yōu)先數(shù)編碼置換。

3.6 強(qiáng)化學(xué)習(xí)階段

本階段是在經(jīng)典TLBO算法的基礎(chǔ)上引入的新階段,目的是對優(yōu)秀教師個體做進(jìn)一步的強(qiáng)化學(xué)習(xí),以更好地引導(dǎo)班級群體的學(xué)習(xí)更新。對此,基于LA-AVNS框架,結(jié)合本問題特性,設(shè)計相應(yīng)的搜索鄰域如下:

(1) 交換鄰域

隨機(jī)選取兩個無緊前緊后約束的維修工序,交換其編碼優(yōu)先數(shù)。

(2) 維修故障工序前插鄰域

隨機(jī)選取一個維修故障工序,查詢其緊前工序的結(jié)束時間并將其作為可插入?yún)^(qū)間的起始值,本工序開始時間為區(qū)間終止,將該工序插入?yún)^(qū)間內(nèi)的任意位置。該鄰域主要可使得故障艦載機(jī)盡快實現(xiàn)維修。

4 維修案例仿真分析

4.1 維修案例的構(gòu)建

維修案例基于圖1所示的航母機(jī)庫環(huán)境,考慮故障維修和定檢維護(hù)等多模式混合情況，設(shè)置10架編號分別為A～J的艦載機(jī)進(jìn)行機(jī)庫維修定檢:其中6架故障艦載機(jī)為波次回收后由甲板轉(zhuǎn)運至機(jī)庫,4架機(jī)庫駐留艦載機(jī)執(zhí)行定檢維護(hù)。后續(xù)的出動波次包括3次,且波次間隔周期為1 h 40min,即SW=[100,200,300]min,波次權(quán)重設(shè)置為v=[0.5,0.3,0.2]。

表1 案例任務(wù)設(shè)置機(jī)庫供電站與機(jī)群停機(jī)位覆蓋關(guān)系 Table 1 Case task hangar power station and fleet parking space covering relations min

針對同型號艦載機(jī),構(gòu)建定檢的通用化單機(jī)定檢流程AON有向網(wǎng)絡(luò)圖如圖5所示,虛線代表與虛擬工序連接。

各定檢保障工序工時、資源和技能需求如表2和表3所示。本案例中特設(shè)、航電、軍械和機(jī)械的維修人員配置數(shù)量為[5,6,4,10],專業(yè)技能兼容設(shè)置為特設(shè)與航電兼容,軍械和機(jī)械兼容,各專業(yè)內(nèi)前4名維修人員具備相應(yīng)兼容專業(yè)技能。

表2 單機(jī)定檢保障工序工時需求 Table 2 Regular maintenance operation hours demand of single aircraft min

表3 單機(jī)定檢保障工序技能資源需求Table 3 Regular maintenance operation set and resource demand of single aircraft

在維修車間配置方面,受機(jī)庫周邊艙室空間所限,航空機(jī)修車間、電子設(shè)備檢修車間、軍械檢修車間、油液探傷車間各配置一間,且可并行作業(yè)工序數(shù)為Ne=[3,2,4,1]。工位空間約束考慮座艙空間,且可并行作業(yè)人數(shù)為1人。

4.2 算法仿真對比分析

為驗證本文提出的HTLBO算法的有效性以及求解MTSPAH的性能,選取TLBO算法、DE算法和PSO算法作為求解此問題的性能對比算法。各算法的參數(shù)設(shè)置如下:HTLBO中班級學(xué)生規(guī)模Np=30,精英教師群體規(guī)模Nt=5,交叉概率cr=0.1,變異概率F=0.1;TLBO中Np和Nt的設(shè)置同HTLBO算法;PSO算法中粒子數(shù)量N=30,學(xué)習(xí)因子c1=2,c2=2,選用線性遞減權(quán)值策略設(shè)置ω=(ωini-ωend)(Q-q)/Q+ωend,其中ω為可變慣性權(quán)值,Q為最大評價次數(shù),q為當(dāng)前評價次數(shù),初始權(quán)值ωini=1.2,迭代結(jié)束權(quán)值ωend=0.1;DE算法中種群規(guī)模為Np=30,交叉概率cr=0.1,變異概率F=0.1。以上算法適應(yīng)度函數(shù)中維修人員負(fù)載方差的權(quán)重系數(shù)α=10-6,且均以評價次數(shù)Q=5 000作為迭代結(jié)束的標(biāo)志。經(jīng)過仿真優(yōu)化,得到MTSPAH的優(yōu)化指標(biāo)波次可用度WA與維修人員負(fù)載方差LBM的對比變化趨勢如圖6和圖7所示,各算法獨立運行15次得到的統(tǒng)計數(shù)據(jù)如表4所示,評級標(biāo)準(zhǔn)選取最優(yōu)解(Bes.)、平均解(Avg.)和標(biāo)準(zhǔn)差(Std.)。

表4 算法結(jié)果統(tǒng)計數(shù)據(jù) Table 4 Algorithm result statistics

通過仿真的對比結(jié)果可以發(fā)現(xiàn),本文提出的HTLBO算法在求解MTSPAH相較于對比算法具有尋優(yōu)能力強(qiáng)、收斂速度快、結(jié)果波動小的特點,其原因有如下3點:教師階段引入的DE算子尋優(yōu)能力和尋優(yōu)速度優(yōu)于其他3種算法;學(xué)生學(xué)習(xí)階段引入的峰值交叉算子,實現(xiàn)了高資源利用率個體交叉向后代傳輸在調(diào)度中的理想特征;強(qiáng)化學(xué)習(xí)階段引入的LA-AVNS框架對種群進(jìn)行局部增強(qiáng)搜索操作,提高了最優(yōu)解的精度和穩(wěn)定性。

為驗證算法在大規(guī)模機(jī)群維修資源高度受限條件下,算法的優(yōu)化求解性能,將出動波次間隔時間更改為80 min,進(jìn)行算法壓力測試仿真,設(shè)置3組出動任務(wù)如表5所示,其他算法參數(shù)保持不變,各算法獨立運行15次得到統(tǒng)計數(shù)據(jù)如表6所示。

表5 機(jī)群保障任務(wù) Table 5 Aircraft group support tasks

表6 高強(qiáng)度任務(wù)仿真結(jié)果統(tǒng)計數(shù)據(jù) Table 6 Simulation results of high-intensity tasks

通過仿真的對比結(jié)果可以發(fā)現(xiàn),在波次間隔時間縮短后,隨著機(jī)群數(shù)量的增加,機(jī)群波次可用度WA逐漸降低,維修人員負(fù)載方差LBM逐漸降低。經(jīng)分析，其原因是在維修任務(wù)緊張、資源高度受限情況下,波次間隔時間內(nèi)提供足夠艦載機(jī)的比率逐步下降,同時由于維修人員維修任務(wù)的大量填充,任務(wù)空閑時間間隔被壓縮,致使維修人員間的維修工作時間差距變小,負(fù)載方差變小,所得結(jié)果分析符合預(yù)期。同時可以看出，算法求解調(diào)度任務(wù)計算時間(Time)逐漸增加,但仍在可接受的求解時間范圍內(nèi)。綜合上述,本文提出的HTLBO算法在求解高度資源受限下的MTSPAH時仍具有較好的性能表現(xiàn)。

5 結(jié) 論

本文針對航母艦載機(jī)機(jī)庫維修任務(wù)調(diào)度問題,以艦載機(jī)機(jī)群波次可用度和機(jī)庫維修人員負(fù)載均衡性為優(yōu)化指標(biāo),提出了一種HTLBO算法。經(jīng)過案例仿真和對比實驗,初步證明算法在解決這類問題上有一定的優(yōu)勢,并給出了一種最優(yōu)維修人員調(diào)度方案。但本文模型和算法的研究目前仍具有局限性,其不考慮任務(wù)變更等突發(fā)因素的干擾且維修工序一旦開始不可中斷的前提假設(shè)與實際復(fù)雜的維修環(huán)境不符,后續(xù)的研究將繼續(xù)改進(jìn)算法以實現(xiàn)動態(tài)調(diào)度，來更加貼近實際機(jī)群機(jī)庫維修調(diào)度。