劉 玨，王能建，羅 旭，孟祥雷

(1. 哈爾濱工程大學(xué) 機(jī)電工程學(xué)院, 黑龍江 哈爾濱 150001； 2. 國(guó)防科技大學(xué) 裝備綜合保障技術(shù)重點(diǎn)實(shí)驗(yàn)室， 湖南 長(zhǎng)沙 410073)

艦載機(jī)保障作業(yè)是保證艦載機(jī)順利出動(dòng)的必要環(huán)節(jié)[1]。由于航母甲板作業(yè)空間有限、海上氣象條件的變化、保障設(shè)備及人員的變動(dòng)，使得艦載機(jī)保障問題有著不同于陸基保障的特殊性。隨著艦載機(jī)種類和數(shù)量的增加，以往依據(jù)經(jīng)驗(yàn)制訂保障計(jì)劃的手工調(diào)度方法將難以滿足未來(lái)戰(zhàn)場(chǎng)的需求，而智能優(yōu)化算法的發(fā)展為研究艦載機(jī)保障作業(yè)問題提供了新的思路。馮強(qiáng)等[2]利用多主體建模技術(shù)對(duì)有限資源下的艦載機(jī)保障調(diào)度進(jìn)行了研究，通過仿真手段分析了特定故障率下固定架次的艦載機(jī)保障作業(yè)。王文秀等[3]以引進(jìn)富余系數(shù)的排序論，對(duì)機(jī)務(wù)保障的資源配置優(yōu)化進(jìn)行了研究。欒孝豐等[4]在仿真模型中嵌入遺傳算法，對(duì)多機(jī)機(jī)務(wù)保障進(jìn)行研究并驗(yàn)證了該方法的有效性。李超等[5]論證了機(jī)務(wù)保障的模塊化趨勢(shì)，給出了其規(guī)劃過程和符號(hào)描述，并通過設(shè)計(jì)結(jié)構(gòu)矩陣(Design Structure Matrix, DSM)算法對(duì)模型求解，論證其提出方法的可行性。呂開東等[6]建立了艦載機(jī)航空保障的開環(huán)排隊(duì)網(wǎng)絡(luò)模型，從整體上分析了其在研究艦載機(jī)保障中的可行性。蘇析超等[7]利用自適應(yīng)變異策略和模擬退火機(jī)制對(duì)Memetic算法進(jìn)行改進(jìn)，將其運(yùn)用于中、大規(guī)模的艦載機(jī)一站式保障調(diào)度研究。Michini等[8]利用逆向強(qiáng)化學(xué)習(xí)方法對(duì)艦載機(jī)艦面保障問題進(jìn)行了研究，在需要同時(shí)對(duì)4架、8架艦載機(jī)同時(shí)保障的任務(wù)中分析比較了不同策略的優(yōu)化方案。

上述研究?jī)?nèi)容多為單機(jī)或多機(jī)未考慮干擾因素的研究，對(duì)多機(jī)保障作業(yè)中含突發(fā)事件干擾的情況論述較少。因此，以不含干擾事件影響的調(diào)度方案為預(yù)設(shè)方案，以事件驅(qū)動(dòng)策略與改進(jìn)的遺傳算法相結(jié)合對(duì)含干擾事件影響的調(diào)度方案進(jìn)行優(yōu)化。

1 艦載機(jī)保障作業(yè)調(diào)度問題數(shù)學(xué)模型

1.1 調(diào)度問題的描述

根據(jù)美國(guó)《海軍航空部隊(duì)航母訓(xùn)練標(biāo)準(zhǔn)手冊(cè)》[9]公布的F/A-18E/F保障標(biāo)準(zhǔn)，總結(jié)了艦載機(jī)單機(jī)保障流程，見圖1，單機(jī)保障作業(yè)時(shí)按流程圖箭頭指示順序進(jìn)行。然而，當(dāng)同時(shí)有多架艦載機(jī)需要進(jìn)行保障且保障組的數(shù)量有限時(shí)，將可能出現(xiàn)以下的資源受限情況[10-11]：①在原保障任務(wù)進(jìn)行時(shí)，有艦載機(jī)退出或有新艦載機(jī)加入保障序列；②保障組數(shù)量較少而待保障的艦載機(jī)數(shù)量較多，或是保障組設(shè)備損壞而導(dǎo)致其不能參與保障；③多機(jī)保障時(shí)保障作業(yè)的調(diào)度方案不合理而導(dǎo)致部分艦載機(jī)的保障完成時(shí)間過長(zhǎng)。發(fā)生以上情況都會(huì)對(duì)艦載機(jī)的持續(xù)作戰(zhàn)能力產(chǎn)生影響，因此，需要綜合考慮多機(jī)保障時(shí)資源受限情況對(duì)艦載機(jī)保障作業(yè)的干擾，并借助優(yōu)化算法獲得合理的保障作業(yè)調(diào)度計(jì)劃，實(shí)時(shí)地對(duì)艦載機(jī)保障調(diào)度過程進(jìn)行優(yōu)化。

艦載機(jī)的保障作業(yè)問題與車間調(diào)度問題相類似，等待保障的艦載機(jī)可看作車間里待加工的工件，各類型保障組可看作是加工工件的機(jī)床，且有多個(gè)同類型機(jī)床可供選擇，但不超過其待加工工件的總數(shù)。因此，關(guān)于艦載機(jī)的保障調(diào)度問題可描述為：有四種類別的保障組對(duì)艦面上n架飛機(jī)進(jìn)行保障，且每架有m道保障工序需要四類保障組完成；這四類保障組分別完成圖1所示的作業(yè)任務(wù)；其中，每道工序的作業(yè)時(shí)間固定，且均對(duì)應(yīng)有Mq(q=1,2,3,4)個(gè)保障組。n架艦載機(jī)進(jìn)入保障區(qū)，以相同的保障工序流程調(diào)用對(duì)應(yīng)類型的保障組進(jìn)行保障作業(yè)，但是，應(yīng)滿足如下假設(shè)條件。

1)保障作業(yè)具有連續(xù)性，每道保障工序作業(yè)中途不可停止，且只有保障完當(dāng)前工序才可開始下一道工序；

2)各艦載機(jī)相互獨(dú)立，各保障工序互不影響；

3)相鄰兩個(gè)工序的結(jié)束與開始的時(shí)間間隔忽略不計(jì)；

4)保障區(qū)內(nèi)可完成上述保障工序，艦載機(jī)無(wú)須牽引車轉(zhuǎn)運(yùn)；

5)不考慮隨機(jī)因素對(duì)保障過程的影響。

1.2 調(diào)度模型參數(shù)及變量定義

1)參數(shù)定義：

n為待保障的艦載機(jī)數(shù)量；m為艦載機(jī)保障工序數(shù)；Oij為表示第i架艦載機(jī)的第j個(gè)保障工序；M為保障組的總數(shù)量；Mq為可對(duì)工序Oij進(jìn)行保障的某一類保障組集合，|Mq|為該類型保障組數(shù)量，其中1≤q≤4；Tijl為由第l(l≤M)個(gè)保障組對(duì)第i架艦載機(jī)的第j道工序的作業(yè)耗時(shí)；Bij為第i架艦載機(jī)的第j道工序開始時(shí)間；Dij為第i架艦載機(jī)的第j道工序結(jié)束時(shí)間；Pij為工序Oij的緊前工序集合；N為同時(shí)需要Mq類保障組的艦載機(jī)數(shù)量；Ci為第i架艦載機(jī)完成所有保障工序的耗時(shí)；Cmax為所有艦載機(jī)完成保障的最大耗時(shí)；Cijhk為保障組從第i架艦載機(jī)的第j道工序作業(yè)結(jié)束至第h架艦載機(jī)的第k道工序開始作業(yè)的轉(zhuǎn)移耗時(shí)。

2)變量定義：

(1)

(2)

圖1 艦載機(jī)單機(jī)保障流程圖Fig.1 Flow chart of support operation of single aircraft

1.3 調(diào)度模型的建立

選取最大保障完成時(shí)間Cmax=max(Ci)作為優(yōu)化目標(biāo),建立艦載機(jī)多機(jī)保障調(diào)度優(yōu)化模型為：

F(x)=min(Cmax)

(3)

(4)

(5)

|Mq|≥1，1≤q≤4

(6)

(7)

(8)

max(Dih)≤Bij， 1≤i≤n,1≤j≤m,?h∈Pij

(9)

Dij+Cijhk+R×βijhk≤Bhk+R1≤i,e≤n,1≤j,g≤m

(10)

N≤|Mq|

(11)

其中，式(3)表示調(diào)度優(yōu)化的目標(biāo)函數(shù)，即實(shí)現(xiàn)保障的最大用時(shí)最短；式(4)表示最大保障用時(shí)與艦載機(jī)保障工序用時(shí)和保障組移動(dòng)用時(shí)的關(guān)系；式(5)表示艦載機(jī)的當(dāng)前保障工序只能同時(shí)存在一個(gè)保障組作業(yè)，即完成該保障任務(wù)的保障組被占用，其值等于1；式(6)和式(7)表示各類型保障組中存在有一個(gè)或多個(gè)能完成相應(yīng)保障工序的該類型保障組；式(8)表示任意艦載機(jī)的某一保障工序的作業(yè)時(shí)間關(guān)系；式(9)表示作業(yè)的緊前關(guān)系約束，即必須保證一個(gè)工序的所有緊前工序均保障結(jié)束后，此工序才能開始；式(10)表示同一保障組不能同時(shí)對(duì)不同的保障工序進(jìn)行作業(yè)，且不同工序按優(yōu)先級(jí)進(jìn)行，式中R為足夠大的實(shí)數(shù)，以保證不等式恒成立；式(11)表示同時(shí)作業(yè)的保障組不得超過該類型的最大數(shù)量。

2 改進(jìn)型遺傳算法設(shè)計(jì)

遺傳算法(Genetic Algorithm, GA)是由Holland[12]提出的，它是一種能在搜索過程中自主學(xué)習(xí)和累積知識(shí)，并行生成多個(gè)個(gè)體，快速尋優(yōu)的自適應(yīng)算法。但是，其收斂過早、精度不高、易陷入局部最優(yōu)的特點(diǎn)，影響了該算法在更多具有現(xiàn)實(shí)意義的復(fù)雜問題中的應(yīng)用。因此，將遺傳算法與禁忌搜索算法相結(jié)合有效地改善了其搜索過程，更有利于獲得最優(yōu)解，詳見2.5節(jié)。

2.1 編碼與解碼

2.1.1 編碼過程

對(duì)于艦載機(jī)保障調(diào)度問題，保障時(shí)有多架艦載機(jī)對(duì)應(yīng)多個(gè)保障工序，因此，實(shí)數(shù)矩陣編碼[13]恰好能直觀地反映矩陣元素與艦載機(jī)及其保障工序之間的約束關(guān)系。該編碼方式能夠有效地搜索種群，獲得最優(yōu)調(diào)度方案，其形式如式(12)所示。

(12)

式中，矩陣Am×n，行表示艦載機(jī)待保障的工序序號(hào)，列表示不同艦載機(jī)的編號(hào)，元素aij是在區(qū)間(1, |Mq|+1)上的隨機(jī)實(shí)數(shù)。其中，整數(shù)部分W(aij)表示第i架艦載機(jī)的第j道保障工序由第W(aij)個(gè)保障組負(fù)責(zé)完成；PoD(aij)(矩陣元素值的小數(shù)部分)的大小決定同一道保障工序在不同艦載機(jī)中的優(yōu)先級(jí)。編碼時(shí)將矩陣各行看作一段，各段以“0”分割，每段基因記載了不同艦載機(jī)的某一道保障工序的信息，因此，整個(gè)矩陣構(gòu)成了一條含艦載機(jī)保障信息的長(zhǎng)度為m×n+m-1的染色體：[a11,a12,…,a1n,0,a21,…，a2n,0,…,0,am1,…，amn]。

如下為區(qū)間(1, |Mq|+1)上隨機(jī)生成的實(shí)數(shù)aij構(gòu)成的編碼矩陣：

其中，矩陣元素a11表示第一架艦載機(jī)的第一道保障工序由保障組1進(jìn)行作業(yè)；矩陣元素a12表示第二架艦載機(jī)的第一道保障工序由保障組1進(jìn)行作業(yè)，但由于其元素值1.6>1.3，因此，第二架艦載機(jī)的第一道保障工序的優(yōu)先級(jí)高于第一架艦載機(jī)，保障組1需先對(duì)第二架艦載機(jī)進(jìn)行保障；矩陣元素a13其值為2.4表示第三架艦載機(jī)的第一道保障工序由保障組2進(jìn)行作業(yè)，其余元素釋義依此類推。

2.1.2 解碼過程

解碼過程是實(shí)現(xiàn)編碼染色體與保障調(diào)度方案的映射，同時(shí)，需充分考慮保障作業(yè)過程中的約束關(guān)系[14]。因此，將保障工序分成若干集合，以時(shí)序推進(jìn)方式調(diào)動(dòng)各保障工序所處集合，步驟如下。

設(shè)Ad為當(dāng)前保障作業(yè)的工序集合，Cd為已完成保障作業(yè)的工序集合，Wl為未保障作業(yè)的工序集合，且隨著時(shí)間推進(jìn)，更新以上工序集合。

Step1：第i架艦載機(jī)進(jìn)入保障站位，將其虛工序Bi的緊后工序PBi依據(jù)值W(aij)釋放至相應(yīng)的保障組序列。

Step2：工序Oij由第l個(gè)保障組保障，記錄其開始時(shí)間Bij并更新集合。

Step3：記錄工序Oij的保障結(jié)束時(shí)間Dij，將集合Ad中的元素轉(zhuǎn)移到集合Cd，并判斷Oij緊后工序的所有緊前工序PHij是否均已結(jié)束；若是，則釋放緊后工序到對(duì)應(yīng)保障組序列。根據(jù)PoD(aij)選取Wl中下一個(gè)保障工序，將其轉(zhuǎn)移到集合Ad，并更新集合Cd。

2.2 初始種群與適應(yīng)度函數(shù)

初始種群是由編碼隨機(jī)產(chǎn)生的若干染色體組成，通過適應(yīng)度函數(shù)來(lái)評(píng)價(jià)個(gè)體的適應(yīng)度值，且與目標(biāo)函數(shù)的最大保障耗時(shí)有關(guān)，見式(13)。

(13)

其中，Cmax(k)表示第k個(gè)調(diào)度方案的最大保障耗時(shí)。

2.3 選擇操作

父代個(gè)體適應(yīng)度值的高低決定了子代個(gè)體被選擇的概率，適應(yīng)度值高，則被選中的概率大，反之，則個(gè)體被淘汰的概率大，因此，以輪盤賭法[15]選擇子代個(gè)體，步驟如下：

Step1：求該染色體Vi(i=1，2，…，S)的適應(yīng)度值eval(Vi)，其中，S表示群體的最大規(guī)模。

Step2：求群體的總體適應(yīng)度值。

(14)

Step3：求染色體Vi(i=1，2，…，S)的被選概率：

(15)

Step4：由式(15)可知，染色體Vi(i=1，2，…，S)的累積概率為：

(16)

選擇時(shí)每一輪將隨機(jī)產(chǎn)生一個(gè)實(shí)數(shù)γ∈(0,1)，若指針落在第i個(gè)區(qū)間，其累積概率為p1+p2+…+pi-1<γ

圖2 輪盤賭選擇示意圖Fig.2 Operation of selection with roulette

2.4 交叉操作

首先，按適應(yīng)度值將若干染色體分組，一組為適應(yīng)度值較高的染色體，其他的組成另一組。然后，從兩組中分別隨機(jī)地選取一條染色體交配，以此法形成新的一對(duì)個(gè)體，將使整個(gè)種群的適應(yīng)度值向最優(yōu)方向發(fā)展，具體的交叉操作如下所述。

將帶有保障調(diào)度信息的染色體分段交叉，且每小段采用一點(diǎn)交叉(one-point crossover)法對(duì)兩條染色體上同一位置的信息進(jìn)行交換，從而確保串位后的兩個(gè)個(gè)體攜帶的保障調(diào)度方案仍是可行的。例如，以A、B表示兩個(gè)父代個(gè)體，在A、B上隨機(jī)選擇一處作為交叉點(diǎn)，如圖3中箭頭標(biāo)記位置；然后，交換交叉點(diǎn)處的基因信息，從而獲得子代A1、B1。

2.5 禁忌搜索下的變異操作

禁忌搜索(Tabu Search, TS)算法是由Glover等[16]提出的，它通過“禁忌表”的記憶方式引導(dǎo)搜索過程，避免陷入局部最優(yōu)或重復(fù)過去的搜索。因此，將它與遺傳算法相結(jié)合，使種群能高效地向優(yōu)良方向繁衍。通過在不同迭代次數(shù)條件下調(diào)用禁忌搜索算子改進(jìn)遺傳算法搜索過程；觀察改進(jìn)算法的收斂效果，并截取遺傳算法迭代第2至5次時(shí)調(diào)用禁忌搜索算子的收斂曲線，見圖4。試驗(yàn)表明，以算法每迭代4次調(diào)用1次禁忌搜索的方式對(duì)遺傳算法進(jìn)行改進(jìn)，在對(duì)保障作業(yè)的優(yōu)化上效果最好。

圖3 遺傳算法的交叉過程Fig.3 Schematic diagram of crossover processing of genetic algorithm

(a) k=2 (b) k=3

(c) k=4 (d) k=5圖4 不同迭代次數(shù)下調(diào)用禁忌搜索的優(yōu)化曲線Fig.4 Optimized curve of tabu search with different number of iterations

因此，以k=4作為調(diào)用禁忌搜索算子的判斷條件。若算法迭代次數(shù)k=4，則以禁忌算子進(jìn)行變異操作，即在遺傳算法框架中運(yùn)用禁忌搜索算法進(jìn)行變異操作，見圖5。設(shè)定算法的迭代閾值，滿足調(diào)用條件，則在交叉操作后用禁忌搜索算子對(duì)種群中每個(gè)個(gè)體的鄰域進(jìn)行搜索，生成候選集合；判斷候選解是否為禁忌表中的對(duì)象，將最大搜索代數(shù)Gmax作為禁忌搜索的結(jié)束條件。

若k≠4，則采用傳統(tǒng)變異算子進(jìn)行變異操作，詳述如下：

1)傳統(tǒng)變異算子以變異概率Pm對(duì)交叉產(chǎn)生的種群隨機(jī)反轉(zhuǎn)其上某一位置的等位基因。

2)在染色體上隨機(jī)選取變異位，依據(jù)如下：

①d=Rand{0,1}。

②若d=1，則r=Rand(0,|Mq|+1-aij)；否則r=Rand(0,aij-1)。

因此，改進(jìn)遺傳算法的實(shí)現(xiàn)步驟如下：

Step1：設(shè)定遺傳算法基本參數(shù)，最大迭代次數(shù)Nd，初始群體規(guī)模Np，交叉概率Pc，變異概率Pm。

Step2：編碼與解碼設(shè)計(jì)，隨機(jī)生成初始種群。

Step3：設(shè)計(jì)算法的適應(yīng)度函數(shù)，計(jì)算種群中個(gè)體的適應(yīng)度值。

Step4：按照輪盤賭規(guī)則進(jìn)行遺傳算法的選擇操作。

Step5：按照2.4節(jié)中的交叉規(guī)則對(duì)選擇后的個(gè)體進(jìn)行交叉操作。

Step6：判斷閾值是否滿足k=4，若k≠4，則以傳統(tǒng)變異算子進(jìn)行變異操作，k=k+1，轉(zhuǎn)至Step 8，否則，以禁忌變異算子完成變異過程。

Step7：調(diào)用禁忌變異算子進(jìn)行變異操作：

①將遺傳操作產(chǎn)生個(gè)體作為初始解，禁忌表設(shè)為空。

②判斷是否滿足停止準(zhǔn)則，若滿足，結(jié)束當(dāng)前循環(huán)，重置閾值和禁忌搜索迭代次數(shù)，k=0，i=0；若不滿足，繼續(xù)以下步驟。

③從初始解x的鄰域中選出符合禁忌要求的候選解。

④判斷候選解是否滿足期望，若滿足，則轉(zhuǎn)至⑦，否則繼續(xù)以下步驟。

圖5 禁忌搜索算子的變異操作流程Fig.5 Flow chart of tabu search operator in improved genetic algorithm

⑤判斷候選解集中的解有無(wú)符合特赦準(zhǔn)則要求的解，若符合，則將其特赦出來(lái)作為最優(yōu)解，轉(zhuǎn)至⑦；否則，繼續(xù)以下步驟。

⑥當(dāng)候選解不符合特赦準(zhǔn)則要求，則在非禁忌對(duì)象中選出最優(yōu)解。

⑦輸出最優(yōu)解。

⑧更新禁忌表，更新迭代次數(shù)ii=ii+1。

Step8：判斷是否滿足算法的結(jié)束條件，若滿足，結(jié)束循環(huán)，否則，轉(zhuǎn)至Step 3繼續(xù)迭代，i=i+1。

3 艦載機(jī)保障作業(yè)仿真

3.1 模型修正策略

遇到干擾事件時(shí)，以如下策略對(duì)模型進(jìn)行修正。

1)保障組可用時(shí)刻修正。艦載機(jī)保障作業(yè)過程遇到突發(fā)事件干擾，則需對(duì)保障調(diào)度方案進(jìn)行重調(diào)度。此時(shí)，保障組的狀態(tài)可能為“忙碌”“休息”。對(duì)于重調(diào)度方案中處于“休息”狀態(tài)的保障組，重調(diào)度指令發(fā)出時(shí)刻即為該保障組的下一項(xiàng)作業(yè)開始時(shí)刻；對(duì)于重調(diào)度方案中處于“忙碌”狀態(tài)的保障組，其作業(yè)過程具有連續(xù)性，應(yīng)等待當(dāng)前保障工序完成，并將該時(shí)刻作為重調(diào)度開始時(shí)刻。

2)艦載機(jī)保障工序矩陣狀態(tài)修正。艦載機(jī)保障作業(yè)遇重調(diào)度時(shí)，除了需要確定保障組的工作狀態(tài)是否可用外，還需要確定艦載機(jī)的保障狀態(tài)，即艦載機(jī)保障作業(yè)是否完成，可分為“正在保障”“保障完成”。對(duì)于進(jìn)入保障區(qū)的艦載機(jī)，其每一道保障工序都對(duì)應(yīng)有這兩個(gè)保障狀態(tài)；若某艦載機(jī)的某一道保障工序的狀態(tài)由“正在保障”變?yōu)椤氨Ｕ贤瓿伞?，則將該道工序放入完工集合，并從工序矩陣中刪除，保留未開始的保障工序。

3)保障設(shè)備工作狀態(tài)修正。保障設(shè)備是否可用，既決定著保障組是否真正可用，也決定著艦載機(jī)保障工序的進(jìn)程，因此，重調(diào)度發(fā)生時(shí)需確定各保障組保障設(shè)備的工作狀態(tài)。當(dāng)保障組設(shè)備故障時(shí)，應(yīng)變更保障組狀態(tài)為“不可用”，并從保障組的可用集合(休息、忙碌)中刪除；正在作業(yè)的保障任務(wù)優(yōu)先級(jí)高，需優(yōu)先安排可用的“休息”保障組接替完成前序保障工序。

3.2 調(diào)度優(yōu)化的仿真流程

在客觀條件不具備的情況下，以模擬真實(shí)環(huán)境要素的仿真手段來(lái)檢驗(yàn)改進(jìn)型遺傳算法對(duì)艦載機(jī)保障調(diào)度的優(yōu)化效果是最為有效的途徑，其流程見圖6。

圖6 仿真流程圖Fig.6 Flow chart of simulation of carrier deck operation

步驟如下：

Step1：仿真開始后，算法給出關(guān)于當(dāng)前艦載機(jī)保障的調(diào)度方案。

Step2：系統(tǒng)根據(jù)調(diào)度方案執(zhí)行調(diào)度任務(wù)。

Step3：系統(tǒng)判斷是否有干擾事件發(fā)生，干擾事件的分類詳見1.1節(jié)，若無(wú)干擾事件影響，轉(zhuǎn)至Step 6。

Step4：發(fā)生干擾事件，按3.1節(jié)所述規(guī)則對(duì)模型進(jìn)行修正。

Step5：對(duì)修正后的模型給出調(diào)度方案，轉(zhuǎn)至Step 2。

Step6：系統(tǒng)判斷所有保障工序是否完成，完成則轉(zhuǎn)至Step 8。

Step7：若保障工序未完成，則繼續(xù)按時(shí)間順序推進(jìn)保障流程。

Step8：所有保障工序完成，則輸出保障作業(yè)的甘特圖。

4 案例分析

4.1 初始調(diào)度方案優(yōu)化

以某波次艦載機(jī)保障作業(yè)為例，保障站位如圖7所示，甲板“一站式”保障位上共有8架艦載機(jī)。其中，靠近③號(hào)升降機(jī)的兩架艦載機(jī)已經(jīng)戰(zhàn)損(顯示為紅色)，無(wú)法在“一站式”保障位上維修，需要調(diào)入機(jī)庫(kù)維修；對(duì)“一站式”保障位中其余6架艦載機(jī)進(jìn)行保障，保障進(jìn)行到第25 min時(shí)，由②號(hào)和③號(hào)升降機(jī)從機(jī)庫(kù)各調(diào)出1架艦載機(jī)升至艦面保障區(qū)。案例中參與保障的各類保障組的數(shù)目為：2個(gè)航電保障組，2個(gè)特設(shè)保障組，3個(gè)軍械保障組、3個(gè)機(jī)械保障組，其編號(hào)、作業(yè)內(nèi)容、作業(yè)順序、作業(yè)耗時(shí)，詳見表1。將保障開始后的第25 min加入2架艦載機(jī)設(shè)為該案例的干擾事件，并在4.2節(jié)中詳述。

圖7 6架待保障的艦載機(jī)Fig.7 Six aircrafts of waiting support operation

如圖6所示，仿真流程開始后，改進(jìn)的遺傳算法對(duì)甲板現(xiàn)有的6架艦載機(jī)進(jìn)行保障作業(yè)的調(diào)度優(yōu)化分析并執(zhí)行其優(yōu)化的調(diào)度方案。在無(wú)干擾的情況下，將按時(shí)間推進(jìn)保障作業(yè)，最終輸出優(yōu)化結(jié)果，同時(shí)與傳統(tǒng)遺傳算法的優(yōu)化結(jié)果做比較，算法及禁忌變異算子的初始參數(shù)設(shè)置如表2～3所示。仿真結(jié)束條件為最大迭代搜索次數(shù)100代。

表1 艦載機(jī)保障工序情況清單[17]Tab.1 List of support processing of aircraft

表2 遺傳算法和改進(jìn)型遺傳禁忌算法主要參數(shù)Tab.2 Primary parameters of genetic algorithm and improved genetic algorithm

表3 禁忌變異算子主要參數(shù)表Tab.3 Primary parameters of mutation operator of tabu method

通過遺傳算法和改進(jìn)型遺傳算法對(duì)艦載機(jī)的最大保障耗時(shí)進(jìn)行優(yōu)化和比較，其結(jié)果見圖8。圖中綠色曲線(GA)反映了遺傳算法各代最優(yōu)解的變化趨勢(shì)，紅色曲線(HGATS)反映了改進(jìn)型遺傳算法各代最優(yōu)解的變化趨勢(shì)。結(jié)果表明，改進(jìn)型遺傳算法在收斂速度以及優(yōu)化艦載機(jī)保障作業(yè)時(shí)間上優(yōu)于傳統(tǒng)遺傳算法。文獻(xiàn)[1]中美軍F/A-18艦載機(jī)出動(dòng)回收保障時(shí)間一般在60～105 min(1+00～1+45 cycle)，而案例中6架艦載機(jī)的保障完成時(shí)間均小于75 min(1+15 cycle)， 見圖9。

以保障組為主體觀察仿真優(yōu)化結(jié)果見圖10，圖中綠色塊表示保障組“忙碌”，黃色塊表示保障組在艦載機(jī)之間的轉(zhuǎn)移耗時(shí)，空白處則表示保障組“休息”。色塊中的字符Pi(i=1,2,3，…)表示正在保障的艦載機(jī)編號(hào)，Pi下面的數(shù)字表示正在保障的保障工序編號(hào)；橫坐標(biāo)表示保障組作業(yè)耗時(shí)，縱坐標(biāo)表示各類保障組及此類保障組的編號(hào)。

以艦載機(jī)為主體觀察仿真優(yōu)化結(jié)果，見圖11。橫坐標(biāo)表示艦載機(jī)保障耗時(shí)，縱坐標(biāo)表示艦載機(jī)的編號(hào)。其中，綠色塊內(nèi)的字符Mij表示類型為i的保障組的第j個(gè)小組，M1表示航電類保障組，M2表示特種設(shè)備(簡(jiǎn)稱：特設(shè))類保障組，M3表示軍械類保障組，M4表示機(jī)械類保障組。每架艦載機(jī)完成保障的耗時(shí)，見圖8。

圖8 算法改進(jìn)前后的艦載機(jī)最大保障完成時(shí)間優(yōu)化曲線Fig.8 Optimizing curve of maximum mission time of aircraft support operation before and after improved algorithm

4.2 重調(diào)度方案優(yōu)化

如圖6所示流程，當(dāng)系統(tǒng)判斷有干擾影響時(shí)，需對(duì)模型進(jìn)行修正，然后，改進(jìn)型遺傳算法對(duì)初始調(diào)度方案進(jìn)行再優(yōu)化。如圖12所示，在原保障方案執(zhí)行第25 min時(shí)有兩架艦載機(jī)(編號(hào)P7、P8)加入保障序列，對(duì)原保障過程形成了突發(fā)干擾。以圖13為例說明遇干擾事件時(shí)的重調(diào)度過程，圖中虛線分割的時(shí)刻(15 min)，航電組1與特設(shè)組1完成前序保障任務(wù)，處于“休息”，而軍械組1與機(jī)械組1仍在“忙碌”，因此不可用。

圖10 8架待保障的艦載機(jī)Fig.10 Eight aircrafts of waiting support operation

甘特圖反映了艦載機(jī)各保障工序與保障組之間的任務(wù)分配關(guān)系。上述干擾事件發(fā)生時(shí)，各類保障組中，特設(shè)保障組1、軍械保障組1和2、機(jī)械保障組1至3均處于“忙碌”狀態(tài)，需待上述保障組完成當(dāng)前作業(yè)后，方可加入重調(diào)度序列。因此，對(duì)比4.1節(jié)中6架艦載機(jī)的完成時(shí)間，8架艦載機(jī)的保障完成時(shí)間普遍要長(zhǎng)，但仍然在單次出動(dòng)回收的最大保障時(shí)間內(nèi)(1+45 cycle)，見圖14。第25分鐘加入新的艦載機(jī)，需對(duì)模型修正后調(diào)用算法重調(diào)度，保障組甘特圖如圖15所示?？梢?，重調(diào)度優(yōu)化后，航電組1、2，特設(shè)組2，軍械組2、3以及機(jī)械組1的保障作業(yè)內(nèi)容發(fā)生了變化。圖16為各艦載機(jī)上進(jìn)行的保障工序甘特圖。

圖11 6架艦載機(jī)優(yōu)化調(diào)度方案保障組甘特圖Fig.11 Gantt chart of optimizing scheduling plan of six aircraft′s support team

圖12 6架艦載機(jī)優(yōu)化調(diào)度方案艦載機(jī)甘特圖Fig.12 Gantt chart of optimizing scheduling plan of six aircraft

圖13 再調(diào)度保障組可用時(shí)刻Fig.13 Free time chart of support team of rescheduling

圖14 8架艦載機(jī)的保障作業(yè)完成時(shí)間Fig.14 Support completion time of eight aircrafts

圖15 8架艦載機(jī)優(yōu)化調(diào)度方案保障組甘特圖Fig.15 Gantt chart of optimizing scheduling plan of eight aircraft′s support team

圖16 8架艦載機(jī)優(yōu)化調(diào)度方案艦載機(jī)甘特圖Fig.16 Gantt chart of optimizing scheduling plan of eight aircrafts

5 結(jié)論

根據(jù)艦載機(jī)保障作業(yè)特點(diǎn)，以改進(jìn)遺傳算法對(duì)艦載機(jī)保障作業(yè)中保障組的調(diào)度問題進(jìn)行案例分析。在無(wú)干擾影響的初始保障調(diào)度方案優(yōu)化中，對(duì)比了改進(jìn)遺傳算法和傳統(tǒng)遺傳算法的效果。結(jié)果表明，以引入禁忌搜索變異算子改進(jìn)遺傳算法來(lái)解決艦載機(jī)調(diào)度優(yōu)化問題是可行的，且獲得最優(yōu)解的迭代次數(shù)及收斂效果要優(yōu)于傳統(tǒng)遺傳算法。在干擾事件影響下，對(duì)某一時(shí)刻有新的艦載機(jī)加入保障序列的問題，以事件驅(qū)動(dòng)機(jī)制對(duì)模型修正后，進(jìn)行重調(diào)度優(yōu)化，優(yōu)化結(jié)果表明該算法仍能得到可行的最優(yōu)解。上述案例僅是一種干擾事件在保障作業(yè)中的影響，隨著仿真流程的循環(huán)及保障任務(wù)的推進(jìn)，其他類型的干擾事件也可能發(fā)生，系統(tǒng)會(huì)根據(jù)具體事件制定新的重調(diào)度策略。案例表明，改進(jìn)遺傳算法能對(duì)干擾事件影響下的多機(jī)保障作業(yè)過程給出較為合理的調(diào)度優(yōu)化方案，具有良好的魯棒性和重要的研究意義。