考慮保障裝備可用度的艦載機作業(yè)調(diào)度優(yōu)化

曾 斌, 陳媛媛,*, 李厚樸

(1. 海軍工程大學管理工程與裝備經(jīng)濟系, 湖北 武漢 430033; 2. 海軍工程大學導航工程系, 湖北 武漢 430033)

0 引 言

艦載機出動架次率是衡量航母綜合作戰(zhàn)能力的關(guān)鍵指標之一,需要在盡可能短的時間內(nèi)調(diào)度最大批次艦載機的出動回收。由于航母飛行甲板狹窄,作業(yè)環(huán)境復雜,加重了艦載機起降所涉及的維修、調(diào)運、加掛等一系列保障工作的難度[1-2]。因此,艦載機甲板作業(yè)調(diào)度已成為當前航母作戰(zhàn)指揮的關(guān)鍵問題。

艦載機甲板作業(yè)調(diào)度,也稱保障調(diào)度,與常規(guī)柔性流水車間調(diào)度相比,難度主要體現(xiàn)在不確定性因素的影響方面。這種不確定性主要體現(xiàn)在3個方面:一是保障資源的不確定性[3-4],這些保障資源包括彈射器阻攔鎖、加油管充氣設備、彈藥裝載設備等,其故障發(fā)生率會影響保障資源的可用性;二是艦載機損傷情況會導致維修的不確定性[5-6];三是作戰(zhàn)任務變化或天氣惡劣造成的調(diào)度延期[7]。

為了解決以上不確定情況下的艦載機甲板作業(yè)調(diào)度問題,國內(nèi)外近年來開展了相關(guān)研究。解決方法可以分為兩大類,一類是引入了項目管理中的反應式調(diào)度技術(shù)[3,5,8],主要研究當動態(tài)環(huán)境引起原調(diào)度方案與執(zhí)行過程之間出現(xiàn)較大偏差時,對其進行局部甚至全局調(diào)整,以保證調(diào)度的順利實施。這種方式的優(yōu)勢是把計劃與控制方案集成起來,缺點是每次重調(diào)度都要花費一定的計劃時間,造成調(diào)度方案的中斷或延時。另一類是基于仿真的優(yōu)化方式。文獻[9]用遺傳算法(genetic algorithm, GA)計算調(diào)度方案時,用仿真程序來代替適應度函數(shù),評價調(diào)度方案的適應度目標值。文獻[10]基于描述艦載機甲板作業(yè)流程的排隊網(wǎng)絡,通過蒙特卡羅仿真生成調(diào)度策略,再利用差分進化算法實施優(yōu)化。這種方式的優(yōu)點是,在仿真模型中能夠模擬出常規(guī)數(shù)學方法難以給出的不確定參數(shù)或復雜場景,從而提高了調(diào)度方案解的優(yōu)化程度。缺點是啟發(fā)算法的每一次迭代過程都要調(diào)度仿真程序,生成初始調(diào)度方案花費時間較長。另外,文獻[11-14]設計了艦載機甲板作業(yè)的仿真平臺,盡管對仿真優(yōu)化具有借鑒意義,但嚴格說并不屬于基于仿真的優(yōu)化,而是把仿真平臺作為不確定環(huán)境下調(diào)度策略的性能評估工具。

從文獻來看,相關(guān)研究把保障裝備出現(xiàn)故障的不確定性與其他兩種不確定性同等對待,但實際工作中可以且必須通過維護維修工作(計劃維修、視情維修和事后維修)來減小保障裝備的故障率,從而提高艦載機的保障水平[15]。航空保障資源涉及裝備類型多且技術(shù)結(jié)構(gòu)復雜,特別是在艦載機分波次連續(xù)出動時工作強度大,持續(xù)時間長,為了減少故障率并提高保障裝備的可用度,各類維護維修的頻率也相應提高,并對艦載機出動造成了極大影響[16]。例如，彈射器的開口氣缸和儲氣罐、阻攔索、加油裝置和充氣裝置的關(guān)鍵零部件等都是計劃維修的重點設備。

計劃性維修的間隔根據(jù)相應裝備使用保養(yǎng)條例,一般都有一個上限時間或次數(shù),如果安排不合理,則會影響調(diào)度方案的執(zhí)行。除了定期計劃維修,還需要在航空保障過程中不斷檢測裝備的劣化程度來安排維修活動,即進行視情維修[17]。如果裝備出現(xiàn)嚴重故障,則需要投入更多的時間和人力物力進行事后維修。

為此，本文在考慮其他不確定影響因素的同時,著重增加了對保障裝備維護維修活動的調(diào)度。主要包括:① 通過在調(diào)度優(yōu)化模型中增加滿足系統(tǒng)可用度的計劃維修約束,能夠同時生成艦載機的甲板作業(yè)調(diào)度方案和保障裝備計劃性維護的時間安排;② 通過基于仿真的優(yōu)化方式,在啟發(fā)算法的適應度評價中增加對視情維修和事后維修的仿真,提高艦載機作業(yè)調(diào)度方案的魯棒性,保證保障裝備長期處于穩(wěn)定水平,減少故障帶來的不確定性影響,從而進一步減少甲板作業(yè)時間;③ 由于不確定條件下艦載機調(diào)度問題屬于非確定性多項式(non-deterministic polynominal, NP)難問題,所以求解算法一般以GA、粒子群優(yōu)化(partice swarm optimization, PSO)算法、模擬退火(simulated annealing, SA)算法等進化算法為主。為了提高改進后調(diào)度模型的求解算法速度,在運行啟發(fā)算法之前,增加一個仿真步驟,指揮員事先可以選擇不同的作戰(zhàn)想定,利用離散仿真工具(人在回路)[16]模擬甲板作業(yè)調(diào)度過程,生成一批初始的可行解即可行的調(diào)度方案,存儲到方案數(shù)據(jù)庫中,以此作為進化算法的初始解和基礎,從而提高進化算法的求解性能。從實驗結(jié)果上看，高質(zhì)量的初始種群確實可以很大程度的加速進化算法的收斂性。

1 調(diào)度模型

1.1 問題描述

設艦載機集合為i={1,2,…,I},艦載機i的保障工序集為p={1,2,…,Pi},不同類型艦載機保障工序不同,為了方便統(tǒng)一描述,可采取活動合并和虛擬站位方式[18]使其一致。工序p具有{u=1,2,…,Up}個可并行工作的保障單元或保障裝備,每一個保障裝備一次只能保障一架艦載機。艦載機允許在航母等待區(qū)等待。保障裝備處于維修狀態(tài)時不能進行保障活動。

圖1為包含保障裝備維護活動的航空作業(yè)甘特圖示例,其中M表示維修活動。從圖1中可見,對保障裝備的維護維修工作可能造成作業(yè)調(diào)度計劃的延遲或中斷,因此需要盡量安排處于空閑狀態(tài)的保障裝備進行維護。

圖1 包含計劃維修的甘特圖例子Fig.1 An example of Gantt chart including planned maintenance

每一道保障工序的持續(xù)時間為隨機變量,根據(jù)隨機規(guī)劃方法,每一次可能的保障工序稱之為一次場景,每一次場景發(fā)生概率用Pr(S)表示。通過這種方式,艦載機的每一道保障工序的持續(xù)時間不再是常數(shù),而是先生成多個不同場景,再根據(jù)場景發(fā)生概率及持續(xù)時間計算均值來得到工序時間[19]。

目標是通過產(chǎn)生兩套調(diào)度方案使得最大保障完成時間最小,一套為所有艦載機的保障順序,具體到某一架艦載機的某一道工序分配到該工序所屬某一保障裝備的某一時間段實施;另一套為每一個保障裝備的計劃維修的分配時段。由于數(shù)學模型中用到的符號較多,下面進行分類說明。

1.2 序號描述

p:保障工序的序號,p={1,2,…,P};

u:從事保障工序p的保障裝備序號,u={1,2,…,Up};

j,k:保障裝備u上的工序?qū)嵤╉樞?j,k={1,2,…,Ku};

l:保障裝備e中計劃維修活動的執(zhí)行順序,l={1,2,…,Lup};

s:場景序號,s={1,2,…,S}。

1.3 參數(shù)描述

Pr(s):場景s的發(fā)生概率;

μup:從事工序p的保障裝備u的修復率;

λup:從事工序p的保障裝備u的故障率;

Dup:對于從事工序p的保障裝備u,每次計劃維修所需要的持續(xù)時間;

α:艦載機保障系統(tǒng)可用度的最小要求;

q:甲板上能夠容納等待保障的艦載機數(shù)量;

M:一個相當大的正整數(shù)。

1.4 因變量描述

Bup:對于從事工序p的保障裝備u,計劃維修的間隔時間;

nup:對于從事工序p的保障裝備u,實施計劃維修的次數(shù);

Tup:從事工序p的保障裝備u上最后一次計劃維修的完成時間;

wi(t):如果艦載機i在t時刻等待保障,則wi(t)為1,否則為0;

Rp(t):t時刻從事工序p的保障裝備u的不可用性;

Rup(t):t時刻工序p的不可用性;

Rall(t):t時刻整個保障系統(tǒng)的不可用性;

b:布爾數(shù),0或1。

1.5 決策變量描述

1.6 數(shù)學模型描述

在存在計劃維修的情況下,t時刻實施工序p的裝備u的瞬時可用度可按文獻[15]修改后如下:

(1)

設工序為串行執(zhí)行,每一道工序中的多個保障裝備并行施工,如果執(zhí)行某工序的設備全部失效,則認為該工序失效。因此,工序p的不可用性計算如下:

(2)

整個保障系統(tǒng)的不可用性可計算如下:

(3)

艦載機保障的數(shù)學模型既可按基于項目調(diào)度的資源約束關(guān)系來建立[5,20],也可按基于車間調(diào)度的出動方式來建立[21-23],本質(zhì)上都屬于任務-資源分配問題。本文采用第2種方式來建立數(shù)學模型,稍加改動也可以按第1種方式建立數(shù)學模型。艦載機保障的目標函數(shù)如下:

(4)

該目標函數(shù)的目的是最小化艦載機保障時間,約束條件如下：

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

Tup≤lBup

(14)

1-Rall(t)≥α

(15)

艦載機作業(yè)優(yōu)化為NP難問題[24-25],特別是需要考慮保障裝備可用度后,問題求解更加困難。本文求解方法可分為3部分:① 通過艦載機保障作業(yè)流程仿真生成滿足約束條件的初始解,以便加快求解速度;② 把初始解作為調(diào)度模型啟發(fā)式求解算法的初始種群進行迭代優(yōu)化,解決保障裝備計劃維修與艦載機作業(yè)聯(lián)合優(yōu)化問題;③ 在啟發(fā)算法每次迭代的適應度評估(即目標函數(shù)評估)中引入離散事件仿真模型,模擬數(shù)學方法難以建模的視情維修和事后維修場景,提高優(yōu)化解的魯棒性。

2 生成初始解的仿真模型

仿真模型可用Anylogic、Extendsim或EntrpriseDynamic等流程仿真軟件開發(fā),本文利用ExtendSim軟件開發(fā)。ExtendSim中,可以利用自帶的隨機函數(shù)生成Activity模塊的處理時間,并用Equation模塊編程實現(xiàn)維修控制代碼,利用Activity模塊表示保障裝備,利用Shutdown模塊(帶故障率和修復率屬性)通過Activity模塊的Shutdown接口啟動或停止Activity模塊,并用物件表示艦載機。當保障裝備失效或進行維修時,物件流停止,因此式(10)和式(11)表示的計劃維修與艦載機保障作業(yè)前后約束關(guān)系得到滿足。仿真模型中艦載機遵循先來先服務的排隊規(guī)則,所以約束式(7)也得到滿足。另外設置Activity模塊一次只能處理一件物件,因此式(5)和式(6)限定的艦載機一次只能在一道工序上的一臺設備上處理的約束關(guān)系也得到滿足。由于該仿真模型是對真實作業(yè)流程的模擬,所以系統(tǒng)可用度約束自動得到滿足。Activity模塊按工序的串并行關(guān)系組織,式(8)和式(9)表示的工序緊前緊后關(guān)系得到滿足。艦載機生成模塊層基于Create模塊和Equation模塊生成待出動的艦載機,初始化模塊層在仿真模型每次運行開始時清空模型,從Excel輸入表中讀取預設的模型參數(shù)(比如某類型艦載機的工序時間等)。當一次仿真運行結(jié)束后,通過Equation模塊把調(diào)度序列及對應的保障完成時間存儲到Excel輸出表中,啟發(fā)算法可以從中選取合適的結(jié)果作為初始解集。在實際使用中,艦載機指揮人員先在仿真模型上設置好各類參數(shù)甚至調(diào)整組織結(jié)構(gòu),運行多次(例如100次)生成滿足條件的結(jié)果。為了消除誤差,前10%運行可看作啟動階段,其結(jié)果不放入啟發(fā)算法,從后90%次運行結(jié)果中挑選一定數(shù)量的調(diào)度序列作為啟發(fā)算法的初始種群。挑選方法可以包括貪婪法、k-means聚類法、最優(yōu)初始群法、混合初始群法等[26-27],以便提高啟發(fā)算法的收斂速度,本文第5節(jié)實驗采用了混合初始群法。圖2為ExtendSim示例。

圖2 ExtendSim仿真模型示例Fig.2 Example of simulation model based on ExtendSim

3 啟發(fā)算法

為了比較不同啟發(fā)式算法解決艦載機調(diào)度問題的性能,分別選取了4種組合優(yōu)化方面應用較為廣泛的算法進行了設計實現(xiàn),分別是GA、SA算法、PSO算法和Memetic算法。這4種算法已在艦載機調(diào)度問題上得到應用[5,28-29]。由于增加了可用度的考量,所以本節(jié)對算法的修改之處進行了描述。Memetic算法的全局搜索采用了GA,其染色體編碼和交叉變異策略如第3.1節(jié)和第3.2節(jié)所示,局部搜索采用了自適應大鄰域搜索算法[30],鄰域結(jié)構(gòu)參見文獻[5]。

3.1 GA的染色體編碼

算法染色體由兩個矩陣構(gòu)成,一個表示艦載機保障作業(yè)調(diào)度序列,矩陣維度為P×I,其中P為保障工序數(shù)量,I為艦載機數(shù)量。每一個等待調(diào)度的艦載機用一個(1,Ku)范圍內(nèi)的實數(shù)表示,其中整數(shù)部分表示艦載機分配的保障裝備序號,小數(shù)部分表示在該保障裝備上的執(zhí)行順序。

例如表1所示,考慮有4架艦載機等待調(diào)度,保障流程包括5道工序,每道工序有4臺可并行工作的裝備,表1為其中一個染色體表示,從第2行(代表第2道工序)可以看出,1號機和4號機的第2道工序都安排在第3臺裝備上執(zhí)行,但是1號機安排在3號機之前實施保障,2號機和3號機的第2道工序分別安排在第1臺和第2臺設備上執(zhí)行。如果某型艦載機無需執(zhí)行某道工序,對應數(shù)值設為0。

表1 表示作業(yè)調(diào)度解決方案的染色體表達示例

第2個染色體表示保障裝備的計劃維修安排是一個P×U矩陣,U為該工序下保障裝備數(shù)量。表2為染色體表達示例,計劃維修染色體矩陣中數(shù)值為整數(shù),表示執(zhí)行的次數(shù)。例如，表2中第1道工序的4臺裝備分別執(zhí)行3次、1次、3次和4次計劃維修。如果某道工序不存在該臺裝備,對應數(shù)值設為0。

表2 表示計劃維修安排的染色體表達例子

3.2 GA的交叉變異策略

雜交算子需要作用于兩套染色體矩陣,采用單點雜交,雜交點在(1,I)之間,圖3為雜交算子的示例。

圖3 表示艦載機作業(yè)調(diào)度的雜交算子示例Fig.3 An example of hybrid operator for job scheduling of carrier aircraft

算法通過相似度SI來判定染色體是否需要變異,相似度計算公式如下:

(16)

(17)

因此,整個種群的評價相似度計算如下:

(18)

式中:N為種群中染色體的數(shù)量,如果相似度大于某一閾值THsi,則執(zhí)行變異。圖4為變異算子的執(zhí)行示例,變異算子隨機選擇某一列反序排列。選擇算子采用通用的輪盤賭方法。算法終止條件為:給定迭代次數(shù)(Niter)內(nèi)最優(yōu)適應度值變化趨于穩(wěn)定。

圖4 表示艦載機作業(yè)調(diào)度的變異算子示例Fig.4 An example of mutation operator for job scheduling of carrier based aircraft

3.3 SA算法和PSO算法

SA算法的實現(xiàn)可以分為3步。第1步:生成初始解群(S1);第2步:對當前解進行隨機擾動,從而生成新解,也稱相鄰解(S2);第3步:針對S1和S2都計算目標函數(shù)值,得到Obj(S1)和Obj(S2),如果Obj(S2)

圖5 表示艦載機作業(yè)調(diào)度的SA擾動算子示例Fig.5 An example of SA perturbation operator for job scheduling of carrier based aircraft

PSO算法中的解集稱為粒子群,起始時每一個粒子群都用兩個屬性-位置和速率來表示。初始化時粒子的位置和屬性賦為隨機值,每一次迭代時,用3個因子來更新粒子的運動,這3個因子分別為當前迭代中粒子速率、Pbest位置和Gbest位置,Pbest為每個粒子當前找到的最優(yōu)解,Gbest為整個群體當前找到的最優(yōu)解。每次迭代時,每個粒子速率和位置更新公式如下:

vi(t+1)=W·vi(t)+C1·rand()[Pbesti-xi(t)]+

C2·rand()[Gbest-xi(t)]

(19)

xi(t+1)=xi(t)+vi(t+1)

(20)

式中:vi(t)為t時刻粒子i的速率;xi(t)為t時刻粒子i的位置;C1、C2和W為用戶設置參數(shù);rand(·)為隨機數(shù)產(chǎn)生函數(shù)。PSO算法的解集結(jié)構(gòu)及終止條件同GA。

4 適應度評估仿真算法

為了提高調(diào)度結(jié)果的魯棒性,啟發(fā)算法的適應度(目標函數(shù)值)尚需要代入仿真場景中進行模擬計算,取其平均值作為返回的適應度。適應度評估仿真算法主要模擬數(shù)學公式難以描述的損傷事故(使用次數(shù)、碰撞、沖擊)引起的保障裝備質(zhì)量劣化,并由此帶來的視情維修和事后維修。圖6顯示了某裝備發(fā)生的7次損傷事故(D1～D7)以及由此引起的兩次維修,M1為視情維修,M2為事后維修。D1～D3次損傷事故造成裝備質(zhì)量下降,但劣化程度沒有超過閾值Lu,所以無需維修。但第4次事故造成劣化程度大于Lu,引起視情維修,修后劣化程度得到緩解,恢復程度由VCBM表示,隨后第5次損傷引起的劣化還在閾值范圍內(nèi),第6次事故造成設備劣化超過閾值Uu,引起事后維修,經(jīng)過大修或更換,劣化值恢復至初始值0。

圖6 裝備劣化示意圖Fig.6 Schematic diagram of equipment degradation

為了對裝備劣化過程及維修事件進行仿真,首先需要定義幾個隨機變量:定義DoD表示劣化程度,設其服從指數(shù)分布(DoD～exp(λDoD));定義DCBM表示視情維修持續(xù)時間,設其服從正態(tài)分布(DCBM～N(μDCBM,σDCBM));定義VCBM表示視情維修對劣化程度的改善值,設其服從正態(tài)分布(VCBM～N(μVCBM,σVCBM));定義DBDM表示事后維修的持續(xù)時間，設其服從正態(tài)分布(DBDM～N(μDBDM,σDBDM))。

適應度評估仿真流程如圖7所示。首先,從啟發(fā)算法中選取解集(候選種群),接著經(jīng)過NumSim次仿真運行,計算候選解集保障時間的平均值和標準差,返回魯棒性最好的最優(yōu)值給啟發(fā)算法,為了掌握增加種群多樣性,也返回部分其他值。

圖7 適應度評估仿真流程Fig.7 Process of fitness evaluation simulation

仿真初始化階段生成損傷事件,設TBD表示損傷事件的時間間隔,按指數(shù)分布(TBD～exp(λTBD))生成并存儲仿真時長內(nèi)所有保障裝備的損傷事件發(fā)生時刻。

仿真內(nèi)循環(huán)的主體部分步驟如下。

步驟 1調(diào)用裝備劣化程度計算函數(shù),計算當前時間的裝備劣化程度。遍歷每一臺保障裝備,如果當前時間為損傷事件發(fā)生時刻,則按公式DoDCur=DoDprv+exp(λDoD)改變該裝備的劣化程度。

步驟 2調(diào)用裝備維修模擬函數(shù),遍歷每一臺裝備,根據(jù)當前劣化程度,分別執(zhí)行視情維修或事后維修。

步驟 2.1如果該裝備當前劣化程度在(Lu,Uu)之間,執(zhí)行視情維修。起始時間為當前時刻,結(jié)束時間為起始時間加上DCBM,視情維修后裝備的劣化程度計算如下:

DoDCur=DoDprv-VCBM (Lu≤DoDprv≤Uu)

步驟 2.2如果該裝備當前劣化程度大于Uu,執(zhí)行事后維修,起始時間為當前時刻,結(jié)束時間為起始時間加上DBDM,事后維修后裝備的劣化程度計算如下:

DoDCur=DoDprv-VBDM (Uu< DoDprv)

本文假設事后維修為換件維修,劣化程度恢復為0。

步驟 3調(diào)用裝備狀態(tài)評估函數(shù),設置保障裝備所處忙閑狀態(tài)。

步驟 4調(diào)用艦載機作業(yè)重計算函數(shù),根據(jù)步驟2得到的維修時間(視情維修或事后維修時間),調(diào)整艦載機保障作業(yè)的開始和結(jié)束時間。

復雜規(guī)劃模型中各類變量、目標函數(shù)及約束關(guān)系僅能隱式表達,從而導致難以求解的問題。而本文提出的基于仿真的優(yōu)化算法不僅能夠解決以上問題,更進行了進一步改進,其優(yōu)勢包括:

(1) 啟發(fā)算法中初始解(種群)的質(zhì)量或適應度對算法性能起著重要作用[26-27]。本文算法中初始解不再是隨機生成,而是從仿真運算結(jié)果中根據(jù)應用需求挑選高質(zhì)量的可行解,加速收斂速度。

(2) 可以與可視化仿真平臺(ExtendSim、Anylogic)聯(lián)接,優(yōu)化過程可以在2維甚至3維視圖中直觀顯示,實現(xiàn)了人在回路的優(yōu)化過程。

(3) 在優(yōu)化算法中建立了數(shù)學方法難以建模的視情維修和事后維修場景,提高優(yōu)化解的魯棒性。

(4) 解決了艦載機調(diào)度模型中的隨機性和不確定性的表示和計算問題。

5 仿真實驗

調(diào)度模型支持不同類型艦載機,其工序執(zhí)行時間不同,但本文主要研究不確定情況下的調(diào)度優(yōu)化。為了便于觀察統(tǒng)計結(jié)果,以分鐘為單位,艦載機所有工序的執(zhí)行時間服從均勻分布U[5,15],保障裝備修復率服從均勻分布U[4,10],故障率服從均勻分布U[40,50],最小可用度設置為0.95,場景數(shù)量設置為12,且發(fā)生概率相同,每道工序有5臺保障裝備可以并行工作。

為了驗證仿真優(yōu)化啟發(fā)算法的性能,特別增加了標準啟發(fā)算法(GA、SA算法和PSO算法,無初始解仿真和適應度評估仿真)和 改進Memetic算法[5,28]進行對比實驗。為了增加種群的多樣性,初始解生成仿真結(jié)束后,抽取20個最優(yōu)解,20個中等解和20個最差解作為啟發(fā)算法的初始種群。根據(jù)啟發(fā)算法的不同,本文把增加了初始化仿真和適應度評估仿真的GA、PSO算法、SA算法和Memetic算法分別簡寫為SGA、SPSO、SSA和SMemetic。

由于啟發(fā)算法中用戶參數(shù)較多,為此采用了多元回歸方法進行設置,回歸方程如下:

建立30組初始實驗,每次實驗運行10次,運行結(jié)果即保障完成時間作為響應變量,從而分別得到SGA、SPSO和SSA的回歸方程。再以式(4)作為優(yōu)化目標函數(shù),用戶參數(shù)為決策變量,帶入CPLEX求解,得到啟發(fā)算法的參數(shù)如表3所示,由于SMemetic的全局搜索結(jié)構(gòu)與SGA相同,所以運行參數(shù)參照SGA設置。

表3 啟發(fā)算法的運行參數(shù)

12類實驗方案的參數(shù)設置如表4所示。針對每一個場景,運行10次計算最小保障完工時間,取其均值作為指標,實驗結(jié)果如圖8所示。從圖8中可以看出,當場景規(guī)模較小時,各算法的計算結(jié)果基本相似,隨著場景規(guī)模變大,SMemetic算法能取得更小的保障完工時間。圖9比較了各個算法所花費的平均計算時間,公平起見,標準算法中增加評估仿真。從結(jié)果中可以看出,場景規(guī)模不大時,算法花費時間基本相同,但隨著場景規(guī)模逐漸變大,不同算法花費的時間也逐漸不同。相比而言,SPSO得到結(jié)果的速度更快,而且其他算法很容易受到場景規(guī)模的影響,所花費時間甚至與場景規(guī)模呈近指數(shù)增加。SMemetic和Memetic算法在迭代數(shù)量固定的情況下,由于增加了鄰域搜索步驟,所以花費時間最多,而PSO和SPSO算法則表現(xiàn)更為穩(wěn)定。這表明初始解的優(yōu)劣對啟發(fā)算法的收斂時間有較大影響。

表4 實驗方案設置

圖8 不同算法保障完工時間Fig.8 Guarantee completion time of different algorithms

圖9 不同算法的運行時間Fig.9 Running time of different algorithms

為了進一步評價艦載機數(shù)量對算法性能的影響,還進行了敏感性分析。采用相對百分率RD作為評價指標,其計算公式如下:

式中:RDij為算法i針對方案j的相對百分率;obj(ijk)為方案j下第k次運行算法i得到的目標函數(shù)值(本文中為保障完工時間);best(j)為所有算法在方案j下得到的最佳目標函數(shù)值。圖10為相對百分率的比較結(jié)果,從圖中可以同樣發(fā)現(xiàn),SPSO和SMemetic算法性能較少受到艦載機數(shù)量的影響,具有更好的魯棒性。而且從以上實驗可以看出,本文提出的適應度評估仿真方法能夠較大增強各類啟發(fā)式算法的性能。

圖10 不同算法的敏感性分析Fig.10 Sensitivity analysis of different algorithms

為了便于在圖中集中反映出損傷事件及對應的維修狀態(tài),對隨機量設置進行了調(diào)整,所有保障裝備采用相同的參數(shù)設置:λDoD=1.2,μDCBM=3.8,σDCBM=0.7,μVCBM=18.1,σRLCBM=1.48,μDBDM=4.28,σDBDM=0.9,λTBD=56.8,另外兩個閾值Lu和Uu分別設置為20和40。

圖11為采用PSO算法下,工序1中3臺保障裝備的甘特圖及對應劣化程度的變化情況。下面以2#設備為例進行說明,其在0～15 min之間不斷遭受磨損和損傷事件導致質(zhì)量下降,由于劣化程度從Lu到Uu速度過快(遭受沖擊),還未來得及視情維修就進入事后維修,并一度中斷5#工序,事后維修換件后劣化程度得到恢復。接著在約40 min和60 min時劣化程度高于Lu,又發(fā)生兩次視情維修,圖11中顯示了視情維修的修復程度及維修持續(xù)時間。劣化程度在約74 min時又出現(xiàn)大于Uu=40的情況,發(fā)生事后維修。圖11上部分的甘特圖描述了艦載機和保障裝備的工作狀態(tài)及執(zhí)行工序。從圖11中可以看出，產(chǎn)生的調(diào)度計劃考慮了設備維修情況,具有良好的魯棒性。

圖11 算法的魯棒性分析Fig.11 Robustness analysis of algorithm

6 結(jié) 論

本文針對艦載機作業(yè)調(diào)度優(yōu)化問題,提出了一種新的滿足保障裝備可用性的綜合性數(shù)學模型,該模型充分考慮了定期計劃維修和隨機保障時間,更加準確地表達了艦載機調(diào)度的實際情況。

由于艦載機調(diào)度為NP難問題,為了求解該模型,設計了4種基于仿真優(yōu)化的啟發(fā)式算法,分別為GA、SA算法、PSO算法和Memetic算法。為了進一步滿足調(diào)度方案對于當前常用的視情維修和事后維修的魯棒性,在啟發(fā)式算法中引入了包含至少6種隨機量的故障維修仿真算法,模擬了保障裝備的劣化程度變化過程及對應的維修活動。

為了檢驗算法性能,設計了12種不同規(guī)模的實驗方案進行求解運算。實驗結(jié)果表明，本文提出的算法性能優(yōu)于常規(guī)啟發(fā)算法,并且在優(yōu)化過程中能夠充分反映隨機故障及對應維修過程的影響,具有較好的適應性。

本文研究也可以與現(xiàn)有研究成果結(jié)合，形成整套解決方案，比如本文生成的作業(yè)調(diào)度計劃，可以為反應式調(diào)度方法提供一個穩(wěn)定可靠的基準調(diào)度方案，從而避免不必要的重調(diào)度，另外在時間充裕情況下本文求解算法的適應度計算也可以增加對艦載機損傷和作戰(zhàn)任務變化的模擬，進一步提高算法的優(yōu)化程度。