基于HA算法的艦載機出動作業調度方法

摘 要：

出動離場是艦載機作戰效能發揮的基礎環節，本文研究其出動作業優化調度，將作業過程抽象為柔性車間調度問題，考慮優先序、資源及空間約束建立了混合整數規劃模型，提出了一種基于種群進化搜索與鄰域改進能力的混合遺傳-模擬退火算法，并給出了作業擾動時的重調度策略，通過引入任務表的生成構建了實際作業調度仿真架構。該架構融合了問題輸入、動態擾動與算法，實用推廣性強。仿真結果表明，所提算法收斂性快、解的準確性好、效率高，可有效解決任務表驅動下的出動調度問題;靈敏度分析發現，保障點-軍械加工對全局調度影響最為顯著。

關鍵詞：

艦載機; 出動作業; 柔性車間調度; 混合整數規劃; 混合算法

中圖分類號：

V 211

文獻標志碼： A""" DOI：10.12305/j.issn.1001-506X.2024.05.22

Sortie scheduling method of carrier aircraft based on HA algorithm

LIU Zixuan1， WAN Bing2， SU Xichao3，*， GUO Fang1， LIU Yujie1

（1. Aviation Foundation College， Naval Aviation University， Yantai 264001， China;

2. Coastal Defense College， Naval Aviation University， Yantai 264001， China;

3. School of Aviation Operation and Support， Naval Aviation University， Yantai 264001， China）

Abstract：

The sortie is the fundamental link for the combat effectiveness of carrier aircraft. This paper studies the sortie optimization scheduling of carrier aircraft， abstracting the operation process as a flexible job-shop scheduling problem （FJSP）. A mixed integer programming model is established considering priority order， resources， and spatial constraints. A hybrid genetic operator and simulated annealing （HA） algorithm based on population evolution search and neighborhood improvement ability is proposed， and a rescheduling strategy is provided for job disturbance. A simulation architecture for actual job scheduling is constructed by introducing the generation of task tables. The architecture integrates problem inputs， dynamic perturbations， and algorithms， making it highly practical and generalizable. Simulation results show that the proposed algorithm has fast convergence， good solution accuracy， and high efficiency， and can effectively solve the sortie scheduling problem driven by task tables. Sensitivity analysis found that the support point ordnance processing has the most significant impact on global scheduling.

Keywords：

carrier aircraft; sortie; flexible job-shop scheduling; mixed integer programming （MIP）; hybrid algorithm

0 引 言

艦載機甲板作業過程占據其任務周期的絕大部分時段，包括駐留、維修、布列與調運、保障、出動離場、回收著艦等階段環節［1］，但最為核心的是出動作業調度，其效能是衡量航母綜合作戰能力的關鍵指標［2］，即在給定時間內持續出動飛機架次最多或者給定機隊規模其出動保障時間最短，為此出動作業優化調度對提升艦載機及航母作戰效能具有重要作用。

目前國外公開文獻不多，主要集中在麻省理工學院的航空航天控制實驗室針對航母甲板作業任務規劃（deck operations course of action planner， DCAP）系統的系列研究，代表有Ryan［3-5］基于人-機交互智能決策進行作業調度，提出人工調度與基于Cplex優化器的自動規劃算法的交互方法，并設計了基于多智體能安全協議作業仿真系統來模擬驗證智能決策算法的性能，但以系統介紹為主，缺少人-機交互策略研究。Rajarshi［6］提出了基于排隊網絡的分布式甲板作業調度方法解決動態調度問題。Michini［7］基于馬爾可夫決策逆向強化學習、學徒學習機制進行作業規劃，但設定問題場景較簡單。國內學者研究廣泛，大體分為：基于艦載機作業分階段調度優化算法［8-11］，基于全作業周期的調度效能評估［12-13］，作業任務規劃調度系統仿真與架構設計［14-19］，以及艦面路徑規劃研究［20-24］。前者代表有調運布列、出動離場、甲板保障等優化研究；中者從作戰任務牽引來評估甲板作業對出動能力的影響;后者側重工程應用但已有文獻尚未進行全流程DCAP設計。而在整個DCAP中，出動調度規劃時效性強、作業工序多、空間約束大、時間窗明顯，涉及布列調運、機務勤務保障及離場等多過程，是其中最復雜的一環。針對出動作業，多以布列與調運、機務勤務保障及離場規劃子任務單獨研究，一體化集中設計不多。

為此，本文開展出動作業一體化調度研究，主要借鑒蘇析超等［10］等關于甲板保障研究所提出的保障點概念，Cui［15］等關于離場調度的任務規劃框架，以及Su［25］等關于隨機調度的魯棒性分析，將作業過程抽象成在空間受限條件下柔性車間調度問題（flexible job-shop scheduling problem， FJSP）模型，開展艦載機出動作業調度建模、算法設計與重調度策略構建研究。

而在調度優化算法［26］方面，目前主要有以分枝定界法為代表的精確解法，如基于混合整數規劃（mixed integer progamming， MIP）模型的Gurobi商業優化器，但其官網中對復雜約束的調度問題案例應用較少;采用約束傳播和鄰域縮減的約束規劃方法，但計算復雜度同精確解法;啟發式規則基礎上的構造啟發法和元啟發式搜索算法，如基于鄰域搜索的模擬退火（simulated annealing， SA）、貪婪迭代算法，基于群體智能搜索的進化算法遺傳算法（genetic algorithm， GA）、人工蜂群算法、粒子群優化算法及量子算法等［27-28］，智能算法雖計算效率高但難以獲得全局最優解、容易早熟或限入局部最優;最后還有基于強化學習的調度算法，案例復現中發現效果并不理想。為此，本文結合GA并行搜索和SA鄰域搜索優勢，提出GA與SA算法的并行混合（hybrid" GA and SA， HA）算法來平衡對艦載機出動作業調度優化問題解空間的全局探索與局部開發，實現問題的優化搜索。

出動作業環節的調度優化從甲板態勢與出動任務出發，通過人工啟發式規則與規劃算法生成任務表，并以此作為出動調度的輸入，運用HA算法得到最佳方案，針對實際運行與規劃方案存在偏差開展重調度策略設計，增強作業調度規劃的魯棒性。

1 出動作業問題描述

艦載機作業通常以作戰訓練為牽引，完成出動、空中任務、回收、調運及維修保障等任務，除空中任務外均屬于調度優化問題。其中，出動與回收作業通常集中完成，遂行連續或波次出動任務，而調運過程貫穿艦載機甲板作業全周期，體現在出動環節保障作業、著艦回收跑道清空、甲板機位編排調整及維修保障飛機轉移等，文獻［8-25］開展了大量的研究，維修保障通常在機庫進行，回收調度則由塔臺完成空中排序與復飛管理。艦載機作業調度系統非常復雜，但各環節相對獨立，可分解為不同作業階段進行優化研究，而其中出動作業工序多、時間緊，是艦載機作戰能力的關鍵因素。本文重點研究艦載機出動作業調度，其作業流程示意圖如圖1所示。

在作戰任務驅動下，由規劃算法（基于人工調配或優先規則）生成飛機出動作業相關數據。作業調度則以該規劃任務為輸入，根據飛機初始停機位情況，先后完成調運、保障、調運及最后的起飛離場等階段。其中，調運由牽引車來完成不同停機位間的飛機轉運;保障由各保障點/保障組完成機務勤務保障（如燃油、軍械等）;離場則根據選擇不同起飛位進行［29］。飛機會因各自任務及所處停機位不同，作業階段會不同，作業時間也有差別。如：掛彈數量不同保障時間有差別，保障點飛機可能無需調運或只調運1次，而遠離保障點的飛機可能調運2次，這些基礎數據由任務規劃算法生成。保障點的機務勤務保障為多道工序的子調度問題（屬于資源受限項目調度），文獻［10］和文獻［25］分別開展了靜態調度和魯棒動態調度研究，本文則將飛機保障抽象出最核心的加油與軍械操作（因其他操作可伴隨完成，融入在保障點/組工作中），可在不同保障點/組完成。階段3的調運所涉及的停機位選擇則由最短處理時間優先（shortest processing time first， SPT）規則完成。

艦載機出動作業調度的目標是快速生成任意作戰任務驅動下優化調度方案，同步考慮甲板設備資源的最大化利用、調運與保障忙閑均衡工作等問題。從圖1看，作業過程可抽象為FJSP［30］，即，n個工件J={J1，J2，…，Jn}和m個機器M={M1，M2，…， Mm}，對Ji∈J包含序列工序操作{oi1，oi2，…，oini}，而oij（i=1，2，…，n; j=1，2，…，ni）工序操作可由一組機器集MijM來加工處理，從而完成對n架飛機在4個階段工序上由牽引車、保障點/組、起飛位等機器作業調度，最終起飛離場。然而，出動作業還面臨保障點容量受限、作業防碰撞等空間約束難題，且存在保障及調運過程中作業時間不確定、隨機性等特點。因此，出動作業調度是一個時間、空間約束強的隨機FJSP，一般而言，隨機調度難以求其最優方案，通常獲得期望處理時間下的最佳調度。為此，對調度方案提出了空間約束、魯棒性要求，調度方案可以較好地適應作業過程擾動（如調運避讓、保障點作業轉移帶來的時間延遲等不確定因素），從而實現任意問題輸入-數據轉換-FJSP模型-調度方案求解。

2 建立MIP模型

艦載機出動作業抽象為FJSP模型中，不同出動任務表現為對FJSP作業表的優化調度，而作業表的生成方案由飛機系泊機位、保障點/組及任務要求決定，由作業經驗、規劃算法和人工選擇得到。對給定作業表，調度方案是基于調度模型實現的，為簡化作業過程，作如下假定：飛機在甲板調運時間基本相同，服從N1（μ1，σ21）分布且σ1離差小，因甲板空間有限，牽引路徑時間相對解系泊位調整時間為小量;牽引車的空載滑行時間忽略，因空載速度快，該時間作為小擾動量納入飛機調運時間處理;艦面機務勤務保障集中在幾個保障點/組之一進行，加工時間由飛機任務或保障點人員/保障資源量決定，服從N2（μ2， σ22）分布且σ2離差小，具體分布參數與保障點及飛機任務有關。其調度問題建立如下MIP模型。

目標函數式（1）～式（3）分別為完成作業時間，各機器累計工作時間和機器最大工作時間的最小化;約束式（4）為飛機i第j階段工序的作業完成時間等于開始時間與所選加工機器處理時間之和;式（5）為對任意給定飛機與階段工序，下階段的開始時間應大于上一階段的結束時間;式（6）確保同一機器每時僅處理一個飛機操作，Xkij，i′j′取0/1時同一機器的前后作業操作不滿足前后優先關系;式（7）為對任意給定的飛機與階段工序操作僅能在一臺機器上進行;式（8）為甲板作業的空間約束關系，即對給定機器k，執行oi′j′工序之前需完成其前序工序oij，式中Prek（oi′j′）表示工序oi′j′在k上的前期工序，這是與經典JSP的最主要區別（因其無需考慮空間約束關系）;式（9）～式（11）為決策變量。

3 模型求解算法設計

針對MIP模型，可采用精確解法或近似算法，如分支定界、束搜索算法，有商業優化器IBM ILOG CPLEX的MIP引擎和Gurobi及開源優化器SCIP等，但算法效率隨問題復雜度成指數級增長;也可以采用約束規劃方法求解，如CPLEX商業優化器的CP引擎，Google推出的Ortools開源約束規劃器，從對Benchmark的案例仿真看，CPLEX效果強于Ortools，遠好于MIP搜索，但商業優化器學術版使用規模也受限，而Ortools結果并不理想，經常驗證不到最優值且運算效率并不高。因此，本文接續目前國內外學者廣泛采用的啟發式搜索算法，重點解決隨機調度問題、多目標優化問題、智能搜索算法的效率問題，提出遺傳算法與模擬退火算法的并行混合算法（hybrid genetic algorithm and simulated annealing， HGASA）。隨機調度由作業時間期望值處理，后面結合魯棒調度給出設置策略;多目標優化則通常用加權方式處理為單目標;而智能搜索算法采用種群進化+局部鄰域搜索混合算法求解。算法總體思路：利用GA基于群體進化的全局并行搜索能力強的特點，并結合SA算法的局部鄰域串行搜索的優勢，將二者并串行集成架構，在GA算子基礎上對種群個體進行SA算法搜索并更新種群，而后重新進行迭代直接滿足終端條件。該架構能有效解決GA局部搜索能力弱而容易早熟收斂的問題，SA算法合理設定降溫速度及步/代數可提高鄰域搜索能力，二者綜合實現了對解空間的全局探索與局部深耕開發，確保了解的質量與全局收斂特性，HGASA架構示意圖如圖2所示。

3.1 編碼規則

編碼主要是將解空間映射到搜索空間的過程。調度是完成操作工序-機器的分配和工序的排序過程，故采用機器分配向量U+工序排序向量V兩個序列編碼表示解——調度方案。其中，U的索引號為1，2，…，L，指示n架飛機工序序列的串接{1，2，…，J1o}+{1，2，…，J2o}+…+{1，2，…，Jno}，第1串序列代表第1架飛機工序序列，而索引位代表相應飛機的操作工序。機器分配向量U記為

U=［u1，u2，…，uL］， ui∈Z+;1≤ui≤li;i=1，2，…，L（12）

式中：ui表示索引位所分配的機器號;li表示索引位i對應工序可選機器數量，具體由調度任務的作業表確定。其中，分配機器號表示相應工序的可選機器集中索引號，該處理方便遍歷索引。

而工序排序向量V記為

V=［v1，v2，…，vL］（13）

式中：工序向量為全體飛機加工工序全排列，索引號i為編排順序即加工優先級，元素值vi為對應工序號。因同一飛機的工序有先后性，工序向量生成時需對相同飛機工序進行順序調整。

表1為一個簡單的FJSP示例，如工序向量V=［2，3，7，5，4，1，6］，表示工序順序o12→o13→o32→o22→o21→o11→o31，但因同一飛機工序先后約束，生成編碼時應調整為o11→o12→o31→o21→o22→o13→o32，其過程為檢索統一工件相鄰工序是否順序有誤，若存在錯誤，則交換兩工序索引位，再重新從第一索引位開始檢索，直至所有工序順序無誤。具體過程如下：① 輸入o12→o13→o32→o22→o21→o11→o31;② o11→o13→o32→o22→o21→o12→o31;③ o11→o12→o32→o22→o21→o13→o31;④ o11→o12→o31→o22→o21→o13→o32;⑤ o11→o12→o31→o21→o22→o13→o32;⑥ 輸出o11→o12→o31→o21→o22→o13→o32。

而機器分配向量U=［1，2，1，3，1，1，1］，表示各工序分配機器情況，u2=2表示工序o12分配在機器M3上加工，因其可選機器集為{M1，M3}。

3.2 初始種群生成規則

編碼由機器分配和工序排序構成，任務分配采用最小處理時間優先規則和隨機分配結合，前者考慮了加工時間和機器負載均衡問題。工序排序的生成則可采用隨機選擇工序、飛機剩余工序最多優先、剩余加工時間最大優化相結合。初始種群生成方法如圖3所示。

3.3 調度解碼策略

調度的編排是基于機器加工甘特圖進行的，當然也可采用析取法。X=［U，V］向量（也稱染色體）即為一個調度方案（解），染色體解碼過程是結合機器甘特圖編排進行的。先由U向量依機器進行工序分組，而V向量依加工時間完成各機器分組上工序優先序排列，后檢查先后工序約束、調整機器閑置。機器k上編排工序oij可視為由開始和完成加工（sij， cij）構成的間隔變量，記為itvskij，其大小為Pkij。工序約束檢查策略，主要對相同飛機的工序間隔itvskij進行先后排列檢查，若不滿足則重置工序（sij， cij）。

工序約束調整策略。先后工序包括同一飛機的前后操作工序，及同一機器上不同加工工序的優先關系（約束式（8）要求）。

機器閑置優化策略。完成染色體解碼及工序約束檢查后，甘特圖中可能存在部分機器閑置時間過長問題，該機器上某些工序在滿足約束時可微調順序，減少機器閑置。定義機器k上空間間隔［Sm，Em］∈Idile（k），閑置檢查策略為

max{Sm，Ci，j－1}+Pkij≤Em， j≥2

Sm+Pkij≤Em， j=1（14）

式（14）表示工序oij在機器k上編排時的機器閑置調整判定;Ci，j-1為工序oij上一個工序完成時間。當oij滿足要求時，Sij=max{Sm，Ci，j-1}/Sm;否則，Sij=Em。綜上，調度解碼算法流程如算法1所示。

采用該甘特圖編排方法，前面給出的編碼可解碼成圖4所示調度甘特圖。甘特圖編排中，涉及到相同工件工序前后約束及機器空閑時工序調整。

3.4 多目標處理策略

多目標優化，可以Pareto優化或加權組合處理，但實際調度中更關注作業時間優化，機器負載利用及均衡問題也為考慮因素，故根據調度員偏好對各目標進行加權處理，為

Min f（λ，g）=λ1Cmax+λ2Wtotal+λ3Wmax（15）

其中，各子目標均為處理時間函數，3個目標函數的目的分別為減小完工時間、減小機器總負載或使機器負載更為平衡。取λ1=1，根據調度員需求取λ2=10-2、λ3=10-4，實現在保證最快完工的前提下盡量優先減小機器總負載這一目的;或取λ2=10-4、λ3=10-2，實現在保證最快完工的前提下盡量優先平衡機器負載這一目的。本文選取系數組合為λ1=1、λ2=10-2、λ3=10-4。

3.5 GA算子操作

由圖2架構，GA算子對生成的種群完成個體選擇、交叉和變異操作，并更新種群。個體評價是基于式（15）并取負值所得到的適應度函數來求解，適應度最高的為精英個體，在種群的遺傳操作中將保留。

3.5.1 選擇/復制操作

為探索的全局性，可采用二元輪盤賭、n-size輪盤賭和線性排序方式選擇染色體作父本，其中輪盤賭為從種群N中隨機取2個或n個個體并選擇適應度最高的，線性排序則將種群個體按其適應度升序排序，個體i排序號ri{1，2，…，N}為其優先值，選擇相應個體的概率為

pi=riN（N+1）/2， i=1，2，…，N（16）

選擇操作主要從種群中選出N/2-1對父本，也匹配池用做后面遺傳操作。測試發現，二元輪盤賭給出的區配池較好。

3.5.2 交叉操作

個體染色體［U， V］，機器分配部分U向量隨機設置交叉點后整體交叉換位;工序排序部分V向量隨機設置交叉點后，父本1交叉點間部分遺傳給子代，父本2剔除與父本1已遺傳部分剩余元素順位遺傳給子代，交叉操作后并對生成子代進行工序先后序檢查修復，如算法2。交叉操作如圖5所示（數據取自表1示例），但該示例無同一飛機、同一機器工序優先序調整情況。

3.5.3 變異操作

僅需單一父本進行操作，U向量隨機選擇某個位置進行變異，即從oi，j： {Mij}集合中隨機選一個機器，而V向量變異則隨機選擇兩個位置進行交換，并由算法2進行工序修復。

綜上，在完成選擇/復制、交叉和變異后，原始種群便生成N/2-1對子代個體，再加上保留適應度最大的2個精英個體，生成與原種群規模相同的子代。

3.6 SA局部搜索改進策略

GA算子為群體并行搜索方法，有利于在解空間進行全局探索，但交叉變異處理幅度較大，容易跳過局部鄰域解而導致早熟收斂，缺少局部深耕開發，故引入局部搜索能力強的SA算法進行改進。SA是基于GA種群的每一個體進行改進搜索，從局部鄰域的攝動調節來搜索更好解。核心是通過模擬降溫操作來調節鄰域移動時適應度值未改進解的接受情況，接受概率為

Pr=eΔobj/q=exp（f（X（t）+Δx（t+1））－f（X（t）））q（17）

式（17）進行抽樣選擇，隨著溫度下降接受適應值未改進的概率愈低，即模擬操作開始可以接受差解，但到后期優質解將得以保留。算法步驟如算法3所示。

SA局部改進策略是基于GA種群多點并行操作，主要是彌補GA鄰域操作增量變化過大問題，進一步挖掘種群個體附近的最優解，補齊GA搜索盲區，防止過早收斂并遠離最優解。

4 重調度計算策略

艦載機出動作業中，各種擾動因素可能隨機發生，如作業時間的隨機性、飛機因故障調整其他飛機出動、新增出動飛機以及機器故障等。隨機擾動出現致使原調度方案難以執行，為此提出幾種可行的重調度策略。

策略1，整體順延策略。仍按照調度方案的順序進行，發生延遲工序之后關聯工序順延處理，該法簡單易行，但是容易出現機器閑置過長、各機器負載不均衡問題。

策略2，提高加工效率。對可能延期的工序，增加該工序所選機器的人員、設備及資源數量，提高機器效率，降低處理延遲時間。該法也無需更改調度方案，實操性較強。

策略3，魯棒調度設計。系統調度魯棒性可表示如下：

R（schedule）=∫（fs（δ）－fs） ·P（δ）dδ（18）

式中：P（δ）為擾動發生概率;fs（δ）為擾動后調度目標值;fs為原調度目標值。反映了作業時間不確定性擾動所引起的目標函數值變化的期望。

但該法難以求解，而針對艦載機出動有交貨期要求時，任務完成時間與交貨期之間的空閑（或稱裕度）較好地反映了調度方案的穩定能力強弱（即遇到擾動時，仍能滿足交貨期），故魯棒性調度的度量可表示如下：

R（schedule）=∑ni=1ωi（di－CiJio）∑ni=1ωidi（19）

式中：Jio為飛機i最后一道工序;ωi為飛機i權值，表示該飛機遵守交貨期的重要性，如需緊急起飛的飛機應盡快完成甲板保障并在交貨期前離場。魯棒調度與原系統區別于目標函數選取，優化方法相同。

艦載機連續或波次出動時通常僅有整體時間窗要求，但部分時候對各飛機離艦時刻要求不同，此時最優的調度方案并非最小完成時間等式（1）～式（3）目標，更強調魯棒調度要求。魯棒性越強，抵抗作業期間擾動影響的能力越強，故可將其取max，相應調度目標函數如式（19）。

策略4，重調度設計。在機器故障及減少或插入出動飛機時，原調度方案可能難以執行。此時，考慮采取重調度策略，更新Operations-table（類似表1，增刪其相關內容），并運用HA算法進行優化解算，得到后續任務調度方案。

策略5，追加編排調整。新增出動飛機任務時，不破壞原調度方案基礎上，利用第3.3節調度解碼中甘特圖編排策略完成新添任務的調度設計。

5 仿真實驗

5.1 算例實現

出動作業場景假定基于“庫茲涅佐夫”甲板但采用3條跑道彈射起飛，保障點/組為4組（分別由2個加油通道、1個軍械組等組成），牽引車為3臺，在圖6所示的某假定狀態下分別完成8架、14架、20架飛機的出動調度計算。綜合圖1描述和HA算法，調度實驗流程如圖7示。將任務規劃系統生成的Operations-table進行優化計算，系統出現重大擾動或機器故障等問題，則啟動重調度策略進行規劃。說明，因甲板空間約束限制，生成的任務表中除出動飛機外還應包括占用起飛跑道或保障點但無出動任務的飛機的調運計劃，任務表Operations-table由圖7左側部分規劃算法生成。HA算法參數設置，GA算子種群：100，代數100代，種群初始化由圖3數據生成，隨機兩點交叉概率為90%，變異發生概率10%;SA算子：初溫q=2 000，tmax=20，同溫迭代20步，退火系數λ=0.55，采用快速退火策略重點開展種群鄰域開發。

根據出動飛機位置、狀態不同，艦載機出動作業在甲板18臺機器上選擇部分機器先后經3～6道工序完成，使得調度方案滿足MIP模型要求。

在艦載機作業中，文獻［29］指出機隊通常采取波次或連續出動，飛機集中出動與回收，那么體現在出動作業上的保障過程與離場過程相對分離，可通過調度分解技術中的階段分解進行優化求解，后面的仿真實驗也可以說明這個問題。

8架飛機出動選擇：7-9-10-14-15-16-19-20，需要調運飛機5-6-3-4-1-2，在調度設計中飛機編號映射為1～8號工件，9號則為需調運的占用起飛通道飛機;14架飛機出動選擇：3-2-1-7-8-9-10-14-15-16-17-18-19-20，需調運飛機5-6-4，在調度設計中飛機編號映射為1～14號，需調運飛機嵌在相應空間約束工序當中;20架飛機出動選擇：全部飛機。其中，出動方案的選擇由Operations-table規劃算法完成，甲板狀態、出動規模、任務時間窗及調度員輸入方案均可生成不同任務表。各組實驗結果的迭代變化曲線如圖8所示，調度方案如圖9所示，作業時間情況如表2所示。

（1） 算法收斂性。圖8中，對不同出動規模飛機的保障作業與全過程作業的最優值與種群均值進化計算，從HA算法迭代情況看：一是混合算法大概在20～30代收斂，比單純GA算法或SA算法效率要高，兼顧全局與深挖局部鄰域解;二是種群均值呈現快速收斂狀態，而且該值在算法收斂期后散布較小，表明算法解的質量較高;三是對

比不同出動規模情況，小規模調度問題保障階段最優解可快速得到，隨著規模增大算法復雜度變大，消耗CPU時間變長但收斂變化規律基本相似。

（2） 算法有效性。圖9給出了不同規模下HA算法的收斂解，圖9（a）、圖9（c）、圖9（e）是基于機器的甘特圖，不同顏色塊代表不同工件（映射為不同飛機）的加工過程，其中在某Mk層Oi，j表示工件i的第j工序在該k機器上加工;圖9（b）、圖9（d）、圖9（f）是基于工件的甘特圖，不同顏色塊表示不同機器的加工，其中在某Ji層Oj，k為第j工序在k機器上加工i工件。從工件時序，機器加工先后序及MIP模型空間約束要求等方面看，調度方案無違背約束情況，算例結果由圖8中算法的收斂性保證結果的優化性。仿真中發現：一是該最佳解并非唯一，這是由于調度過程中存在部分工序選擇不同機器對問題最終目標值無影響，即部分工序操作自由度大對整體方案影響較小，比如在解決占用起飛跑道的飛機調運中，牽引車的選擇安排靈活度大;二是作業調度中保障點的軍械加工是關鍵工序，其調度對目標影響較大，相比而言加油工序則較為靈活，比如在保障作業中加油，實驗中發現隨著規模增多，不同飛機先后加油及相同保障點飛機對加油機器的選擇可以有多種方案而不影響最終結果;三是保障與離場階段作業時長相差明顯，從不同出動實驗看，保障時間占總作業時間的80%～88%（具體階段作業時間見表2），而且本實驗中對離場階段僅作單工序處理，若將離場過程展開為并行流水車調度（即考慮甲板滑行段阻塞等待），離場時間會比表2結果要短40%左右，然而本文假定對出動調度問題算法的科學有效性研究影響并不太大，即便如此假定，保障作業時間仍占絕對主體，離場效率較高。

（3） 調度分解可行性與關鍵工序。從圖9調度甘特圖看，假如保障與離場一體化設計，目標優化方向勢必出現邊保障邊離場，即甘特圖中將出現在一波飛機出動中，第1架飛機離場與最后一架的間隔將接近整個作業保障過程，那么在出動規模較大時將出現保障結束后，首架離場飛機可能面臨任務結束進場回收，這將與文獻［29］的艦載機出動模式違背。從安全角度講，保障過程與離場過程整體應相對分離，即保障任務基本結束后方進行集中離場調度。在階段分解過程中，離場階段可以適度提前，與保障作業部分適量交叉，從而可提高作業效率。

圖11分別給出14架和20架飛機出動規模時各機器累計加工時長，橫坐標為加工機器（由牽引車、保障點、起飛位等所屬機器構成）。可以看出，完成相同工序的機器累計時長基本相同，說明最佳方案對加工機器具有較好的均衡性。另一方面，圖11中各保障點-軍械處理的累計時長最大，通過與表5數據比較，最大軍械加工時間基本決定了保障作業的時間（前面甘特圖也給出了類似結論），二者相差甚小。因此，要提高飛機出動效能，應重點考慮軍械工序的增速。

5.2 算法對比分析

在5.1算例仿真條件下，本文HA與GA、SA、候鳥優化（migrating birds optimization， MBO）、差分進化（differential evolution， DE）等經典車間調度問題算法進行比較［26，30］，為便于比較各算法終止條件迭代100代，以模型第1目標作為評價函數，各算法運行20次，得各算法性能指標Cmax情況：最好解、均值、最壞解，結果如表3所示。通過比較，HA算法無論從搜索能力還是解的質量，都要優于其他算法，該算法集成了GA全局性與SA鄰域局部搜索性能并提升了算法效能，同時也好于MBO算法。算法搜索方面，隨著出動規模增加搜到最優解的概率降低，如在8架飛機出動時，多次模擬全部得到最優解；但規模增大時，多次實驗的收斂值存在散布與抖動，即搜索的“最優性”得不到保證，解的穩定性下降。綜合比較，各算法總體效果，HAfGAfDEfMBOfSA。

5.3 模型靈敏度分析

（1） 機器數量變化對調度效率影響

工作機器包括保障點數、牽引車數及起飛位數等。實驗結果表明，一是單獨改變牽引車數量，由3臺降為2臺，在大規模出動中將增加整體作業時間，而由3臺增加為4臺時，并未能顯著提升作業效能;二是起飛位數量的增加，對于離場作業效能的提升比例較大，但由于保障耗時長致使其改變對調度過程影響較小，而反之若故障導致可用起飛位減少時，平行機調度變單機調度作業時間將顯著增加，影響作戰效能;三是保障點中的供油管線增加，并不能明顯提高出動效能，下圖12是對20架飛機出動調度的仿真實驗，與油管增加前相比作業時間縮短為119.5 min，提速不到1 min。但是若對保障點軍械工作組，作業時間將大幅度縮小到93.6 min，減少近30 min，當然這種設定取于該軍械工序的設備數量及自動化程度。目前，美國新改進的福特級航母將采用一站式保障［31］，加油、軍械等保障可在各保障點同步并行作業，該方法將極大提升保障與出動效能。一站式保障將是未來甲板作業主要改進方式。

（2） Operations-table生成對調度影響

出動任務由圖7流程生成任務表，而對不同出動規模的調度，甲板空間約束是影響任務表的首要因素。小規模出動時問題復雜度低，其任務表對應的HA算法方案最優性可以得到保證。但隨著出動規模增多，對于不同甲板艦載機布列狀態，各飛機作業工序選擇增多，可原位保障、也可跨保障點作業。出動飛機與駐留飛機的選擇組合多，不同駐留方案對出動保障、離場都是空間約束，直接影響任務表中不同飛機工序的生成。對于相同出動規模飛機，不同任務表所得到的最佳目標值差異較大。通過實驗分析知，小規模時任務表優先選擇保障點2～保障點4飛機出動，保障點1的附近飛機選擇繼續駐留并調運騰空起飛跑道;中規模時任務表盡可能平衡保障點2～保障點4飛機規模，盡可能不安排跨點保障，保障點1飛機出動安排宜少;大規模時任務表的生成應平衡各保障點的飛機規模，空間約束直接納入相應飛機相關工序當中。以上啟發式規則可極大提高任務表規劃效率，直接影響最終出動調度效能。實驗表明，任務表的不同選擇可導致該出動調度的最佳目標值間的差異達30%。

6 結 論

（1） HA算法綜合了GA并行搜索與SA局部搜索優點，設計了機器、飛機兩段式編解碼和GA種群進化與SA鄰域搜索結構很好切合了調度問題模型，算法收斂性快、穩定性強，與經典算法相比其解的散布均小、解的質量好，能有效解決艦載機出動調度優化問題。當然算法隨著出動規模增大，效率有所降低。

（2） 提出了空間約束通過任務表嵌在飛機作業工序中處理策略，實現了實際問題與FJSP模型的匹配，仿真發現任務表的不同生成策略對調度結果影響較大，出動飛機與駐留飛機的選擇應基于各保障點均衡原則規劃。

（3） 通過對8、14、20架不同規模飛機的出動調度實驗，保障、離場作業應相對分離規劃，保障點-加油設備的增加對調度影響不顯著，而保障點-軍械為關鍵工序，對整個調度效能影響較大，若每個保障點增加1臺軍械點，出動效率提高達25%。對出動規模小于20架次時，牽引車3臺基本可滿足要求而不影響整體調度效果。離場階段的調度性能還可以進一步提升，但不影響本文算法應用與相關分析結論。因此，出動作業保障應提升軍械加工效率或增加其設備。

（4） 提出了針對隨機作業過程中的重調度策略，這是算法應用到實際問題中的處理架構，可根據作業進程選擇策略并重新調優化，增強了算法魯棒性能，具有較好實用價值。

參考文獻

［1］ 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.

［2］ 劉翱， 劉克. 艦載機保障作業調度問題研究進展［J］. 系統工程理論與實踐， 2017， 37（1）： 49-60.

LIU A， LIU K. Advances in carrier-based aircraft deck operation scheduling［J］. Systems Engineering-Theory amp; Practice， 2017， 37（1）： 49-60.

［3］ RYAN J C. Evaluating safety protocols for manned unmanned environments through agent based simulation［D］. Massachusetts： Massachusetts Institute of Technology， 2014.

［4］ RYAN J C， BANERJEE A G， CUMMINGS M L， et al. Comparing the performance of expertuser heuristics and an integer linear program in aircraft carrier deck operations［J］. IEEE Trans.on Cybernetics， 2014， 44（6）： 761-773.

［5］ 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.

［6］ RAJARSHI G D. A queueing network based approach to distributed aircraft carrier deck scheduling［C］∥Proc.of the AIAA Infotech@Aerospace Conference， 2011： 1514.

［7］ MICHINI B， HOW J P. A human-interactive course of action planner for aircraft carrier deck operations［C］∥Proc.of the AIAA Infotech@Aerospace Conference， 2011： 1515.

［8］ 張智， 林圣琳， 朱齊丹， 等. 考慮運動學約束的不規則目標遺傳避碰規劃算法［J］. 航空學報， 2015， 36（4）： 1348-1358.

ZHANG Z， LIN S L， ZHU Q D， et al. Genetic collision avoidance planning algorithm for irregular shaped object with kinematics constraint［J］. Acta Aeronautica et Astronautica Sinica， 2015， 36（4）： 1348-1358.

［9］ 蘇析超， 韓維， 蕭衛， 等. 基于Memetic算法的艦載機艦面一站式保障調度［J］. 系統工程與電子技術， 2016， 38（10）： 2303-2309.

SU X C， HAN W， XIAO W， et al. Pit-stop support scheduling on deck of carrier plane based on Memetic algorithm［J］. Systems Engineering and Electronics， 2016， 38（10）： 2303-2309.

［10］ 蘇析超， 韓維， 張勇， 等. 考慮人機匹配模式的艦載機甲板機務勤務保障調度算法［J］. 航空學報， 2018， 39（12）： 222314.

SU X C， HAN W， ZHANG Y， et al. Scheduling algorithm for maintenace and service support of carrier-based aircraft on flight deck with different man-aircraft matching patterns［J］. Acta Aeronautica Sinica， 2018， 39（12）： 222314.

［11］ WANG X W， LIU J， SU X C， et al. A review on carrier aircraft dispatch path planning and control on deck［J］. China Journal of Aeronautics， 2022， 33（12）： 3039-3057.

［12］ 鄭茂， 黃勝， 王超. 優先網絡排隊的艦載機出動回收能力研究［J］. 北京理工大學學報， 2013， 33（10）： 1051-1055.

ZHENG M， HUANG S， WANG C. Research on aircraft sortie generation rate with the use of HOL closed queueing network model［J］. Transactions of Beijing Institute of Technology， 2013， 33（10）： 1051-1055.

［13］ 楊放青， 王超， 姜濱， 等. 艦載機出動回收調度策略生成方法［J］. 北京理工大學學報， 2018， 38（10）： 1030-1036.

YANG F Q， WANG C， JIANG B， et al. A method of policy automated generation for carrier aircraft sortie and recovery scheduling［J］. Transactions of Beijing Institute of Technology， 2018， 38（10）： 1030-1036.

［14］ WU Y， QU X J， Obstacle avoidance and path planning for carrier aircraft launching［J］. Chinese Journal of Aeronautics， 2015， 28（3）： 695-703.

［15］ CUI J P， WU Y， SU X C， et al. A task allocation model for a team of aircraft launching on the carrier［J］. Mathematical Problems in Engineering， 2018， 2018： 7920806.

［16］ SU X C， HAN W， WU Y， et al. A proactive robust scheduling method for aircraft carrier flight deck operations with stochastic durations［J］. Complexity， 2018， 2018： 6932985.

［17］ GUO F， HAN W， SU X C， et al. A bi-population immune algorithm for weapon transportation support scheduling problem with pickup and delivery on aircraft carrier deck［J］. Defence Technology， 2021， 22： 119-134.

［18］ LIU Y J， HAN W， SU X C， et al. Optimization of fixed aviation support resource station configuration for aircraft carrier based on aircraft dispatch mission scheduling［J］. Chinese Journal of Aeronautics， 2023， 36（2）： 127-138.

［19］ ZHENG M， YANG F Q， DONG Z P， et al. Carrier-borne aircrafts aviation operation automated scheduling using multiplicative weights apprenticeship learning［J］. International Journal of Advanced Robotic Systems， 2019， 16（1）. https：∥doi.org/10.1177/1729881419828917.

［20］ LIU J， HAN W， WANG X W， et al. Research on cooperative trajectory planning and tracking problem for multiple carrier aircraft on the deck［J］. IEEE Systems Journal， 2019， 14（2）： 3027-3038.

［21］ WU Y， LOW K H， HU X. Trajectory-based flight scheduling for AirMetro in urban environments by conflict resolution［J］. Transportation Research Part C： Emerging Technologies， 2021， 131： 103355.

［22］ WU Y， QU X J. Path planning for taxi of carrier aircraft launching［J］. Science China Technological Sciences， 2013， 56（6）： 1561-1570.

［23］ SU X C， LI Z Y， SONG J Y， et al. A path planning method for carrier aircraft on deck combining artificial experience and intelligent search［C］∥Proc.of the 4th International Workshop on Materials Science and Engineering， 2018， 381（1）： 012194.

［24］ LIU J， HAN W， LI J， et al. Integration design of sortie sche-duling for carrier aircrafts based on hybrid flexible flowshop［J］. IEEE Systems Journal， 2019， 14（1）： 1503-1511.

［25］ SU X C， HAN W， WU Y， et al. A robust scheduling optimization method for flight deck operations of aircraft carrier with ternary interval durations［J］. IEEE Access， 2018， 6： 69918-69936.

［26］ RONALD L R. Optimization in operations research［M］. 2nd ed. Upper Saddle River， NJ： Pearson Higher Education， 2017： 5-15.

［27］ YUAN Y， XU H. Multiobjective flexible job shop scheduling using memetic algorithms［J］. IEEE Trans.on Automation Science and Engineering， 2015， 12（1）： 336-353.

［28］ DRISS I， MOUSS K N， LAGGOUN A. A new genetic algorithm for flexible job shop scheduling problems［J］. Journal of Mechanical Science and Technology， 2015， 29（3）： 1273-1281.

［29］ 姜龍光. 國外航母航空保障系統［M］. 北京： 國防工業出版社， 2016.

JIANG L G. Foreign aircraft carrier aviation support system［M］. Beijing： National Defense Industry Press， 2016.

［30］ PEZZELLA F， MORGANTI G， CIASCHETTI， et al. A genetic algorithm for the flexible job-shop scheduling problem［J］. Compu-ters amp; Operations Research， 2008， 35（10）： 3202-3212.

［31］ 劉相春. 美國“福特”級航母“一站式保障”技術特征和關鍵技術分析［J］. 中國艦船研究， 2013， 8（6）： 1-5.

LIU X C. Technical features and critical technologies for the “pit-stop” aircraft servicing adopted by ford class aircraft carriers［J］. Chinese Journal of Ship Research， 2013， 8（6）： 1-5.

作者簡介

劉子玄（1998—），男，碩士研究生，主要研究方向為艦載航空保障。

萬 兵（1991—），男，講師，博士，主要研究方向為艦載航空保障、飛行器制導控制與動力學。

蘇析超（1989—），男，副教授，博士，主要研究方向為艦載航空保障。

郭 放（1990—），男，博士研究生，主要研究方向為艦載航空保障。

劉玉杰（1983—），男，高級工程師，博士，主要研究方向為艦載航空保障、艦載機動力學。