艦載機保障作業調度決策研究?

李 經 孫 哲 李夢龍 余明暉

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

1 引言

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

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

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

2 保障作業調度系統分析

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

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

3 調度數學模型建立

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

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

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

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

4 求解算法

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

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

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

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

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

圖1 遺傳算法流程圖

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

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

3）交叉操作。在經過選擇操作后產生的新種

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

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

5 計算結果

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

表2 保障站位

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

圖2 甘特圖

6 結語

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