摘 要：

出動(dòng)離場(chǎng)是艦載機(jī)作戰(zhàn)效能發(fā)揮的基礎(chǔ)環(huán)節(jié)，本文研究其出動(dòng)作業(yè)優(yōu)化調(diào)度，將作業(yè)過(guò)程抽象為柔性車間調(diào)度問(wèn)題，考慮優(yōu)先序、資源及空間約束建立了混合整數(shù)規(guī)劃模型，提出了一種基于種群進(jìn)化搜索與鄰域改進(jìn)能力的混合遺傳-模擬退火算法，并給出了作業(yè)擾動(dòng)時(shí)的重調(diào)度策略，通過(guò)引入任務(wù)表的生成構(gòu)建了實(shí)際作業(yè)調(diào)度仿真架構(gòu)。該架構(gòu)融合了問(wèn)題輸入、動(dòng)態(tài)擾動(dòng)與算法，實(shí)用推廣性強(qiáng)。仿真結(jié)果表明，所提算法收斂性快、解的準(zhǔn)確性好、效率高，可有效解決任務(wù)表驅(qū)動(dòng)下的出動(dòng)調(diào)度問(wèn)題;靈敏度分析發(fā)現(xiàn)，保障點(diǎn)-軍械加工對(duì)全局調(diào)度影響最為顯著。

關(guān)鍵詞：

艦載機(jī); 出動(dòng)作業(yè); 柔性車間調(diào)度; 混合整數(shù)規(guī)劃; 混合算法

中圖分類號(hào)：

V 211

文獻(xiàn)標(biāo)志碼： 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 引 言

艦載機(jī)甲板作業(yè)過(guò)程占據(jù)其任務(wù)周期的絕大部分時(shí)段，包括駐留、維修、布列與調(diào)運(yùn)、保障、出動(dòng)離場(chǎng)、回收著艦等階段環(huán)節(jié)［1］，但最為核心的是出動(dòng)作業(yè)調(diào)度，其效能是衡量航母綜合作戰(zhàn)能力的關(guān)鍵指標(biāo)［2］，即在給定時(shí)間內(nèi)持續(xù)出動(dòng)飛機(jī)架次最多或者給定機(jī)隊(duì)規(guī)模其出動(dòng)保障時(shí)間最短，為此出動(dòng)作業(yè)優(yōu)化調(diào)度對(duì)提升艦載機(jī)及航母作戰(zhàn)效能具有重要作用。

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

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

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

出動(dòng)作業(yè)環(huán)節(jié)的調(diào)度優(yōu)化從甲板態(tài)勢(shì)與出動(dòng)任務(wù)出發(fā)，通過(guò)人工啟發(fā)式規(guī)則與規(guī)劃算法生成任務(wù)表，并以此作為出動(dòng)調(diào)度的輸入，運(yùn)用HA算法得到最佳方案，針對(duì)實(shí)際運(yùn)行與規(guī)劃方案存在偏差開展重調(diào)度策略設(shè)計(jì)，增強(qiáng)作業(yè)調(diào)度規(guī)劃的魯棒性。

1 出動(dòng)作業(yè)問(wèn)題描述

艦載機(jī)作業(yè)通常以作戰(zhàn)訓(xùn)練為牽引，完成出動(dòng)、空中任務(wù)、回收、調(diào)運(yùn)及維修保障等任務(wù)，除空中任務(wù)外均屬于調(diào)度優(yōu)化問(wèn)題。其中，出動(dòng)與回收作業(yè)通常集中完成，遂行連續(xù)或波次出動(dòng)任務(wù)，而調(diào)運(yùn)過(guò)程貫穿艦載機(jī)甲板作業(yè)全周期，體現(xiàn)在出動(dòng)環(huán)節(jié)保障作業(yè)、著艦回收跑道清空、甲板機(jī)位編排調(diào)整及維修保障飛機(jī)轉(zhuǎn)移等，文獻(xiàn)［8-25］開展了大量的研究，維修保障通常在機(jī)庫(kù)進(jìn)行，回收調(diào)度則由塔臺(tái)完成空中排序與復(fù)飛管理。艦載機(jī)作業(yè)調(diào)度系統(tǒng)非常復(fù)雜，但各環(huán)節(jié)相對(duì)獨(dú)立，可分解為不同作業(yè)階段進(jìn)行優(yōu)化研究，而其中出動(dòng)作業(yè)工序多、時(shí)間緊，是艦載機(jī)作戰(zhàn)能力的關(guān)鍵因素。本文重點(diǎn)研究艦載機(jī)出動(dòng)作業(yè)調(diào)度，其作業(yè)流程示意圖如圖1所示。

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

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

2 建立MIP模型

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

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

3 模型求解算法設(shè)計(jì)

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

3.1 編碼規(guī)則

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

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

式中：ui表示索引位所分配的機(jī)器號(hào);li表示索引位i對(duì)應(yīng)工序可選機(jī)器數(shù)量，具體由調(diào)度任務(wù)的作業(yè)表確定。其中，分配機(jī)器號(hào)表示相應(yīng)工序的可選機(jī)器集中索引號(hào)，該處理方便遍歷索引。

而工序排序向量V記為

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

式中：工序向量為全體飛機(jī)加工工序全排列，索引號(hào)i為編排順序即加工優(yōu)先級(jí)，元素值vi為對(duì)應(yīng)工序號(hào)。因同一飛機(jī)的工序有先后性，工序向量生成時(shí)需對(duì)相同飛機(jī)工序進(jìn)行順序調(diào)整。

表1為一個(gè)簡(jiǎn)單的FJSP示例，如工序向量V=［2，3，7，5，4，1，6］，表示工序順序o12→o13→o32→o22→o21→o11→o31，但因同一飛機(jī)工序先后約束，生成編碼時(shí)應(yīng)調(diào)整為o11→o12→o31→o21→o22→o13→o32，其過(guò)程為檢索統(tǒng)一工件相鄰工序是否順序有誤，若存在錯(cuò)誤，則交換兩工序索引位，再重新從第一索引位開始檢索，直至所有工序順序無(wú)誤。具體過(guò)程如下：① 輸入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。

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

3.2 初始種群生成規(guī)則

編碼由機(jī)器分配和工序排序構(gòu)成，任務(wù)分配采用最小處理時(shí)間優(yōu)先規(guī)則和隨機(jī)分配結(jié)合，前者考慮了加工時(shí)間和機(jī)器負(fù)載均衡問(wèn)題。工序排序的生成則可采用隨機(jī)選擇工序、飛機(jī)剩余工序最多優(yōu)先、剩余加工時(shí)間最大優(yōu)化相結(jié)合。初始種群生成方法如圖3所示。

3.3 調(diào)度解碼策略

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

工序約束調(diào)整策略。先后工序包括同一飛機(jī)的前后操作工序，及同一機(jī)器上不同加工工序的優(yōu)先關(guān)系（約束式（8）要求）。

機(jī)器閑置優(yōu)化策略。完成染色體解碼及工序約束檢查后，甘特圖中可能存在部分機(jī)器閑置時(shí)間過(guò)長(zhǎng)問(wèn)題，該機(jī)器上某些工序在滿足約束時(shí)可微調(diào)順序，減少機(jī)器閑置。定義機(jī)器k上空間間隔［Sm，Em］∈Idile（k），閑置檢查策略為

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

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

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

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

3.4 多目標(biāo)處理策略

多目標(biāo)優(yōu)化，可以Pareto優(yōu)化或加權(quán)組合處理，但實(shí)際調(diào)度中更關(guān)注作業(yè)時(shí)間優(yōu)化，機(jī)器負(fù)載利用及均衡問(wèn)題也為考慮因素，故根據(jù)調(diào)度員偏好對(duì)各目標(biāo)進(jìn)行加權(quán)處理，為

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

其中，各子目標(biāo)均為處理時(shí)間函數(shù)，3個(gè)目標(biāo)函數(shù)的目的分別為減小完工時(shí)間、減小機(jī)器總負(fù)載或使機(jī)器負(fù)載更為平衡。取λ1=1，根據(jù)調(diào)度員需求取λ2=10-2、λ3=10-4，實(shí)現(xiàn)在保證最快完工的前提下盡量?jī)?yōu)先減小機(jī)器總負(fù)載這一目的;或取λ2=10-4、λ3=10-2，實(shí)現(xiàn)在保證最快完工的前提下盡量?jī)?yōu)先平衡機(jī)器負(fù)載這一目的。本文選取系數(shù)組合為λ1=1、λ2=10-2、λ3=10-4。

3.5 GA算子操作

由圖2架構(gòu)，GA算子對(duì)生成的種群完成個(gè)體選擇、交叉和變異操作，并更新種群。個(gè)體評(píng)價(jià)是基于式（15）并取負(fù)值所得到的適應(yīng)度函數(shù)來(lái)求解，適應(yīng)度最高的為精英個(gè)體，在種群的遺傳操作中將保留。

3.5.1 選擇/復(fù)制操作

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

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

選擇操作主要從種群中選出N/2-1對(duì)父本，也匹配池用做后面遺傳操作。測(cè)試發(fā)現(xiàn)，二元輪盤賭給出的區(qū)配池較好。

3.5.2 交叉操作

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

3.5.3 變異操作

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

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

3.6 SA局部搜索改進(jìn)策略

GA算子為群體并行搜索方法，有利于在解空間進(jìn)行全局探索，但交叉變異處理幅度較大，容易跳過(guò)局部鄰域解而導(dǎo)致早熟收斂，缺少局部深耕開發(fā)，故引入局部搜索能力強(qiáng)的SA算法進(jìn)行改進(jìn)。SA是基于GA種群的每一個(gè)體進(jìn)行改進(jìn)搜索，從局部鄰域的攝動(dòng)調(diào)節(jié)來(lái)搜索更好解。核心是通過(guò)模擬降溫操作來(lái)調(diào)節(jié)鄰域移動(dòng)時(shí)適應(yīng)度值未改進(jìn)解的接受情況，接受概率為

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

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

SA局部改進(jìn)策略是基于GA種群多點(diǎn)并行操作，主要是彌補(bǔ)GA鄰域操作增量變化過(guò)大問(wèn)題，進(jìn)一步挖掘種群個(gè)體附近的最優(yōu)解，補(bǔ)齊GA搜索盲區(qū)，防止過(guò)早收斂并遠(yuǎn)離最優(yōu)解。

4 重調(diào)度計(jì)算策略

艦載機(jī)出動(dòng)作業(yè)中，各種擾動(dòng)因素可能隨機(jī)發(fā)生，如作業(yè)時(shí)間的隨機(jī)性、飛機(jī)因故障調(diào)整其他飛機(jī)出動(dòng)、新增出動(dòng)飛機(jī)以及機(jī)器故障等。隨機(jī)擾動(dòng)出現(xiàn)致使原調(diào)度方案難以執(zhí)行，為此提出幾種可行的重調(diào)度策略。

策略1，整體順延策略。仍按照調(diào)度方案的順序進(jìn)行，發(fā)生延遲工序之后關(guān)聯(lián)工序順延處理，該法簡(jiǎn)單易行，但是容易出現(xiàn)機(jī)器閑置過(guò)長(zhǎng)、各機(jī)器負(fù)載不均衡問(wèn)題。

策略2，提高加工效率。對(duì)可能延期的工序，增加該工序所選機(jī)器的人員、設(shè)備及資源數(shù)量，提高機(jī)器效率，降低處理延遲時(shí)間。該法也無(wú)需更改調(diào)度方案，實(shí)操性較強(qiáng)。

策略3，魯棒調(diào)度設(shè)計(jì)。系統(tǒng)調(diào)度魯棒性可表示如下：

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

式中：P（δ）為擾動(dòng)發(fā)生概率;fs（δ）為擾動(dòng)后調(diào)度目標(biāo)值;fs為原調(diào)度目標(biāo)值。反映了作業(yè)時(shí)間不確定性擾動(dòng)所引起的目標(biāo)函數(shù)值變化的期望。

但該法難以求解，而針對(duì)艦載機(jī)出動(dòng)有交貨期要求時(shí)，任務(wù)完成時(shí)間與交貨期之間的空閑（或稱裕度）較好地反映了調(diào)度方案的穩(wěn)定能力強(qiáng)弱（即遇到擾動(dòng)時(shí)，仍能滿足交貨期），故魯棒性調(diào)度的度量可表示如下：

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

式中：Jio為飛機(jī)i最后一道工序;ωi為飛機(jī)i權(quán)值，表示該飛機(jī)遵守交貨期的重要性，如需緊急起飛的飛機(jī)應(yīng)盡快完成甲板保障并在交貨期前離場(chǎng)。魯棒調(diào)度與原系統(tǒng)區(qū)別于目標(biāo)函數(shù)選取，優(yōu)化方法相同。

艦載機(jī)連續(xù)或波次出動(dòng)時(shí)通常僅有整體時(shí)間窗要求，但部分時(shí)候?qū)Ω黠w機(jī)離艦時(shí)刻要求不同，此時(shí)最優(yōu)的調(diào)度方案并非最小完成時(shí)間等式（1）～式（3）目標(biāo)，更強(qiáng)調(diào)魯棒調(diào)度要求。魯棒性越強(qiáng)，抵抗作業(yè)期間擾動(dòng)影響的能力越強(qiáng)，故可將其取max，相應(yīng)調(diào)度目標(biāo)函數(shù)如式（19）。

策略4，重調(diào)度設(shè)計(jì)。在機(jī)器故障及減少或插入出動(dòng)飛機(jī)時(shí)，原調(diào)度方案可能難以執(zhí)行。此時(shí)，考慮采取重調(diào)度策略，更新Operations-table（類似表1，增刪其相關(guān)內(nèi)容），并運(yùn)用HA算法進(jìn)行優(yōu)化解算，得到后續(xù)任務(wù)調(diào)度方案。

策略5，追加編排調(diào)整。新增出動(dòng)飛機(jī)任務(wù)時(shí)，不破壞原調(diào)度方案基礎(chǔ)上，利用第3.3節(jié)調(diào)度解碼中甘特圖編排策略完成新添任務(wù)的調(diào)度設(shè)計(jì)。

5 仿真實(shí)驗(yàn)

5.1 算例實(shí)現(xiàn)

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

根據(jù)出動(dòng)飛機(jī)位置、狀態(tài)不同，艦載機(jī)出動(dòng)作業(yè)在甲板18臺(tái)機(jī)器上選擇部分機(jī)器先后經(jīng)3～6道工序完成，使得調(diào)度方案滿足MIP模型要求。

在艦載機(jī)作業(yè)中，文獻(xiàn)［29］指出機(jī)隊(duì)通常采取波次或連續(xù)出動(dòng)，飛機(jī)集中出動(dòng)與回收，那么體現(xiàn)在出動(dòng)作業(yè)上的保障過(guò)程與離場(chǎng)過(guò)程相對(duì)分離，可通過(guò)調(diào)度分解技術(shù)中的階段分解進(jìn)行優(yōu)化求解，后面的仿真實(shí)驗(yàn)也可以說(shuō)明這個(gè)問(wèn)題。

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

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

比不同出動(dòng)規(guī)模情況，小規(guī)模調(diào)度問(wèn)題保障階段最優(yōu)解可快速得到，隨著規(guī)模增大算法復(fù)雜度變大，消耗CPU時(shí)間變長(zhǎng)但收斂變化規(guī)律基本相似。

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

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

圖11分別給出14架和20架飛機(jī)出動(dòng)規(guī)模時(shí)各機(jī)器累計(jì)加工時(shí)長(zhǎng)，橫坐標(biāo)為加工機(jī)器（由牽引車、保障點(diǎn)、起飛位等所屬機(jī)器構(gòu)成）?？梢钥闯?，完成相同工序的機(jī)器累計(jì)時(shí)長(zhǎng)基本相同，說(shuō)明最佳方案對(duì)加工機(jī)器具有較好的均衡性。另一方面，圖11中各保障點(diǎn)-軍械處理的累計(jì)時(shí)長(zhǎng)最大，通過(guò)與表5數(shù)據(jù)比較，最大軍械加工時(shí)間基本決定了保障作業(yè)的時(shí)間（前面甘特圖也給出了類似結(jié)論），二者相差甚小。因此，要提高飛機(jī)出動(dòng)效能，應(yīng)重點(diǎn)考慮軍械工序的增速。

5.2 算法對(duì)比分析

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

5.3 模型靈敏度分析

（1） 機(jī)器數(shù)量變化對(duì)調(diào)度效率影響

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

（2） Operations-table生成對(duì)調(diào)度影響

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

6 結(jié) 論

（1） HA算法綜合了GA并行搜索與SA局部搜索優(yōu)點(diǎn)，設(shè)計(jì)了機(jī)器、飛機(jī)兩段式編解碼和GA種群進(jìn)化與SA鄰域搜索結(jié)構(gòu)很好切合了調(diào)度問(wèn)題模型，算法收斂性快、穩(wěn)定性強(qiáng)，與經(jīng)典算法相比其解的散布均小、解的質(zhì)量好，能有效解決艦載機(jī)出動(dòng)調(diào)度優(yōu)化問(wèn)題。當(dāng)然算法隨著出動(dòng)規(guī)模增大，效率有所降低。

（2） 提出了空間約束通過(guò)任務(wù)表嵌在飛機(jī)作業(yè)工序中處理策略，實(shí)現(xiàn)了實(shí)際問(wèn)題與FJSP模型的匹配，仿真發(fā)現(xiàn)任務(wù)表的不同生成策略對(duì)調(diào)度結(jié)果影響較大，出動(dòng)飛機(jī)與駐留飛機(jī)的選擇應(yīng)基于各保障點(diǎn)均衡原則規(guī)劃。

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

（4） 提出了針對(duì)隨機(jī)作業(yè)過(guò)程中的重調(diào)度策略，這是算法應(yīng)用到實(shí)際問(wèn)題中的處理架構(gòu)，可根據(jù)作業(yè)進(jìn)程選擇策略并重新調(diào)優(yōu)化，增強(qiáng)了算法魯棒性能，具有較好實(shí)用價(jià)值。

參考文獻(xiàn)

［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ī)保障作業(yè)調(diào)度問(wèn)題研究進(jìn)展［J］. 系統(tǒng)工程理論與實(shí)踐， 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］ 張智， 林圣琳， 朱齊丹， 等. 考慮運(yùn)動(dòng)學(xué)約束的不規(guī)則目標(biāo)遺傳避碰規(guī)劃算法［J］. 航空學(xué)報(bào)， 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］ 蘇析超， 韓維， 蕭衛(wèi)， 等. 基于Memetic算法的艦載機(jī)艦面一站式保障調(diào)度［J］. 系統(tǒng)工程與電子技術(shù)， 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ī)匹配模式的艦載機(jī)甲板機(jī)務(wù)勤務(wù)保障調(diào)度算法［J］. 航空學(xué)報(bào)， 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］ 鄭茂， 黃勝， 王超. 優(yōu)先網(wǎng)絡(luò)排隊(duì)的艦載機(jī)出動(dòng)回收能力研究［J］. 北京理工大學(xué)學(xué)報(bào)， 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ī)出動(dòng)回收調(diào)度策略生成方法［J］. 北京理工大學(xué)學(xué)報(bào)， 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］ 姜龍光. 國(guó)外航母航空保障系統(tǒng)［M］. 北京： 國(guó)防工業(yè)出版社， 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］ 劉相春. 美國(guó)“福特”級(jí)航母“一站式保障”技術(shù)特征和關(guān)鍵技術(shù)分析［J］. 中國(guó)艦船研究， 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.

作者簡(jiǎn)介

劉子玄（1998—），男，碩士研究生，主要研究方向?yàn)榕炤d航空保障。

萬(wàn) 兵（1991—），男，講師，博士，主要研究方向?yàn)榕炤d航空保障、飛行器制導(dǎo)控制與動(dòng)力學(xué)。

蘇析超（1989—），男，副教授，博士，主要研究方向?yàn)榕炤d航空保障。

郭 放（1990—），男，博士研究生，主要研究方向?yàn)榕炤d航空保障。

劉玉杰（1983—），男，高級(jí)工程師，博士，主要研究方向?yàn)榕炤d航空保障、艦載機(jī)動(dòng)力學(xué)。