不確定性工時下甲板作業的前攝性魯棒調度

萬兵，蘇析超，郭放，韓維，梁勇

海軍航空大學，煙臺 264001

航母是海上“移動基地”，其作戰效能的發揮直接由搭載艦載機的出動能力來決定[1]。艦載機在出動前都要進行以充添加掛為標志的使用保障工作，即加油、注水、掛彈、出動前檢查等時序要求工序，但由于受到甲板空間、機位、保障資源數量等的限制，在對艦載機機群進行保障時，會出現競爭使用資源的情況，影響到各單機保障工作，以至于增加了單機的保障準備時間，進而影響到機群作業進度，因此甲板作業的科學調度、統籌規劃需求迫切。此外，工時不確定性導致實際作業與調度計劃出現偏差，降低方案的可執行率，影響艦載機出動效能。綜上，開展不確定工時條件下甲板作業魯棒調度優化研究，對應對不確定性工時擾動、競爭性保障資源沖突，確保各階段作業協調有序，并對提升艦載機出動能力與航母作戰保障水平意義重大。

近年來，圍繞甲板作業調度學者主要從出動回收全流程和分階段優化研究，美國麻省理工大學人工智能研究所Ryan等[2-3]開發了艦母甲板作業規劃決策支持系統，建立艦載機全流程作業混合整數規劃模型，引入“人在回路”的決策方法，并用優化器Gurobi/Cplex進行求解，比較了自動算法與人工經驗的決策效果。Michini和How[4]提出了基于專家經驗的逆向強化學習機制，完善了智能調度策略，但對不確定環境下的決策問題效果不佳。Zheng等[5]針對全流程連續作業提出了基于學徒學習的智能調度算法，算法較好地跟蹤了專家經驗，但作業過程模擬較簡單且所選定特征量難以反映真實場景，其智能決策結果僅提供頂層的任務規劃，相比于基于AnyLogic[6]全局信息、動態交互的全流程模擬決策，其任務規劃效果無法評估。文獻[7-10]則從調運、甲板作業、出動及回收等方面進行基于啟發式算法求解。Qi和Wang[11]提出層次任務網絡規劃架構采用回溯算法，解決了艦面保障任務耦合問題，其分層規劃思想貼近指揮員-飛行計劃-調度員-調度方案-執行的垂直體系，是調度分解的一種思路，但回溯法僅為現行約束規劃的一種策略，仍有較大改進空間。綜合現有研究及甲板作業特點，分階段研究集中對起降作業中調運、保障等具體作業調度的優化生成，而全流程研究對細節忽略較多，僅適合做作業任務規劃，可作為時間窗約束嵌入各階段作業調度計劃。研究分階段中時長占比最大的甲板作業保障，相比文獻[9]給出的柔性車間調度模型，對于人力與設備分配及時序編排問題，資源受限項目調度模型(Resource Constrained Project Scheduling Problem, RCPSP)更接近其本質。故對多機甲板作業保障，實則完成具有工時不確定和空間約束的多項目資源受限項目調度優化工作。

針對該階段調度研究，Cui等[12]綜合考慮了多機保障流程約束和保障單元約束，建立了多機一體化機務保障調度模型；筆者團隊[13]引入“油電氣液”等勤務保障的協同作用和約束限制，建立了機務勤務一站式保障調度模型。劉欽輝等[14]考慮了甲板站位空間因素對艦載機作業的影響，設計了融合串行調度和并行調度的混合調度算法生成多站式保障調度方案。對上述多站式、集中式和一站式保障，甲板作業集中式保障能力強、利于大規模機群分波出動，但資源調度復雜度高，故重點研究該模式下的調度優化。

與現有的經典多項目RCPSP問題相比，有以下幾點不同：① 資源覆蓋所帶來的空間約束問題，比如甲板上有多個加油站，但對某一加油站則僅能覆蓋保障其附近2個停機位，故即便在加油站資源充裕時上述2機位由于空間約束無法同時加油作業；② 資源使用的容量約束，對同一類資源除數量限制外，同時使用的容量也有要求，比如充氧氮站/車同時工作的站數不得超過某閾值；③ 機隊保障作業并非單機項目調度的并行疊加擴充，在其合成的多項目調度中，不同項目的相同工序(如加油等)存在工序耦合，除前兩個因素外，指揮員或調度人員的偏好會導致并行項目流圖間存在耦合時序關系；④ 不確定工時顯著服從一定的概率分布，容易采用Monte Carlo模擬其隨機規律。

目前，艦載機不確定性作業調度領域文獻較少，Yuan等[15]提出預-反應式調度策略，突出采用重調度策略來適應不確定性；Su等[16]基于雙種群差分進化算法采用工時三點估計法進行魯棒動態調度研究，通過設定最大適應不確定性的魯棒指標搜索最優基線調度；李亞飛等[17]提出基于多智能體強化學習DQN(Deep Q Netwrok)的艦載機保障作業實時調度方法，立足部分可觀測的彌補決策過程(Markov Decision Process，MDP)過程開展全流程動態環境下的在線學習與離線調配。針對不確定性的Multi-RCPSP問題，可采用隨機調度、模糊調度、多智能體調度、重調度或基于啟發式規則的在線調度方法。而調度更突出計劃性與可執行性，目前研究較多的是魯棒調度技術[18-19]，魯棒性指標有完成時間裕度、最壞情況最小及按時完成率最大等，主要方法有基于關鍵鏈的時間緩沖法[20]、兩階段Benders-Cuts分解[21]或多階段列生成算法[22]，前者是基于調度生成機制的智能優化算法，處理大規模問題占優；后者采用主-子問題對偶分解的優化器精確求解，應對中小規模問題效率極高。但當前不確定調度領域缺乏前攝計劃性調度，而這可超前指導甲板作業執行。

綜上分析，以艦載機甲板集中式保障模式為背景，重點開展具有隨機分布的不確定工時的魯棒調度研究，提出機隊按時完成概率，最大完工期望和方差等指標構建綜合魯棒性指標，依托前攝性調度基于改進Memetic[13]元啟發式算法(Improve Memetic, I-Memetic)生成滿足魯棒性能的基準調度方案，提升機隊在甲板作業周期內應對工時不確定的抗擾動能力，確保機隊出動按節拍連續可靠。

1 問題描述

艦載機甲板集中式保障(Aircraft Carrier Deck Centralized Operation, ACDCO)是指艦載機機群出庫轉運或著艦回收后，根據甲板布列計劃，調運至指定保障停機位，并在這一陣位完成直接出動準備或再次出動準備所涉及的機務勤務保障作業，甲板保障全程只需牽引調運1次。而前攝式魯棒調度[20](Proactive Robust Scheduling, PRS)是指在實際保障開展前，根據歷史作業數據信息對隨機因素進行預測，預先采取措施，以生成抗干擾能力較強的基準調度方案。因此，艦載機甲板集中式保障前攝魯棒性調度(ACDCO-PRS)問題可描述為：在滿足工序保障流程約束和資源約束條件下，通過預先構建基準調度計劃，合理地規劃作業時序和分配工序保障所需的人員設備等資源，使得在實際工時不確定擾動下，仍能保證機群保障作業完工的高效性和魯棒性。

根據甲板保障作業約束條件屬性，可將其劃分為作業流程優先序約束和資源約束兩大類，其中資源約束又可細分為人員、設備等可更新資源約束站位空間資源約束和供給資源約束。

1) 作業流程約束。艦載機在入位系留后，將進行裝備檢查、加油、充氣、軍械等一系列機務勤務保障作業，若將單機的保障活動抽象為1個項目，那么波次出動的機隊保障作業流程可采用增廣拓展AON(Activity on Node Network)圖進行描述，可參考文獻[23]。然而不同于傳統多項目調度，由于固定資源站共用所帶來的空間約束致使不同項目間相同工序出現交叉耦合，需添加額外優先序，使得模型求解更為復雜。

2) 人員、設備資源約束。保障人員按專業分為特設、軍械、機械、航電等類型，而保障設備主要包括為艦載機提供油、電、氣、液等勤務保障的固定資源站。圖1為俄羅斯庫茲涅佐夫航母的人員設備資源覆蓋與轉移示意圖。資源配置競爭沖突明顯，多機依序分配不同設備站資源。約束有以下特點：① 同一時刻工序占用資源總量限制；② 任務結束后釋放資源并轉移至其它工序；③ 固定設備覆蓋因素帶來資源轉移范圍受限，即固定資源僅為輻射區域飛機用；④ 人員約束可靈活設置成單機組保障和跨區域統籌，從提高效率角度可采用全域分配模式。

圖1 某航母甲板資源保障示意圖

甲板作業中，由于人員熟練度、資源轉移、設備安裝、飛機狀態、甲板突發狀況及備彈數、加油量等不同客觀因素影響，工序工時具有隨機性，假定可從歷史作業信息中通過假設檢驗方式獲得該不確定性相應概率分布函數，那么采用傳統隨機調度可以解決調度方案生成，其做法是針對1組隨機抽樣的工時進行多調度方案設計，通過多備份方案與重調度策略匹配不確定性。然而從甲板作業安全有序角度應減少項目執行中的重調度，因此提出基于魯棒性指標的前攝性調度，可較好地平衡計劃執行性與項目完成率，以滿足機隊出動回收作業全流程有序銜接、連續循環。

2 ACDCO-PRS模型及求解構架

模型建立前，作如下假設：① 作業過程不可中斷，全程無人員和設備變更；② 同一人員或設備某時刻只能保障1個工序；③ 人員設備等轉移時間遠小于工序保障用時，可在不確定性工時中給予考慮，在本模型中忽略；④ 不考慮重大故障和任務變更等其它干擾；⑤ 不確定工時的分布規律已知；⑥ 人員保障范圍為全域作業；⑦ 飛機進行原位機務勤務保障，無需中途調運。

2.1 模型參數及決策變量

主要參數及決策變量定義如表1和表2所示。

表1 模型參數及符號定義

表2 決策變量定義

2.2 數學模型

(1)

式中：F為目標優化函數值；ω為第2個目標VCmax的加權值；Pr為完工滿足(·)內容的概率。

約束條件設置為

(2)

(3)

?i,e∈I,?j∈Ji?g∈Je

(4)

(5)

(6)

?i∈I,?j∈Ji,?k∈Ks, ?t>0

(7)

(8)

(9)

(10)

(11)

式(2)表示第i架艦載機入場系留完畢后才能開始保障，j=1代表開始的虛工序；式(3)表示各艦載機工序的緊前關系約束；式(4)表示占用相同資源的工序需按優先級依次開展，其中BM為足夠大實數，確保不等式恒成立；式(5)和式(6)分別代表保障人員和設備的數量約束，即同一時刻所有處于執行狀態的工序對某類專業人員或某類設備需求量需小于其數量上限；式(7)表示空間資源約束，即占用同一艦載機站位空間的不同工序不得同時作業；式(8)代表供給性資源約束，即任意時刻對某供給性資源的需求不超過其供給能力限制；式(9)為設備及人員的保障范圍約束，即只對在保障設備及保障人員的保障范圍之內的艦載機進行保障；式(10)和式(11)分別為工序對人員和設備需求量的分配量的匹配約束。

2.3 模型求解框架

根據ACDCO-PRS模型的決策變量定義，需要優化的內容包括保障時序方案和人員、設備分配方案。對此，設計ACDCO-PRS魯棒性調度優化方法的求解框架如圖2所示。

圖2 ACDCO-PRS求解總體架構

求解過程包含3個主要環節：一是通過三階段魯棒調度生成機制得到魯棒性基準調度方案，其中依次進行基于串行調度的基準時序方案、魯棒性設備調整和魯棒性人員分配3個階段，通過所設計的設備調整魯棒性和人員分配魯棒性指標，使得改進后方案的魯棒性相對基準時序方案的魯棒性有局部提升；二是提出預約束調度策略，其作用是針對給定的基準調度方案，在不確定工時干擾下按照既定的調度規則生成的實際作業執行進程，從而通過Monte-Carlo仿真映射至式(1)的魯棒性目標；三是針對魯棒性目標，設計了I-Memetic算法對基準時序方案進行優化搜索，最終獲得優化的魯棒調度方案。

3 前攝性魯棒調度生成機制

艦載機甲板集中式保障因涉及多架艦載機、多種資源在不確定工時下的有效協調，是1個多約束、大規模的NP-hard優化問題，與基于活動列表的經典隨機調度不同，實際作業應基于基準調度進行。對此應生成前攝性魯棒調度，包括生成初步作業時序計劃及人員設備分配方案的基準調度方法，解決工時不確定條件下的基準調度執行的預約束調度策略。從而實現對給定基準調度，在不確定工時擾動下按既定調度規則生成的實際作業進程，并由2.3節完成其魯棒指標評價。

3.1 基準調度方案生成

針對艦載機甲板集中式保障基準調度方案所包含的時序方案、保障人員分配方案和保障設備分配方案等3個核心要素，提出1種三階段魯棒性基準調度方案生成機制：首先在第一階段，基于串行調度生成機制(Serial Schedule Generation Scheme, SSGS)產生基準時序方案，在給定時序方案下，由于固定資源站保障范圍的約束，設備分配不具備隨意變更特性，如某加油站的保障對象由艦載機A更換至艦載機B后可能導致前者無覆蓋加油站而延遲等待，因此在本階段基準時序方案還需匹配設備預先分配方案；相反地，人員分配具有互為替換性，可在后續階段根據時序方案進行匹配。其次，考慮人員和設備的魯棒性分配，在給定時序方案的前提下，資源分配方案可有多種選擇，所形成的資源流網絡也千差萬別，文獻[24]研究表明，資源流網絡所增加的額外前后序關聯數越少，活動之間的時差越大，則項目調度的魯棒性越強。基于這一原則，階段二和階段三分別提出魯棒性設備分配調整機制和人員分配機制，從而形成完整的基準調度方案。

3.1.1 基于串行調度的時序方案

取各工序期望工時Edij為輸入，基于項目工序優先序，采用文獻[16]所提出面向甲板保障約束的串行調度生成機制得到保障的時序方案{[Sij,Eij]}(i∈I,j∈Ji)，其中工序所需設備的選擇采用基于覆蓋范圍內剩余工序作業時間最少優先規則(Minimum Total Processing Time Remaining in Covering Area, MTRCA)，即每個決策時刻選擇空閑設備中覆蓋范圍內的艦載機待保障工序時間和最小的設備，從而得出設備的預先分配方案。通過MTRCA分配，一方面緩解覆蓋較多艦載機工序的設備的使用沖突，使工作負載均衡；另一方面避免設備使用過度集中造成保障總時間的延遲。

基于時序方案生成機制的本質是左向對齊調度，使得工序的時序計劃盡量靠時間軸的左側安排，即盡早安排工序的開始時間。為進一步縮短總的工期，往往結合右向對齊調度一同使用，雙向迭代算法即為一類代表。

圖3 左右對齊調度編排示意圖

3.1.2 設備分配調整的魯棒指標

上節生成的基準方案為僅考慮優化時序的初始配置，還需作進一步調整以應對不確定工時擾動，增強調度魯棒性。

定義1具有資源轉移關系工序對(Oij,Oeg)的空閑時差(Pairwise Flaoat,PF)

(12)

式中，Oij∈Peg表示工序對(Oij,Oeg)間無流程邏輯和資源流向的先后約束關系；否則，后續工序必然受前序工序影響，此時空間時差雖無緩沖意義，但并未引入額外資源流，因此具備更優的魯棒性，不妨令其取值加上極大值BM。

由于當前階段人員并未分配，設備分配未確定，資源流僅包括空間資源。考慮到活動空閑時差對魯棒性指標的保護效果并非隨著空閑時差的增加而線性遞增，故引入設備分配魯棒性指標。

定義2基于指數遞減的效用函數來描述設備分配魯棒性的替換指標RE:

(13)

以指導搜索在不破壞原有時序方案情況下的魯棒最優設備分配方案，其中Qk為第k(k∈Ke)類設備具有相同設備轉移關系的工序對集。

具體到設備的調整操作時，僅需確保每次調整后的局部魯棒性優于調整前，則設備分配的全局魯棒性必將持續優化。引入2類調整操作：①交換，即分屬不同設備的兩個工序互為交換設備分配，實施交換的前提是交換后仍滿足設備覆蓋范圍約束，且工序保障時序不會與其他工序干涉；②插入，即將工序由原所屬設備轉移分配至另一設備，實施平移的前提除了滿足設備覆蓋范圍約束外，工序保障時序不會與目標設備的所有工序存在干涉，如圖4所示。

圖4 魯棒性設備調整示意圖

3.1.3 人員分配的魯棒指標

結合工序時序和設備分配方案完成人員分配，人員分配的魯棒性指標與上節類似，借鑒空閑時差的概念，

定義3Oij與第k類可分配人員r之間的空閑時差

(14)

式中：LFTkr表示第k類保障人員r的最近保障完成時刻，對應最近完工的工序Oeg，該值相對于分配時刻Sij而言，并隨著分配的深入而遞增，Pij表示的Oij緊前工序集的構建在式(12)基礎上新增了保障設備分配所形成的資源流前后繼約束。

定義4利用指數型效用函數作為人員分配的魯棒性指標，

RPijkr=exp(-IFijkr)

(15)

進而針對不同專業類型需求選擇魯棒性指標最小的人員進行分配。

3.2 預約束調度策略

甲板作業中，以基準調度作為不確定工時調度策略的參照，若采用基于工序優先列表的調度策略需提前將基準計劃按照工序開始時間升序排列轉化為工序優先列表。基準調度計劃由串行調度機制生成，若直接采用基于資源調度策略CRB、接力賽或時刻表策略則會將原始計劃的積極進度特性破壞并轉變為非延遲進度特性，從而劣化了解的性能；而基于工序調度策略CAB受制于優先級列表，導致無約束限制，本可提前開始的活動必須延遲至活動列表優先的工序開始后。

綜合調度策略優劣，提出一種面向艦載機甲板作業隨機調度的預約束策略(Pre-Constraint policy,CPC)，該策略同樣以并行時間遞推調度為主線，確保滿足約束的工序盡早調度；而在調度開始前，將人員約束、設備約束、空間約束和供給約束預先轉換為工序之間的邏輯約束關系，從而保證了基準調度方案的積極進度特性不受并行調度的影響。具體預先約束轉換過程如下：

1) 將基準調度方案中各人員、設備的保障資源流轉換為工序之間的完成—開始型緊前約束，如某保障人員所分配的保障工序Oij優先于Oeg，則在初始流程約束中增加OijOeg前后續約束，并更新多機保障工序流程網絡D=(V,AN,AR)。

2) 將基準調度方案中各工序占用相同空間的前后順序，按照人員、設備保障工序流的轉換方式，同樣轉變為完成—開始型緊前約束。

4 魯棒調度的I-Memetic算法

基于上述魯棒調度方法，在給定基準時序方案下，可相應得出魯棒性設備和人員的分配方案，進而通過預約束隨機調度策略結合Monte Carlo仿真方法求解基準方案的魯棒性指標。然而，基準時序方案的優劣將直接影響到保障作業魯棒性的大小，常規基于啟發式規則制定的基準時序方案并不具備面向魯棒性指標的優化性能。對此，本文設計一種結合雙種群遺傳優化和自適應變鄰域局部優化的I-Memetic算法對基準時序方案進行優化。

4.1 算法總體流程

I-Memetic算法流程如圖5所示，步驟如下：

圖5 I-Memetic算法流程圖

步驟2對當前種群PopL進行遺傳進化，采用右向對齊生成時序方案，根據閾值評估機制進行Monte Carlo魯棒性指標解碼，每個個體的進化操作按如下步驟執行：

1) 取左種群PopL的第i個個體作為父代個體，再從除父代個體之外的PopL剩余種群中隨機選擇2個互不相同的個體，根據二元錦標賽策略，選擇其中適應度值最優的作為母代個體。

2) 對父代個體和母代個體執行基于資源利用率的兩點交叉和變異操作，生成2個子代個體。

3) 對2個子代個體分別進行基于串行調度機制的右向對齊調度，得到時序方案和預先設備分配方案。

5) 在確保預先設備分配不變的條件下，通過左向對齊將原時序方案轉化為標準時序方案，進而采用魯棒性設備分配調整機制和人員分配機制形成完整的基準調度方案。

6) 基于預約束調度策略，在Monte Carlo隨機采樣的作業場景下，對基準調度方案進行調度并統計式(1)中的魯棒性指標。

7) 對比2個子代個體的適應度值，擇優保留，以右向對齊形成的初始調度時序方案的開始時間修正原父代個體編碼，得到所有子代新個體組成的右種群PopR。

步驟3判斷當前累積評價次數是否達到最大評價次數，若是，則迭代終止，并輸出最優基準調度方案和魯棒性指標；否則，轉入步驟4進行右種群的遺傳進化。

步驟4對右種群PopR進行遺傳進化，具體每個個體的進化操作步驟與左種群進化相同，其中的操作差別在于以下3點：① 時序方案由基于串行調度機制的左向對齊調度生成；② 由于左向對齊生成的時序方案即為標準時序方案，因此相對5) 中僅需進行魯棒性人員分配和設備調整；③ 最終保留的精英子代的編碼采用左向對齊形成時序方案的結束時間來修正，得到所有子代新個體組成的左種群PopL。

步驟5對當前歷史最優解進行自適應變鄰域搜索，若有改進，則修正編碼并替換左種群PopL中的最劣解，并將新的左種群返回步驟2。

4.2 編碼與評價

為確保基準方案下的保障作業盡早開始，標準的時序方案由左向對齊操作生成，針對右向對齊所生成時序方案的魯棒性評價，需首先在確保設備分配不變的條件下，通過左向對齊將其轉化為標準時序方案，進而按照上述流程開展評價。

4.3 遺傳操作

作業調度瓶頸因素往往存在于資源利用率較高的時段，而利用率低時段的工序仍有充分利用資源以提升作業效率的潛質，故將資源利用率作為一項啟發性因子，以引導遺傳進化中的交叉變異操作。

定義5基準保障方案S在t時刻的加權綜合資源利用率為

(16)

4.4 自適應變鄰域局部搜索

除遺傳操作外，還引入局部搜索機制(鄰域變換)，引導優有個體在適應度函數的極值處作深度探索。該搜索機制，一是利于種群個體跳出局部最優解，二是根據當前狀態調整鄰域結構加快搜索[24-25]。針對優先數編碼設計了5類不同規模的鄰域結構：

1) 交換鄰域：隨機交換不存在前后續結束工序的編碼所對應基因位的優先數。

3) 項目內活動災變鄰域：隨機選取機群中艦載機i，再隨機取出其中Na(Na∈Z[4,9])個工序，對每個工序按照插入鄰域依次重新插入。

(17)

式中：width為衡量抽樣概率的延展參數，算法取值為width=1。

5) 項目重組鄰域：隨機選取機群中艦載機i，對其所屬所有工序按流程進行隨機插入，即重組其時序優先數。

根據鄰域規模來劃分，交換鄰域和插入鄰域屬于小規模鄰域結構，項目內活動災變鄰域和局部時間活動災變鄰域屬于中規模鄰域結構，項目重組鄰域輸入大規模鄰域結構。

(18)

(19)

式(19)為第g次局部搜索選中第i個鄰域結構進行操作后的概率更新公式，式(19)為未選中鄰域結構的概率更新公式，αreward、αpenalty分別為獎勵學習和懲罰學習速率，Nl為鄰域結構數，β(g)為第g次迭代所獲得的回報反饋，不妨取：

(20)

從而確保當鄰域結構在進化過程有改進效果時，其選擇概率會相應增加。

4.5 閾值評估機制

(21)

F(x1)

(22)

(23)

5 仿真實驗

5.1 場景設置

甲板作業保障仿真場景如圖1所示，機隊調度為多個單機作業的綜合，單機調度的項目流圖及作業工序參見文獻[23]中圖、表的資源覆蓋數據。各類保障工序在人員主觀因素、保障對象狀態、設施設備保障條件等客觀因素綜合作用下，保障時間所服從的分布規律不盡相同。在作業交互數據合理假定下通過AnyLogic仿真軟件模擬測試，作業工時的概率分布主要包括：截斷正態分布、均勻分布和二項分布。其中，工時服從二項分布的保障工序主要包括充氧和充氮，并非每次飛行前準備都需要實施，而是根據一定概率進行保障，其本質即為實驗次數為1的伯努利試驗，事件發生概率為p。

表3 保障工序時間隨機分布參數

5.2 確定性保障調度仿真及算法對比

經多次實驗比對，將設計的I-Memetic算法參數設置為：種群規模NP=30，標準變異概率Pm=0.1，局部搜索的循環鄰域操作次數下界，上界，學習自動機的獎勵學習速率和懲罰學習速率分別為αreward=0.8、αpenalty=0.8。標準GA算法中，采用二元錦標賽選擇、兩點交叉和隨機變異操作，其中變異概率取Pm=0.05，LA-VNS算法參數的設置與上述I-Memetic算法一致，其它算法的參數則參照所引用文獻的參數設置。算法取最大調度次數作為終止條件，在1個場景下進行1次完整的機群保障作業仿真，即為1次調度。

將上述8種算法在不同調度次數下分別進行30次獨立運行，得到的結果如表4所示，其中Q為調度次數。

表4 算法性能對比

對比表4的數據，可以看出：① 所提出的I-Memetic算法相對其它算法有了更進一步的提升，無論在各調度次數等級下，算法的最優解搜索能力和算法穩定性均優于其它所列算法；② 通過標準GA算法的仿真結果對比，說明本文I-Memetic算法可有效克服傳統標準GA算法的缺陷，避免限入局部最優解或導致提前收斂，從而可有效挖掘適應度函數空間，且驗證了所采用的雙種群迭代機制具有良好的可拓展性；③ 在LA-VNS算法的仿真結果對比，說明提出的基于學習自動機的變鄰域搜索算法不僅局部搜索能力良好，同時具有較強的全局搜索性能，優于標準GA、MDE、Memetic和SAHGA等算法。

5.3 魯棒調度策略與算法對比

在所設計的機群保障案例下，考慮工序保障時間隨機不確定下的前攝性魯棒調度優化仿真，主要包括2部分，一是基于本文設計的I-Memetic算法，對比CPC、接力賽、時刻表、CRB和CAB等5類調度策略，在不同魯棒人員分配和設備調整執行模式和不同調度次數下的魯棒性指標；二是對比本文I-Memetic算法、DSaDEII算法與求解經典資源受限隨機項目調度問題的ABGA(Artifical Beecolony Genetic Algonthm)算法[29]、果蠅算法(Order-based Fruit fly Optimization Algorithm, OFOA)[30]用于求解ACDCO-PRS的魯棒性效果。

在人員、設備魯棒調度分配對比分析中，設置I-Memetic算法參數與5.2節相同，魯棒指標權重ω=0.1，優化過程抽樣場景NS=20，所有仿真結果均基于30次獨立運行得出。

首先，對不同調度策略、不同魯棒人員分配與設備調整執行模式和不同調度次數下的魯棒調度優化進行對比，得到仿真結果如表5所示。其中魯棒人員分配和魯棒設備調整可選擇執行(是)或不執行(否)，當不執行魯棒設備調整時，按照基于串行調度機制所生成的初始設備分配方案執行保障；當不執行魯棒人員分配時，則按照累積保障時間最少優先規則進行分配；由于CRB策略和CAB策略是面向任務列表，因此不涉及人員和設備分配方案。表中結果[abc]分別表示機群按時完工概率、完工時間期望和完工時間方差。

同時，基于CPC策略，魯棒人員分配和設備調整均執行，調度次數為Q=250 000下得到的最優基準方案，分別采用4類調度策略進行場景抽樣數為3 000次的蒙特卡洛仿真，所得保障完工時間分布的箱線圖如圖6所示，其中橫軸為表5中的CPC、接力賽(Roadrunner)、時刻表(Railway)及CAB等調度策略，縱軸為保障完工時間(min)。

表5 調度策略性能對比

又取最優基準方案中的時序方案，分別在不同魯棒人員分配和設備調整執行模式下進行場景抽樣數為3 000次的蒙特卡洛仿真，所得保障完工時間分布的箱線圖如圖7所示。其中的1、2、3、4編號的箱線圖分別代表魯棒人員分配和設備調整均有，隨機人員分配而有魯棒設備調整，有魯棒人員分配而無魯棒設備調整以及魯棒人員分配和設備調整均無等4類組合。

通過表5、圖6基于不同調度策略的魯棒性目標仿真結果，圖7對有無魯棒人員/設備分配情況下完工時間的對比實驗，可知：

圖6 不同調度策略下保障完工時間箱線圖

圖7 不同魯棒性分配組合下保障完工時間箱線圖

1) 在給定魯棒人員分配和設備調整模式下，從整體魯棒性指標看來，調度策略的排序為CPC>時刻表>接力賽>CAB>CRB。時刻表策略由于限制了開工時間，一定程度上減少了開工時間波動性，因此其完工時間的方差較小；接力賽策略對所有工序采用并行調度，破壞了基準調度方案中供給性資源保障計劃的積極進度特性，從而劣化了解的魯棒性能；同樣，基于并行調度機制的CRB策略對基準調度方案的積極進度特性的破壞則是全方面的，因此所得結果較差。

2) 魯棒人員分配和魯棒設備調整機制均對基準調度方案的魯棒性指標有提升作用，且前者的作用相對后者作用更為明顯。這主要是由于工序保障對人員的需求遠高于對設備的需求，且設備主要是一對一需求，即1架飛機對某類設備可能僅有1道工序有需求，一對多需求的以電站為主，因此可供魯棒性設備調整的對象并不多，而魯棒人員分配則面向所有工序集合，影響范圍更廣。

為驗證I-Memetic算法有效性，將其與求解資源受限隨機項目調度問題的代表性算法進行對比，包括ABGA和OFOA。不同最大調度次數下的最優解的魯棒性指標和平均魯棒性指標統計如表6所示。其中，DSaDEII算法除了算法框架與I-Memetic算法不同，其內涵均與I-Memetic算法相一致，包括魯棒人員分配和設備調整機制，CPC調度策略，基于蒙特卡洛仿真的閾值評估機制等。在調度策略上，ABGA采用CAB策略，OFOA采用CRB策略。

表6 魯棒調度優化算法對比

6 結論與展望

在對工時具有隨機不確定性假設下，針對機隊保障應最大可能在甲板作業周期內完成，提出前攝性魯棒調度和預約束策略，運用I-Memetic算法結合Monte Carlo仿真驗證了魯棒基準調度的可行性、算法的有效性。

圖8 保障人員分配甘特圖

2) Monte Carlo對魯棒優化的基準調度方案仿真表明，方案能較好地適應人員、設備工時擾動影響。

3) 提出的I-Memetic算法顯著優于已有智能優化算法，預約束策略好于接力賽、時刻表等魯棒調度策略。

由于對RCPSP的資源分類過細致，使模型復雜、約束耦合多、求解困難，下步可考慮采用調度分解方式開展同類資源歸并的分層規劃、甲板分區保障的并行調度研究，從而降低問題復雜度，由任務規劃算法重構RCPSP網絡流圖，采用Cplex約束規劃器求解。也可使用強化學習方法，結合專家知識開展包括但不限于工時不確定條件下動態調度。此外，對工時不確定性還可考慮凸多面體等處理辦法，引入其它可調節魯棒性指標開展基于優化器精確解法的調度研究。