基于HTLBO算法的艦載機機群機庫維修任務調度

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

(1. 海軍航空大學航空作戰勤務學院, 山東 煙臺 264001; 2. 海軍航空大學航空基礎學院, 山東 煙臺 264001)

0 引 言

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

為提高艦載機機群的出動效率,縮短艦載機的維修保障時間,要求形成高效的維修保障任務規劃。但相較于陸基修理廠,航母機庫內空間小、環境復雜,對維修人員協同程度要求高，維修人員編制、設施設備等資源受限且對維修時限要求嚴格,給維修任務調度帶來了挑戰。基于航母機庫的環境特點,科學地對機庫內維修人員和設施設備進行調度時序規劃和資源分配,縮短作業時間,提高資源的利用率,是提高機庫內機群維修效率的關鍵,這對艦載機機群盡快恢復可用狀態并形成戰斗力具有重要的意義。

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

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

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

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

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

1 問題描述

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

1.1 作業流程

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

1.2 維修人員與技能

1.3 維修設備/車間

1.4 維修工位空間

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

2 模型建立

本節將在模型假設的基礎上結合模型的約束條件建立MTSPAH的數學優化模型。

2.1 模型假設

為建立MTSPAH模型,提出如下假設:

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

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

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

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

2.2 模型的變量與約束條件

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

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

pi:第i架艦載機的維修停機位;

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

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

At:機群在t時刻處于執行狀態的所有維修工序集;

Ait:第i架艦載機在t時刻處于執行狀態的維修工序集;

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

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

dij:工序Oij的維修作業工時;

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

nsik:第i架艦載機第k類工位容納的人員數量;

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

Emij:維修工序Oij的保障結束時間。

決策變量如下:

約束條件包括:

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

2.3 目標函數

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

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

(12)

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

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

(13)

3 HTLBO算法設計

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

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

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

本文在標準TLBO算法[18]的基礎上,針對MTSPAH模型的特點,設計了一種HTLBO算法,算法流程如圖3所示。

算法具體的執行步驟如下:

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

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

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

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

步驟 5令G=G+1,判斷是否達到迭代終止條件,若是,則迭代終止,并輸出最優教師個體對應的維修調度方案和資源分配方案;否則,轉入步驟2繼續教與學優化迭代。

HTLBO的主要改進點體現在以下3個方面:

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

(2) 在學生學習階段,引入峰值交叉算子進行種群個體間的交叉學習;

(3) 在強化學習階段,引入LA-AVNS操作對精英種群進行局部增強搜索。

3.1 編碼操作

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

3.2 解碼操作

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

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

3.3 適應度函數

為便于算法進行個體適應度比較,將字典序分層目標通過賦予權重組合為單目標,并定義個體適應度為

f=(1-WA)+αLBM

(14)

式中:α(0<α?1)為維修人員負載方差的權重系數,維修調度指揮員可根據保障需求進行權重調節,鑒于艦載機機群機庫維修任務的需求為優先保證提供完好的滿足波次需求數量的艦載機,故可將權重系數取為小量。

3.4 教師教學階段

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

(15)

3.5 學生學習階段

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

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

(16)

(17)

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

(18)

鑒于峰值區間包含了個體的優良基因,算法采用兩點交叉進行峰值區間的優先數編碼置換。

3.6 強化學習階段

本階段是在經典TLBO算法的基礎上引入的新階段,目的是對優秀教師個體做進一步的強化學習,以更好地引導班級群體的學習更新。對此,基于LA-AVNS框架,結合本問題特性,設計相應的搜索鄰域如下:

(1) 交換鄰域

隨機選取兩個無緊前緊后約束的維修工序,交換其編碼優先數。

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

隨機選取一個維修故障工序,查詢其緊前工序的結束時間并將其作為可插入區間的起始值,本工序開始時間為區間終止,將該工序插入區間內的任意位置。該鄰域主要可使得故障艦載機盡快實現維修。

4 維修案例仿真分析

4.1 維修案例的構建

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

表1 案例任務設置機庫供電站與機群停機位覆蓋關系 Table 1 Case task hangar power station and fleet parking space covering relations min

針對同型號艦載機,構建定檢的通用化單機定檢流程AON有向網絡圖如圖5所示,虛線代表與虛擬工序連接。

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

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

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

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

4.2 算法仿真對比分析

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

表4 算法結果統計數據 Table 4 Algorithm result statistics

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

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

表5 機群保障任務 Table 5 Aircraft group support tasks

表6 高強度任務仿真結果統計數據 Table 6 Simulation results of high-intensity tasks

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

5 結 論

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