面向故障擾動(dòng)的艦面保障重調(diào)度仿真研究

蔣婷婷，韓 維，蘇析超

(海軍航空工程學(xué)院 飛行器工程系， 山東 煙臺(tái) 264001)

面向故障擾動(dòng)的艦面保障重調(diào)度仿真研究

蔣婷婷，韓 維，蘇析超

(海軍航空工程學(xué)院 飛行器工程系， 山東 煙臺(tái) 264001)

針對艦載機(jī)艦面保障過程中設(shè)備故障擾動(dòng)下的重調(diào)度問題，綜合考慮保障的工序邏輯約束和人員、設(shè)備等資源約束，提出了艦載機(jī)保障重調(diào)度預(yù)判機(jī)制，建立了艦載機(jī)艦面保障重調(diào)度模型，并采用變鄰域算法對模型進(jìn)行求解。仿真結(jié)果表明，重調(diào)度預(yù)判機(jī)制可以進(jìn)一步節(jié)省重調(diào)度保障時(shí)間，變鄰域算法求解速度可以滿足任務(wù)需求。該重調(diào)度模型和算法能夠在任務(wù)要求保障完工時(shí)間內(nèi)，高效解決由于保障工序故障而導(dǎo)致的艦載機(jī)艦面保障重調(diào)度問題。

艦載機(jī)；艦面保障；重調(diào)度優(yōu)化；變鄰域算法

艦載機(jī)甲板保障調(diào)度是指在時(shí)間、空間、資源及工序邏輯等多重約束下對艦載機(jī)進(jìn)行維護(hù)保障。由于實(shí)際保障調(diào)度過程中一直存在動(dòng)態(tài)擾動(dòng)，因此對該過程的優(yōu)化對提升艦載機(jī)出動(dòng)架次率有重要影響。

國內(nèi)外關(guān)于艦載機(jī)動(dòng)態(tài)調(diào)度的研究主要集中在實(shí)時(shí)調(diào)度方面。美國麻省理工學(xué)院的Michini[1]和Ryan[2]等聯(lián)合開發(fā)了航母甲板作業(yè)規(guī)劃決策支持系統(tǒng)(deck operations course of action planner，DCAP)，以進(jìn)行基于人機(jī)交互的智能決策。文獻(xiàn)[3-5]考慮了艦載機(jī)故障等動(dòng)態(tài)因素，提出了基于多主體系統(tǒng)(MAS)技術(shù)的實(shí)時(shí)動(dòng)態(tài)調(diào)度模型。文獻(xiàn)[6]基于系統(tǒng)動(dòng)力學(xué)理論建立了艦載機(jī)動(dòng)態(tài)調(diào)運(yùn)復(fù)雜時(shí)變系統(tǒng)的存量流量圖及數(shù)學(xué)模型。文獻(xiàn)[7]建立了基于層次任務(wù)網(wǎng)絡(luò)(HTN)的動(dòng)態(tài)甲板任務(wù)規(guī)劃系統(tǒng)，可對任務(wù)變化做出實(shí)時(shí)響應(yīng)。在重調(diào)度方面，文獻(xiàn)[8]分析了作戰(zhàn)任務(wù)變更對艦載機(jī)航空保障調(diào)度的影響，采用重調(diào)度理論研究了基于任務(wù)的連續(xù)出動(dòng)艦載機(jī)航空保障重調(diào)度模型。

在對艦載機(jī)進(jìn)行保障時(shí)，一旦發(fā)生設(shè)備故障，保障的組織實(shí)施便會(huì)發(fā)生相應(yīng)改變，因而需要根據(jù)當(dāng)前狀態(tài)進(jìn)行重調(diào)度，即在初始調(diào)度方案執(zhí)行基礎(chǔ)上，根據(jù)發(fā)生的故障對后續(xù)工序開始時(shí)間安排和資源分配進(jìn)行重新調(diào)度。

1 艦面保障重調(diào)度問題建模

1.1 問題描述

故障擾動(dòng)導(dǎo)致的保障重調(diào)度涉及到大量人員、設(shè)備的重新分配，造成整個(gè)保障的任務(wù)量和難度顯著增加。本文建立了重調(diào)度預(yù)判機(jī)制，重調(diào)度預(yù)判流程見圖1。

圖1 重調(diào)度預(yù)判流程

進(jìn)行完全重調(diào)度仿真時(shí)，故障時(shí)刻正在執(zhí)行的工序按照原初始計(jì)劃進(jìn)行，以滿足最小保障完工時(shí)間為目標(biāo)，對未開始執(zhí)行工序進(jìn)行重調(diào)度，確定每個(gè)艦載機(jī)每道工序進(jìn)行保障時(shí)的開始時(shí)間及人員、設(shè)備分配情況，高效地輔助保障指揮管理人員制定滿足保障需求的保障調(diào)度計(jì)劃。

1.2 符號(hào)定義

定義模型參數(shù)如下：

I為艦載機(jī)i的集合；

Ji為艦載機(jī)i的工序集合；

Oij為第i架艦載機(jī)的第j道工序；

Sij為工序Oij的保障開始時(shí)間；

EXi為艦載機(jī)i入場系留完畢時(shí)間；

Pij為工序Oij的前驅(qū)任務(wù)集合；

dij為工序Oij的工期；

Kp為保障人員專業(yè)種類集合；

Lpk為第k(k∈Kp)類專業(yè)保障人員集合；

rpijk為工序Oij所需第k(k∈Kp)類專業(yè)保障人員的數(shù)量；

Kr為保障設(shè)備種類集合；

Lrk為第k(k∈Kr)種設(shè)備保障單元集合；

reijk為工序Oij所需第k(k∈Kr)種保障設(shè)備的數(shù)量；

Kw為消耗性資源種類集合；

rwijk為Oij所需第k(k∈Kw)類消耗性資源的數(shù)量；

變量Oij(t)當(dāng)工序Oij在t時(shí)刻處于執(zhí)行狀態(tài)則為1，否則為0；

變量Xpijkl當(dāng)工序Oij分配給第l(l∈Lpk)個(gè)保障人員時(shí)則為1，否則為0；

變量Xeijkl當(dāng)工序Oij分配給第l(l∈Lrk)個(gè)保障設(shè)備時(shí)則為1，否則0。

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

目標(biāo)函數(shù)如下：

(1)

約束條件如下：

Si1≥EXi, ?i∈I

(2)

(3)

(4)

(5)

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

(6)

(7)

(8)

(9)

?j∈Ji,?k∈Kr,?l∈Lrk,

?k′∈Kp,?l′∈Lpk

(10)

(11)

(12)

式(1)代表目標(biāo)函數(shù)為最小化完全重調(diào)度保障完工時(shí)間。其中

(13)

式(2)～式(12)表示約束條件。式(2)表示第i架艦載機(jī)入場系留完畢后才能開始保障，j=1代表開始的虛工序；式(3)～式(5)動(dòng)態(tài)地表示艦載機(jī)各工序、人員、設(shè)備的狀態(tài)，且表示保障過程中已經(jīng)開始的保障活動(dòng)不允許中斷；式(6)表示各艦載機(jī)工序的緊前關(guān)系約束；式(7)～式(9)分別代表人員、設(shè)備和消耗性資源的數(shù)量約束，即任一時(shí)刻所有處于執(zhí)行狀態(tài)的工序?qū)λ鼈兊男枨罅啃∮谄鋽?shù)量上限；式(10)為設(shè)備及人員的保障范圍約束，即只對在保障設(shè)備及保障人員的保障范圍之內(nèi)的艦載機(jī)進(jìn)行保障；式(11)～式(12)分別表示設(shè)備和人員需求匹配約束，即被分配數(shù)量應(yīng)等于其需求量。

2 變鄰域算法

Mladenovic和Hansen[9]于1997年提出了變鄰域算法(Variable Neighborhood Search,VNS)，其基本思想是：構(gòu)造多個(gè)鄰域結(jié)構(gòu)，在一個(gè)鄰域結(jié)構(gòu)內(nèi)搜索局部最優(yōu)解，當(dāng)局部搜索陷入局部最優(yōu)時(shí)，通過系統(tǒng)地改變鄰域結(jié)構(gòu)尋找最優(yōu)解。相對于傳統(tǒng)的固定鄰域搜索算法，基于多鄰域結(jié)構(gòu)集的系統(tǒng)變化拓展搜索范圍，搜索能力更強(qiáng)，而且VNS算法無需調(diào)整參數(shù)，實(shí)現(xiàn)簡單，因而在組合優(yōu)化領(lǐng)域得到了廣泛應(yīng)用。

2.1 編碼和解碼

本算法采用基于開始時(shí)間的優(yōu)先數(shù)編碼[10]，即序列中的每個(gè)元素固定表示調(diào)度任務(wù)時(shí)的優(yōu)先權(quán)，在調(diào)度時(shí)根據(jù)任務(wù)優(yōu)先權(quán)的大小決定任務(wù)調(diào)度順序，一般將每個(gè)元素初始化為[0,1]的隨機(jī)數(shù)，本文將每道工序的開始時(shí)間作為優(yōu)先數(shù)。根據(jù)上述模型表示為X=[S11S12…S1|J1|S21…Sij…Sn|Jn|]，其中，Sij為第i架艦載機(jī)第j道工序的開始時(shí)間，用以表示編碼中的優(yōu)先數(shù)。

對個(gè)體進(jìn)行解碼通常采用串行調(diào)度生成方案(Serial Schedule Generation Scheme,SSGS)或并行調(diào)度生成方案(Parallel Schedule Generation Scheme,PSGS)。本文在考慮拓?fù)湫蛄泻唾Y源約束的情況下，提出了一種先串行調(diào)度后并行分配的兩階段解碼方案，首先僅考慮人員的數(shù)量限制，不考慮其分配，采用SSGS產(chǎn)生工序調(diào)度方案，確定了每道工序的起止時(shí)間，其中設(shè)備的選擇采用基于覆蓋范圍內(nèi)剩余工序作業(yè)時(shí)間最少優(yōu)先規(guī)則(MTRCA)[11]；第二階段，考慮人員負(fù)載均衡性，基于各工序開工時(shí)間和PSGS機(jī)制，按時(shí)序由小到大并行遞推為各工序分配保障人員，在每一個(gè)決策時(shí)刻，優(yōu)先選取累積保障時(shí)間最少的人員，生成最終的保障調(diào)度和人員分配方案。

2.2 鄰域結(jié)構(gòu)

設(shè)計(jì)VNS算法首要問題是設(shè)計(jì)最優(yōu)解的鄰域。根據(jù)艦載機(jī)保障重調(diào)度問題的特點(diǎn)，采用了四種產(chǎn)生最優(yōu)解鄰域的方法，除了兩點(diǎn)交換Swap和插入Insert這兩種基本的鄰域結(jié)構(gòu)外，本文設(shè)計(jì)了另外兩種復(fù)合鄰域結(jié)構(gòu)：鄰域結(jié)構(gòu)中的每個(gè)復(fù)合動(dòng)作均由毀壞動(dòng)作和重建動(dòng)作(Ruin amp; Recreate，Ramp;R)兩個(gè)動(dòng)作構(gòu)成，毀壞動(dòng)作代表將從序列中移除部分元素，重建動(dòng)作表示對這些元素進(jìn)行打亂重排后，再將它們重新插入返回序列中。兩種復(fù)合鄰域結(jié)構(gòu)的區(qū)別在于進(jìn)行毀壞重建的范圍，即進(jìn)行毀壞重建的元素?cái)?shù)量，這決定了序列變化的強(qiáng)度。

1) 兩點(diǎn)交換Swap。隨機(jī)產(chǎn)生兩個(gè)交換位置，并交換兩個(gè)位置上的元素。

2) 插入Insert。隨機(jī)產(chǎn)生兩個(gè)元素位置，將位置序號(hào)大的元素p插入位置序號(hào)小的元素q之前，元素q及其之后的元素按順序向后順延。

3) 單架艦載機(jī)內(nèi)工序的毀壞重建Ramp;R1。即從單架艦載機(jī)序列中隨機(jī)產(chǎn)生m個(gè)(mgt;2，是整數(shù))元素位置，在考慮工序邏輯關(guān)系的前提下，打亂重排這些元素的順序。

4) 整個(gè)重調(diào)度工序的毀壞重建Ramp;R2?？紤]工序邏輯的條件下，針對重調(diào)度的個(gè)體X=[S11S12…S1|J1|S21…Sij…Sn|Jn|]隨機(jī)產(chǎn)生n(ngt;m)個(gè)元素進(jìn)行打亂重排。

前兩種鄰域結(jié)構(gòu)能對局部區(qū)域進(jìn)行細(xì)致搜索，有利于算法的探索能力。Ramp;R2較之Ramp;R1打亂重排的工序更多，因此Ramp;R2會(huì)對當(dāng)前解造成更大的破壞，一定程度上增強(qiáng)了算法的開發(fā)能力，利于跳出局部最優(yōu)。

2.3 算法框架

基于上述4種鄰域結(jié)構(gòu)，變鄰域搜索算法具體操作步驟如下：

步驟1 確定四種鄰域結(jié)構(gòu)Nk(k=1,2,3,4)，進(jìn)行初始化操作，輸入評價(jià)次數(shù)Q和初始解X，令i=0，最優(yōu)個(gè)體best_X=X。

步驟2 如果滿足循環(huán)終止條件(igt;Q)，輸出最優(yōu)個(gè)體best_X；否則，令k=1。

步驟3 按鄰域結(jié)構(gòu)Nk隨機(jī)產(chǎn)生一個(gè)新解X′，比較其與初始解X的適應(yīng)度值。

步驟4 若f(X′)lt;f(X)，則輸出k，令best_X=X′，適應(yīng)度值小的解代替初始解，并繼續(xù)在鄰域結(jié)構(gòu)Nk內(nèi)搜索；否則，k=k+1。

步驟5 若kgt;4，則i=i+1，返回步驟2；否則返回步驟3，進(jìn)入下一個(gè)鄰域結(jié)構(gòu)搜索。

3 仿真結(jié)果與分析

3.1 算例描述

以庫茲涅佐夫號(hào)航母為實(shí)例分析對象，假定某出動(dòng)任務(wù)需要對8架艦載機(jī)進(jìn)行出動(dòng)前的機(jī)務(wù)勤務(wù)保障作業(yè)。設(shè)備對艦載機(jī)的保障覆蓋情況見表1。

表1 設(shè)備對艦載機(jī)保障覆蓋關(guān)系

單機(jī)的保障工序流程圖如圖2所示。圖2中：各編號(hào)標(biāo)注為所需保障人員專業(yè)類別和設(shè)備類型，且需求量均為1，工序3—5—7—12之間虛線連接表示存在站位空間約束。

圖2 單機(jī)保障工序流程

3.2 初始調(diào)度

令算法評價(jià)次數(shù)Q=100，m取[4,8]中的隨機(jī)整數(shù)，n取[9,15]中的隨機(jī)整數(shù)，在2.30 GHz，4.00 GB內(nèi)存的SONY筆記本上仿真8次所得結(jié)果如表2所示。

表2 初始調(diào)度仿真結(jié)果 min

圖3 初始調(diào)度人員分配甘特圖

3.3 重調(diào)度預(yù)判

本算例隨機(jī)挑選t=20 min時(shí)，第四架艦載機(jī)的第18道工序發(fā)生故障，其在初始調(diào)度中工期為8 min，執(zhí)行時(shí)間段為17～25 min，現(xiàn)令其工期延長為18 min。采用相同的參數(shù)進(jìn)行重調(diào)度預(yù)判，得到不完全重調(diào)度保障時(shí)間為76 min，人員分配甘特圖如圖4所示，仿真耗時(shí)不超過1 s?？梢钥闯鰧Ρ瘸跏颊{(diào)度，每個(gè)保障人員分配的工序與初始調(diào)度相同，但工序開始時(shí)間因?yàn)楣收瞎ば虻脑虬l(fā)生了順延。由于不完全重調(diào)度的時(shí)間大于任務(wù)要求保障完成時(shí)間，因此需要進(jìn)行完全重調(diào)度。

3.4 完全重調(diào)度

針對初始調(diào)度在t=20 min的時(shí)刻進(jìn)行完全重調(diào)度，重調(diào)度時(shí)刻正在工作的各設(shè)備、人員需完成當(dāng)前工序才能參與重調(diào)度，未調(diào)度工序則需要在新的初始條件下重新進(jìn)行分配。采用相同的參數(shù)進(jìn)行仿真，所得最優(yōu)保障完成時(shí)間為69 min，滿足任務(wù)要求保障完成時(shí)間。每次仿真耗時(shí)不超過8 s。對應(yīng)人員分配甘特圖如圖5所示。

圖4 重調(diào)度預(yù)判人員分配甘特圖

圖5 完全重調(diào)度人員分配甘特圖

在故障工序時(shí)間延長10 min的條件下，現(xiàn)以表3直觀地對各調(diào)度狀態(tài)所需的保障時(shí)間進(jìn)行對比。

表3 各調(diào)度狀態(tài)下保障時(shí)間 min

其中右移調(diào)度表示故障發(fā)生后，所有未調(diào)度工序的開始時(shí)間整體右移故障延遲時(shí)間，在本案例中即為10 min，所以右移調(diào)度的調(diào)度時(shí)間為79 min。表3表明完全重調(diào)度效果突出，可以大大縮減工序故障導(dǎo)致的時(shí)間推延。

同時(shí)，仿真過程中還發(fā)現(xiàn)重調(diào)度預(yù)判的程序運(yùn)行時(shí)間要明顯短于完全重調(diào)度的程序運(yùn)行時(shí)間，即若預(yù)判所得不完全重調(diào)度保障完工時(shí)間在任務(wù)要求保障完工時(shí)間之內(nèi)，即可直接進(jìn)行不完全重調(diào)度，可進(jìn)一步縮短了重調(diào)度的時(shí)間，同時(shí)避免了實(shí)際重調(diào)度過程中人員和設(shè)備又被重新分配工序?qū)е碌幕靵y。

從圖3、圖5中可以清楚地看出各保障人員在各個(gè)時(shí)刻分配到的艦載機(jī)工序，各艦載機(jī)工序之間的任務(wù)優(yōu)先級(jí)也得到了滿足，同時(shí)滿足任務(wù)要求的保障時(shí)間。因此，利用變鄰域算法得到的調(diào)度甘特圖可以方便地指導(dǎo)艦載機(jī)艦面保障調(diào)度。

4 結(jié)論

本文研究了基于工序故障所引起的艦載機(jī)艦面保障重調(diào)度問題，在考慮資源約束和工序邏輯約束的條件下，建立了基于重調(diào)度預(yù)判機(jī)制的艦面保障重調(diào)度模型，并設(shè)計(jì)了針對重調(diào)度模型的變鄰域算法。仿真結(jié)果表明，重調(diào)度預(yù)判機(jī)制可以進(jìn)一步節(jié)省重調(diào)度保障時(shí)間，避免實(shí)際調(diào)度過程中的工序分配混亂，而變鄰域算法也具有較好的探索和尋優(yōu)性能。該模型和算法能夠在任務(wù)要求保障完工時(shí)間內(nèi)，高效解決由于保障工序故障而導(dǎo)致的艦載機(jī)艦面保障重調(diào)度問題。

[1] MICHINI B,HOW J P.A human-interactive course of action planner for aircraft carrier deck operations[J].AIAA,2011:1-11.

[2] RYAN J,CUMMINGS M,ROY N,et al.Designing an interactive local and global decision support system for aircraft carrier deck scheduling[M]//Infotech@ Aerospace 2011.2011:1516.

[3] 馮強(qiáng),曾聲奎,康銳.基于MAS的艦載機(jī)動(dòng)態(tài)調(diào)度模型[J].航空學(xué)報(bào),2009,30(11):2119-2125.

[4] 馮強(qiáng),曾聲奎,康銳.基于多主體的艦載機(jī)綜合保障過程建模方法[J].系統(tǒng)工程與電子技術(shù),2010,32(1):211-216.

[5] 馮強(qiáng),曾聲奎,康銳.不確定條件下艦載機(jī)動(dòng)態(tài)調(diào)度仿真與優(yōu)化方法[J].系統(tǒng)仿真學(xué)報(bào),2011,23(7):1497-1501.

[6] 岳奎志,孫聰,羅明強(qiáng),等.艦載機(jī)動(dòng)態(tài)調(diào)運(yùn)系統(tǒng)的運(yùn)行模型[J].北京航空航天大學(xué)學(xué)報(bào),2013,39(8):1062-1068.

[7] QI C,WANG D.Dynamic aircraft carrier flight deck task planning based on HTN[J].Ifac Papersonline,2016,49(12):1608-1613.

[8] 魏昌全,陳春良,王保乳.基于任務(wù)的連續(xù)出動(dòng)艦載機(jī)航空保障重調(diào)度研究[J].指揮控制與仿真,2012,34(3):23-26.

[9] MLADENOVI N,HANSEN P.Variable neighborhood search[J].European Journal of Operational Research,2008,191(3):593-595.

[10] DEBELS D,VANHOUCKE M.A decomposition-based genetic algorithm for the resource constrained project scheduling problem[J].Operations Research,2007,55(3):457-469.

[11] 蘇析超,韓維,蕭衛(wèi),等.基于Memetic算法的艦載機(jī)艦面一站式保障調(diào)度[J].系統(tǒng)工程與電子技術(shù),2016,38(10):2303-2309.

(責(zé)任編輯唐定國)

ReschedulingStudyofCarrierAirplaneSupportonDeckUndertheBreakdownDisturbance

JIANG Tingting， HAN Wei， SU Xichao

(Department of Airborne Vehicle Engineering, Naval Aeronautical and Astronautical University, Yantai 264001, China)

In order to solve the rescheduling problem due to equipment breakdown during the carrier airplane support on deck, the topological constraints and resource constraints including crew and equipment are taken into account, and the prognosis for the rescheduling is proposed. Based on this, the rescheduling model of flight deck operations is established, and the Variable Neighborhood Search (VNS) algorithm is used. The simulation results show that the prognosis for the rescheduling can save the great deal of time and the VNS algorithm performs well to satisfy the mission requirements. The rescheduling model and VNS algorithm can effectively solve the rescheduling problem caused by equipment breakdown during the carrier plane support on deck within the required time.

carrier airplane; support on deck; rescheduling optimization; variable neighborhood search algorithm

2017-07-15；

2017-08-10

國家自然科學(xué)基金項(xiàng)目(51375490)

蔣婷婷(1995—)，女，碩士研究生，主要從事艦載機(jī)航空保障工程研究。

韓維(1970—)，男，博士。教授，主要從事航空保障工程和飛行動(dòng)力學(xué)研究。

后勤保障與裝備管理

10.11809/scbgxb2017.11.021

本文引用格式：蔣婷婷，韓維，蘇析超.面向故障擾動(dòng)的艦面保障重調(diào)度仿真研究[J].兵器裝備工程學(xué)報(bào)，2017(11):93-98.

formatJIANG Tingting，HAN Wei，SU Xichao.Rescheduling Study of Carrier Airplane Support on Deck Under the Breakdown Disturbance[J].Journal of Ordnance Equipment Engineering,2017(11):93-98.

V271.4+92

A

2096-2304(2017)11-0093-06