面向故障擾動的艦面保障重調度仿真研究

蔣婷婷，韓 維，蘇析超

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

面向故障擾動的艦面保障重調度仿真研究

蔣婷婷，韓 維，蘇析超

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

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

艦載機；艦面保障；重調度優化；變鄰域算法

艦載機甲板保障調度是指在時間、空間、資源及工序邏輯等多重約束下對艦載機進行維護保障。由于實際保障調度過程中一直存在動態擾動，因此對該過程的優化對提升艦載機出動架次率有重要影響。

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

在對艦載機進行保障時，一旦發生設備故障，保障的組織實施便會發生相應改變，因而需要根據當前狀態進行重調度，即在初始調度方案執行基礎上，根據發生的故障對后續工序開始時間安排和資源分配進行重新調度。

1 艦面保障重調度問題建模

1.1 問題描述

故障擾動導致的保障重調度涉及到大量人員、設備的重新分配，造成整個保障的任務量和難度顯著增加。本文建立了重調度預判機制，重調度預判流程見圖1。

圖1 重調度預判流程

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

1.2 符號定義

定義模型參數如下：

I為艦載機i的集合；

Ji為艦載機i的工序集合；

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

Sij為工序Oij的保障開始時間；

EXi為艦載機i入場系留完畢時間；

Pij為工序Oij的前驅任務集合；

dij為工序Oij的工期；

Kp為保障人員專業種類集合；

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

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

Kr為保障設備種類集合；

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

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

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

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

變量Oij(t)當工序Oij在t時刻處于執行狀態則為1，否則為0；

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

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

1.3 數學模型

目標函數如下：

(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)代表目標函數為最小化完全重調度保障完工時間。其中

(13)

式(2)～式(12)表示約束條件。式(2)表示第i架艦載機入場系留完畢后才能開始保障，j=1代表開始的虛工序；式(3)～式(5)動態地表示艦載機各工序、人員、設備的狀態，且表示保障過程中已經開始的保障活動不允許中斷；式(6)表示各艦載機工序的緊前關系約束；式(7)～式(9)分別代表人員、設備和消耗性資源的數量約束，即任一時刻所有處于執行狀態的工序對它們的需求量小于其數量上限；式(10)為設備及人員的保障范圍約束，即只對在保障設備及保障人員的保障范圍之內的艦載機進行保障；式(11)～式(12)分別表示設備和人員需求匹配約束，即被分配數量應等于其需求量。

2 變鄰域算法

Mladenovic和Hansen[9]于1997年提出了變鄰域算法(Variable Neighborhood Search,VNS)，其基本思想是：構造多個鄰域結構，在一個鄰域結構內搜索局部最優解，當局部搜索陷入局部最優時，通過系統地改變鄰域結構尋找最優解。相對于傳統的固定鄰域搜索算法，基于多鄰域結構集的系統變化拓展搜索范圍，搜索能力更強，而且VNS算法無需調整參數，實現簡單，因而在組合優化領域得到了廣泛應用。

2.1 編碼和解碼

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

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

2.2 鄰域結構

設計VNS算法首要問題是設計最優解的鄰域。根據艦載機保障重調度問題的特點，采用了四種產生最優解鄰域的方法，除了兩點交換Swap和插入Insert這兩種基本的鄰域結構外，本文設計了另外兩種復合鄰域結構：鄰域結構中的每個復合動作均由毀壞動作和重建動作(Ruin amp; Recreate，Ramp;R)兩個動作構成，毀壞動作代表將從序列中移除部分元素，重建動作表示對這些元素進行打亂重排后，再將它們重新插入返回序列中。兩種復合鄰域結構的區別在于進行毀壞重建的范圍，即進行毀壞重建的元素數量，這決定了序列變化的強度。

1) 兩點交換Swap。隨機產生兩個交換位置，并交換兩個位置上的元素。

2) 插入Insert。隨機產生兩個元素位置，將位置序號大的元素p插入位置序號小的元素q之前，元素q及其之后的元素按順序向后順延。

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

4) 整個重調度工序的毀壞重建Ramp;R2。考慮工序邏輯的條件下，針對重調度的個體X=[S11S12…S1|J1|S21…Sij…Sn|Jn|]隨機產生n(ngt;m)個元素進行打亂重排。

前兩種鄰域結構能對局部區域進行細致搜索，有利于算法的探索能力。Ramp;R2較之Ramp;R1打亂重排的工序更多，因此Ramp;R2會對當前解造成更大的破壞，一定程度上增強了算法的開發能力，利于跳出局部最優。

2.3 算法框架

基于上述4種鄰域結構，變鄰域搜索算法具體操作步驟如下：

步驟1 確定四種鄰域結構Nk(k=1,2,3,4)，進行初始化操作，輸入評價次數Q和初始解X，令i=0，最優個體best_X=X。

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

步驟3 按鄰域結構Nk隨機產生一個新解X′，比較其與初始解X的適應度值。

步驟4 若f(X′)lt;f(X)，則輸出k，令best_X=X′，適應度值小的解代替初始解，并繼續在鄰域結構Nk內搜索；否則，k=k+1。

步驟5 若kgt;4，則i=i+1，返回步驟2；否則返回步驟3，進入下一個鄰域結構搜索。

3 仿真結果與分析

3.1 算例描述

以庫茲涅佐夫號航母為實例分析對象，假定某出動任務需要對8架艦載機進行出動前的機務勤務保障作業。設備對艦載機的保障覆蓋情況見表1。

表1 設備對艦載機保障覆蓋關系

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

圖2 單機保障工序流程

3.2 初始調度

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

表2 初始調度仿真結果 min

圖3 初始調度人員分配甘特圖

3.3 重調度預判

本算例隨機挑選t=20 min時，第四架艦載機的第18道工序發生故障，其在初始調度中工期為8 min，執行時間段為17～25 min，現令其工期延長為18 min。采用相同的參數進行重調度預判，得到不完全重調度保障時間為76 min，人員分配甘特圖如圖4所示，仿真耗時不超過1 s。可以看出對比初始調度，每個保障人員分配的工序與初始調度相同，但工序開始時間因為故障工序的原因發生了順延。由于不完全重調度的時間大于任務要求保障完成時間，因此需要進行完全重調度。

3.4 完全重調度

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

圖4 重調度預判人員分配甘特圖

圖5 完全重調度人員分配甘特圖

在故障工序時間延長10 min的條件下，現以表3直觀地對各調度狀態所需的保障時間進行對比。

表3 各調度狀態下保障時間 min

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

同時，仿真過程中還發現重調度預判的程序運行時間要明顯短于完全重調度的程序運行時間，即若預判所得不完全重調度保障完工時間在任務要求保障完工時間之內，即可直接進行不完全重調度，可進一步縮短了重調度的時間，同時避免了實際重調度過程中人員和設備又被重新分配工序導致的混亂。

從圖3、圖5中可以清楚地看出各保障人員在各個時刻分配到的艦載機工序，各艦載機工序之間的任務優先級也得到了滿足，同時滿足任務要求的保障時間。因此，利用變鄰域算法得到的調度甘特圖可以方便地指導艦載機艦面保障調度。

4 結論

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

[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] 馮強,曾聲奎,康銳.基于MAS的艦載機動態調度模型[J].航空學報,2009,30(11):2119-2125.

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

[5] 馮強,曾聲奎,康銳.不確定條件下艦載機動態調度仿真與優化方法[J].系統仿真學報,2011,23(7):1497-1501.

[6] 岳奎志,孫聰,羅明強,等.艦載機動態調運系統的運行模型[J].北京航空航天大學學報,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] 魏昌全,陳春良,王保乳.基于任務的連續出動艦載機航空保障重調度研究[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] 蘇析超,韓維,蕭衛,等.基于Memetic算法的艦載機艦面一站式保障調度[J].系統工程與電子技術,2016,38(10):2303-2309.

(責任編輯唐定國)

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

國家自然科學基金項目(51375490)

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

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

后勤保障與裝備管理

10.11809/scbgxb2017.11.021

本文引用格式：蔣婷婷，韓維，蘇析超.面向故障擾動的艦面保障重調度仿真研究[J].兵器裝備工程學報，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