基于彈藥掛載工作的艦載機保障作業調度

呂曉峰,楊東澤,王麗婷,馬 羚

(海軍航空大學 岸防兵學院, 山東 煙臺 264001)

0 引言

艦載機作為航母編隊戰斗力的核心,出動架次率將直接影響航母編隊的戰斗力。艦載機在出動前需進行多項保障作業,其中彈藥掛載工作較為復雜,是影響艦載機出動能力的主要因素之一。艦載機出動保障作業流程復雜,并且以上保障作業的進行涉及到多個專業與多種保障設備,各個保障作業之間不僅受到時序約束,同時受到保障設備、保障人員和戰位空間等資源約束。因此在對艦載機保障資源合理規劃的基礎上提高彈藥保障能力尤為重要,也是提高艦載機彈藥保障能力的迫切需求。

關于艦載機保障作業調度問題,國內外已從不同角度進行了大量分析研究工作。在構建模型方面,蘇析超等[1-4]基于艦載機一站式保障模式研究航空保障作業調度優化問題,考慮到設備與人員等約束,在典型任務下運用多種算法求解了調度方案。文獻[5-7]從保障作業中會出現擾動事件的角度建立了艦載機保障作業調度模型,運用智能算法求解艦載機甲板作業動態調度問題。文獻[8]設計了雙種群遺傳算法比較不同人機匹配模式下的保障效率與人員負載均衡性,并分析了各個模式的優劣。劉玨等[9]在遺傳算法中引入禁忌搜索算子求解了含干擾事件的多機保障問題。張豪等[10]基于隨機過程與線性策略建立了艦載機作業流程調度仿真模型,分析了不同調度策略下對艦載機作業安全和出動架次率的影響。但是,上述研究通過不斷增加艦載機保障作業約束的復雜度進一步完善模型,未結合彈藥掛載工作的特殊性。艦載機彈藥掛載需要時間較長,有彈藥掛載需求的艦載機通常需要多枚彈藥,掛載彈藥時會受到眾多約束,并且實際進行彈藥掛載任務時,航母彈藥保障人員會將某一架艦載機的所有彈藥集中在一個時間區間內掛載,因此針對彈藥掛載工作的特殊性,需要提供一個有利于彈藥掛載工作的艦載機保障作業調度方案,通過該方案為彈藥掛載工作人員提供便利。

在算法設計方面,艦載機保障作業調度問題本質上屬于資源受限項目調度問題(resource constrained project scheduling problem,RCPSP),近年來該問題的主要求解方法大致采用元啟發式算法[11]。Mahmud等[12]提出了一種融合3種啟發式算法的定制進化算法,更好地修正了不可行解并提高了解的質量。陳浩杰等[13]設計了一種多樣性種群更新方式,提出了一種改進超啟發式遺傳規劃算法,提高了算法的搜索能力。Ling等[14]提出一種新的概率模型和更新機制并將其納入EDA的搜索框架提高了算法搜索能力。同時也有對遺傳算法[15-16]、粒子群算法[17]和NSGA-Ⅱ[18]算法進行改進以求解RCPSP問題。其中NSGA-Ⅱ算法被廣泛應用于求解多目標優化問題,但該算法也存在易于早熟、解集多樣性不足等問題。

針對以上不足,結合艦載機彈藥掛載的實際情況,在艦載機多機一體化聯合保障模式下建立了考慮彈藥掛載工作下的艦載機保障作業調度模型,提出了一種新的染色體片段的編碼方式以及相應的交叉和變異操作,結合經典的NSGA-Ⅱ算法提出一種改進的NSGA-Ⅱ算法[19]。

1 問題描述

艦載機一體化聯合保障是指艦載機在滿足單機保障流程約束的條件下,合理調度人員與設備等保障資源,更加高效地完成艦載機保障作業,提高艦載機出動效率,同時在保障過程中,艦載機不需要往返轉運,只需在固定的停機位進行保障,保障資源在不同的艦載機戰位之間轉換保障。艦載機在固定停機位進行保障作業時合理地調度保障資源尤為重要,因此制定符合實際約束與高效的保障資源調度方案是執行艦載機出動保障任務的關鍵。艦載機在進行保障作業時所受到的資源約束主要可將其分為保障流程約束、保障人員約束、保障設備約束、供給性資源約束與保障空間約束。

1) 保障流程約束。艦載機在進行保障作業時需受到單機保障流程約束,各個工序需滿足緊前工序和緊后工序約束關系。如圖1所示為多機保障網絡圖[1],圖中Oij表示第i架艦載機正在進行第j道保障工序,S和E為虛擬工序,不進行實質工作且不消耗資源,分別表示起始節點與結束節點,Si和Ei為第i架艦載機的虛擬起始工序和虛擬結束工序。

圖1 多機保障網絡圖

2 彈藥掛載下的艦載機保障作業調度模型建立

2.1 調度模型參數定義

調度模型中各參數定義如下:

I={1,2,…,n}表示需保障的艦載機集合,n為艦載機數量;

Ji={1,2,…,|Ji|}為第i架艦載機的工序集,|Ji|為第i架艦載機的工序數;

Sij為工序Oij保障起始時間;

Tij為工序Oij保障所需時間;

Eij為工序Oij保障結束時間;

Cmax為艦載機最大保障結束時間;

Vek和Vpk分別為艦載機保障人員和保障設備的負載方差;

Pij為工序Oij的緊前工序集;

決策變量定義為:

2.2 模型建立

為了使得到的調度方案更加合理可行,在優化目標方面構建了艦載機保障作業完成時間和負載方差最小化的多目標優化模型,即

F1=minCmax

F2=min(Vek+Vpk)

(1)

式(1)中

(2)

(3)

約束條件為

Eij=Sij+Tij, ?i∈I, ?j∈Ji

(4)

(5)

Sij≥Sih+Tih, ?h∈Pij,?i∈I,?j∈Ji

(6)

(7)

(8)

(9)

(10)

(11)

其中,式(1)為模型的目標函數;式(4)表示工序Oij的保障起始時間與結束時間的關系;式(5)表示不同工序分配至相同的保障設備或人員時按照優先級有序保障;式(6)表示同一艦載機的不同工序需滿足緊前關系約束;式(7)表示工序Oij保障期間所需的該類人員需求量需小于其數量上限;式(8)表示同一艦載機的戰位空間不能超過其可容納的人員數量;式(9)表示工序Oij保障期間所需的該類設備需求量需小于其數量上限;式(10)表示工序Oij保障期間所需的該類供給性資源需求量需小于其可同時供給的數量上限;式(11)表示在進行彈藥掛載時不能與其沖突的工序同時保障。

3 改進型NSGA-Ⅱ算法設計

NSGA-Ⅱ算法是基于Pareto最優解的多目標優化算法,通過對種群進行快速非支配排序以達到對種群的分級,在求解多目標問題中已被廣泛應用[20-21]。NSGA-Ⅱ算法通過對種群進行快速非支配排序達到對種群的分級,計算種群個體的擁擠度來保持種群的多樣性,以得到較優解[22]。

3.1 編碼與解碼

RCPSP問題中個體的編碼方式主要包括任務列表編碼、優先數編碼以及優先規則(優先權)編碼,其中任務列表編碼性能通常會優于其他編碼方式[23],并且操作簡單、易于實現,因此具有較為廣泛的應用。但是在保障對象與保障工序較多的情況下,隨機生成的任務列表編碼很難滿足各個工序之間的緊前緊后約束關系,為了進一步提高算法的效率,在編碼時結合工序間的緊前緊后約束關系分片段生成染色體。

根據任務列表編碼方式,生成的染色體維度為num=∑|Ji|,其中根據各個工序的優先級分片段生成染色體。首先將虛擬起始放置在片段1,其次按照優先級將其緊后工序安置在片段2中,依次類推,完成染色體的編碼,如圖2所示。其中xk為一個小數,整數部分表示艦載機序號,小數部分表示工序號。

圖2 染色體編碼示意圖

解碼操作是根據染色體的編碼轉化成可執行的調度方案,結合當前資源分配現狀,在滿足資源約束的條件下根據染色體編碼方案將各個工序安排至最早可能開始的時間,為了完成上述操作,采用了串行調度機制(SSGS)[24]進行解碼。

3.2 快速非支配排序

NSGA-Ⅱ中的快速非支配排序是根據個體的支配關系對種群進行分級,其作用是指引搜索向Pareto最優解集方向進行,使種群向最優解集方向進化,并根據個體擁擠度在相同層級的個體內進行選擇性排序。通過循環遍歷所有個體,并比較個體間的適應度值確定其支配關系,即支配關系代表了解的優劣程度,經過多輪排序,最終得到種群個體的非支配層次關系。令p為當前個體,q為與個體p比較的其他個體,P為當前種群,np為當前個體被其他個體支配的數量,Sp為受個體p支配的個體集合,Fi為第i級非支配解集,Q為存放下一層級的非支配解的集合。實現流程如下:

for eachp∈P

Sp=?

np=0

for eachq∈P

if (pq) then 如果p支配q

Sp=SP∪{q} 將q添加到個體p的支配

else if (qp) then 集合SP中

np=np+1 支配p的個體個數遞增

ifnp=0 thenp屬于第一層級

prank=1

F1=F1∪{p}

i=1 初始化層級數

whileFi≠?

Q=? 集合Q用于存儲下一

for eachp∈Fi層級的個體

for eachq∈Sp

nq=nq-1

ifnq=0 then 個體q屬于下一層級的非支配解

qrank=i+1

Q=Q∪{q}

i=i+1

Fi=Q

根據以上步驟可將種群進行分層,對于同一層級內的個體通過擁擠距離進行區分,優先選擇擁擠距離較大的個體,可以使相似度較低的解保存下來,可形成分配比較均勻的Pareto前沿[25]。

3.3 交叉操作

算法設計中的交叉方式主要包括單點交叉、多點交叉和部分匹配交叉等[26],在進行上述交叉操作時,染色體的編碼會發生變化,破壞染色體編碼中的前后約束關系,在進行交叉操作之后需判斷是否滿足約束關系,若不滿足需進行調整。因此考慮到工序之間的緊前緊后約束關系,并結合染色體的編碼方式提出了基于染色體片段的交叉方式,將編碼中的片段視為一個整體,可縮小交叉位置的范圍,并避免了不可行解的發生,提高了算法的搜索速度,圖3為染色體的交叉操作示意圖[15]。其中染色體內的數值僅供交叉操作的演示,與實際染色體的數值無關,具體操作方法如下:

Step 1:令交叉概率為p1,隨機生成α(0≤α≤1),設參加交叉操作的2個父代個體分別為A1和A2。若α≥p1則進行下一步驟,否則直接進行變異操作。

Step 2:生成片段選擇參數b(b∈[1,nm]),nm為染色體片段個數,通過參數b確定染色體的交叉點pos1。

Step 3:將A1的前pos1個片段與A2的后nm-pos1個片段進行組合形成子代個體B1,同時將A2的前pos1個片段與A1的后nm-pos1個片段進行組合形成子代個體B2。

圖3 染色體交叉操作示意圖

3.4 變異操作

種群通過變異操作對染色體的局部基因值做變動獲得新的個體,增加了種群的多樣性。傳統的變異操作是一種盲目的、隨機的變異過程,主要有“基于位置的變異”和“基于次序的變異”,其中基于位置的變異操作是在染色體中隨機生成2個變異位,并將后續的基因直接插入到第一個變異位置之前,基于次序的變異操作同樣在染色體中隨機生成2個變異位,并將2個變異位的基因進行交換,若不滿足緊前約束關系,則需停止此次操作,轉入下次交換。上述變異操作的隨機性較大,不能夠保證每次變異之后染色體的質量,需要設計一個能夠判斷變異之后的染色體是否滿足緊前緊后約束關系并進行修正的機制,增加了算法的復雜度,因此本文設計了基于染色體片段的變異操作,圖4為染色體的變異操作示意圖,具體操作方法如下:

Step 1:令變異概率為p2,隨機生成β(0≤β≤1)。若β≥p1則進行下一步驟,否則跳過變異操作。

Step 2:生成片段選擇參數d(d∈[1,nm]),nm為染色體片段個數,通過參數d確定染色體的變異片段位置,并隨機生成變異點pos1和pos2,其中需小于該片段中的基因數。

Step 3:在染色體片段d中交換變異點pos1和pos2兩處的基因。

圖4 染色體變異操作示意圖

3.5 最優調度方案選擇

由于艦載機保障作業完成時間與保障資源負載最小化2個優化目標之間可能存在對立關系,在多目標優化問題中并不存在某種單一的最優解決方案[27],Pareto前沿的各個調度方案之間互不支配,需要針對研究問題從多個調度方案中選擇適合該問題的最優調度方案。從Pareto前沿的多個調度方案選擇最優的方案通常采用的方法是加權求和法,該方法常用于作業調度多目標優化問題。定義權衡適應度值為

F=ω1F1+ω2λF2

(12)

式(12)中:ω1、ω2分別為對應目標函數值的權重系數;λ為平衡系數。

求解多目標優化問題時,不同目標其側重點不同,通過賦予各個目標不同的權重系數來選擇最優方案。針對本文中研究的問題,負載方差和保障作業完成時間相差一到2個數量級,需要根據實際數值設置平衡系數,否則數量級小的目標函數對權衡適應度值的影響很小。艦載機保障作業中需優先保證作業完成時間,故將權重系數取為相對大值。

3.6 算法流程

本文中提出的算法流程如圖5所示[15]。

圖5 算法流程圖

具體的操作步驟如下:

Step 1:設置算法基本參數:種群數量、迭代次數、交叉率和變異率,并根據本文設計的編碼方式進行染色體編碼。

Step 2:對種群快速非支配排序并計算擁擠度。

Step 3:按照本文中設計的交叉和變異操作對種群進行迭代更新。

Step 4:若達到算法終止條件則輸出種群中的最優方案,否則轉至Step 2。

4 仿真分析

本文中的艦面保障作業調度以國外某型航母為例,典型任務為6架艦載機同時進行出動前的保障作業,并假設在保障過程中所有參與保障的艦載機不發生故障,艦載機的出動保障作業流程如圖1所示。圖中工序15為艦載機彈藥掛載工序,每架艦載機的彈藥掛載時間長度為30 min,針對此次保障的艦載機其各工序對各類資源的需求如表1所示[28]。各個工序的所需時長如表2所示。

表1 保障工序資源需求

表2 保障工序所需時長

上述前5種保障設備均為固定設備,無法覆蓋到全部機位,慣導對準裝置相較于其他保障設備較為充足,不會對艦載機的出動保障作業造成約束,表3表示各個保障設備對各個機位的覆蓋情況。

對于改進的NSGA-Ⅱ算法種群數量設置為Pop=100,算法迭代次數設置為cg=100,交叉率設置為p1=0.8,變異概率設置為p2=0.2,保障作業完成時間權重設置為ω1=0.7,負載方差權重設置為ω2=0.7,平衡系數為λ=50,在相同的參數設置下選取文獻[29]中的NSGA-Ⅱ算法與本文設計的改進NSGA-Ⅱ算法進行對比,運用Matlab軟件進行仿真,圖6為改進NSGA-Ⅱ與NSGA-Ⅱ得到的非支配解對比圖[21]。圖7為改進NSGA-Ⅱ與NSGA-Ⅱ的迭代過程圖[25]。

表3 保障設備對各個機位的覆蓋情況

圖6 改進NSGA-Ⅱ與NSGA-Ⅱ所得的非支配解

圖7 改進NSGA-Ⅱ與NSGA-Ⅱ迭代過程圖

圖6和圖7中改進NSGA-Ⅱ算法和NSGA-Ⅱ藍色的符號與線條表示改進NSGA-Ⅱ算法的仿真結果,紅色的符號與線條表示NSGA-Ⅱ的仿真結果。根據圖6可看出改進的NSGA-Ⅱ算法非支配解集性能更優,NSGA-Ⅱ算法生成的解全部被改進的NSGA-Ⅱ生成的解支配。根據圖7可看出改進的NSGA-Ⅱ算法收斂速度更快,全局搜索能力更強,其在迭代至32代時求得最優權重適應度值67.85,而NSGA-Ⅱ算法在迭代至44代時求得權重適應度值78.445,并陷入了局部最優解。通過2種算法比較,改進后的算法收斂速度提升了23%,最優解提升了16%。

圖8 保障人員調度甘特圖

圖9 保障設備調度甘特圖

圖10 6架艦載機優化調度方案甘特圖

5 結論

本文中建立了彈藥掛載工作下的艦載機保障作業調度模型,提出了一種改進的NSGA-Ⅱ算法,對艦載機保障資源進行合理調度,得到主要結論如下:

1) 對艦載機的彈藥掛載調度與其他出動保障作業進行區分考慮,將每架艦載機的彈藥掛載時間安排為一個時間區間,建立了艦載機保障作業調度模型。

2) 提出了基于工序優先級的染色體片段編碼,并在此基礎上對NSGA-Ⅱ算法的交叉與變異操作提出改進。

3) 對設計的模型與算法進行仿真,結果表明,艦載機彈藥掛載工作更加切合實際,降低了艦載機保障作業的復雜度,算法收斂速度提升了23%,最優解提升了16%。