朱興動(dòng) 孟楊凱 黃 葵 范加利

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

1 引言

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

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

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

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

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

圖1 艦載機(jī)甲板保障工序流程

工序說明:

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

工序1:加油

工序2:掛彈

工序3:牽引至暖機(jī)位

工序4:慣導(dǎo)對(duì)準(zhǔn)

工序5:暖機(jī)

工序6:滑行

工序7:起飛

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

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

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

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

1）飛機(jī)加油、掛彈、轉(zhuǎn)運(yùn)三項(xiàng)任務(wù)不可同時(shí)進(jìn)行，但可不分先后。

2）慣導(dǎo)對(duì)準(zhǔn)、暖機(jī)、滑行、起飛四項(xiàng)任務(wù)必須依次執(zhí)行。

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

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

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

6）機(jī)位當(dāng)前占用情況下不可作為轉(zhuǎn)運(yùn)目標(biāo)機(jī)位。

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

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

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

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

3 模型求解算法

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

3.1 禁忌算法

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

3.1.1 禁忌算法編碼方案

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3）獲得endtime表中當(dāng)前完工時(shí)間最小保障小組。

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

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

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

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

圖3 工作日志表worklist示意圖

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

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

10）更新保障小組當(dāng)前所在機(jī)位、正在保障服務(wù)飛機(jī)編號(hào)，更新各飛機(jī)各工序開始時(shí)間、結(jié)束時(shí)間。

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

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

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

1）獲得endtime表中當(dāng)前完工時(shí)間最小保障小組。

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

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

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

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

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

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

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

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

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

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

4 案例仿真

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

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

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

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

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

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

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

5 結(jié)語

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