張 勇

(1.海軍航空大學(xué) 航空作戰(zhàn)勤務(wù)學(xué)院， 山東 煙臺(tái) 264001; 2.清華大學(xué) 精密儀器系， 北京 100084)

1 引言

航空保障調(diào)度系統(tǒng)正常運(yùn)行是實(shí)現(xiàn)艦載機(jī)出動(dòng)回收的基礎(chǔ)，提高艦載機(jī)保障作業(yè)調(diào)度能力對(duì)于提升航母編隊(duì)整體作戰(zhàn)效能具有重要意義[1]。

近年來，艦載機(jī)保障作業(yè)調(diào)度處于由智能優(yōu)化調(diào)度向人機(jī)交互智能決策調(diào)度的過渡階段。Dastidar等[2]提出了基于排隊(duì)網(wǎng)的艦載機(jī)保障作業(yè)調(diào)度方法，各保障站位視為網(wǎng)絡(luò)中的節(jié)點(diǎn)，將調(diào)度問題被轉(zhuǎn)化為訪問節(jié)點(diǎn)的決策問題。Yu等[3]基于柔性作業(yè)車間調(diào)度模型，提出了艦載機(jī)保障作業(yè)調(diào)度問題的混合整數(shù)規(guī)劃模型。Su等[4]研究了不確定工時(shí)保障作業(yè)魯棒調(diào)度問題，并提出了魯棒調(diào)度機(jī)制，設(shè)計(jì)了魯棒調(diào)度算法。李經(jīng)等[5]以尼米茲航母多站式保障為背景，研究了艦載機(jī)多站式保障調(diào)度問題，并利用遺傳算法求解問題，但沒有給出具體人員和設(shè)備的調(diào)度方案。韓維等[6]詳細(xì)描述了單機(jī)保障作業(yè)流程，分析了保障作業(yè)約束，建立了基于計(jì)劃評(píng)審技術(shù)的多機(jī)一體化機(jī)務(wù)保障作業(yè)調(diào)度模型。蔣婷婷等[7]針對(duì)艦載機(jī)集中式保障模式，綜合考慮保障中的工序邏輯約束和資源約束，建立了艦載機(jī)集中式保障調(diào)度動(dòng)態(tài)分層目標(biāo)優(yōu)化模型。蘇析超等[8]研究了不同人機(jī)匹配模式下的艦載機(jī)機(jī)務(wù)勤務(wù)保障調(diào)度問題，通過仿真試驗(yàn)表明，一體化保障模式具有更高的保障效率和人員負(fù)載均衡性。

隨著艦載機(jī)“綜合保障”概念的提出與實(shí)踐，機(jī)務(wù)保障人員“一專多能”已成為發(fā)展趨勢(shì)。在一體化保障模式下，艦載機(jī)艦面保障作業(yè)需要機(jī)務(wù)保障人員可以完成跨專業(yè)、多工種的保障工作，因此機(jī)務(wù)保障人員專業(yè)合并是艦載機(jī)艦面保障作業(yè)需要研究的問題。本文首先建立了保障作業(yè)與資源配置聯(lián)合優(yōu)化(joint optimization for flight deck operations and resource allocation,JOFDORA)模型。然后，設(shè)計(jì)了改進(jìn)的NSGA Ⅱ算法(improved nondominated sorting genetic algorithm Ⅱ,iNSGA Ⅱ)用于模型求解。在個(gè)體選擇階段，采用k-means聚類方法將種群個(gè)體分組，在不同分組中分別選取個(gè)體用于種群進(jìn)化。在進(jìn)化階段，采用正態(tài)分布取樣變異算子控制基因變異范圍。種群合并后，采用刪減策略去除聯(lián)合種群重復(fù)個(gè)體。最后基于案例仿真，驗(yàn)證了模型和算法的有效性，研究了保障人員專業(yè)合并對(duì)于艦載機(jī)保障作業(yè)調(diào)度效能的影響。

2 數(shù)學(xué)模型

艦載機(jī)在出動(dòng)之前需要進(jìn)行加油、掛彈、充氧、通電等保障作業(yè)，以維持其良好的作戰(zhàn)性能。艦載機(jī)進(jìn)入保障停機(jī)位之后，各專業(yè)機(jī)務(wù)保障人員按照既定的工序執(zhí)行順序，進(jìn)行艦載機(jī)的保障作業(yè)，作業(yè)過程中，各類固定保障設(shè)備為各項(xiàng)工序作業(yè)提供油、液、氣、電等供給類資源。為提高保障效率，甲板上還配置一定數(shù)量的移動(dòng)保障設(shè)備。受供給能力的制約，各供給類資源僅可同時(shí)為一定數(shù)量的保障設(shè)備提供服務(wù)。各工序存在多種執(zhí)行模式，不同執(zhí)行模式需要的保障人員數(shù)量不同，但需要的保障設(shè)備數(shù)量相同。保障人員在執(zhí)行工序時(shí)，需要占據(jù)一定的工位空間。艦載機(jī)艦面作業(yè)調(diào)度問題可視為滿足工序邏輯約束和資源約束條件下的資源受限項(xiàng)目調(diào)度問題。JOFDORA模型中涉及的符號(hào)描述如表1所示。

表1 JOFDORA模型符號(hào)表

續(xù)表(表1)

建立的JOFDORA模型如下：

(1)

Si1≥Exi, ?i∈I

(2)

Sij≥Eih, ?(i,h)∈Pij, ?(i,j)∈J

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

其中：式(1)表示模型的目標(biāo)函數(shù)為最小化保障完工時(shí)間和最小化保障人員、移動(dòng)保障設(shè)備配置數(shù)量；式(2)表示艦載機(jī)各保障工序最早開始時(shí)間為其進(jìn)入保障停機(jī)位的時(shí)間；式(3)為工序邏輯約束，只有當(dāng)某工序的所有緊前工序完成后，該工序才可以開始；式(4)為工序的執(zhí)行模式約束；式(5)表示工序的開始與結(jié)束時(shí)間決策變量的關(guān)系；式(6)表示保障人員轉(zhuǎn)移時(shí)序約束，只有當(dāng)保障人員從前一個(gè)保障工位轉(zhuǎn)移至待調(diào)度工序工位后，待調(diào)度工序才可以開始執(zhí)行；式(7)表示保障設(shè)備只能對(duì)其覆蓋范圍內(nèi)的艦載機(jī)提供資源服務(wù)；式(8)表示保障設(shè)備的轉(zhuǎn)移時(shí)序約束；式(9)表示工位空間最大容納人員量約束；式(10)表示供給類資源最大供給量約束；式(11)和(12)表示調(diào)度方案中的人員及設(shè)備的分配量與需求量關(guān)系；式(13)、(14)表示決策變量關(guān)系約束。

3 iNSGA Ⅱ算法

JOFDORA問題屬于大規(guī)模多目標(biāo)組合優(yōu)化問題，以群智能優(yōu)化算法等為代表的元啟發(fā)式算法在此類問題中應(yīng)用效果較好[9-12]。NSGA Ⅱ算法[13]作為經(jīng)典的多目標(biāo)進(jìn)化算法，在多目標(biāo)優(yōu)化領(lǐng)域具有廣泛的應(yīng)用，但NSGA Ⅱ算法存在非支配個(gè)體多樣性低，個(gè)體在目標(biāo)函數(shù)空間分布性差等缺點(diǎn)，本文在NSGA Ⅱ算法基礎(chǔ)上，采用k-means聚類方法將種群分組[14]，并在種群合并后采用刪減策略去除聯(lián)合種群重復(fù)個(gè)體，提出了iNSGA Ⅱ算法，用于JOFDORA模型的求解。

3.1 算法整體流程

iNSGA Ⅱ算法流程如圖1所示，N為種群個(gè)體數(shù)量。在個(gè)體選擇階段，采用k-means聚類方法將種群個(gè)體分為k組，然后隨機(jī)選擇兩組，分別在兩組中采用二元錦標(biāo)賽方式選擇一個(gè)個(gè)體，2個(gè)個(gè)體經(jīng)過交叉、變異后產(chǎn)生子代。父代種群與子代種群合并后，采用刪減策略去除聯(lián)合種群中重復(fù)個(gè)體，然后進(jìn)行重組裁剪，產(chǎn)生新的父代種群。重復(fù)以上過程，直至達(dá)到最大評(píng)價(jià)次數(shù)，輸出父代種群個(gè)體及個(gè)體對(duì)應(yīng)的調(diào)度方案，算法終止。

3.2 編碼與解碼

采用四段編碼方案，第一段編碼用于表示工序調(diào)度的優(yōu)先級(jí)[15]。第二段編碼用于表示機(jī)務(wù)保障人員配置數(shù)量，記人員資源強(qiáng)度為RS，第k(k∈Kp)類專業(yè)人員配置數(shù)量|Lpk|由式(15)計(jì)算得到：

(15)

目標(biāo)函數(shù)f2、f3可將個(gè)體編碼中第二、三段編碼對(duì)應(yīng)的數(shù)值分別相加計(jì)算得到。對(duì)于目標(biāo)函數(shù)f1，采用串行調(diào)度生成機(jī)制將工序調(diào)度優(yōu)先級(jí)轉(zhuǎn)換為可行調(diào)度方案，進(jìn)而得到保障完工時(shí)間[16]。

圖1 iNSGA Ⅱ算法流程框圖

3.3 k-means聚類算法

經(jīng)過重組裁剪得到新的父代種群后，需要從中選擇個(gè)體執(zhí)行交叉、變異操作，以實(shí)現(xiàn)種群的進(jìn)化。若直接從父代種群中選取個(gè)體，容易導(dǎo)致進(jìn)行交叉操作的個(gè)體相似度過高，進(jìn)而導(dǎo)致子代個(gè)體與父代個(gè)體差異性小，降低種群個(gè)體多樣性，最終得到的Pareto最優(yōu)解集分布性變差。本文采用k-means聚類算法將父代個(gè)體分為k組，然后從不同組中分別選取個(gè)體，提高了選擇個(gè)體的差異性，提高算法的搜索能力。k-means聚類算法的偽代碼如下:

Algorithm：k-means algorithm

Input：k, parents populationPpop

Randomly selectkindividuals fromPpopas cluster centers

Repeat

Foreach individualpinPpop

Calculate the Euclidean distance betweenpand each cluster center in the objective space

Reassignpto the cluster with the minimum Euclidean distance

Update the cluster center as the mean value of members in the objective space for each cluster

Untilclusters do not change

Output:kclusters

首先隨機(jī)選取父代種群中的k個(gè)個(gè)體作為各組聚類中心，然后計(jì)算父代種群中各個(gè)體到這k個(gè)聚類中心的歐式距離(目標(biāo)函數(shù)空間)，將其歸入歐式距離最小的組，全部個(gè)體分組完畢后，計(jì)算各組目標(biāo)函數(shù)均值作為新的聚類中心。重復(fù)以上過程，直至聚類結(jié)果不發(fā)生改變。

3.4 選擇、交叉與變異

在交叉階段，對(duì)選擇的子代個(gè)體的每一段編碼實(shí)行單點(diǎn)交叉操作。對(duì)于完成交叉操作的2個(gè)子代個(gè)體編碼進(jìn)行變異操作，其中對(duì)于第一、二、四段編碼采用均勻變異方式。為了能夠使算法在相同或相近的人員配置數(shù)量下通過迭代進(jìn)一步壓縮算法得到的機(jī)群保障完工時(shí)間，對(duì)于第三段編碼采用正態(tài)分布取樣變異方式，對(duì)子代個(gè)體的第三段編碼中的人員配置數(shù)量|Lpk|，用均值為|Lpk|，方差為1的正態(tài)分布隨機(jī)數(shù)替代，即

|Lpk|←?norm(|Lpk|,1)」

(16)

若隨機(jī)數(shù)為負(fù)數(shù)，則重新生成隨機(jī)數(shù)。各段編碼的變異率分別是pmut1，pmut2，pmut3，pmut4。

算法中共涉及兩次個(gè)體選擇。首先在種群聚類操作后，從k組父代種群中隨機(jī)選取兩組，在每組種群中選擇2個(gè)父代個(gè)體，比較2個(gè)父代個(gè)體的適應(yīng)度函數(shù)值，選取適應(yīng)度好的個(gè)體作為子代。其次是在重組裁剪時(shí)，依次按照適應(yīng)度高、非支配排序序值低、擁擠度小的原則，從聯(lián)合種群中擇優(yōu)選擇N個(gè)個(gè)體作為新的父代種群，用以執(zhí)行下一次的種群進(jìn)化。

3.5 刪減策略

聯(lián)合種群經(jīng)過非支配快速排序后，按照個(gè)體序值從大到小的順序，依次判斷目標(biāo)函數(shù)空間內(nèi)有無重復(fù)個(gè)體，若有，則將重復(fù)個(gè)體刪除。經(jīng)過個(gè)體刪減后，聯(lián)合種群中的每個(gè)個(gè)體在目標(biāo)函數(shù)空間中都有唯一的位置，避免重復(fù)個(gè)體進(jìn)入下一次的種群進(jìn)化階段，提高種群個(gè)體的多樣性，提高進(jìn)化效率。需要注意的是，經(jīng)過個(gè)體刪減后，聯(lián)合種群中應(yīng)至少保留N個(gè)個(gè)體，否則無法完成后續(xù)種群的重組裁剪操作。

4 仿真試驗(yàn)及分析

4.1 案例描述

航母甲板共有16個(gè)保障停機(jī)位，仿真試驗(yàn)中共設(shè)計(jì)了任務(wù)1～任務(wù)3三類保障任務(wù)。機(jī)務(wù)保障人員共有4個(gè)專業(yè)類型，勤務(wù)保障設(shè)備共有5種類型，供給類資源共有5種類型，每類勤務(wù)保障設(shè)備均需要消耗對(duì)應(yīng)的供給類資源，僅考慮座艙一種類型的工位空間，可同時(shí)容納的保障人員數(shù)量為1。人員資源強(qiáng)度上下限分別為RSU=3.9和RSL=2.0。各類型移動(dòng)類保障設(shè)備配置數(shù)量上下限分別取NeU=3,NeL=0。受篇幅限制，文中沒有給出各工序工期、執(zhí)行模式及其所需的資源類型，保障人員和保障設(shè)備在工位之間的轉(zhuǎn)移時(shí)間，以及勤務(wù)保障設(shè)備的覆蓋范圍。

考慮到特設(shè)和航電2個(gè)專業(yè)的保障內(nèi)容、維護(hù)設(shè)備具有一定的相似性，因此本文將2個(gè)專業(yè)合并為綜合航電專業(yè)。

4.2 仿真結(jié)果分析

iNSGAⅡ算法參數(shù)設(shè)置為種群數(shù)量N=100，各段編碼的變異率分別是pmut1=0.05，pmut2=0.2，pmut3=0.2，pmut4=0.2，k-means聚類數(shù)量k=10。算法的終止條件為評(píng)價(jià)次數(shù)達(dá)到5 000次，算法獨(dú)立重復(fù)運(yùn)行10次，將10次仿真得到的Pareto最優(yōu)解集合并，作為最終的仿真結(jié)果。

為了更加清楚地反映保障人員專業(yè)合并之后對(duì)調(diào)度方案的影響，將任務(wù)1～任務(wù)3的專業(yè)合并前、后移動(dòng)保障設(shè)備配置數(shù)量分別為3、4時(shí)的Pareto最優(yōu)解單獨(dú)提取出來，結(jié)果如圖2—圖4所示。

圖2 專業(yè)合并前、后任務(wù)1的Pareto最優(yōu)解曲線

圖3 專業(yè)合并前、后任務(wù)2的Pareto最優(yōu)解曲線

圖4 專業(yè)合并前、后任務(wù)3的Pareto最優(yōu)解曲線

由圖2—圖4可以發(fā)現(xiàn)，在相同的機(jī)務(wù)保障人員和移動(dòng)保障設(shè)備配置數(shù)量下，專業(yè)合并之后同一保障任務(wù)的保障完工時(shí)間普遍小于專業(yè)合并之前。隨著保障任務(wù)規(guī)模的擴(kuò)大，專業(yè)合并對(duì)于保障效率的提升效果越來越顯著。在移動(dòng)保障設(shè)備配置數(shù)量相同的情況下，隨著機(jī)務(wù)保障人員配置數(shù)量的增加，專業(yè)合并前后保障完工時(shí)間差值逐漸減小，這是由于機(jī)務(wù)保障人員配置數(shù)量增加后，其對(duì)于保障完工時(shí)間的約束性減小，保障完工時(shí)間主要受移動(dòng)保障設(shè)備和甲板消耗性資源的限制，專業(yè)合并對(duì)于保障效率提升的效果不再顯著。因此，在機(jī)務(wù)保障人員配置數(shù)量受限的情況下，專業(yè)合并會(huì)顯著提升給機(jī)務(wù)勤務(wù)保障效率，縮短保障完工時(shí)間。

5 結(jié)論

構(gòu)建了JOFDORA模型，在NSGA Ⅱ算法基礎(chǔ)上，采用k-means聚類方法將種群分組，并增加了刪減策略，提出了iNSGA Ⅱ算法用于模型的求解。在試驗(yàn)仿真部分，討論了航電和特設(shè)專業(yè)的機(jī)務(wù)保障人員合并對(duì)于保障效率的影響。結(jié)果表明，在機(jī)務(wù)保障人員配置數(shù)量受限的情況下，專業(yè)合并會(huì)顯著提升艦載機(jī)保障效率，縮短保障完工時(shí)間。