一種航母甲板作業(yè)快速調(diào)度算法

朱興動(dòng)，范加利，王 正，趙宏強(qiáng)

(1.海軍航空大學(xué)，山東 煙臺(tái) 265200；2.海軍航空大學(xué) 青島校區(qū)，山東 青島 266041)

0 引 言

艦載機(jī)在航母甲板上的起降一般分波次循環(huán)進(jìn)行，按循環(huán)方式分單周期、雙周期等，循環(huán)間隔受艦載機(jī)制空時(shí)間影響，美軍歷次演習(xí)證明，航母航空保障作業(yè)中，雙周期循環(huán)出動(dòng)能夠提高艦載機(jī)的出動(dòng)強(qiáng)度，而雙周期連續(xù)出動(dòng)的制約因素主要在于艦載機(jī)制空時(shí)間和艦載機(jī)再次出動(dòng)準(zhǔn)備時(shí)間的匹配。在循環(huán)出動(dòng)模型下，留給艦載機(jī)進(jìn)行再次出動(dòng)準(zhǔn)備的時(shí)間非常有限，美國海軍1997 年對(duì)尼米茲級(jí)航母進(jìn)行高強(qiáng)度出動(dòng)演習(xí)表明，當(dāng)循環(huán)周期為1 h 45 min 時(shí)，平均可用甲板作業(yè)時(shí)間僅為57 min。因此，在艦載機(jī)和航母設(shè)計(jì)定型后，如何優(yōu)化配置和合理安排批次艦載機(jī)的再次出動(dòng)保障工作對(duì)于提高航母艦載機(jī)出動(dòng)強(qiáng)度的提高具有非常重要的意義。

受作業(yè)完成時(shí)間的不確定性、艦載機(jī)及保障裝設(shè)備故障的隨機(jī)性、作業(yè)環(huán)節(jié)的多態(tài)性等因素的影響，涉及多架艦載機(jī)、多種保障資源的艦載機(jī)再次出動(dòng)作業(yè)的調(diào)度問題屬于典型的動(dòng)態(tài)調(diào)度問題。近年來，國內(nèi)學(xué)者在該領(lǐng)域進(jìn)行了大量的研究工作，針對(duì)該問題常用的方法是建模仿真方法[1-2,6]、最優(yōu)化方法[3]，以及基于專家方案的逆向強(qiáng)化學(xué)習(xí)方法等[4]。但多數(shù)文獻(xiàn)中仍以靜態(tài)調(diào)度為研究基礎(chǔ)[5,7]，通過提高調(diào)度結(jié)果的魯棒性和自適應(yīng)性來增強(qiáng)調(diào)度系統(tǒng)（算法）對(duì)動(dòng)態(tài)、隨機(jī)環(huán)境的響應(yīng)能力，避免頻繁重調(diào)度?；诜抡娴难芯糠椒ㄓ?jì)算時(shí)間偏長，對(duì)于實(shí)時(shí)重調(diào)度的適應(yīng)能力較弱。

圖 1 艦載機(jī)再次出動(dòng)準(zhǔn)備作業(yè)時(shí)序Fig.1 The sequence diagram of carrier aircraft turnaround operations

針對(duì)航母艦載機(jī)甲板航空保障作業(yè)的調(diào)度問題，本文在對(duì)調(diào)度作業(yè)指揮人員實(shí)際需求分析的基礎(chǔ)上，重點(diǎn)研究了雙周期出動(dòng)模式下艦載機(jī)再次出動(dòng)準(zhǔn)備的調(diào)度問題，建立了艦載機(jī)再次出動(dòng)準(zhǔn)備的優(yōu)化計(jì)算模型，并設(shè)計(jì)一種適用于動(dòng)態(tài)甲板環(huán)境的基于啟發(fā)式禁忌搜索的快速求解算法，最后以庫茲涅佐夫航母上8 機(jī)雙周期再次出動(dòng)準(zhǔn)備作業(yè)為例進(jìn)行驗(yàn)證。

1 艦載機(jī)再次出動(dòng)保障任務(wù)調(diào)度模型

1.1 艦載機(jī)甲板作業(yè)描述

俄羅斯 “庫茲涅佐夫” 航母是一種采用滑躍方式起飛的中型航母，通常搭載蘇-35 飛機(jī)作為主戰(zhàn)艦載機(jī)。航母設(shè)計(jì)階段，通常將飛行甲板分為若干功能區(qū)域，并在各區(qū)域設(shè)置多個(gè)站位，受空間及站位配置資源的限制，“庫茲涅佐夫” 航母上，艦載機(jī)著艦后必須先滑行至臨時(shí)停機(jī)位，而在起飛前則必須牽引至暖機(jī)位進(jìn)行慣導(dǎo)對(duì)準(zhǔn)、暖機(jī)、飛控系統(tǒng)自檢等作業(yè)，隨后依次滑行至起飛位起飛。艦載機(jī)再次出動(dòng)準(zhǔn)備的作業(yè)流程如圖1 所示。

對(duì)于任一架艦載機(jī)，圖中作業(yè)集 TS1中的加油、掛彈和牽引至暖機(jī)位作業(yè)的執(zhí)行順序可任意調(diào)換，但受技術(shù)和管理性約束，對(duì)于某一架飛機(jī)這3 項(xiàng)作業(yè)不能同時(shí)進(jìn)行； 作業(yè)集 TS2中的慣導(dǎo)對(duì)準(zhǔn)、 暖機(jī)、 滑行、起飛任務(wù)必須依次執(zhí)行；再次出動(dòng)機(jī)務(wù)檢修（飛機(jī)后的檢修、視情添加輔助油料、充氧充氮等）作業(yè)可與作業(yè)集 T S1和 T S2中的部分作業(yè)并行執(zhí)行。

上述諸多作業(yè)中按照對(duì)甲板資源的需求類型可分為特定甲板資源、不定甲板資源和無需資源作業(yè)。對(duì)于加油作業(yè)，每一停機(jī)區(qū)能夠同時(shí)加油的艦載機(jī)數(shù)量受該區(qū)加油站數(shù)量的限制；對(duì)于掛彈作業(yè)，受甲板配置的掛彈小組數(shù)約束；對(duì)于轉(zhuǎn)運(yùn)作業(yè)，除了受轉(zhuǎn)運(yùn)小組數(shù)量約束外，還受空間路徑約束；機(jī)務(wù)保障受機(jī)務(wù)保障小組數(shù)量約束，因機(jī)務(wù)作業(yè)可與加油掛彈并行作業(yè)，此處忽略該約束；慣導(dǎo)對(duì)準(zhǔn)、暖機(jī)等作業(yè)受甲板可用暖機(jī)位數(shù)量的約束；滑行作業(yè)可視為不需甲板資源作業(yè)類型；起飛作業(yè)受起飛站位數(shù)量的約束，對(duì)于庫茲涅佐夫航母，每一時(shí)刻只能起飛1 架艦載機(jī)。

1.2 艦載機(jī)甲板作業(yè)調(diào)度的數(shù)學(xué)模型

模型中以一波次艦載機(jī)全部著艦滑行至臨時(shí)停機(jī)位為甲板航空保障作業(yè)調(diào)度起始點(diǎn)，不考慮再次出動(dòng)機(jī)務(wù)檢修工作所需資源和用時(shí)。相關(guān)參數(shù)定義如下：艦載機(jī) i ∈{1,···I} ， I為當(dāng)前要需進(jìn)行再次出動(dòng)準(zhǔn)備的艦載機(jī)架數(shù)；作業(yè)j ∈V，對(duì)于每一架艦載機(jī)，其甲板作業(yè)集，Ji為第i架艦載機(jī)需要執(zhí)行的保障作業(yè)數(shù)量； Vnr， Vrs和 Vra分別代表非資源需求、特定資源、不定資源作業(yè)集。每一任務(wù)j 也屬于一個(gè)任務(wù)類型集 Ej，如果是非資源需求任務(wù)它等于j，并且包括所有需要同類資源的作業(yè)。注意到僅一種特定資源型任務(wù)存在于 Vi中，即起飛。 Vs表示由于安全原因不能同時(shí)執(zhí)行的作業(yè)集，如對(duì)同一架飛機(jī)的加油和掛彈作業(yè)； Tij是艦載機(jī) i 完成作業(yè)工序 j的時(shí)間，對(duì)于任一飛機(jī)的任一作業(yè)，因人員作業(yè)效率、加油量、掛彈種類及站位分布的不同，其作業(yè)時(shí)間不完全相同，但可根據(jù)統(tǒng)計(jì)任務(wù)持續(xù)時(shí)間的均值和3σ 之和作為該時(shí)間值，這種取值方法可以提高調(diào)度計(jì)劃的魯棒性； stij、edij分 別表示第 i 架艦載機(jī)第 j項(xiàng)作業(yè)的開始時(shí)間和結(jié)束時(shí)間； k ∈{1,···,K} 為調(diào)度時(shí)間序列； yijk∈{0,1}，當(dāng)k = stij時(shí) yijk= 1， 表 示 k 時(shí) 刻 第 i 架 艦 載 機(jī) 第 j項(xiàng) 作 業(yè) 開始； Ci為艦載機(jī)完成最后一道作業(yè)（起飛）的時(shí)間；每一飛機(jī)的順序作業(yè)型任務(wù)用帶權(quán)圖 Gi=(Vi,Ai)表示， 其中dmini是使得任務(wù)ni開始的時(shí)間間隙， Sni與任務(wù) mi的開始時(shí)間相關(guān)，Smi滿足不等式為本波次再次出動(dòng)準(zhǔn)備時(shí)間； Njk是在某一時(shí)刻 k，執(zhí)行作業(yè)j的可用甲板資源數(shù)量。

調(diào)度模型的目標(biāo)函數(shù)取為最小化本波次艦載機(jī)的再次出動(dòng)準(zhǔn)備時(shí)間：

約束條件為：

式（2）和式（3）聯(lián)合確保每一作業(yè)必須只被每一架飛機(jī)啟動(dòng)一次，帶有僅單一資源的特定性任務(wù)需要額外執(zhí)行要求的作業(yè)通過式（ 3） 強(qiáng)調(diào)。 不等式（4）確保作業(yè)期間的時(shí)序優(yōu)先級(jí)條件，該不等式主要針對(duì)作業(yè)集 TS2。不等式（5）確保僅有有限數(shù)量的甲板資源被用于完成不定資源約束型作業(yè)，不等式（6）確保對(duì)于每一架飛機(jī)沒有2 個(gè)可以導(dǎo)致安全問題的作業(yè)同時(shí)進(jìn)行，不等式（7）表示調(diào)運(yùn)可行路徑約束通，其中 ZWi1表 示艦載機(jī)在甲板的停機(jī)站位， Hs表示艦艏區(qū)域站位集合；Xzwp表 示站位的 x坐 標(biāo)， jzy表示轉(zhuǎn)運(yùn)作業(yè).

2 求解算法

若將待保障的艦載機(jī)視為工件，將保障資源視為加工機(jī)器，則艦載機(jī)循環(huán)出動(dòng)的再次出動(dòng)準(zhǔn)備作業(yè)調(diào)度模型可視為具有工序順序不定、加工時(shí)間不確定的柔性車間作業(yè)調(diào)度問題，該問題屬于一類NP-難解問題，時(shí)間復(fù)雜度為因其解空間搜索量巨大，很難獲得精確的全局最優(yōu)解。禁忌搜索已經(jīng)被證明是解決該問題的較好算法，但基本禁忌搜索算法容易陷入局部極小，且初始解選取不同，最終得到的優(yōu)化解的質(zhì)量也存在差異，為解決該問題，本文采用迭代搜索，在算法中加入簡單的攝動(dòng)策略，來幫助搜索跳出局部最優(yōu)[8]。

2.1 算法總體框架

迭代禁忌搜索算法從某一局部極小值開始，重復(fù)地使用攝動(dòng)策略使之逃離該局部極小值，并基于禁忌搜索算法去尋找另一局部極小，直到滿足停止條件。解的接受標(biāo)準(zhǔn)決定新的局部極小值是否被接受，還是繼續(xù)從一些以前訪問過的解繼續(xù)搜索。迭代禁忌搜索算法的總體框架如下：

步驟1function ITS（），

步驟2基于啟發(fā)式規(guī)則的初始解→s，

步驟3s←tabuSearch（s），

步驟4for ii = 1，…，maxIT do，

步驟5s′←perturb（s），(s′,i)

步驟6s←tabuSearch ，(ii/maxIT)2s?

步驟7以概率1- 接受：s← ，

步驟8end for，

步驟9返回搜索中發(fā)現(xiàn)的最優(yōu)解 s?，

步驟10end function。

在該算法中，在第 ii次迭代結(jié)束時(shí)，新解以概率1?(ii/maxIT)2被接受。否則搜索繼續(xù)從當(dāng)前的 s?開始，該值在搜索中被更新，并最終返回。接受標(biāo)準(zhǔn)被選擇在開始時(shí)分散搜索，而在最優(yōu)解附近強(qiáng)化搜索。

2.2 基于啟發(fā)式規(guī)則的初始解生成

初始解的生成規(guī)則基于優(yōu)先級(jí)索引策略、先到先服務(wù)和艦首區(qū)艦載機(jī)優(yōu)先原則生成，具體規(guī)則如下：

1）對(duì)于掛彈、轉(zhuǎn)運(yùn)作業(yè)類受限保障資源，優(yōu)先分配給甲板首區(qū)停機(jī)位上待保障的艦載機(jī)；

2）對(duì)于加油作業(yè)，按照區(qū)域，首先進(jìn)入該區(qū)域停機(jī)位的艦載機(jī)優(yōu)先接受加油服務(wù)；

3）對(duì)于轉(zhuǎn)運(yùn)作業(yè)，每一區(qū)域需要轉(zhuǎn)運(yùn)的艦載機(jī)，按照后進(jìn)先出的順序依次轉(zhuǎn)運(yùn)；

4）在滿足相關(guān)約束條件的前提下，盡量避免長時(shí)間占用著艦跑道；

5）在甲板范圍內(nèi)，盡可能保持各類保障資源的負(fù)擔(dān)均勻。

2.3 約束條件的處理

艦載機(jī)再次出動(dòng)作業(yè)調(diào)度問題的約束條件比起一般的車間作業(yè)調(diào)度問題更為復(fù)雜，主要體現(xiàn)在 TS1作業(yè)集中的任務(wù)無固定作業(yè)順序，調(diào)運(yùn)作業(yè)存在某些空間約束等。在實(shí)施搜索過程中，不判別解的可行性，而是對(duì)違反約束的解的工序之間插入時(shí)間間隙作為懲罰。以掛彈作業(yè)為例，具體算法如下：

步驟1function C aldt （）；

步驟2記錄沒架飛機(jī)第j 到作業(yè)工序?yàn)閽鞆椬鳂I(yè)的飛機(jī)數(shù)為tgd，自增；

步驟3取當(dāng)前艦載機(jī)作業(yè)工序j 的上一工序結(jié)束時(shí)間→T empJ；

步驟4若當(dāng)前為所有飛機(jī)的第一道作業(yè)工序，且tdg ≤NGD（ 掛彈資源約束），則 d t = 0 ， 否則 d t = tgdd，tgdd為 d 區(qū)域的預(yù)計(jì)掛彈作業(yè)時(shí)間；

步驟5當(dāng)前已安排掛彈作業(yè)的飛機(jī)數(shù)量 n gdTask ，并將其預(yù)計(jì)結(jié)束時(shí)間按從小到大排序；

步驟6若當(dāng)前非第一道作業(yè)工序，且n gdTask ＜NGD，則 dt = 0 ， 否 則dt = max{tmpTgd(ngdTask ?NGD+1)}?tempJ,0。

2.4 領(lǐng)域構(gòu)造策略

領(lǐng)域結(jié)構(gòu)是對(duì)初始解進(jìn)行一次移動(dòng)操作而獲得另一個(gè)解的機(jī)制。在禁忌搜索算法中，領(lǐng)域結(jié)構(gòu)直接影響禁忌搜索算法的搜索效率[9-11]。因艦載機(jī)再次出動(dòng)甲板作業(yè)中，對(duì)于每架飛機(jī)集T S2中的作業(yè)優(yōu)先順序固定，保障作業(yè)時(shí)間主要受各架機(jī) TS1集中3 個(gè)作業(yè)工序安排順序的影響。為了兼顧搜索時(shí)間和解的質(zhì)量，本算法中采用2 種領(lǐng)域，第1 種結(jié)構(gòu)在啟發(fā)式初始解的基礎(chǔ)上，依次對(duì)每架飛機(jī) TS1的作業(yè)順序進(jìn)行交換和插入移動(dòng)（3 個(gè)工序共可進(jìn)行5 次移動(dòng)）；第2 種領(lǐng)域結(jié)構(gòu)是在攝動(dòng)函數(shù)中對(duì)待保障的所有 I 架艦載機(jī) T S1集的第 j道作業(yè)工序進(jìn)行約束條件檢驗(yàn)，并按最小違背原則進(jìn)行移動(dòng)。

3 算例仿真

以庫茲涅佐夫航母為實(shí)例，對(duì)8 機(jī)雙周期連續(xù)出動(dòng)模式下的艦載機(jī)再次出動(dòng)保障進(jìn)行調(diào)度仿真。甲板初始停機(jī)數(shù)設(shè)為16 架，假設(shè)連續(xù)出動(dòng)過程中所有艦載機(jī)均無故障，艦載機(jī)各作業(yè)工序的時(shí)間取值如下：加油時(shí)間tjy= 18 min ； 掛彈時(shí)間取為[ tdgstgdztgdzwtgdyw]=min ；轉(zhuǎn)運(yùn)時(shí)間 tzy= 7 min；慣導(dǎo)對(duì)準(zhǔn)時(shí)間 tdz= 8 min ；暖機(jī)時(shí)間 tnj= 8 min；滑行和起飛時(shí)間分別為 thx= 1 min 和 tqf= 1 min。 掛彈小組數(shù)NGD= 4； 轉(zhuǎn)運(yùn)組數(shù) NZY= 3。算法基于MATLAB R2014a實(shí)現(xiàn)，計(jì)算機(jī)配置為2.4 GHz 主頻，8 G 內(nèi)存，Win7系統(tǒng)。文中算法（I-TB) 與模擬退火（SA）算法、普通禁忌搜索（TB）算法以及全局搜索算法的計(jì)算結(jié)果如表1 所示。表中耗時(shí)是指獲得優(yōu)化解的用時(shí)，時(shí)間差別主要因算法收斂速度引起。文中算法解的收斂曲線如圖2 所示，8 機(jī)出動(dòng)模式下的作業(yè)調(diào)度甘特圖如圖3 所示。圖中矩形內(nèi)數(shù)字表示飛機(jī)號(hào)×100+作業(yè)序號(hào)，作業(yè)序號(hào)1～7 依次表示加油、掛彈、轉(zhuǎn)運(yùn)、慣導(dǎo)對(duì)準(zhǔn)、暖機(jī)、滑行和起飛。

從仿真結(jié)果可以看出， I-TB 算法、 SA 算法、TB 算法較全局搜索算法的搜索效率均有非常顯著的提高，其中I-TB 算法搜索時(shí)間最短；在解的質(zhì)量方面，全局搜索算法可獲得全局最優(yōu)解，其他3 種算法均無法保證獲得全局最優(yōu)解，但I(xiàn)-TB 算法與TB 和SA 相比解的質(zhì)量更高。從調(diào)度算法輸出的甘特圖上看，算法結(jié)果能夠獲得調(diào)度專家的認(rèn)可。

表 1 算法性能對(duì)比Tab.1 Performance evaluation of algorithms

圖 2 I-TB 算法收斂曲線Fig.2 Convergence curve of I-TB algorithm

圖 3 8 機(jī)再次出動(dòng)準(zhǔn)備調(diào)度時(shí)序圖Fig.3 Turnaround operations scheduling diagram for 8 carrier aircrafts

4 結(jié) 語

本文針對(duì)雙周期連續(xù)出動(dòng)模式下的艦載機(jī)艦面保障作業(yè)調(diào)度問題，通過分析作業(yè)流程和資源約束條件，以優(yōu)化批次飛機(jī)最短再次出動(dòng)準(zhǔn)備時(shí)間為目標(biāo)，建立了優(yōu)化計(jì)算模型。在此基礎(chǔ)上，采用迭代禁忌搜索算法框架設(shè)計(jì)了一種基于啟發(fā)式初始解的快速求解算法，并給搜素過程中的約束條件處理測量和領(lǐng)域構(gòu)造策略。通過以庫茲涅佐夫航母為背景的仿真計(jì)算驗(yàn)證了算法的有效性，且算法獲得的調(diào)度結(jié)果能夠被甲板調(diào)度專家接受。