基于改進(jìn)引力搜索算法的艦載機(jī)一站式保障作業(yè)優(yōu)化調(diào)度方法?

朱興動(dòng) 趙 洋 范加利 黃 葵

（1.海軍航空大學(xué) 煙臺(tái) 264001）（2.海軍航空大學(xué)青島校區(qū) 青島 266041）

1 引言

集大量高新技術(shù)成果于一體的航空母艦已經(jīng)成為評價(jià)一支現(xiàn)代海軍作戰(zhàn)能力的核心要素，在其構(gòu)建的海上大縱深，多層次的攻防體系中，艦載戰(zhàn)斗機(jī)扮演著一個(gè)重要的角色。而艦載機(jī)的數(shù)量及其出動(dòng)能力也成為了衡量航母的綜合作戰(zhàn)性能的關(guān)鍵指標(biāo)［1］。而航空艦面保障作業(yè)效率是影響艦載機(jī)出動(dòng)回收能力的主要因素。制定高效可行的艦載機(jī)甲板作業(yè)度方案，對于提升艦載機(jī)艦面保障能力具有重要意義。

相關(guān)研究主要圍繞傳統(tǒng)的多站位保障與一站式保障兩種不同的保障模式展開，而一站式保障模式相較于傳統(tǒng)的保障模式極大地提升了保障效率，將會(huì)是未來航母所采用的主流保障模式［7］。一站式保障模式對艦載機(jī)保障作業(yè)的有序管理、分配提出了更高的要求，其中各項(xiàng)保障作業(yè)工序?qū)ΡＵ腺Y源的爭奪沖突消解問題，以及如何對各艦載機(jī)的保障工序進(jìn)行合理規(guī)劃，避免再次出動(dòng)準(zhǔn)備各項(xiàng)保障作業(yè)間的相互干擾的問題尤為突出。但目前艦載機(jī)一站式保障調(diào)度的相關(guān)研究在以上兩個(gè)方面仍有所欠缺，因此，本文對一站式保障模式的作業(yè)流程、資源約束特性以及不同的出動(dòng)模式下各類艦載機(jī)的放飛優(yōu)先級進(jìn)行了系統(tǒng)性地分析，建立了艦載機(jī)一站式保障調(diào)度模型，并設(shè)計(jì)了一種適用于求解大規(guī)模作業(yè)調(diào)度，消解資源沖突的改進(jìn)GSA算法求解該模型。最后，通過對“福特”級航母的典型出動(dòng)案例仿真驗(yàn)證了算法的可行性和有效性。

2 模型建立

美國“福特”級航母首次引入了一站式保障模式的概念［8］，在飛行甲板右舷設(shè)置了18 個(gè)“一站式保障區(qū)”，所有“一站式保障區(qū)”的保障模塊都進(jìn)行了系統(tǒng)化的集成設(shè)計(jì)，集中設(shè)置了油、氣、電、液等艦面保障設(shè)備。艦載機(jī)著艦并自主滑入保障站位后，按照作業(yè)流程有序開展機(jī)務(wù)勤務(wù)保障作業(yè)，主要包括添加燃油、補(bǔ)充氧氣、航電檢查、特設(shè)檢查、機(jī)械檢查以及軍械檢查等一系列工序，艦載機(jī)不需移動(dòng)即可完成全部保障作業(yè)。一站式保障作業(yè)的節(jié)點(diǎn)活動(dòng)網(wǎng)絡(luò)圖（Active On the Node，AON）如圖1。

2.1 模型假設(shè)

假設(shè)1：艦載機(jī)按照給定的保障流程進(jìn)行，保障工序之間有串行、并行和柔性關(guān)系；

假設(shè)2：任意艦載機(jī)的保障作業(yè)，對其他艦載機(jī)工序的完成沒有影響；

假設(shè)3：進(jìn)行再次出動(dòng)準(zhǔn)備作業(yè)的艦載機(jī)均滿足一站式保障條件，能夠在同一站位完成所有保障工序，不需調(diào)運(yùn)；

假設(shè)4：保障人員的保障范圍均可覆蓋到全體保障站位；

假設(shè)5：航母的各類消耗性資源儲(chǔ)存總量充足；假設(shè)6：不考慮突發(fā)故障和其他干擾因素。

2.2 參數(shù)設(shè)定

I={1，…，i，…，n} ：I表示待保障艦載機(jī)機(jī)群集合，n為當(dāng)前需要進(jìn)行再次出動(dòng)準(zhǔn)備作業(yè)的艦載機(jī)架數(shù)；V={(i，j)|i?I，j?Ji} 表示甲板作業(yè)集，即所有要執(zhí)行的工序，其中Ji={1，2，…，|Ji|}為艦載機(jī)i(i?I)的全部保障工序集合，| ? |為集合中元素的個(gè)數(shù)；TX={1，…，i，…，tx} 表示甲板勤務(wù)作業(yè)調(diào)度時(shí)間序列；Oij表示艦載機(jī)i的第j項(xiàng)保障工序；Hi表示艦載機(jī)i(i?I)的保障停機(jī)位；stij表示工序Oij的開始執(zhí)行時(shí)間；edij表示工序Oij的結(jié)束時(shí)間；INit表示艦載機(jī)i(i?I)在t時(shí)刻處于保障作業(yè)狀態(tài)的工序集；Tij表示艦載機(jī)i(i?I)完成第j項(xiàng)保障工序的持續(xù)時(shí)間；Qi表示艦載機(jī)i(i?I)自主滑抵一站式保障停機(jī)位的時(shí)間；Wij表示Oij的緊前工序集合；Gp表示機(jī)務(wù)保障人員專業(yè)類型集合；Ge表示勤務(wù)保障設(shè)備類型集合；Gh表示保障工位空間類型集合；Gr表示航母甲板的供給性資源類型集合；Lrmk表示甲板的第k(k?Gr) 類供給性資源最多可同時(shí)維持Lrmk個(gè)固定保障設(shè)備的運(yùn)轉(zhuǎn)；NS表示甲板一站式保障站位的數(shù)量。Npijk表示工序Oij所需的第k(k?Gp)類保障人員的數(shù)量；Neijk表示工序Oij所需的第k(k?Ge)類保障設(shè)備的數(shù)量；Nrijk表示工序Oij所需的第k(k?Gr)供給性資源的數(shù)量；NHik表示艦載機(jī)i(i?I)的第k(k?Gs)類工位空間可同時(shí)容納的機(jī)務(wù)保障人員數(shù)量；Lpk={1，2，…，|Lpk|}表示第k(k?Gp)類機(jī)務(wù)保障人員集合；Lek表示第k(k?Ge)類勤務(wù)保障設(shè)備；Wsij表示工序Oij的保障工位。

2.3 再次出動(dòng)保障調(diào)度模型

甲板航空保障作業(yè)的調(diào)度起始點(diǎn)為一波次艦載機(jī)全部著艦并滑行至一站式保障站位。

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

艦載機(jī)機(jī)群出動(dòng)架次率是衡量航母作戰(zhàn)及綜合保障能力的常用指標(biāo)［4，9］，而提高艦載機(jī)出動(dòng)架次率的一個(gè)直接有效的途徑就是縮短單波次甲板機(jī)務(wù)勤務(wù)保障作業(yè)完工時(shí)間。

各類甲板資源中，對保障效能具有決定性影響的主要為機(jī)務(wù)保障人員和保障設(shè)備的配置數(shù)量及其工作性能［5］，最終體現(xiàn)在保障完工時(shí)間的變化上。因此，調(diào)度模型的指標(biāo)函數(shù)取為最小化一波次艦載機(jī)機(jī)群再次出動(dòng)保障作業(yè)時(shí)間，即最小化最大完工時(shí)間：

依據(jù)優(yōu)化目標(biāo)定義決策變量：

2.3.2 約束條件

1）機(jī)務(wù)保障人員約束。任意時(shí)刻所有保障作業(yè)對某類專業(yè)人員的需求量不得大于該類專業(yè)保障人員配置數(shù)量：

2）甲板勤務(wù)保障設(shè)備約束：

此外，若同一架艦載機(jī)的兩相鄰工序分配在同一個(gè)保障設(shè)備上，那么后續(xù)工序無需等待前一個(gè)工序結(jié)束即可開始保障：

3）保障工序流程約束：

艦載機(jī)各保障作業(yè)開始與結(jié)束的時(shí)序關(guān)系：

4）保障站位數(shù)量約束：

5）工位空間約束：

6）資源供給能力約束：

7）資源需求與分配約束：

8）艦載機(jī)起飛優(yōu)先級約束：

3 GSA算法設(shè)計(jì)

保障作業(yè)調(diào)度優(yōu)化的最終目標(biāo)是最小化一波次保障作業(yè)的最大保障完工時(shí)間，該問題可以抽象為具有NP-hard 特性的資源受限多項(xiàng)目調(diào)度問題（Resource-constrained multi-project scheduling，RCMPSP）［8］，目前解決此類問題的方法主要有引力搜索算法（GSA）、粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）、遺傳算法（Genetic Algorithm，GA）等其他智能優(yōu)化算法。研究表明，GSA 算法在優(yōu)化調(diào)度［10］、數(shù)字辨識［11］等領(lǐng)域具有更好的簡潔性和實(shí)用性，其尋優(yōu)精度和收斂速度對比PSO、GA 等算法具有相當(dāng)?shù)膬?yōu)勢［12］。因此，本文選取了GSA作為求解算法，但GSA 存在易早熟收斂，局部搜索能力差的問題［13］，故本文設(shè)計(jì)了一種改進(jìn)的引力搜索算法（IGSA）來求解保障作業(yè)調(diào)度優(yōu)化問題。IGSA的流程如圖2所示。其中δ2表示粒子適應(yīng)度方差，c為判斷閾值。

圖2 IGSA算法流程圖

3.1 編碼與基于SSGS的解碼過程

3.1.1 編碼

由于艦載機(jī)保障作業(yè)調(diào)度問題是離散的［15］，考慮到本文所研究的調(diào)度問題中包含三個(gè)子問題，即工序排序、保障設(shè)備分配以及保障人員分配，所以引入了二元任務(wù)鏈表，即為滿足保障流程約束條件的作業(yè)序列編碼。它由兩部分組成，包括艦載機(jī)與工序。圖3 給出了一個(gè)可行的二元任務(wù)鏈表示意圖，其中第一行向量I表示艦載機(jī)編號，第二行向量J表示工序號，n、m表示艦載機(jī)機(jī)群所有工序數(shù)量。

圖3 艦載機(jī)保障作業(yè)調(diào)度編碼示意圖

3.1.2 解碼

根據(jù)資源需求生成調(diào)度方案需要利用調(diào)度生成機(jī)制（Schedule Generation Scheme，SGS）實(shí)現(xiàn)食物位置編碼向調(diào)度方案的映射。SGS 有串聯(lián)進(jìn)度生成機(jī)制（Serial Schedule Generation Scheme，SSGS）和并聯(lián)進(jìn)度生成機(jī)制［16］（Parallel Schedule Generation Scheme，PSGS）。

Krüger 在研究中指出，SSGS 是具有活動(dòng)性的積極的調(diào)度計(jì)劃，而PSGS 生成的只是非延遲性的調(diào)度計(jì)劃，且不考慮有限性資源的分配問題［17］。對于求解多資源約束下的最小化最大保障時(shí)間的問題，SSGS 能夠較快搜索更為完整的解空間，鑒于此，本文基于SSGS生成調(diào)度方案，根據(jù)作業(yè)調(diào)度編碼映射到調(diào)度方案，輸出滿足時(shí)序關(guān)系和資源約束的優(yōu)化調(diào)度任務(wù)鏈表，進(jìn)而得到各保障工序的最大完工時(shí)間即目標(biāo)函數(shù)值、人員和設(shè)備的調(diào)度方案及其作業(yè)時(shí)序。在此過程中引入資源沖突消解策略［18］來引導(dǎo)算法產(chǎn)生積極調(diào)度計(jì)劃。SSGS 以時(shí)間為階段變量，共有J 個(gè)階段。定義三個(gè)工序集合存在于在每一個(gè)階段g 對應(yīng)的調(diào)度時(shí)刻tg中：已完成工序集（Complete group）表示為Cg；可調(diào)度工序集（Decision group）表示為Dg；執(zhí)行工序集（Active group）表示為Ag。在任意階段g 中，引入了資源沖突消解策略和資源優(yōu)先分配規(guī)則的SSGS算法包括以下步驟：

Step 1選取當(dāng)前可調(diào)度工序集Dg中第一序列的工序，加入到執(zhí)行工序集Ag中。為當(dāng)前執(zhí)行工序集中工序執(zhí)行三層決策。

Step 2以Ag中當(dāng)前執(zhí)行工序的緊前工序的最大完成時(shí)間為時(shí)間變量的起始值，以1 個(gè)時(shí)間單位為步長向后步進(jìn)搜索，直到某一時(shí)刻的保障人員、保障設(shè)備，工位空間以及消耗資源剩余量滿足當(dāng)前執(zhí)行工序?qū)ΡＵ腺Y源的需求量，將該時(shí)刻設(shè)定為當(dāng)前執(zhí)行工序的開始時(shí)間stij，結(jié)束時(shí)間edij=stij+Tij。

Step 3按照保障人員與保障設(shè)備的分配規(guī)則為當(dāng)前執(zhí)行工序?qū)ふ耶?dāng)前時(shí)間點(diǎn)中符合規(guī)則的人員與設(shè)備，將stij至edij時(shí)間序列中的與置為零。

Step 4更新保障人員、保障設(shè)備、剩余資源和站位空間的信息。

Step 5將當(dāng)前執(zhí)行工序加入到已完成工序集Cg中并從Dg和Ag中刪除，重復(fù)執(zhí)行Step 1，直至可調(diào)度工序集合為空集，然后轉(zhuǎn)入下一階段，當(dāng)Dg=?，調(diào)度完成。

3.2 粒子位置更新策略

通過先例保全交叉法（Modified Precedence Preservative Crossover，MPPX）對當(dāng)前全局的粒子位置進(jìn)行擾動(dòng)［19］。首先產(chǎn)生一個(gè)長度為n 的隨機(jī)二進(jìn)制矢量，其維數(shù)相當(dāng)于任一粒子位置全部工序矢量的長度，用于選擇。粒子元素以生成新的粒子位置。其中0和1分別代表第一個(gè)和第二個(gè)粒子位置。這些數(shù)字代表元素從食物位置中移除并放入新粒子位置向量的順序。從左邊開始，根據(jù)隨機(jī)矢量的順序選擇一個(gè)元素，并從兩個(gè)食物位置矢量中移除，然后放入一個(gè)新的食物位置，直到兩個(gè)食物位置向量都為空。

其次，針對保障作業(yè)調(diào)度這種大規(guī)模RCMPSP問題難以跳出局部最優(yōu)的特性，引入一種基于子拓?fù)涔ば蚓W(wǎng)的變異策略［20］，以產(chǎn)生更大的鄰域變換范圍，防止算法早熟收斂，提高種群的多樣性。變異策略主要步驟如下：

Step 1在當(dāng)前種群中按概率Pm 選取執(zhí)行變異操作的食物位置向量集合，提取單一向量Re-Chrom執(zhí)行步驟2；

Step 2在ReChrom 中隨機(jī)選擇一個(gè)操作點(diǎn)P?[1，|Ji|-len]，其中l(wèi)en 為重排子向量（即子任務(wù)鏈）的長度，選取P 至P+len 位的向量記為nC，并記錄P 和P+len 位在ReChrom 中位置LocP與LocP+len；

Step 3將nC 中的工序按照艦載機(jī)保障流程AON 圖的作業(yè)工序約束關(guān)系構(gòu)造所選取子向量的AON 子圖，依照子圖的約束對子向量進(jìn)行隨機(jī)重排；

Step 4用重排后的子向量（即子任務(wù)鏈）替代ReChrom 中[LocP，LocP+len]區(qū)間內(nèi)的向量，構(gòu)造出新的食物位置向量。

為進(jìn)一步減少算法迭代的時(shí)間，提高算法收斂速度，在執(zhí)行完交叉、變異擾動(dòng)后，計(jì)算當(dāng)前所有粒子的適應(yīng)度值，并選取部分最優(yōu)解作為初始解執(zhí)行禁忌搜索［21］，算法主要流程如下。

步驟1接收初始解，作為當(dāng)前解，將該粒子位置加入禁忌表；

步驟2創(chuàng)建當(dāng)前解的候選解解集（鄰域解解集）；

步驟3在候選解解集中選擇目標(biāo)函數(shù)值最優(yōu)且不在禁忌表中的解，作為新的當(dāng)前解；

步驟4新的當(dāng)前解加入禁忌表，并更新禁忌表，判斷此時(shí)是否滿足終止條件，若是，則繼續(xù)執(zhí)行下一步，反之則轉(zhuǎn)至步驟2；

步驟5輸出搜索到的最優(yōu)解，即最優(yōu)粒子位置。

4 仿真分析

4.1 案例構(gòu)建

本文基于“福特”號航母甲板保障資源配置情況構(gòu)建艦載機(jī)機(jī)群保障仿真案例，航母右舷的一站式保障區(qū)最多可停放20多架艦載機(jī)并能同時(shí)為18架艦載機(jī)提供各種保障，其中一站式保障站位編號分別為1～18，本文構(gòu)建了一個(gè)艦載機(jī)機(jī)群雙周期連續(xù)出動(dòng)保障案例，對8機(jī)和12機(jī)輪轉(zhuǎn)兩種出動(dòng)模式進(jìn)行調(diào)度仿真，表2 給出了不同作戰(zhàn)模式下的各類型艦載機(jī)的起飛優(yōu)先權(quán)；作戰(zhàn)任務(wù)需求設(shè)定為預(yù)警機(jī)、電子戰(zhàn)飛機(jī)、空對地打擊戰(zhàn)斗機(jī)以及護(hù)航機(jī)。艦載機(jī)編號為1～12，只采用甲板的一站式保障區(qū)。任一艦載機(jī)i的單機(jī)保障工序流程如圖1所示，其中編號1 和編號19 為虛擬開始/結(jié)束工序。各保障工序?qū)ΡＵ腺Y源的需求和執(zhí)行工序的時(shí)間參數(shù)情況以及保障設(shè)備的覆蓋范圍由于篇幅限制，未在文中給出。

表2 不同作戰(zhàn)任務(wù)下的艦載機(jī)起飛優(yōu)先權(quán)

4.2 仿真結(jié)果

仿真案例采用的硬件平臺(tái)為Windows11 操作系統(tǒng)，Intel（R）Core（TM）i7-12700K CPU，3.61GHz主頻，32G 內(nèi)存，Matlab R2022a 仿真軟件。經(jīng)多次實(shí)驗(yàn)對比分析，最終設(shè)定的算法參數(shù)為算法的種群規(guī)模N2=50，引力系數(shù)G0=50，粒子加速度α=10，遷移因子MF=15，變異概率Mutation（m）=0.2，交叉概率Crossrate（c）=0.2，貪婪搜索概率TSrate（s）=0.4，算法整體最大迭代次數(shù)T=300。

12 機(jī)輪轉(zhuǎn)模式下任務(wù)C 的最大保障完工時(shí)間隨下層迭代的曲線如圖4 所示。最終求解得到的任務(wù)C 的再次出動(dòng)保障作業(yè)的保障人員和保障設(shè)備的最優(yōu)調(diào)度方案如圖5 和圖6 所示。其中，橫坐標(biāo)表示再次出動(dòng)準(zhǔn)備作業(yè)中一波次保障過程的時(shí)間軸，圖5 縱坐標(biāo)Gpk-l代表第k 類專業(yè)中第l 個(gè)保障人員。圖6 縱坐標(biāo)Gek-l代表第k 類第l個(gè)保障設(shè)備。

圖4 最大保障完工時(shí)間收斂圖

圖5 任務(wù)C的保障人員最優(yōu)調(diào)度甘特圖

圖6 任務(wù)C的保障設(shè)備最優(yōu)調(diào)度甘特圖

5 結(jié)語

針對一站式保障模式下艦載機(jī)保障作業(yè)調(diào)度問題，對艦載機(jī)再次出動(dòng)保障任務(wù)的流程、保障資源約束進(jìn)行了系統(tǒng)性的分析，建立了一站式保障調(diào)度優(yōu)化模型，進(jìn)而設(shè)計(jì)了一種改進(jìn)的引力搜索算法用于該問題的求解。引入了融合資源沖突消解策略的串行進(jìn)度生成機(jī)制來生成調(diào)度方案并解決作業(yè)調(diào)度過程中的資源爭奪問題；采用MMPX 交叉法、基于子拓?fù)渚W(wǎng)絡(luò)的變異策略以及禁忌搜索，提高算法的尋優(yōu)能力。

最后通過對“福特”級航母艦面保障調(diào)度典型案例的仿真分析，驗(yàn)證了本文所提模型和求解算法在一站式保障作業(yè)調(diào)度優(yōu)化問題中具有良好的求解性能，表明了算法的有效性和可行性。