基于工作日志表的艦載機甲板作業優化調度算法?

朱興動 孟楊凱 黃 葵 范加利

（1.海軍航空大學 煙臺 264000）（2.海軍航空大學青島校區 青島 266041）

1 引言

航空母艦是以艦載機為主要武器并作為海上活動基地的大型水面戰斗艦艇、海軍水面戰斗艦艇的最大艦種。航母戰斗力集中體現在艦載機群的戰斗力，航母艦載機起飛前，需經過甲板系列保障工序，但受制于航母甲板保障資源與空間資源有限，保障過程的高度時間緊迫性，甲板保障調度成為影響航母戰斗力的重要因素。

針對此類資源受限、作業順序不確定、工序數量不確定等含多重不確定性因素的保障調度，屬車間柔性作業，是典型資源受限項目調度問題（RCPSP）。針對目前航母甲板調度領域研究多具有工位實際約束考慮不足及因工位約束帶來的衍生影響考慮不足的缺陷，本文通過對工位約束進行全面分析，包含保障資源服務工位范圍限制、基于甲板實時工位狀態的作業持續時間不同、機位占用、因初始工位不同而導致的保障工序需求數量不同、保障小組機位間轉運調整時間等，形成符合實際作戰條件的數學調運模型，設計出適合解決復雜工位約束限制的甲板調度算法。最后以庫茲涅佐夫號航母上12機出動準備作業為例進行驗證。

2 航母甲板保障作業調度模型

2.1 航母甲板保障作業描述

俄羅斯“庫茲涅佐夫”航母艦面共33個停機位，3個滑躍起飛位。航母艦載機出動前，共需進行檢修、加油、掛單、牽引至暖機位（由機位可否進行暖機工作決定工序是否存在）、慣導對準、暖機等工序，最后滑行至起飛位，完成起飛，具體過程如圖1所示。

圖1 艦載機甲板保障工序流程

工序說明:

工序0:艦載機、保障組停靠機位初始狀態

工序1:加油

工序2:掛彈

工序3:牽引至暖機位

工序4:慣導對準

工序5:暖機

工序6:滑行

工序7:起飛

工序8:機務檢修

其中，工序3牽引至暖機位若因艦載機機位具有可暖機屬性，即可無需此工序，由工序1、2完成后進入工序4；受安全管理性約束，艦載機的加油、掛彈和牽引至暖機位三項任務，不可同時進行，但可不分先后，慣導對準、暖機、滑行、起飛四項任務必須依次執行。工序8機務檢修伴隨勤務保障全程進行。

甲板保障調度作業的目標，即需依據甲板各保障小組初始所在工位、艦載機初始停放工位、甲板工位距離矩陣、各保障小組移動速度、艦載機甲板轉運速度（若含此工序）、各保障點可服務機位范圍列表、各機位飛機占用，生成基于目前甲板狀況的全部飛機起飛完畢的最小化全部保障時間的最優調度方案。

2.2 甲板調度約束分析

1）飛機加油、掛彈、轉運三項任務不可同時進行，但可不分先后。

2）慣導對準、暖機、滑行、起飛四項任務必須依次執行。

3）根據機位屬性，為可暖機機位/不可暖機機位，若飛機所處不可暖機機位，慣導對準前需由轉運小組轉運至可暖機機位。

4）甲板共設9個加油保障點，各保障點具有不同數量的可保障機位范圍，不同保障點可保障機位可具有重復，保障點對可保障機位范圍外的飛機無效（不可保障）。

5）根據飛機轉運工序的完成，所在機位產生變化。對后序工序的機位選擇產生實時變化、加油保障點可保障范圍內的飛機及其所在機位產生實時變化。

6）機位當前占用情況下不可作為轉運目標機位。

2.3 調度模型建立

本文研究模型調度初始起點:艦載機均在甲板機位停靠，不考慮機庫飛機轉出、飛機任務完畢甲板降落。因機務檢修工作伴隨艦載機多項工作同時進行，無需單獨進行工序安排，故不考慮在內。

模型內相關參數定義如下:F為目標函數，Cmax為一波次艦載機完成所有工序的最大所需時間，航母甲板艦載機數量為I，各艦載機表示為i∈｛1，……，I｝，每架艦載機i均有工作集Vi，其中Vi=｛J1，……，Jj｝，j為作業數量；Vnr為非資源需求的工作集，Vrs為特定資源需求工作集，Vra為不定資源需求工序集，任一工作Jj必包含在內。Vs為不可同時執行的作業集，包含加油、掛彈、轉運；Tij是艦載機i完成作業工序j的時間，stij為第i架艦載機第j項作業的開始時間，stij≥ 0，edij為第i架艦載機第j項作業的結束時間；dij為第i架艦載機第j項作業的持續時間；作業過程不可中斷，edij=stij+dij；Ci為艦載機i完成最后一道作業，即起飛的時間；yijk=1為第i架艦載機第j項作業開始；dmini是第i架艦載機任務mi、ni開始的時間間隔；Njk是在某一時刻k，執行作業j的可用甲板資源數量。

模型中，式（1）為目標函數；等式（2）、（3）為保證每架艦載機同一工序只執行一次，不可重復執行；不等式（4）為工序作業的時序優先級關系，針對作業T中慣導對準、暖機、滑行、起飛四項任務必須依次執行。不等式（5）確保不定資源約束型作業對甲板資源的需求小于甲板資源總量。不等式（6）確保加油、掛彈、牽引至暖機位三項工作中的任意兩項不可同時執行。不等式（7）表示機位轉運可行性。

3 模型求解算法

保障資源受限，工序數量不確定的柔性資源受限項目調度問題是典型NP難題，當前已證明禁忌算法是解決該類問題最優算法之一。本節闡述求解調度算法主要內容，包含禁忌算法結構思想，編碼方案、算法鄰域結構設計、初始解優先規則設計及實現過程、算法解的優化方案設計等內容。求解算法側重于對現有數據數值的調度算法構思、實現，忽略算法數據數值的獲取，實際應用中可采用經驗數值。

3.1 禁忌算法

模型優化過程采用禁忌算法，禁忌算法具有很強全局搜索能力，并可避免優化結果局部最優。禁忌算法的基本思想是在搜索過程中將近期歷史的變換過程放入禁忌表中（Tabu List）中，阻止重復變換，即可有效避免搜索循環。禁忌表模仿了人類記憶功能，為元啟發式算法之一。

3.1.1 禁忌算法編碼方案

算法編碼采用順序編碼方式，由1～n數字組成，分別代表第1至n種工序，此種編碼方式優點在于同一染色體內不可出現數字重復，即Xi=｛x1，x2，……，xj｝，xj∈｛1，2……，n｝，且當m≠n時，xm≠xn，編碼的不同數值代表不同保障工序，先后順序代表工序執行順序。例某架飛機編碼為Xm=（2315476），即艦載機甲板保障調度按照各數值所代表工序順序進行。

3.1.2 禁忌算法鄰域結構設計

算法鄰域結構是算法尋優過程中計算目標函數值所依據的拓撲結構。算法解由矩陣編碼組成，矩陣編碼以行為單位成為各調度單位的調度執行方案，如m*n矩陣可代表甲板m架艦載機分別包含的n道工序甲板調度方案，或可代表甲板m個調度小組分別對n架艦載機保障的保障調度順序。算法鄰域結構采用首先獲取解的任意兩行行排列組合方案，其次完成各行之間任意數字兩兩交叉變換的策略，組成各算法解的鄰域結構。因算法采用順序編碼，針對數字交叉可造成的同一調度單位內數值缺失與數值重復引起的編碼非法，如同一艦載機工序調度方案中同時含兩個“3”工序或缺少“1”工序等，數值交叉變換采用部分映射交叉（PMX）方式完成。部分映射交叉（PMX）步驟如下:

1）選擇A編碼的交換數值x與B編碼的交換數值y；

2）確定交叉點數值映射關系，即x—y；

3）將A編碼的x數值由y替代，同時將A編碼原y數值由x替代；

4）將B編碼的y數值由x替代，同時將B編碼原x數值由y替代。

針對算法解共含m*（m-1）/2個行排列組合方案，鄰域結構為完成全部行排列方案的全部兩兩數字對應變換。例:選取第一行與第二行，完成第一行的第一個數字與第二行的第五個數字交叉，結果如圖2所示。

圖2 鄰域結構算法示意圖

3.2 基于優先規則初始解的生成

初始解的生成規則基于優先級索引策略，具體規則如下。

1）對于加油類受資源保障服務范圍限制資源，各保障點優先保障服務范圍內距離最近艦載機。

2）對于轉運工序受目標機位資源空余限制類保障，各轉運組優先選擇距離最近艦載機及距離艦載機最近暖機位資源。

3）因轉運工序消耗時間資源少，加油類資源受保障服務范圍限制，艦載機優先進行加油工序。

4）在甲板范圍內盡可能保持各類資源均勻分配。

針對此優先規則，算法實現過程具體如下。

1）掃描甲板停放飛機信息，進行飛機編碼，并獲取停放機位，得到planeinformation表依據停放機位的暖機屬性信息可知每架飛機轉運需求，得到每架飛機保障工序數量。

2）設計endtime表，記錄所有保障小組的當前工作的完工時間，每種保障工序獨立成行，表格初始化為0。

3）獲得endtime表中當前完工時間最小保障小組。

4）若保障小組有服務飛機，檢查該機是否滿足完成慣導對準前所有工序，若滿足，安排后序工序進行起飛，完成起飛數量FLY+1，并釋放當前所在可暖機機位。

5）選擇該保障小組保障范圍內距離最近的未進行過此項工序且未正在保障作業的艦載機進行工作，若存在滿足條件艦載機，have閾值為1，否則為0。若為轉運工序，需額外增加選擇空余可暖機機位中最近機位步驟，若無空余，have閾值為0。

6）have閾值若為1，進行后續步驟，否則該保障小組endtime+60，進行延遲選擇，轉步驟3）。

7）對各保障組工序種類完成數量sum+1，對保障飛機編號進行工作日志worklist更新。此表按保障工種成行，依開始時間順序記錄保障飛機編號，如圖3所示。

圖3 工作日志表worklist示意圖

8）更新 endtime=endtime+tmove+twork。tmove為保障小組從上個保障工位到此保障工位的移動時間，twork為此次保障持續時間。

9）若為轉運，更新planeinformation表中飛機轉運完成后所在機位信息，更新空余可暖機機位信息。

10）更新保障小組當前所在機位、正在保障服務飛機編號，更新各飛機各工序開始時間、結束時間。

11）轉步驟3），直至甲板所有艦載機完成起飛。

3.3 基于鄰域結構解的目標函數值計算

在得到算法優先規則初始解或基于鄰域結構算法解后，需對算法解進行目標函數值計算，作為算法優化過程優化依據。算法解的目標函數值計算依據甲板信息（含飛機編號及停靠機位、機位屬性）、保障小組信息（含所在機位及當前工序結束時間endtime，初始化為0），依照工作日志worklist安排工序進行，具體算法如下。

1）獲得endtime表中當前完工時間最小保障小組。

2）若保障小組有服務飛機，檢查該機是否滿足完成慣導對準前所有工序，若滿足，安排后序工序進行起飛，完成起飛數量FLY+1，并釋放當前所在可暖機機位。

3）保障小組從工作日志中當前工種的第一個飛機編號開始，選取未進行過此項工序的保障飛機進行保障工序安排，have閾值為1，否則為0。若工種為加油，則需添加額外條件滿足此加油保障點保障范圍內機位。若為轉運，需添加額外有空余暖機位條件。

4）若have閾值為1，進入后續保障工序安排，否則轉步驟2）選下一最小endtime保障小組。

5）計算保障前保障小組工位間轉移所需時間tmove，TSij=endtime+tmove，TEij=TSij+tij，endtime=TEij，若飛機當前有正在進行保障工序，TSij=TEij-1，TEij=TSij+tij。

6）更新保障小組當前所在機位、正在保障服務飛機編號，更新各飛機各工序開始時間、結束時間，記錄各飛機各工序執行記錄，若為轉運，更新planeinformation表中飛機轉運完成后所在機位信息，更新空余可暖機機位信息。

7）轉步驟2），直至甲板所有飛機完成起飛。

3.4 解的優化方案設計

算法解在完成目標函數值計算后，需對算法解按算法鄰域結構生成新的算法解方案，用于計算新的目標函數值，成為算法迭代中算法解自適應優化的過程。甲板保障小組依靠worklist調度，直至全部保障流程完成。因此工作日志成為算法目標函數值計算依據及算法解及算法解優化過程依據。故優化方案針對工作日志worklist執行。worklist各行數值分別代表不同工序種類依次進行保障服務飛機的順序。解的歷代優化通過實現對工作日志worklist按3.1.2鄰域結構算法完成數值對應變換。

依工作日志worklist生成優化算法鄰域結構過程中，針對工作日志出現兩行數量不一致情況，如10號飛機需加油工序卻無需轉運工序，則加油一行中含10編號，轉運無10編號，實行如下解決方案:選取兩行各自交叉編號時，檢查對立行有無該編號，若無或兩行選取編號相同，則跳過。

通過此鄰域結構算法完成解的優化方案迭代可解決加油、掛彈、轉運等工序在初始解中優先安排順序對整體方案的影響，同一工序不同小組在優先規則中的選擇對優化方案的影響、調度過程可能出現的保障小組暫時等待對整體調度方案的優化，不同艦載機因轉運時序不同而選擇的不同暖機位對整體優化調度的影響等問題，實現完全依靠算法自動尋優，實現調度算法的優化。

4 案例仿真

以庫茲涅佐夫號航母為例。對航母甲板艦載機出動調度仿真，設艦載機以雙周期連續出動為背景條件。設甲板初始停機數量為12，對全部艦載機進行調度運算。仿真過程中假設所有艦載機均無故障、保障點均無故障。工序保障時間取值如下:加油26min，加油保障小組甲板移動速度1m/s、掛彈25min、掛彈保障小組甲板移動速度1.5m/s、轉運保障小組甲板移動速度1.5m/s，加車后艦載機甲板轉運速度0.7m/s、慣導對準13分鐘、暖機5min、滑行1min、起飛1min，加油保障小組NJY=9，掛彈保障小組NGD=3、轉運保障小組NZY=4。

初始狀態甲板艦載機停放信息如表1所示。

表1 甲板艦載機初始狀態信息

圖4 甲板艦載機優化調度方案甘特圖

仿真通過Matlab 2014a實現基于表1信息的航母甲板12機出動進行調度方案優化，優化調度方案結果甘特圖如圖4所示，甘特圖中，灰色部分為當前艦載機工序進行前，保障小組由前一艦載機完成后轉移至當前機位所需移動時間。1～7數字代表相應保障工序。

優化后執行結果各艦載機轉運記錄如表2所示，其中2、10、12號艦載機初始機位具有可暖機屬性，無需轉運。

表2 甲板艦載機優化調度方案執行完成轉運記錄

5 結語

本文針對庫茲涅佐夫航母艦載機以連續出動模式進行批次出動的甲板艦載機保障作業調度問題，通過分析甲板作業流程、資源約束條件和工位約束限制，以出動的最短準備時間為目標，建立了優化計算模型。在此基礎上，采用禁忌算法框架設計了考慮充分工位約束限制的調度求解算法，通過以庫茲涅佐夫航母為背景的仿真計算驗證了算法的有效性，且算法獲得的調度結果能夠被甲板調度專家接受。