李 經(jīng) 孫 哲 李夢龍 余明暉

（1.海軍駐中國艦船研究設計中心軍事代表室 武漢 430064）（2.中國船舶重工集團有限公司 北京 100097）（3.華中科技大學自動化學院 武漢 430074）

1 引言

艦載機保障作業(yè)調(diào)度是指在航母甲板提供的有限資源下，對艦載機和各項保障資源進行調(diào)度，為艦載機的起飛和作戰(zhàn)提供維護和支持。艦載機的保障作業(yè)周期越短，反映航母的保障能力越強［1］。由于艦載機的保障作業(yè)運行在航母甲板上，其作業(yè)環(huán)境相對于陸地更加惡劣，并且在調(diào)度過程中需要多架艦載機、多個部門、多種資源的相互配合協(xié)調(diào)。所以，資源的有限性和作業(yè)環(huán)境的不穩(wěn)定性是艦載機保障作業(yè)調(diào)度的主要特征。

目前在航母甲板作業(yè)調(diào)度的研究有：麻省理工學院的計算機科學與人工智能實驗室將專家經(jīng)驗和計算機的計算能力相結合，開發(fā)了航母甲板作業(yè)規(guī)劃決策支持系統(tǒng)DCAP（Deck operations course of action planner），對艦載機保障作業(yè)調(diào)度進行智能決策［2］；RGDastidar等采用了基于排隊網(wǎng)絡的分布式策略，進行航母甲板作業(yè)的仿真［3］；岳奎志等基于系統(tǒng)動力學理論，建立了艦載機動態(tài)調(diào)運的存量流量圖和數(shù)學模型［4］；馮強等根據(jù)艦載機的實時動態(tài)綜合保障需求，提出了基于多Agent的艦載機動態(tài)保障模型［5］；李耀宇等建立了基于排隊網(wǎng)絡的艦載機甲板調(diào)度模型，使用差分進化算法生成優(yōu)化策略［6］。

從現(xiàn)有的研究狀況看，目前在針對艦載機保障作業(yè)調(diào)度問題求解算法上的研究較少，并且主要是通過計算仿真方法來求解。仿真方法對于模型的參數(shù)和邏輯關系敏感，會因為參數(shù)選擇不同而導致結論不同。本文通過對艦載機保障作業(yè)的分析，根據(jù)其特點在合理假設的基礎上建立了艦載機的保障調(diào)度模型，考慮到智能搜索算法在計算速度上相對于仿真方法的優(yōu)越性，并且易于和其他算法相結合，故在遺傳算法的基礎上，對染色體編碼、交叉、變異等進行研究設計，提出一種能夠適用于保障作業(yè)問題的算法來對該模型進行求解。最后通過設計實例計算，驗證了算法對艦載機保障作業(yè)調(diào)度問題的適用性。

2 保障作業(yè)調(diào)度系統(tǒng)分析

艦載機保障系統(tǒng)是一個涉及到多項資源、多個部門的復雜系統(tǒng)，是保障艦載機在航母上安全起降和有序作業(yè)的核心［7］，其主要功能包括保障艦載機從機庫調(diào)運到甲板，對艦載機的起飛和著陸進行引導協(xié)調(diào)，負責艦載機的支持和維修，配給艦載機所需要的武器彈藥等資源。艦載機在作戰(zhàn)任務下達后，根據(jù)作戰(zhàn)任務確定艦載機的出動方式［8］。艦載機的整體保障作業(yè)階段一致，由于各艦載機有著不同的狀態(tài)和不同的作戰(zhàn)任務，其所需要執(zhí)行的保障任務方案可能在局部存在不同。所有艦載機的保障作業(yè)主要包括：飛行前的檢查；充電；故障檢查維修；補充添加特種氣體、液體和燃料。戰(zhàn)斗機需要掛載彈藥、航空導彈等。電子戰(zhàn)飛機則需要更新軟件和數(shù)據(jù)庫、錄入敵人特征信號等。

與岸基戰(zhàn)斗機相比，航母艦載機的保障作業(yè)有著甲板作業(yè)環(huán)境差、空間狹窄、保障設施特殊等特點［9］。在艦載機保障過程中，艦載機會完成被牽引車調(diào)運、進入保障站位、起飛前保障、故障檢查、起飛執(zhí)行任務以及著艦調(diào)運等活動。而在整個流程中，艦載機到達彈射位進行起飛前的保障作業(yè)是主要難點。其需要多個專業(yè)保障部門共同完成，而且受到甲板資源的約束，因此艦載機的保障作業(yè)過程相當復雜。針對艦載機調(diào)運作業(yè)所處的環(huán)境和作業(yè)流程等特點，應該合理安排和規(guī)劃艦載機的調(diào)運順序、分配相關設備和人力資源，提高艦載機調(diào)運作業(yè)調(diào)度的效率［10］，避免資源沖突和混亂的發(fā)生，保證各項作業(yè)活動的高效有序進行。

3 調(diào)度數(shù)學模型建立

通過上述對艦載機保障作業(yè)調(diào)度過程的分析，以尼米茲級航母的傳統(tǒng)多站式保障作為參考，可以將保障作業(yè)調(diào)度問題描述如下：假設某個波次中需要出動n架艦載機，整個保障作業(yè)流程有m個保障階段，能夠為第i個保障階段提供保障的保障站位有Mi個。所有的艦載機從0時刻開始，按照給定的保障作業(yè)次序，依次到各個保障站位進行不同的保障作業(yè)，直到完成所有保障階段，再被滑行至起飛站位進行起飛。在保障作業(yè)過程中，每架艦載機都可以分別在Mi個保障站位上進行保障，在不同保障站位上進行的保障作業(yè)是并行的，而在相同保障站位上進行的保障作業(yè)是串行的，即不能同一時間在同一保障站位給大于一架的艦載機進行保障。本文的調(diào)度目標為最小化最大完工時間，其中，最大完工時間為開始第一架艦載機開始保障的時間至最后一架艦載機完成最后階段保障任務的時間。

本文以尼米茲級航母的多站式保障作為背景，對艦載機保障作業(yè)調(diào)度問題作數(shù)學建模，并約定以下假設：不考慮保障作業(yè)進行過程中的各種因素干擾；不考慮多個波次之間的相互影響；不考慮甲板的空間布局；在保障作業(yè)過程中，設備均能夠穩(wěn)定運行，不會受損而不能工作；同一時刻同一艦載機只能在一個保障站位上進行保障作業(yè)，同一時刻同一保障站位只能給一架艦載機提供保障；艦載機的保障作業(yè)的工藝路線已經(jīng)確定；艦載機保障作業(yè)的保障時間是確定的，不考慮隨機情況；一個波次中需要進行保障的艦載機數(shù)量是確定的，不會在保障過程中增加或者減少；不考慮甲板上的突發(fā)事件。建立艦載機保障作業(yè)的數(shù)學模型如下：

其中參數(shù)說明如下：cj為第 j架艦載機完成保障任務的時刻；cij為第 j架艦載機在第i個保障階段的保障結束時間；sij為第 j架艦載機在第i個保障階段的保障開始時間；dijk為第 j架艦載機第i個保障階段在第k個保障站位上的保障服務時間；xijk為1時，表示第 j架艦載機第i個保障階段是選擇第k個保障站位上完成，當xijk為0時，則相反。

其中，式（1）為目標函數(shù)，表示調(diào)度目標為最小化最大完工時間；式（2）表示艦載機 j的最大完工時間為該艦載機最后的保障階段的完工時間；式（3）表示保障完工時間為保障開始時間加上保障服務時間；式（4）表示同一時間內(nèi)，一個保障站位只能為一架艦載機提供保障服務；式（5）表示一架艦載機需要按照保障次序依次進行保障；式（6）表示一架艦載機在一個保障階段只能選擇一個保障站位進行保障作業(yè)。

4 求解算法

航母艦載機保障作業(yè)涉及到復雜的流程約束、資源約束和環(huán)境約束［11］，傳統(tǒng)人工調(diào)度的效率隨著艦載機保障數(shù)量規(guī)模增大而急劇下降，計算量耗費大［12］。為了有效地求解艦載機保障作業(yè)調(diào)度問題，得出合理的調(diào)度方案，本文采用智能搜索算法來對上述模型進行求解。而在智能搜索算法中，遺傳算法有著易于表示可行解、全局搜索和并行計算能力的優(yōu)點，因此利用遺傳算法來對艦載機保障作業(yè)調(diào)度問題進行求解更加合適。

遺傳算法（Genetic algorithm）是一種借鑒物種進化規(guī)則的智能算法，對種群中各個個體的適應度值進行計算，然后淘汰掉適應度低的個體，保留適應度高的個體，使得適合環(huán)境的基因能夠得以延續(xù)。遺傳算法在計算過程中，通過選擇、交叉、變異三個操作，來實現(xiàn)種群的進化演變。圖1表示了遺傳算法的流程。

根據(jù)上述分析，本文提出一種基于遺傳算法的調(diào)度算法，用于求解艦載機保障作業(yè)調(diào)度問題，該算法設計如下。

1）染色體的編碼方式。艦載機保障作業(yè)調(diào)度可以看成在各個階段中將每個艦載機分配到合適的保障站位上。因此，依照這個思路，在該算法中采用矩陣形式的染色體來表示可行解。其構造形式如下：

式（7）中矩陣 Am×n中元素 aij是一個整數(shù)，并且1≤aij≤Mi，其表示第 j架艦載機在第i個保障階段選擇到第aij個保障站位上進行保障。

圖1 遺傳算法流程圖

式（8）中 f為該染色體的適應度值；max(cj)為染色體解碼的調(diào)度方案的完工時間；M為常數(shù)。其中，完工時間的計算步驟如下：首先，由染色體所得出的艦載機保障站位分配方案；然后，根據(jù)艦載機保障站位的分配方案，根據(jù)先到先服務原則（First-Come-First-Serviced，F(xiàn)CFS）對各個艦載機到達保障站位的次序進行排序，即在每個節(jié)點上，計算上一階段保障作業(yè)完成的時間，按照完成時間排序，先完成的艦載機優(yōu)先開始進入下一個保障站位進行保障作業(yè)，當時間相同時，優(yōu)先選擇保障時間短的艦載機進行保障。

2）選擇操作。算法采用輪盤賭式的選擇方法，計算種群中每個個體的適應度值，并按照適應度值從大到小排序。適應度值越大的個體，其在輪盤中所占的比例越大。因此，適應度值越高的個體，越容易被選中而使得其染色體的特征得以延續(xù)，適應度值越低的個體則被淘汰的可能性越大。

3）交叉操作。在經(jīng)過選擇操作后產(chǎn)生的新種

2）適應度函數(shù) 適應度函數(shù)采用下式求得：群中，以Pc的概率選擇兩個個體進行交叉產(chǎn)生新一代個體。文本算法采用的交叉操作為分段交叉方法，隨機選擇染色體中的幾個小段，然后進行單點交叉。例如隨機生成和染色體相同規(guī)模的矩陣，元素由0和1構成，當該元素為1時，對兩個染色體相應位置的元素進行交換，為0時則保留不動。

4）變異操作。為了擴大遺傳算法的搜索范圍，避免局部收斂現(xiàn)象的發(fā)生，保證種群的多樣性，算法在交叉操作后產(chǎn)生的新種群以Pb的概率選擇單個個體進行變異操作。具體變異操作：隨機選擇該個體染色體中的某一個片段aij，然后在區(qū)間[1，Mi]取隨機整數(shù)a′ij且 a′ij不等于aij，作為變異結果替換aij，然后生成新的個體。

5 計算結果

為了驗證上文中提出遺傳算法對艦載機保障作業(yè)調(diào)度模型的求解效果，設計了一個實例：假設在某個波次中，一共有24架艦載機需要出動執(zhí)行任務，每架艦載機的保障作業(yè)包括有加油、飛行準備、充電、掛彈四項保障任務，每項保障作業(yè)有兩個保障站位提供保障服務。艦載機到各個保障站位上完成保障作業(yè)的時間如表1，保障站位和保障作業(yè)的對應關系如表2。

表2 保障站位

在遺傳算法中，染色體的種群規(guī)模取100，交叉概率 Pc為0.8，變異概率 Pb取0.1，迭代次數(shù)取100。對該實例進行求解，可得到調(diào)度方案的最大完工時間為247，其甘特圖如圖2所示?？梢酝ㄟ^實驗結果看出，利用所提出的遺傳算法對艦載機保障作業(yè)進行調(diào)度之后，可以得到可行的調(diào)度方案，能夠同時滿足保障站位和保障次序的約束，即一個保障站位同一時間只能給一架艦載機提供保障服務，并且艦載機依照保障次序進行保障。

圖2 甘特圖

6 結語

本文以尼米茲級航母的傳統(tǒng)多站式保障作為背景，通過對艦載機保障作業(yè)的研究，建立了艦載機保障作業(yè)調(diào)度問題的數(shù)學模型，并采用遺傳算法用于求解模型，最后通過設計一個實例計算，驗證了算法的可行性。由于艦載機保障作業(yè)十分復雜，本文提出的一些假設和可能與實際作業(yè)有些偏差，需要更多的數(shù)據(jù)進行后續(xù)的實驗驗證，在今后的研究中，可以考慮減少艦載機調(diào)運次數(shù)作為優(yōu)化目標、對問題模型引入甲板的空間約束、考慮艦載機的調(diào)運過程等，使得研究能夠應用到實際當中。