呂曉峰,楊東澤,王麗婷,馬 羚
(海軍航空大學(xué) 岸防兵學(xué)院, 山東 煙臺(tái) 264001)
艦載機(jī)作為航母編隊(duì)?wèi)?zhàn)斗力的核心,出動(dòng)架次率將直接影響航母編隊(duì)的戰(zhàn)斗力。艦載機(jī)在出動(dòng)前需進(jìn)行多項(xiàng)保障作業(yè),其中彈藥掛載工作較為復(fù)雜,是影響艦載機(jī)出動(dòng)能力的主要因素之一。艦載機(jī)出動(dòng)保障作業(yè)流程復(fù)雜,并且以上保障作業(yè)的進(jìn)行涉及到多個(gè)專業(yè)與多種保障設(shè)備,各個(gè)保障作業(yè)之間不僅受到時(shí)序約束,同時(shí)受到保障設(shè)備、保障人員和戰(zhàn)位空間等資源約束。因此在對(duì)艦載機(jī)保障資源合理規(guī)劃的基礎(chǔ)上提高彈藥保障能力尤為重要,也是提高艦載機(jī)彈藥保障能力的迫切需求。
關(guān)于艦載機(jī)保障作業(yè)調(diào)度問(wèn)題,國(guó)內(nèi)外已從不同角度進(jìn)行了大量分析研究工作。在構(gòu)建模型方面,蘇析超等[1-4]基于艦載機(jī)一站式保障模式研究航空保障作業(yè)調(diào)度優(yōu)化問(wèn)題,考慮到設(shè)備與人員等約束,在典型任務(wù)下運(yùn)用多種算法求解了調(diào)度方案。文獻(xiàn)[5-7]從保障作業(yè)中會(huì)出現(xiàn)擾動(dòng)事件的角度建立了艦載機(jī)保障作業(yè)調(diào)度模型,運(yùn)用智能算法求解艦載機(jī)甲板作業(yè)動(dòng)態(tài)調(diào)度問(wèn)題。文獻(xiàn)[8]設(shè)計(jì)了雙種群遺傳算法比較不同人機(jī)匹配模式下的保障效率與人員負(fù)載均衡性,并分析了各個(gè)模式的優(yōu)劣。劉玨等[9]在遺傳算法中引入禁忌搜索算子求解了含干擾事件的多機(jī)保障問(wèn)題。張豪等[10]基于隨機(jī)過(guò)程與線性策略建立了艦載機(jī)作業(yè)流程調(diào)度仿真模型,分析了不同調(diào)度策略下對(duì)艦載機(jī)作業(yè)安全和出動(dòng)架次率的影響。但是,上述研究通過(guò)不斷增加艦載機(jī)保障作業(yè)約束的復(fù)雜度進(jìn)一步完善模型,未結(jié)合彈藥掛載工作的特殊性。艦載機(jī)彈藥掛載需要時(shí)間較長(zhǎng),有彈藥掛載需求的艦載機(jī)通常需要多枚彈藥,掛載彈藥時(shí)會(huì)受到眾多約束,并且實(shí)際進(jìn)行彈藥掛載任務(wù)時(shí),航母彈藥保障人員會(huì)將某一架艦載機(jī)的所有彈藥集中在一個(gè)時(shí)間區(qū)間內(nèi)掛載,因此針對(duì)彈藥掛載工作的特殊性,需要提供一個(gè)有利于彈藥掛載工作的艦載機(jī)保障作業(yè)調(diào)度方案,通過(guò)該方案為彈藥掛載工作人員提供便利。
在算法設(shè)計(jì)方面,艦載機(jī)保障作業(yè)調(diào)度問(wèn)題本質(zhì)上屬于資源受限項(xiàng)目調(diào)度問(wèn)題(resource constrained project scheduling problem,RCPSP),近年來(lái)該問(wèn)題的主要求解方法大致采用元啟發(fā)式算法[11]。Mahmud等[12]提出了一種融合3種啟發(fā)式算法的定制進(jìn)化算法,更好地修正了不可行解并提高了解的質(zhì)量。陳浩杰等[13]設(shè)計(jì)了一種多樣性種群更新方式,提出了一種改進(jìn)超啟發(fā)式遺傳規(guī)劃算法,提高了算法的搜索能力。Ling等[14]提出一種新的概率模型和更新機(jī)制并將其納入EDA的搜索框架提高了算法搜索能力。同時(shí)也有對(duì)遺傳算法[15-16]、粒子群算法[17]和NSGA-Ⅱ[18]算法進(jìn)行改進(jìn)以求解RCPSP問(wèn)題。其中NSGA-Ⅱ算法被廣泛應(yīng)用于求解多目標(biāo)優(yōu)化問(wèn)題,但該算法也存在易于早熟、解集多樣性不足等問(wèn)題。
針對(duì)以上不足,結(jié)合艦載機(jī)彈藥掛載的實(shí)際情況,在艦載機(jī)多機(jī)一體化聯(lián)合保障模式下建立了考慮彈藥掛載工作下的艦載機(jī)保障作業(yè)調(diào)度模型,提出了一種新的染色體片段的編碼方式以及相應(yīng)的交叉和變異操作,結(jié)合經(jīng)典的NSGA-Ⅱ算法提出一種改進(jìn)的NSGA-Ⅱ算法[19]。
艦載機(jī)一體化聯(lián)合保障是指艦載機(jī)在滿足單機(jī)保障流程約束的條件下,合理調(diào)度人員與設(shè)備等保障資源,更加高效地完成艦載機(jī)保障作業(yè),提高艦載機(jī)出動(dòng)效率,同時(shí)在保障過(guò)程中,艦載機(jī)不需要往返轉(zhuǎn)運(yùn),只需在固定的停機(jī)位進(jìn)行保障,保障資源在不同的艦載機(jī)戰(zhàn)位之間轉(zhuǎn)換保障。艦載機(jī)在固定停機(jī)位進(jìn)行保障作業(yè)時(shí)合理地調(diào)度保障資源尤為重要,因此制定符合實(shí)際約束與高效的保障資源調(diào)度方案是執(zhí)行艦載機(jī)出動(dòng)保障任務(wù)的關(guān)鍵。艦載機(jī)在進(jìn)行保障作業(yè)時(shí)所受到的資源約束主要可將其分為保障流程約束、保障人員約束、保障設(shè)備約束、供給性資源約束與保障空間約束。
1) 保障流程約束。艦載機(jī)在進(jìn)行保障作業(yè)時(shí)需受到單機(jī)保障流程約束,各個(gè)工序需滿足緊前工序和緊后工序約束關(guān)系。如圖1所示為多機(jī)保障網(wǎng)絡(luò)圖[1],圖中Oij表示第i架艦載機(jī)正在進(jìn)行第j道保障工序,S和E為虛擬工序,不進(jìn)行實(shí)質(zhì)工作且不消耗資源,分別表示起始節(jié)點(diǎn)與結(jié)束節(jié)點(diǎn),Si和Ei為第i架艦載機(jī)的虛擬起始工序和虛擬結(jié)束工序。

圖1 多機(jī)保障網(wǎng)絡(luò)圖




調(diào)度模型中各參數(shù)定義如下:
I={1,2,…,n}表示需保障的艦載機(jī)集合,n為艦載機(jī)數(shù)量;
Ji={1,2,…,|Ji|}為第i架艦載機(jī)的工序集,|Ji|為第i架艦載機(jī)的工序數(shù);

Sij為工序Oij保障起始時(shí)間;
Tij為工序Oij保障所需時(shí)間;
Eij為工序Oij保障結(jié)束時(shí)間;
Cmax為艦載機(jī)最大保障結(jié)束時(shí)間;
Vek和Vpk分別為艦載機(jī)保障人員和保障設(shè)備的負(fù)載方差;
Pij為工序Oij的緊前工序集;



決策變量定義為:

為了使得到的調(diào)度方案更加合理可行,在優(yōu)化目標(biāo)方面構(gòu)建了艦載機(jī)保障作業(yè)完成時(shí)間和負(fù)載方差最小化的多目標(biāo)優(yōu)化模型,即
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)為模型的目標(biāo)函數(shù);式(4)表示工序Oij的保障起始時(shí)間與結(jié)束時(shí)間的關(guān)系;式(5)表示不同工序分配至相同的保障設(shè)備或人員時(shí)按照優(yōu)先級(jí)有序保障;式(6)表示同一艦載機(jī)的不同工序需滿足緊前關(guān)系約束;式(7)表示工序Oij保障期間所需的該類人員需求量需小于其數(shù)量上限;式(8)表示同一艦載機(jī)的戰(zhàn)位空間不能超過(guò)其可容納的人員數(shù)量;式(9)表示工序Oij保障期間所需的該類設(shè)備需求量需小于其數(shù)量上限;式(10)表示工序Oij保障期間所需的該類供給性資源需求量需小于其可同時(shí)供給的數(shù)量上限;式(11)表示在進(jìn)行彈藥掛載時(shí)不能與其沖突的工序同時(shí)保障。
NSGA-Ⅱ算法是基于Pareto最優(yōu)解的多目標(biāo)優(yōu)化算法,通過(guò)對(duì)種群進(jìn)行快速非支配排序以達(dá)到對(duì)種群的分級(jí),在求解多目標(biāo)問(wèn)題中已被廣泛應(yīng)用[20-21]。NSGA-Ⅱ算法通過(guò)對(duì)種群進(jìn)行快速非支配排序達(dá)到對(duì)種群的分級(jí),計(jì)算種群個(gè)體的擁擠度來(lái)保持種群的多樣性,以得到較優(yōu)解[22]。
RCPSP問(wèn)題中個(gè)體的編碼方式主要包括任務(wù)列表編碼、優(yōu)先數(shù)編碼以及優(yōu)先規(guī)則(優(yōu)先權(quán))編碼,其中任務(wù)列表編碼性能通常會(huì)優(yōu)于其他編碼方式[23],并且操作簡(jiǎn)單、易于實(shí)現(xiàn),因此具有較為廣泛的應(yīng)用。但是在保障對(duì)象與保障工序較多的情況下,隨機(jī)生成的任務(wù)列表編碼很難滿足各個(gè)工序之間的緊前緊后約束關(guān)系,為了進(jìn)一步提高算法的效率,在編碼時(shí)結(jié)合工序間的緊前緊后約束關(guān)系分片段生成染色體。
根據(jù)任務(wù)列表編碼方式,生成的染色體維度為num=∑|Ji|,其中根據(jù)各個(gè)工序的優(yōu)先級(jí)分片段生成染色體。首先將虛擬起始放置在片段1,其次按照優(yōu)先級(jí)將其緊后工序安置在片段2中,依次類推,完成染色體的編碼,如圖2所示。其中xk為一個(gè)小數(shù),整數(shù)部分表示艦載機(jī)序號(hào),小數(shù)部分表示工序號(hào)。

圖2 染色體編碼示意圖
解碼操作是根據(jù)染色體的編碼轉(zhuǎn)化成可執(zhí)行的調(diào)度方案,結(jié)合當(dāng)前資源分配現(xiàn)狀,在滿足資源約束的條件下根據(jù)染色體編碼方案將各個(gè)工序安排至最早可能開始的時(shí)間,為了完成上述操作,采用了串行調(diào)度機(jī)制(SSGS)[24]進(jìn)行解碼。
NSGA-Ⅱ中的快速非支配排序是根據(jù)個(gè)體的支配關(guān)系對(duì)種群進(jìn)行分級(jí),其作用是指引搜索向Pareto最優(yōu)解集方向進(jìn)行,使種群向最優(yōu)解集方向進(jìn)化,并根據(jù)個(gè)體擁擠度在相同層級(jí)的個(gè)體內(nèi)進(jìn)行選擇性排序。通過(guò)循環(huán)遍歷所有個(gè)體,并比較個(gè)體間的適應(yīng)度值確定其支配關(guān)系,即支配關(guān)系代表了解的優(yōu)劣程度,經(jīng)過(guò)多輪排序,最終得到種群個(gè)體的非支配層次關(guān)系。令p為當(dāng)前個(gè)體,q為與個(gè)體p比較的其他個(gè)體,P為當(dāng)前種群,np為當(dāng)前個(gè)體被其他個(gè)體支配的數(shù)量,Sp為受個(gè)體p支配的個(gè)體集合,Fi為第i級(jí)非支配解集,Q為存放下一層級(jí)的非支配解的集合。實(shí)現(xiàn)流程如下:
for eachp∈P
Sp=?
np=0
for eachq∈P
if (pq) then 如果p支配q
Sp=SP∪{q} 將q添加到個(gè)體p的支配
else if (qp) then 集合SP中
np=np+1 支配p的個(gè)體個(gè)數(shù)遞增
ifnp=0 thenp屬于第一層級(jí)
prank=1
F1=F1∪{p}
i=1 初始化層級(jí)數(shù)
whileFi≠?
Q=? 集合Q用于存儲(chǔ)下一
for eachp∈Fi層級(jí)的個(gè)體
for eachq∈Sp
nq=nq-1
ifnq=0 then 個(gè)體q屬于下一層級(jí)的非支配解
qrank=i+1
Q=Q∪{q}
i=i+1
Fi=Q
根據(jù)以上步驟可將種群進(jìn)行分層,對(duì)于同一層級(jí)內(nèi)的個(gè)體通過(guò)擁擠距離進(jìn)行區(qū)分,優(yōu)先選擇擁擠距離較大的個(gè)體,可以使相似度較低的解保存下來(lái),可形成分配比較均勻的Pareto前沿[25]。
算法設(shè)計(jì)中的交叉方式主要包括單點(diǎn)交叉、多點(diǎn)交叉和部分匹配交叉等[26],在進(jìn)行上述交叉操作時(shí),染色體的編碼會(huì)發(fā)生變化,破壞染色體編碼中的前后約束關(guān)系,在進(jìn)行交叉操作之后需判斷是否滿足約束關(guān)系,若不滿足需進(jìn)行調(diào)整。因此考慮到工序之間的緊前緊后約束關(guān)系,并結(jié)合染色體的編碼方式提出了基于染色體片段的交叉方式,將編碼中的片段視為一個(gè)整體,可縮小交叉位置的范圍,并避免了不可行解的發(fā)生,提高了算法的搜索速度,圖3為染色體的交叉操作示意圖[15]。其中染色體內(nèi)的數(shù)值僅供交叉操作的演示,與實(shí)際染色體的數(shù)值無(wú)關(guān),具體操作方法如下:
Step 1:令交叉概率為p1,隨機(jī)生成α(0≤α≤1),設(shè)參加交叉操作的2個(gè)父代個(gè)體分別為A1和A2。若α≥p1則進(jìn)行下一步驟,否則直接進(jìn)行變異操作。
Step 2:生成片段選擇參數(shù)b(b∈[1,nm]),nm為染色體片段個(gè)數(shù),通過(guò)參數(shù)b確定染色體的交叉點(diǎn)pos1。
Step 3:將A1的前pos1個(gè)片段與A2的后nm-pos1個(gè)片段進(jìn)行組合形成子代個(gè)體B1,同時(shí)將A2的前pos1個(gè)片段與A1的后nm-pos1個(gè)片段進(jìn)行組合形成子代個(gè)體B2。

圖3 染色體交叉操作示意圖
種群通過(guò)變異操作對(duì)染色體的局部基因值做變動(dòng)獲得新的個(gè)體,增加了種群的多樣性。傳統(tǒng)的變異操作是一種盲目的、隨機(jī)的變異過(guò)程,主要有“基于位置的變異”和“基于次序的變異”,其中基于位置的變異操作是在染色體中隨機(jī)生成2個(gè)變異位,并將后續(xù)的基因直接插入到第一個(gè)變異位置之前,基于次序的變異操作同樣在染色體中隨機(jī)生成2個(gè)變異位,并將2個(gè)變異位的基因進(jìn)行交換,若不滿足緊前約束關(guān)系,則需停止此次操作,轉(zhuǎn)入下次交換。上述變異操作的隨機(jī)性較大,不能夠保證每次變異之后染色體的質(zhì)量,需要設(shè)計(jì)一個(gè)能夠判斷變異之后的染色體是否滿足緊前緊后約束關(guān)系并進(jìn)行修正的機(jī)制,增加了算法的復(fù)雜度,因此本文設(shè)計(jì)了基于染色體片段的變異操作,圖4為染色體的變異操作示意圖,具體操作方法如下:
Step 1:令變異概率為p2,隨機(jī)生成β(0≤β≤1)。若β≥p1則進(jìn)行下一步驟,否則跳過(guò)變異操作。
Step 2:生成片段選擇參數(shù)d(d∈[1,nm]),nm為染色體片段個(gè)數(shù),通過(guò)參數(shù)d確定染色體的變異片段位置,并隨機(jī)生成變異點(diǎn)pos1和pos2,其中需小于該片段中的基因數(shù)。
Step 3:在染色體片段d中交換變異點(diǎn)pos1和pos2兩處的基因。

圖4 染色體變異操作示意圖
由于艦載機(jī)保障作業(yè)完成時(shí)間與保障資源負(fù)載最小化2個(gè)優(yōu)化目標(biāo)之間可能存在對(duì)立關(guān)系,在多目標(biāo)優(yōu)化問(wèn)題中并不存在某種單一的最優(yōu)解決方案[27],Pareto前沿的各個(gè)調(diào)度方案之間互不支配,需要針對(duì)研究問(wèn)題從多個(gè)調(diào)度方案中選擇適合該問(wèn)題的最優(yōu)調(diào)度方案。從Pareto前沿的多個(gè)調(diào)度方案選擇最優(yōu)的方案通常采用的方法是加權(quán)求和法,該方法常用于作業(yè)調(diào)度多目標(biāo)優(yōu)化問(wèn)題。定義權(quán)衡適應(yīng)度值為
F=ω1F1+ω2λF2
(12)
式(12)中:ω1、ω2分別為對(duì)應(yīng)目標(biāo)函數(shù)值的權(quán)重系數(shù);λ為平衡系數(shù)。
求解多目標(biāo)優(yōu)化問(wèn)題時(shí),不同目標(biāo)其側(cè)重點(diǎn)不同,通過(guò)賦予各個(gè)目標(biāo)不同的權(quán)重系數(shù)來(lái)選擇最優(yōu)方案。針對(duì)本文中研究的問(wèn)題,負(fù)載方差和保障作業(yè)完成時(shí)間相差一到2個(gè)數(shù)量級(jí),需要根據(jù)實(shí)際數(shù)值設(shè)置平衡系數(shù),否則數(shù)量級(jí)小的目標(biāo)函數(shù)對(duì)權(quán)衡適應(yīng)度值的影響很小。艦載機(jī)保障作業(yè)中需優(yōu)先保證作業(yè)完成時(shí)間,故將權(quán)重系數(shù)取為相對(duì)大值。
本文中提出的算法流程如圖5所示[15]。

圖5 算法流程圖
具體的操作步驟如下:
Step 1:設(shè)置算法基本參數(shù):種群數(shù)量、迭代次數(shù)、交叉率和變異率,并根據(jù)本文設(shè)計(jì)的編碼方式進(jìn)行染色體編碼。
Step 2:對(duì)種群快速非支配排序并計(jì)算擁擠度。
Step 3:按照本文中設(shè)計(jì)的交叉和變異操作對(duì)種群進(jìn)行迭代更新。
Step 4:若達(dá)到算法終止條件則輸出種群中的最優(yōu)方案,否則轉(zhuǎn)至Step 2。
本文中的艦面保障作業(yè)調(diào)度以國(guó)外某型航母為例,典型任務(wù)為6架艦載機(jī)同時(shí)進(jìn)行出動(dòng)前的保障作業(yè),并假設(shè)在保障過(guò)程中所有參與保障的艦載機(jī)不發(fā)生故障,艦載機(jī)的出動(dòng)保障作業(yè)流程如圖1所示。圖中工序15為艦載機(jī)彈藥掛載工序,每架艦載機(jī)的彈藥掛載時(shí)間長(zhǎng)度為30 min,針對(duì)此次保障的艦載機(jī)其各工序?qū)Ω黝愘Y源的需求如表1所示[28]。各個(gè)工序的所需時(shí)長(zhǎng)如表2所示。

表1 保障工序資源需求

表2 保障工序所需時(shí)長(zhǎng)

上述前5種保障設(shè)備均為固定設(shè)備,無(wú)法覆蓋到全部機(jī)位,慣導(dǎo)對(duì)準(zhǔn)裝置相較于其他保障設(shè)備較為充足,不會(huì)對(duì)艦載機(jī)的出動(dòng)保障作業(yè)造成約束,表3表示各個(gè)保障設(shè)備對(duì)各個(gè)機(jī)位的覆蓋情況。
對(duì)于改進(jìn)的NSGA-Ⅱ算法種群數(shù)量設(shè)置為Pop=100,算法迭代次數(shù)設(shè)置為cg=100,交叉率設(shè)置為p1=0.8,變異概率設(shè)置為p2=0.2,保障作業(yè)完成時(shí)間權(quán)重設(shè)置為ω1=0.7,負(fù)載方差權(quán)重設(shè)置為ω2=0.7,平衡系數(shù)為λ=50,在相同的參數(shù)設(shè)置下選取文獻(xiàn)[29]中的NSGA-Ⅱ算法與本文設(shè)計(jì)的改進(jìn)NSGA-Ⅱ算法進(jìn)行對(duì)比,運(yùn)用Matlab軟件進(jìn)行仿真,圖6為改進(jìn)NSGA-Ⅱ與NSGA-Ⅱ得到的非支配解對(duì)比圖[21]。圖7為改進(jìn)NSGA-Ⅱ與NSGA-Ⅱ的迭代過(guò)程圖[25]。

表3 保障設(shè)備對(duì)各個(gè)機(jī)位的覆蓋情況

圖6 改進(jìn)NSGA-Ⅱ與NSGA-Ⅱ所得的非支配解

圖7 改進(jìn)NSGA-Ⅱ與NSGA-Ⅱ迭代過(guò)程圖
圖6和圖7中改進(jìn)NSGA-Ⅱ算法和NSGA-Ⅱ藍(lán)色的符號(hào)與線條表示改進(jìn)NSGA-Ⅱ算法的仿真結(jié)果,紅色的符號(hào)與線條表示NSGA-Ⅱ的仿真結(jié)果。根據(jù)圖6可看出改進(jìn)的NSGA-Ⅱ算法非支配解集性能更優(yōu),NSGA-Ⅱ算法生成的解全部被改進(jìn)的NSGA-Ⅱ生成的解支配。根據(jù)圖7可看出改進(jìn)的NSGA-Ⅱ算法收斂速度更快,全局搜索能力更強(qiáng),其在迭代至32代時(shí)求得最優(yōu)權(quán)重適應(yīng)度值67.85,而NSGA-Ⅱ算法在迭代至44代時(shí)求得權(quán)重適應(yīng)度值78.445,并陷入了局部最優(yōu)解。通過(guò)2種算法比較,改進(jìn)后的算法收斂速度提升了23%,最優(yōu)解提升了16%。


圖8 保障人員調(diào)度甘特圖

圖9 保障設(shè)備調(diào)度甘特圖

圖10 6架艦載機(jī)優(yōu)化調(diào)度方案甘特圖
本文中建立了彈藥掛載工作下的艦載機(jī)保障作業(yè)調(diào)度模型,提出了一種改進(jìn)的NSGA-Ⅱ算法,對(duì)艦載機(jī)保障資源進(jìn)行合理調(diào)度,得到主要結(jié)論如下:
1) 對(duì)艦載機(jī)的彈藥掛載調(diào)度與其他出動(dòng)保障作業(yè)進(jìn)行區(qū)分考慮,將每架艦載機(jī)的彈藥掛載時(shí)間安排為一個(gè)時(shí)間區(qū)間,建立了艦載機(jī)保障作業(yè)調(diào)度模型。
2) 提出了基于工序優(yōu)先級(jí)的染色體片段編碼,并在此基礎(chǔ)上對(duì)NSGA-Ⅱ算法的交叉與變異操作提出改進(jìn)。
3) 對(duì)設(shè)計(jì)的模型與算法進(jìn)行仿真,結(jié)果表明,艦載機(jī)彈藥掛載工作更加切合實(shí)際,降低了艦載機(jī)保障作業(yè)的復(fù)雜度,算法收斂速度提升了23%,最優(yōu)解提升了16%。