基于工作日志表的艦載機甲板作業(yè)優(yōu)化調(diào)度算法?

朱興動 孟楊凱 黃 葵 范加利

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

1 引言

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

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

2 航母甲板保障作業(yè)調(diào)度模型

2.1 航母甲板保障作業(yè)描述

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

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

工序說明:

工序0:艦載機、保障組?？繖C位初始狀態(tài)

工序1:加油

工序2:掛彈

工序3:牽引至暖機位

工序4:慣導(dǎo)對準

工序5:暖機

工序6:滑行

工序7:起飛

工序8:機務(wù)檢修

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

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

2.2 甲板調(diào)度約束分析

1）飛機加油、掛彈、轉(zhuǎn)運三項任務(wù)不可同時進行，但可不分先后。

2）慣導(dǎo)對準、暖機、滑行、起飛四項任務(wù)必須依次執(zhí)行。

3）根據(jù)機位屬性，為可暖機機位/不可暖機機位，若飛機所處不可暖機機位，慣導(dǎo)對準前需由轉(zhuǎn)運小組轉(zhuǎn)運至可暖機機位。

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

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

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

2.3 調(diào)度模型建立

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

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

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

3 模型求解算法

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

3.1 禁忌算法

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

3.1.1 禁忌算法編碼方案

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

3.1.2 禁忌算法鄰域結(jié)構(gòu)設(shè)計

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

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

2）確定交叉點數(shù)值映射關(guān)系，即x—y；

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

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

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

圖2 鄰域結(jié)構(gòu)算法示意圖

3.2 基于優(yōu)先規(guī)則初始解的生成

初始解的生成規(guī)則基于優(yōu)先級索引策略，具體規(guī)則如下。

1）對于加油類受資源保障服務(wù)范圍限制資源，各保障點優(yōu)先保障服務(wù)范圍內(nèi)距離最近艦載機。

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

3）因轉(zhuǎn)運工序消耗時間資源少，加油類資源受保障服務(wù)范圍限制，艦載機優(yōu)先進行加油工序。

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

針對此優(yōu)先規(guī)則，算法實現(xiàn)過程具體如下。

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

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

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

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

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

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

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

圖3 工作日志表worklist示意圖

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

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

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

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

3.3 基于鄰域結(jié)構(gòu)解的目標函數(shù)值計算

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

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

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

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

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

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

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

7）轉(zhuǎn)步驟2），直至甲板所有飛機完成起飛。

3.4 解的優(yōu)化方案設(shè)計

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

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

通過此鄰域結(jié)構(gòu)算法完成解的優(yōu)化方案迭代可解決加油、掛彈、轉(zhuǎn)運等工序在初始解中優(yōu)先安排順序?qū)φw方案的影響，同一工序不同小組在優(yōu)先規(guī)則中的選擇對優(yōu)化方案的影響、調(diào)度過程可能出現(xiàn)的保障小組暫時等待對整體調(diào)度方案的優(yōu)化，不同艦載機因轉(zhuǎn)運時序不同而選擇的不同暖機位對整體優(yōu)化調(diào)度的影響等問題，實現(xiàn)完全依靠算法自動尋優(yōu)，實現(xiàn)調(diào)度算法的優(yōu)化。

4 案例仿真

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

初始狀態(tài)甲板艦載機停放信息如表1所示。

表1 甲板艦載機初始狀態(tài)信息

圖4 甲板艦載機優(yōu)化調(diào)度方案甘特圖

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

優(yōu)化后執(zhí)行結(jié)果各艦載機轉(zhuǎn)運記錄如表2所示，其中2、10、12號艦載機初始機位具有可暖機屬性，無需轉(zhuǎn)運。

表2 甲板艦載機優(yōu)化調(diào)度方案執(zhí)行完成轉(zhuǎn)運記錄

5 結(jié)語

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