范加利, 黃 葵,*, 朱興動(dòng), 孟楊凱

(1. 海軍航空大學(xué)青島校區(qū)航空保障與場站管理系, 山東 青島 266041; 2. 海軍航空大學(xué), 山東 煙臺(tái) 264000)

0 引 言

航空保障作業(yè)調(diào)度是指在航母甲板提供的有限資源下,多架艦載機(jī)、多個(gè)部門、多種資源相互協(xié)調(diào)配合,對各項(xiàng)保障資源進(jìn)行合理分配,高效完成艦載機(jī)的各項(xiàng)保障作業(yè)任務(wù)[1]。但由于保障任務(wù)的執(zhí)行過程可能存在諸多擾動(dòng)事件,打破原有調(diào)度計(jì)劃的正常執(zhí)行[2]。為盡可能減少艦載機(jī)保障效率所受影響,需在擾動(dòng)事件發(fā)生的同時(shí),針對當(dāng)前甲板艦載機(jī)及保障組的工序進(jìn)行狀況及各保障任務(wù)完成與未完成情況列表,以生成連貫的后續(xù)保障調(diào)度方案[3-5]。

關(guān)于艦載機(jī)甲板作業(yè)調(diào)度問題,國內(nèi)外學(xué)者從不同角度進(jìn)行了大量研究工作,取得了很多有益成果。蘇析超等[2,6-10]從機(jī)務(wù)保障作業(yè)建模的角度研究一體化保障模式的調(diào)度優(yōu)化問題,在該模型的基礎(chǔ)上,考慮資源配置、人機(jī)匹配等現(xiàn)實(shí)問題,嘗試了使用多種不同算法對該問題進(jìn)行求解和分析。文獻(xiàn)[11-18]從艦載機(jī)勤務(wù)保障建模的角度建立了艦載機(jī)甲板作業(yè)調(diào)度模型,并針對典型場景,對比研究了專家調(diào)度與智能求解算法的優(yōu)劣。文獻(xiàn)[18]將甲板位置作為一種資源約束,研究了艦載機(jī)的甲板調(diào)度問題。周曉光等[19]分析了甲板作業(yè)對艦載機(jī)出動(dòng)架次率的影響。文獻(xiàn)[6,20]介紹了面向艦載機(jī)故障擾動(dòng)、作業(yè)時(shí)間不確定情形的作業(yè)重調(diào)度問題,該類研究主要基于對機(jī)務(wù)作業(yè)過程的建模,調(diào)度模型較復(fù)雜,求解實(shí)時(shí)性有待提高,且往往只針對某一類擾動(dòng)或不確定性進(jìn)行研究,難以與實(shí)際作業(yè)過程相吻合。

針對艦載機(jī)甲板動(dòng)態(tài)調(diào)度問題,本文通過建立甲板作業(yè)模型與調(diào)度數(shù)學(xué)模型,對調(diào)度過程存在的潛在擾動(dòng)事件進(jìn)行分析,形成不同的重調(diào)度窗口,并制定相應(yīng)的重調(diào)度解決策略,同時(shí)設(shè)計(jì)了動(dòng)態(tài)調(diào)度求解算法的具體內(nèi)容及操作方法。

動(dòng)態(tài)調(diào)度求解算法是在調(diào)度方案運(yùn)行的過程中,依據(jù)所發(fā)生的不同擾動(dòng)事件,進(jìn)入預(yù)設(shè)的對應(yīng)重調(diào)度窗口,觸發(fā)窗口下的算法執(zhí)行機(jī)制[6,21]。算法依據(jù)對該擾動(dòng)所預(yù)設(shè)的解決方法,通過所設(shè)計(jì)的編碼方案,記錄當(dāng)前艦載機(jī)保障狀態(tài)、保障組工作狀態(tài)、各項(xiàng)保障的預(yù)計(jì)完成時(shí)間等信息內(nèi)容,再生成新的工序調(diào)度排班表,按照混合交叉方法,得到鄰域結(jié)構(gòu),并將其作為優(yōu)化路徑,結(jié)合解碼方法及禁忌方法,計(jì)算得到當(dāng)前狀態(tài)下的重調(diào)度方案。最后,以某型航母為對象,進(jìn)行動(dòng)態(tài)調(diào)度仿真驗(yàn)證。

1 艦載機(jī)再次出動(dòng)保障調(diào)度模型

1.1 艦載機(jī)甲板作業(yè)描述

艦載機(jī)保障調(diào)度目標(biāo)是使批次艦載機(jī)完成甲板保障后全部起飛的所用時(shí)間最小化,記所用時(shí)間為C。典型的艦載機(jī)甲板作業(yè)流程如圖1所示。

圖1 艦載機(jī)甲板作業(yè)流程圖Fig.1 Flowchart of carrier aircraft flight deck operation

暖機(jī)、慣性導(dǎo)航對準(zhǔn)等作業(yè)屬于起飛前必做的作業(yè),調(diào)運(yùn)、滑行、加油、武器加載等作業(yè)屬于視情開展的作業(yè)內(nèi)容[11]。暖機(jī)是利用艦面電源起動(dòng)飛機(jī)發(fā)動(dòng)機(jī),對飛機(jī)操縱等性能進(jìn)行檢查[12]?；惺侵笍谋Ｕ蠙C(jī)位滑行到起飛機(jī)位的過程[13]。

考慮到甲板空間限制、作業(yè)安全法規(guī)限制等因素,艦載機(jī)甲板作業(yè)工序約束如下。

(1) 出于安全考慮,艦載機(jī)的甲板加油、掛載彈藥作業(yè)不宜同時(shí)進(jìn)行。對于任一架艦載機(jī),任一保障作業(yè),只要作業(yè)開始就不中斷執(zhí)行。

(2) 慣導(dǎo)對準(zhǔn)、暖機(jī)、滑行3項(xiàng)作業(yè)應(yīng)待艦載機(jī)轉(zhuǎn)入暖機(jī)位后依次開展,且任一架艦載機(jī)的這3道工序順序是一致的。

(3) 所有艦載機(jī)起飛前均需從暖機(jī)位滑出,處于其他機(jī)位的艦載機(jī)必須進(jìn)行必要的調(diào)運(yùn)作業(yè)。該約束決定了艦載機(jī)甲板作業(yè)工序中是否需加入了調(diào)運(yùn)作業(yè)工序。

(4) 飛行甲板加油保障點(diǎn)數(shù)量和位置均固定,各保障點(diǎn)所能保障的停機(jī)位范圍已知,且部分機(jī)位可活動(dòng)2個(gè)或2個(gè)以上加油點(diǎn)保障。

(5) 暖機(jī)位當(dāng)前被占用的情況下,不能被選擇作為其他飛機(jī)的目標(biāo)轉(zhuǎn)運(yùn)機(jī)位。

(6) 對于調(diào)運(yùn)作業(yè)而言,必須確保存在可行的轉(zhuǎn)運(yùn)作業(yè)路徑。

1.2 艦載機(jī)甲板作業(yè)調(diào)度的數(shù)學(xué)模型

艦載機(jī)的機(jī)務(wù)保障作業(yè)與甲板保障作業(yè)中的加油、慣性導(dǎo)航對準(zhǔn)、武器加載等作業(yè)環(huán)節(jié)可以并行實(shí)施。為此,在建模過程中,可以不考慮機(jī)務(wù)保障作業(yè)的調(diào)度問題,從而降低模型的復(fù)雜度。本文研究的甲板作業(yè)調(diào)度想定是艦載機(jī)的多波次循環(huán)出動(dòng)場景。該模型的起點(diǎn)為典型的再次出動(dòng)準(zhǔn)備情況。所謂再次出動(dòng)準(zhǔn)備,是指一批次艦載機(jī)的最后一架艦載機(jī)完成起飛后,經(jīng)過戰(zhàn)訓(xùn)任務(wù)飛行,而后依次著艦,經(jīng)必要的準(zhǔn)備后再次參加下一階段飛行。對于航母艦載機(jī)循環(huán)出動(dòng)而言,再次出動(dòng)準(zhǔn)備時(shí)間可以定義為:上一批次艦載機(jī)的最后一架艦載機(jī)著艦到下一批次最后一架艦載機(jī)完成起飛的時(shí)間。這個(gè)時(shí)間與甲板調(diào)度效率、參飛艦載機(jī)的數(shù)量、甲板作業(yè)效率等因素有關(guān)。

根據(jù)約束條件和實(shí)際作業(yè)過程,建立抽象模型如下[22]。

符號(hào)描述:記循環(huán)出動(dòng)過程中,上一次完成艦載機(jī)著艦至下一次完成最后一架艦載機(jī)起飛所需的最長保障作業(yè)時(shí)間為Cmax。一批次艦載機(jī)完成保障作業(yè)時(shí)間定義為,批次中最后一架艦載機(jī)完成機(jī)位停靠到該批次艦載機(jī)最后一架艦載機(jī)完成起飛所需的時(shí)間,也相當(dāng)于再次出動(dòng)準(zhǔn)備時(shí)間。記艦載機(jī)i從實(shí)施第1道保障作業(yè)到完成起飛所用時(shí)間為Ci。

批次中包含的艦載機(jī)數(shù)量定義為I;每一艦載機(jī)i對應(yīng)的甲板作業(yè)工序集是Vi,其中Vi={Ji1,Ji2,…,Jij},j表示甲板作業(yè)工序數(shù);記飛行甲板作業(yè)保障資源集合為R。在所有工序中,Vnr為不需要保障資源的工序集,Vrs為需要特定保障資源的工序集,Vra是需要保障的資源。該資源數(shù)量布置一個(gè)可進(jìn)行分配的作業(yè)工序集,顯然任一工序Jij必需包含在工序集Vi內(nèi)。艦載機(jī)的調(diào)運(yùn)、加油、彈藥加載等工序不能同時(shí)進(jìn)行,記類似的工序集合為Vs;VRs為某一保障資源能保障的停機(jī)位集合;yijk=1表示第i架艦載機(jī)第j項(xiàng)作業(yè)開始;dmini是第i架艦載機(jī)工序mi、ni開始和結(jié)束時(shí)間的間隔;艦載機(jī)i完成保障作業(yè)j所需時(shí)間記為Tij;Njk表示時(shí)刻k,可用于保障作業(yè)j的保障資源總數(shù)量;stij為第i架艦載機(jī)第j項(xiàng)作業(yè)的開始時(shí)間,stij≥0;記艦載機(jī)i完成第j項(xiàng)作業(yè)的完工時(shí)刻為edij;記艦載機(jī)i完成作業(yè)j所花費(fèi)的時(shí)間為dij;記彈藥裝載組、轉(zhuǎn)運(yùn)保障組等需進(jìn)行移動(dòng)實(shí)施保障的保障組在甲板上移動(dòng)的時(shí)間為Ml。

目標(biāo)函數(shù):

F=minCmax

(1)

約束條件:

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

sti1jzy≤sti2jzy,?ZWi1,i2∈Hs;Xzwi1≥Xzwi2

(10)

模型中,式(1)為目標(biāo)函數(shù);式(2)～式(10)為約束條件。式(2)和式(3)為對艦載機(jī)作業(yè)工序唯一執(zhí)行性的約束;式(4)是對艦載機(jī)作業(yè)工序前后關(guān)系的約束,針對作業(yè)集中艦載機(jī)的導(dǎo)航對準(zhǔn)、暖機(jī)、滑行、起飛等4項(xiàng)作業(yè);式(5)確?；コ夤ば虿荒芡瑫r(shí)安排執(zhí)行;式(6)用于表達(dá)某一資源在飛行甲板配置的可用總數(shù)量的約束,該數(shù)量可能因?yàn)橘Y源故障等擾動(dòng)因素而變化;式(9)表達(dá)了任一保障資源不可同時(shí)服務(wù)兩架艦載機(jī);式(8)表達(dá)了對于同一架艦載機(jī)具有緊前緊后關(guān)系的保障作業(yè)工序,開始與結(jié)束時(shí)間必須滿足的間隔時(shí)間約束;式(7)確保對于任一架艦載機(jī)的保障,加油作業(yè)和彈藥加載不能同時(shí)進(jìn)行,調(diào)運(yùn)與其他任何作業(yè)不同時(shí)進(jìn)行;式(10)表示艦載機(jī)轉(zhuǎn)運(yùn)需滿足的路徑可行條件。

2 動(dòng)態(tài)調(diào)度方法

2.1 重調(diào)度窗口與策略制定

重調(diào)度窗口是調(diào)度基于突發(fā)離散事件進(jìn)入重調(diào)度系統(tǒng)的入口分類,由于采用事件驅(qū)動(dòng)作為重調(diào)度策略,因此重調(diào)度窗口的預(yù)設(shè)以及窗口下相應(yīng)解決辦法的預(yù)設(shè)必不可少,具體內(nèi)容如下。

(1) 新增艦載機(jī)加入保障流程。適用于因作戰(zhàn)策略的改變,新增艦載機(jī)加入艦載機(jī)編隊(duì)或由于某架艦載機(jī)檢測出現(xiàn)故障新增其他艦載機(jī)代替的情況。當(dāng)事件觸發(fā)時(shí),保持甲板全部正在進(jìn)行保障工序的保障組及艦載機(jī)的工作狀態(tài)不變,把保障組當(dāng)前正在執(zhí)行中的工序預(yù)計(jì)完成時(shí)間作為此保障組釋放時(shí)間,將新增艦載機(jī)的全部待保障工序納入甲板保障未完成部分,根據(jù)當(dāng)前空閑保障組及正在工作保障組的釋放時(shí)間,結(jié)合甲板保障全部未完成部分,進(jìn)行調(diào)度算法計(jì)算。

(2) 艦載機(jī)故障退出保障流程。適用于艦載機(jī)在機(jī)務(wù)保障伴隨勤務(wù)保障共同進(jìn)行的過程中,因發(fā)現(xiàn)艦載機(jī)部分零部件存在待維修更換、不適宜繼續(xù)執(zhí)行飛行任務(wù)的情況。當(dāng)事件觸發(fā)時(shí),當(dāng)前保障組及艦載機(jī)立即停止工作狀態(tài),艦載機(jī)停止參與后續(xù)甲板保障調(diào)度,當(dāng)前保障組進(jìn)入空閑釋放狀態(tài),保持甲板其他正在進(jìn)行保障工序的保障組及艦載機(jī)的工作狀態(tài)不變,根據(jù)當(dāng)前空閑保障組及正在工作保障組的釋放時(shí)間,結(jié)合甲板保障未完成部分(其中故障艦載機(jī)未完成部分不算入內(nèi))進(jìn)行調(diào)度運(yùn)行。

(3) 保障組故障退出保障流程。適用于保障組因人員或設(shè)備原因停止后續(xù)甲板保障工序。此時(shí)分為兩種情況,一為保障組退出時(shí)可將當(dāng)前工序執(zhí)行完畢,二為退出時(shí)當(dāng)前保障工序無法執(zhí)行完畢,后續(xù)需由其他相同工序保障組接替完成。當(dāng)事件觸發(fā)時(shí),若工序可執(zhí)行完畢,則按照當(dāng)前此保障組預(yù)計(jì)完成時(shí)間對艦載機(jī)做釋放,對釋放時(shí)刻的甲板保障組狀態(tài)及未完成工序狀態(tài)進(jìn)入重調(diào)度計(jì)算;若工序無法執(zhí)行完畢,則按照故障時(shí)間對艦載機(jī)立即釋放,同時(shí)艦載機(jī)當(dāng)前工序的計(jì)算機(jī)編碼不做已完成標(biāo)記,工序內(nèi)容繼續(xù)參與后續(xù)重調(diào)度,對故障時(shí)刻甲板狀態(tài)進(jìn)入重調(diào)度計(jì)算。

(4) 新增保障組加入保障流程。適用于保障組前期因人員或設(shè)備原因停止甲板保障參與的后期加入。當(dāng)事件觸發(fā)時(shí),保持甲板全部正在進(jìn)行保障工序的保障組及艦載機(jī)的工作狀態(tài)不變,把工序完成時(shí)間作為保障組釋放時(shí)間,將新增保障組作為空閑保障組,根據(jù)當(dāng)前全部空閑保障組及正在工作保障組的釋放時(shí)間,對未完成的保障工序進(jìn)行重調(diào)度計(jì)算。

(5) 保障工序完成時(shí)間發(fā)生變化。適用于當(dāng)前保障工作實(shí)際完成時(shí)間早于或晚于原調(diào)度方案中預(yù)計(jì)的完成時(shí)間,或?qū)ば虮Ｕ系挠?jì)劃執(zhí)行所需時(shí)間發(fā)生改變,如由計(jì)劃所持的艦載導(dǎo)彈型號(hào)發(fā)生改變導(dǎo)致工序計(jì)劃時(shí)間改變的情況。該情況下,需設(shè)置偏離閥值,首先計(jì)算實(shí)際情況與原調(diào)度計(jì)劃的偏離程度。若偏離程度超出閥值,則進(jìn)入重調(diào)度系統(tǒng),根據(jù)甲板保障組實(shí)際釋放時(shí)間與改變工序進(jìn)行的計(jì)劃所需時(shí)間,進(jìn)入重調(diào)度計(jì)算。若未超出閥值,則不進(jìn)入重調(diào)度系統(tǒng)。

2.2 時(shí)間變化偏離程度計(jì)算

在針對保障完成時(shí)間變化的重調(diào)度窗口中,當(dāng)保障工作實(shí)際完成時(shí)間早于或晚于原調(diào)度方案中預(yù)計(jì)的完成時(shí)間,或工序保障的計(jì)劃執(zhí)行所需時(shí)間發(fā)生改變時(shí),須首先依據(jù)相應(yīng)編碼進(jìn)行偏離程度計(jì)算。在偏離程度大于相應(yīng)限制情況下進(jìn)入重調(diào)度系統(tǒng)執(zhí)行重調(diào)度方案計(jì)算。否則,對原調(diào)度方案進(jìn)行時(shí)間平移。偏離程度Δc計(jì)算方式具體如下。

(1)若時(shí)間延遲情況下,偏離程度計(jì)算公式為

Δc=edij(new)-edij

(11)

式中:edij(new)的含義為艦載機(jī)在該工序延遲后的工序完成時(shí)間;edij是艦載機(jī)該工序延遲前的計(jì)劃完成時(shí)間。在完成偏離程度計(jì)算后,對偏離程度Δc進(jìn)行重調(diào)度判別計(jì)算,判別條件計(jì)算公式如下:

Δc≥sti(j+1)-edij

(12)

Δc≥rstm+1-redm

(13)

式中:redm為該保障小組在調(diào)度計(jì)劃中當(dāng)前任務(wù)的計(jì)劃完成時(shí)間;sti(j+1)為保障調(diào)度計(jì)劃中艦載機(jī)出現(xiàn)延遲工序的后一保障工序的開始時(shí)間;rstm+1為該延遲工序的對應(yīng)保障組在調(diào)度計(jì)劃中的下一保障任務(wù)的開始時(shí)間。

依據(jù)判別式計(jì)算,若滿足二者其中之一,則進(jìn)入重調(diào)度算法求解優(yōu)化重調(diào)度方案。

(2)在時(shí)間提前的情況下,偏離程度計(jì)算公式為

Δc=edij-edij(new)

(14)

對偏離程度Δc進(jìn)行重調(diào)度判別計(jì)算,公式如下:

∑NRs+1

(15)

∑NRs=Ns,edij

(16)

式中:NRs+1為在艦載機(jī)工序相較于原定完成時(shí)間的提前時(shí)間段內(nèi),保障調(diào)度計(jì)劃內(nèi)該艦載機(jī)所提前的工序的后一工序任務(wù)的工序保障種類在該時(shí)間段內(nèi)在甲板的同時(shí)進(jìn)行數(shù)量;Ns+1為后一工序任務(wù)的工序保障種類的資源總量;NRs的含義為艦載機(jī)提前工序的工序保障種類的甲板的同時(shí)進(jìn)行數(shù)量;Ns為該工序種類的資源總量。

式(15)用于判別在工序任務(wù)提前完成時(shí),該艦載機(jī)后一工序任務(wù)是否存在可提前進(jìn)行的可能性。式(16)用于判別該艦載機(jī)所提前的任務(wù)工序在原調(diào)度計(jì)劃中任務(wù)結(jié)束時(shí)甲板是否處于該資源的供給飽和狀態(tài),若飽和,則該保障工序的任務(wù)完成時(shí)間提前帶來了重調(diào)度的可操作性。

在任務(wù)時(shí)間提前狀態(tài)下,若據(jù)判別式計(jì)算滿足二者其中之一,則進(jìn)入重調(diào)度算法求解更新優(yōu)化的重調(diào)度方案。

3 求解算法

禁忌優(yōu)化算法已經(jīng)被證明具有很強(qiáng)的全局搜索能力,且無需對求解的問題進(jìn)行編碼與解碼操作,運(yùn)算效率高。本文使用該算法對上述模型進(jìn)行優(yōu)化求解,可以在保證求解質(zhì)量的同時(shí),提高算法實(shí)時(shí)性,以滿足瞬息萬變的航母甲板作業(yè)態(tài)勢。遺傳算法因編碼方式靈活,在求解多項(xiàng)目調(diào)度和車間調(diào)度問題中得到廣泛應(yīng)用[23-29]。本節(jié)針對甲板調(diào)度作業(yè)模型的特殊性,在禁忌搜索算法框架下,設(shè)計(jì)了一種編碼式解結(jié)構(gòu)、構(gòu)造鄰域結(jié)構(gòu)及相應(yīng)的交叉、變異方法,并采用啟發(fā)式解碼法實(shí)現(xiàn)了問題的求解。

3.1 算法流程與描述

針對甲板調(diào)度方案優(yōu)化求解,對其優(yōu)化研究流程的展示如圖2所示。

圖2 改進(jìn)的禁忌優(yōu)化算法流程圖Fig.2 Flowchart of improvement tabu optimization algorithm

算法首先根據(jù)啟發(fā)式規(guī)則,生成甲板初始調(diào)度方案,以調(diào)度排班表及甘特圖作為方案結(jié)果。然后,基于編碼的交叉算法對工作日制進(jìn)行變換,全部的變換方案構(gòu)成算法優(yōu)化的鄰域結(jié)構(gòu),作為下一次禁忌優(yōu)化算法的路徑參考。通過對工作日制的解碼計(jì)算,從中選取最優(yōu)且不在禁忌表內(nèi)的變換作為優(yōu)化操作。同時(shí),將此次變換計(jì)入禁忌表內(nèi),以此循環(huán),直至達(dá)到目標(biāo)迭代次數(shù),以最優(yōu)方案調(diào)度結(jié)果生成甲板調(diào)度甘特圖。

3.2 滾動(dòng)調(diào)度算法設(shè)計(jì)

由于在重調(diào)度窗口下進(jìn)入調(diào)度方案計(jì)算,是在原調(diào)度方案的執(zhí)行過程中進(jìn)行的,此時(shí)甲板的艦載機(jī)及保障組不是初始未工作狀態(tài),而是各自均有正在進(jìn)行的工序保障的狀態(tài),且調(diào)度的工序內(nèi)容也僅針對甲板全部艦載機(jī)還未進(jìn)行的部分工序內(nèi)容。因此,動(dòng)態(tài)調(diào)度需要一種在生成調(diào)度方案的同時(shí)可滿足復(fù)雜情況約束的調(diào)度算法。

滾動(dòng)調(diào)度算法的主要思想是通過連續(xù)滾動(dòng)控制將全部的調(diào)度過程細(xì)分為連貫的靜態(tài)區(qū)間,通過使每個(gè)靜態(tài)區(qū)間的調(diào)度達(dá)到最優(yōu)來獲得整體的調(diào)度方案。由于拆分為不同的靜態(tài)區(qū)間,在進(jìn)入重調(diào)度窗口后,可通過對調(diào)度的連續(xù)滾動(dòng)控制,每次針對不同的約束狀況,通過對計(jì)算機(jī)編碼的計(jì)算,做出符合當(dāng)下情況的調(diào)度步驟。該方法可容納過程中出現(xiàn)的各類約束限制,如各保障組之間及艦載機(jī)之間存在不同的釋放時(shí)間,在未到達(dá)釋放時(shí)間時(shí)不可對其進(jìn)行工序安排的情況。艦載機(jī)之間未完成的工序集各不相同,還可能面臨著因艦載機(jī)增加或取消導(dǎo)致未完成工序集改變的情況等。

針對滾動(dòng)調(diào)度算法的思想,設(shè)計(jì)完工時(shí)間表矩陣作為滾動(dòng)調(diào)度的計(jì)算依據(jù),將甲板各類工序的全部保障組當(dāng)前任務(wù)預(yù)計(jì)完工時(shí)間記錄在內(nèi),通過對完工時(shí)間表矩陣內(nèi)的數(shù)值進(jìn)行計(jì)算,獲取可進(jìn)行任務(wù)安排的保障小組,依據(jù)對距離編碼矩陣、艦載機(jī)的任務(wù)完成工作集矩陣以及各類其他約束矩陣的數(shù)值計(jì)算,對其派遣最優(yōu)任務(wù)計(jì)劃,同時(shí)對任務(wù)派遣做工作日制矩陣記錄,以此循環(huán)進(jìn)行,直至完成全部甲板工序調(diào)度。其中,依據(jù)完工時(shí)間表對保障小組的每一次任務(wù)派遣,都可視為連貫的靜態(tài)區(qū)間。通過對每一次派遣做最優(yōu)選擇并滾動(dòng)進(jìn)行,從而獲取重調(diào)度方案,供禁忌優(yōu)化算法尋優(yōu)計(jì)算。

3.3 編碼策略

通過對問題的分析,問題求解的決策包含:各艦載機(jī)的柔性工序順序、各工序所對應(yīng)分配的保障小組、艦載機(jī)轉(zhuǎn)運(yùn)工序的機(jī)位安排等。通過將柔性工序順序與對應(yīng)保障小組編碼整合,編碼部分包含艦載機(jī)工序、機(jī)位以及約束,共三重編碼。

(1) 艦載機(jī)工序編碼

針對甲板上每一架艦載機(jī)i,假設(shè)艦載機(jī)的甲板作業(yè)工序數(shù)為n,保障每種工序的資源數(shù)量為m,工序編碼應(yīng)當(dāng)體現(xiàn)其工序順序及實(shí)施該工序保障的是m個(gè)保障資源中的哪一個(gè)。對保障工序使用1 到n順序編碼,在編碼規(guī)則中設(shè)置約束:?i≠j,ni≠nj。同樣地,順序編碼法也適應(yīng)于保障資源的編碼,且也存在約束:?i≠j,mi≠mj。

具體的編碼構(gòu)造方法如構(gòu)造的編碼矩陣所示:

(17)

艦載機(jī)個(gè)體用矩陣的行代表,矩陣的列排序代表各架艦載機(jī)的保障工序順序,aij的值表示工序內(nèi)容和實(shí)施該工序保障的保障資源編號(hào),編碼由“工序種類”+“0”+“同種保障資源編號(hào)”組成。例如,a31的編碼為“204”,代表編號(hào)為3的艦載機(jī),第1個(gè)執(zhí)行的保障作為編號(hào)為2的作業(yè),且為該艦載機(jī)完成作業(yè)2而實(shí)施的保障資源為該工序所需資源的第4組。

(2) 機(jī)位編碼

停機(jī)位功能對于艦載機(jī)的甲板保障調(diào)度的影響極大,通過機(jī)位屬性,可獲得機(jī)位間的距離信息及機(jī)位對工序的支持性信息等。經(jīng)分析,甲板上的i架艦載機(jī)與n種不同工序所各自對應(yīng)的m個(gè)保障小組均包含機(jī)位屬性,編碼方式如下:

式中:B和C矩陣聯(lián)合記錄甲板機(jī)位信息,B矩陣記錄艦載機(jī)的機(jī)位信息,艦載機(jī)編號(hào)與行序列一一對應(yīng),記錄艦載機(jī)所在機(jī)位;C矩陣記錄保障組的機(jī)位信息,行序列與工序種類編號(hào)一一對應(yīng),列序列與工序內(nèi)的每一保障組一一對應(yīng),記錄各保障組當(dāng)前所在機(jī)位。

(3) 機(jī)位約束編碼矩陣

約束編碼矩陣用于存放甲板全部的約束行為,用于調(diào)度模型求解過程中算法從中提取約束信息,從而計(jì)算最終作業(yè)結(jié)束時(shí)間,最終目標(biāo)是剔除違背約束的解,保留可行解。約束編碼采用矩陣形式,每個(gè)元素只能取值為0或1。用于表示機(jī)位屬性。1表示機(jī)位具備某項(xiàng)作業(yè)的保障能力,0則表示不可進(jìn)行該作業(yè)。

3.4 調(diào)度排班策略

調(diào)度排班策略為每一甲板保障作業(yè)工序安排相應(yīng)的艦載機(jī)保障順序。調(diào)度排班策略從工序的角度分配艦載機(jī),這種策略可以提高編碼效率和搜索效率,使得調(diào)度結(jié)果更具體。調(diào)度排班表是一個(gè)n列m行的矩陣,每一行對應(yīng)某一個(gè)保障工序,行中的n個(gè)元素是完成該工序的艦載機(jī)的排列順序。由于各艦載機(jī)所要接受的保障作業(yè)工序內(nèi)容不一定相同,所以對于不同工序,它所對應(yīng)的需實(shí)施該工序的艦載機(jī)數(shù)量不同。表內(nèi)編碼值代表艦載機(jī)的機(jī)號(hào),針對同一工序,也就是矩陣的同一行,編碼值不可能出現(xiàn)重復(fù),這是因?yàn)閷τ谌我慌炤d機(jī),假設(shè)同一作業(yè)只實(shí)施一次。工序調(diào)度排班表的解碼結(jié)果如圖3所示。

圖3 工序調(diào)度排班表編碼與解碼示意圖Fig.3 Schematic diagram of coding and decoding of operation of scheduling tabulation

在工序調(diào)度排班表內(nèi),僅有各工序相對應(yīng)的保障順序,保障順序內(nèi)無需對應(yīng)工序內(nèi)各保障組。原因在于,在依據(jù)調(diào)度方案不斷尋優(yōu)解碼計(jì)算時(shí),遵守左對齊解碼規(guī)則:首先各工序均依據(jù)默認(rèn)編號(hào)從小至大的保障組進(jìn)行艦載機(jī)編號(hào)依次選取以進(jìn)行保障,當(dāng)完成首輪選取后,再依據(jù)工序內(nèi)各保障組的最早完工時(shí)間選取保障順序內(nèi)的下一待保障艦載機(jī)。

針對規(guī)則內(nèi)同一工序存在默認(rèn)的保障組選擇順序及各工序在矩陣內(nèi)的行順序不同對優(yōu)化結(jié)果可能帶來的不利影響,可通過交叉算法在得到優(yōu)化路徑時(shí)消除此影響。

調(diào)度算法的優(yōu)化搜索路徑應(yīng)當(dāng)覆蓋調(diào)度排班表采取某種變換策略所形成的全部變換方案。對全部搜索解實(shí)施解碼計(jì)算,獲取調(diào)度的優(yōu)化結(jié)果。

3.5 基于優(yōu)先規(guī)則的重調(diào)度初始調(diào)度生成

當(dāng)進(jìn)入重調(diào)度窗口后,針對滾動(dòng)調(diào)度算法,生成初始調(diào)度方案的具體步驟如下。

步驟 1創(chuàng)建保障組完工時(shí)間表,初始數(shù)值為進(jìn)入重調(diào)度窗口的時(shí)間數(shù)值,創(chuàng)建空白調(diào)度排班表,生成甲板當(dāng)前艦載機(jī)、保障組的工序完成狀況及相應(yīng)時(shí)間、機(jī)位等信息的編碼,用于滾動(dòng)調(diào)度仿真計(jì)算。

步驟 2在完工時(shí)間表內(nèi),將正在執(zhí)行甲板保障工作任務(wù)對應(yīng)的完工時(shí)間數(shù)值改為工序的預(yù)計(jì)完成時(shí)間。針對不同的重調(diào)度窗口,依據(jù)其對應(yīng)策略,對甲板艦載機(jī)工序編碼、保障組及停機(jī)位等信息編碼做對應(yīng)刷新。

步驟 3查詢獲取加油、掛彈、轉(zhuǎn)運(yùn)工序完工時(shí)間表內(nèi)的最小值所對應(yīng)保障小組,對此保障小組進(jìn)行可保障工作內(nèi)容檢查及派發(fā)。在任務(wù)派發(fā)的同時(shí),以工序?yàn)閱挝?將保障艦載機(jī)編號(hào)記錄于工作日制表。若此保障小組因艦載機(jī)工序約束、甲板機(jī)位約束或自身保障范圍限制等原因沒有可進(jìn)行的工作任務(wù),則跳過此保障組,選擇次最小值的保障小組重復(fù)上述過程,進(jìn)行任務(wù)派發(fā)。

步驟 4在滾動(dòng)調(diào)度仿真過程中,對完成新任務(wù)選擇的保障組進(jìn)行編碼信息更新,包含所在機(jī)位、完工時(shí)間、保障艦載機(jī)等信息,對被選擇的艦載機(jī)進(jìn)行編碼信息更新,包含工序進(jìn)行記錄、工序起止時(shí)間等信息,根據(jù)艦載機(jī)涉及的轉(zhuǎn)運(yùn)機(jī)位信息,實(shí)時(shí)更新停機(jī)位占用編碼。

步驟 5對完成加油、彈藥加載、調(diào)運(yùn)保障作業(yè)的艦載機(jī),直接依次安排慣導(dǎo)對準(zhǔn)、暖機(jī)、滑行作業(yè)。視起飛位可用情況安排起飛作業(yè)。

步驟 6循環(huán)執(zhí)行步驟2至步驟5,直至完成所有艦載機(jī)的保障作業(yè)安排。

完成上述計(jì)算,便可獲取重調(diào)度的初始優(yōu)化調(diào)度方案及所對應(yīng)工作日制記錄。

3.6 鄰域結(jié)構(gòu)設(shè)計(jì)

由于動(dòng)態(tài)調(diào)度算法與靜態(tài)調(diào)度算法在運(yùn)行時(shí)的甲板狀態(tài)不同,因此產(chǎn)生的調(diào)度排班表編碼內(nèi)容不同。靜態(tài)調(diào)度在甲板初始狀態(tài)下運(yùn)行,因此在初始調(diào)度方案生成的調(diào)度排班表中,各項(xiàng)工序的保障編碼包含甲板全部對此工序有需求的待保障艦載機(jī)的編號(hào)。動(dòng)態(tài)調(diào)度是在調(diào)度的進(jìn)行過程中進(jìn)行的,部分艦載機(jī)已完成了部分保障工序,因此在初始調(diào)度方案生成的調(diào)度排班表中,各行之間編碼的數(shù)量及內(nèi)容各不相同。若采用原交叉方式,由于艦載機(jī)編號(hào)可能僅在矩陣的某一行內(nèi)出現(xiàn),無法與其他行的編碼進(jìn)行部分映射交叉,所產(chǎn)生的鄰域結(jié)構(gòu)無法充分體現(xiàn)全部的優(yōu)化路徑方向,從而導(dǎo)致優(yōu)化算法無法取得最優(yōu)結(jié)果。對此,算法對調(diào)度排班表采用部分映射交叉與普通交叉的雙重交叉結(jié)合的方式,以產(chǎn)生優(yōu)化所需要的鄰域結(jié)構(gòu)。

(1) 部分映射交叉

部分映射交叉的操作方式是在確定兩行之間的數(shù)值映射關(guān)系后,將兩行的對應(yīng)數(shù)值做映射變換。部分映射交叉方法與文獻(xiàn)[30]中交叉方法類似,在因動(dòng)態(tài)調(diào)度所產(chǎn)生的調(diào)度排班表中,各行之間編碼的數(shù)量及內(nèi)容各不相同,部分映射交叉方案的記錄必須滿足其交叉合法條件,即在兩行之間分別選取編碼作為彼此的映射關(guān)系時(shí),兩個(gè)編碼的所在行內(nèi)也必須包含映射對象的編碼。如圖4所示,在第1行選取編碼數(shù)值1、第2行選取編碼數(shù)值4作為映射關(guān)系時(shí),因第1行存在映射對象4,第2行也存在映射對象1,即映射交叉方案合法。對滿足合法條件的交叉方案,進(jìn)行行排列關(guān)系及映射關(guān)系的記錄。

圖4 動(dòng)態(tài)調(diào)度部分映射交叉示意圖Fig4 Schematic diagram of dynamic scheduling partial mapping

(2) 普通交叉

普通交叉是對調(diào)度排班表的全部矩陣行的每一行進(jìn)行單行內(nèi)兩數(shù)值的位置交叉變換操作。通過獲取各行內(nèi)編碼的兩兩排列組合方案得到其全部交叉方案,并對其進(jìn)行記錄,如圖5所示。

圖5 動(dòng)態(tài)調(diào)度普通交叉示意圖Fig.5 Schematic diagram of dynamic scheduling common intersections

鄰域結(jié)構(gòu)由調(diào)度排班表編碼矩陣內(nèi)全部可行的映射交叉方案(方案A)以及全部的普通交叉方案(方案B)共同組成。通過對其全部鄰域結(jié)構(gòu)的解碼、擇優(yōu),完成其甲板重調(diào)度方案的優(yōu)化。

其中,由交叉方案A組成的鄰域結(jié)構(gòu),是為了在艦載機(jī)待保障的工序有兩個(gè)及以上的情況下,實(shí)現(xiàn)對艦載機(jī)工序的保障順序交叉互換尋優(yōu),而又不引起行內(nèi)編碼重復(fù)的不合法性。由交叉方案B組成的鄰域結(jié)構(gòu),是為了在同一工序中有多架待保障艦載機(jī)情況下,實(shí)現(xiàn)工序?qū)ε炤d機(jī)的選擇順序的交叉互換尋優(yōu)。通過將兩種交叉方案結(jié)合,共同組成鄰域結(jié)構(gòu),擴(kuò)大解的搜索范圍,提高解的質(zhì)量。

3.7 雙重禁忌表策略

在普通調(diào)度算法中,由于鄰域結(jié)構(gòu)由單一的部分映射交叉方案組成,禁忌優(yōu)化算法在優(yōu)化過程中,也僅需單一的禁忌表實(shí)現(xiàn)對優(yōu)化過程中被選擇的交叉方案的禁忌記錄。而由于動(dòng)態(tài)調(diào)度算法的鄰域結(jié)構(gòu)由兩種不同的交叉方案組成,不同的交叉方案所產(chǎn)生的方案記錄矩陣不同,因此在優(yōu)化的過程中,需要兩個(gè)禁忌表分別記錄兩種交叉方案中被選擇的方案的禁忌值。

3.8 解碼策略

解碼的目的在于獲取問題的調(diào)度解。通過將調(diào)度排班表按照鄰域結(jié)構(gòu)中的每一個(gè)交叉變換方案逐一做變換,對變換后的調(diào)度排班表按照解碼策略進(jìn)行甲板仿真,得到相應(yīng)調(diào)度結(jié)果。對比完成甲板全部保障的最短時(shí)間,若時(shí)間優(yōu)于當(dāng)前最優(yōu)目標(biāo)值(初始記錄為原調(diào)度排班表未交叉變換時(shí)所對應(yīng)的甲板最短保障時(shí)間),則記錄此變換方案,更新最優(yōu)目標(biāo)值,以此循環(huán)進(jìn)行,直至完成全部的鄰域結(jié)構(gòu)解碼計(jì)算。其中,在對鄰域結(jié)構(gòu)全部變換方案進(jìn)行逐一變換計(jì)算的過程中,變換操作不累計(jì),每一次變換操作都針對于原調(diào)度排班表,而不是針對于在鄰域結(jié)構(gòu)上進(jìn)行一個(gè)變換方案操作后的調(diào)度排班表。

詳細(xì)的解碼算法步驟如下。

步驟 1創(chuàng)建與調(diào)度排班表對應(yīng)維度的工序完工時(shí)間表,令其所有元素均為0。

步驟 2在調(diào)度排班表中,依照艦載機(jī)的加油、彈藥裝載、調(diào)運(yùn)的順序查詢作業(yè)完工時(shí)間,工序?qū)?yīng)行元素按從小到大順序排列(順序的制定是針對初始狀態(tài)下完工時(shí)間表數(shù)值均為0以及過程中可能出現(xiàn)相同最小值情況下,有固定的解碼規(guī)程,且此順序與初始調(diào)度方案計(jì)算過程相同,以免產(chǎn)生誤差),完工時(shí)間最小值將通過該步驟獲取,同時(shí)記錄該值對應(yīng)的保障資源(小組)的編號(hào)。

步驟 3獲取步驟2查詢所得的保障(資源)小組序號(hào),根據(jù)所屬工序,按照調(diào)度排班表中該工序的元素排列順序選取對應(yīng)編號(hào)的艦載機(jī),并賦予其該項(xiàng)作業(yè)作為開始。判斷該工序的所需保障資源是否屬于固定點(diǎn)保障多個(gè)停機(jī)位的資源,若是,則按照編碼順序選取在該保障點(diǎn)服務(wù)范圍內(nèi)的艦載機(jī)進(jìn)行保障;因式(2)中的約束條件中對作業(yè)工序不能中斷約束,當(dāng)前工序開始時(shí)間取值應(yīng)為被選飛機(jī)正在執(zhí)行保障作業(yè)的完工時(shí)間。

步驟 4實(shí)時(shí)更新作業(yè)工序選擇信息,包含所在機(jī)位編碼、完工時(shí)間編碼、保障艦載機(jī)編碼等信息,同時(shí)對進(jìn)行任務(wù)安排的艦載機(jī)進(jìn)行編碼信息更新,包含工序記錄編碼、工序起止時(shí)間編碼等信息,若涉及機(jī)位轉(zhuǎn)運(yùn),則還需更新停機(jī)位占用的信息編碼。

步驟 5對完成加油、彈藥加載、調(diào)運(yùn)保障作業(yè)的艦載機(jī),直接依次安排慣導(dǎo)對準(zhǔn)、暖機(jī)、滑行作業(yè)。視起飛位可用情況安排起飛作業(yè)。

步驟 6循環(huán)執(zhí)行步驟2～步驟5,直至完成所有艦載機(jī)的保障作業(yè)安排。

按上述算法解碼后,對調(diào)度排班表對應(yīng)的調(diào)度解執(zhí)行領(lǐng)域變換操作,同時(shí)在禁忌表內(nèi)記錄該變換方案,在禁忌算法框架下循環(huán)搜索,至此則完成優(yōu)化過程中的一次優(yōu)化前進(jìn)。在總的優(yōu)化算法框架下多次迭代直至收斂,取最小值作為目標(biāo)調(diào)度方案。

4 算例仿真

為充分驗(yàn)證禁忌算法框架下多重編碼策略的重調(diào)度算法的有效性,在PC機(jī)上,采用Matlab 2014a軟件實(shí)施仿真。調(diào)度模型以某型航母為例,考慮艦載機(jī)多機(jī)多波次循環(huán)出動(dòng)等典型場景,在仿真過程中假設(shè)所有參與飛行的艦載機(jī)不發(fā)生故障。各工序保障時(shí)間取值來源于實(shí)踐經(jīng)驗(yàn)平均值,參數(shù)取值如下:彈藥加載時(shí)間25 min,暖機(jī)時(shí)長5 min,艦載機(jī)滑行用時(shí)1 min,慣導(dǎo)對準(zhǔn)作業(yè)時(shí)間13 min,加油時(shí)長取26 min(該值隨加油量變化,此處采用固定值仿真)。保障資源移動(dòng)速度方面,加油保障組的甲板移動(dòng)速度取為1 m/s,彈藥保障組的甲板移動(dòng)速度為1.5 m/s,轉(zhuǎn)運(yùn)組空載和牽引時(shí)的速度分別為1.5 m/s和0.7 m/s。

仿真研究基于飛行甲板12架艦載機(jī)的想定而進(jìn)行,彈藥加載保障組數(shù)量NGD=5、轉(zhuǎn)運(yùn)小組數(shù)量NZY=3,完好情況下飛行甲板加油保障點(diǎn)數(shù)量NJY=9。初始狀態(tài)下,甲板艦載機(jī)停放信息如表1所示,飛機(jī)站位數(shù)字依一定規(guī)律標(biāo)號(hào),分別與甲板停機(jī)位一一對應(yīng)。

表1 甲板艦載機(jī)初始位置信息Table 1 Aircraft initial position status on flight deck

續(xù)表1Continued Table 1

根據(jù)艦載機(jī)在甲板上的停放位置,按啟發(fā)式規(guī)則和禁忌算法結(jié)合的方法產(chǎn)生靜態(tài)甲板調(diào)度方案,如圖6所示,用于后續(xù)對算法結(jié)果的對比分析。

圖6 12機(jī)動(dòng)態(tài)調(diào)度初始調(diào)度甘特圖Fig.6 Gantt chart of 12 aircraft dynamic scheduling initial schedule

(1) 對原調(diào)度方案在執(zhí)行過程中,在1 000 s時(shí)刻下,模擬掛彈保障第3組出現(xiàn)故障但可完成當(dāng)前正在執(zhí)行任務(wù)的情況。進(jìn)入動(dòng)態(tài)調(diào)度算法后,基于當(dāng)前各艦載機(jī)、保障組工序執(zhí)行情況,生成動(dòng)態(tài)調(diào)度方案如圖7所示。

圖7 保障組故障動(dòng)態(tài)重調(diào)度甘特圖Fig.7 Gantt chart of support group failure dynamic rescheduling

通過調(diào)度甘特圖圖6可發(fā)現(xiàn),在1 000 s時(shí)刻進(jìn)入重調(diào)度算法時(shí),由于編號(hào)為P2至P11的艦載機(jī)當(dāng)前有正在執(zhí)行的工序,故所生成的重調(diào)度甘特圖圖7中該部分艦載機(jī)的當(dāng)前工序未受影響,而當(dāng)前工序的后續(xù)工序調(diào)度安排產(chǎn)生了變化。編號(hào)為P1和P12的艦載機(jī)由于在1 000 s時(shí)刻下沒有正在執(zhí)行的工序,因此在進(jìn)入重調(diào)度算法后立即產(chǎn)生了新的調(diào)度方案。由于保障組203故障,通過重調(diào)度甘特圖圖7可見后續(xù)保障中無該保障組參與,通過對比分析可證實(shí)算法的有效性。

(2) 在原調(diào)度方案執(zhí)行過程中,在1 000 s時(shí)刻下,增加掛彈保障第6組,所在甲板機(jī)位為12號(hào),動(dòng)態(tài)調(diào)度方案如圖8所示。

圖8 增加保障組動(dòng)態(tài)重調(diào)度甘特圖Fig.8 Gantt chart of increased support group dynamic rescheduling

新增加掛彈保障組第6組,依據(jù)編碼規(guī)則,保障組對應(yīng)編號(hào)為206,通過對比調(diào)度甘特圖圖6可發(fā)現(xiàn),艦載機(jī)P2至P11的當(dāng)前工序無影響,在當(dāng)前工序完成時(shí)刻后,后續(xù)調(diào)度方案產(chǎn)生變化,艦載機(jī)P1和P12在1 000 s時(shí)刻下無正在執(zhí)行工序,則在重調(diào)度時(shí)刻產(chǎn)生新的調(diào)度方案,且在后續(xù)調(diào)度方案中,保障組206參與調(diào)度任務(wù)安排,如圖8中紅色方框所示。通過對比分析可證實(shí)算法的有效性。

(3)在原調(diào)度方案執(zhí)行過程中,在1 000 s時(shí)刻下,編號(hào)為P5的艦載機(jī)機(jī)務(wù)檢查出現(xiàn)故障,動(dòng)態(tài)調(diào)度方案如圖9所示。

圖9 艦載機(jī)故障動(dòng)態(tài)重調(diào)度甘特圖Fig.9 Gantt chart of aircraft failure dynamic reschedule

通過重調(diào)度甘特圖圖9可發(fā)現(xiàn),在1 000 s時(shí)刻下艦載機(jī)P5發(fā)現(xiàn)故障,立即停止了當(dāng)前工序的進(jìn)行,101保障組即刻釋放,且艦載機(jī)P5不再參與原定的后續(xù)調(diào)度。通過對比靜態(tài)調(diào)度甘特圖圖6可見,P5艦載機(jī)原定在加油保障工序完成后進(jìn)行轉(zhuǎn)運(yùn)工序,由保障組302進(jìn)行。在1 000 s時(shí)刻下產(chǎn)生的新調(diào)度方案中,302保障組負(fù)責(zé)在艦載機(jī)P11完成當(dāng)前加油工序后對其進(jìn)行轉(zhuǎn)運(yùn)工作,通過對比分析可證實(shí)算法的有效性。

(4) 在原調(diào)度方案執(zhí)行過程中,在2 200 s時(shí)刻下,增加編號(hào)為13的艦載機(jī),機(jī)位在9號(hào),動(dòng)態(tài)調(diào)度方案如圖10所示。

圖10 新增艦載機(jī)動(dòng)態(tài)重調(diào)度甘特圖Fig.10 Gantt chart of increased aircraft dynamic reschedule

由于艦載機(jī)P13所在9號(hào)機(jī)位可進(jìn)行發(fā)動(dòng)機(jī)的啟動(dòng)、暖機(jī)工序,因此起飛前保障無需進(jìn)行轉(zhuǎn)運(yùn)工序,產(chǎn)生重調(diào)度甘特度圖圖10。雖然在2 000 s時(shí)刻下進(jìn)行重調(diào)度計(jì)算,但由于當(dāng)前工序執(zhí)行的飽和狀態(tài),艦載機(jī)P13加油工序由加油保障組103完成對艦載機(jī)P4的加油作業(yè)后進(jìn)行,如圖10內(nèi)紅色方框及對應(yīng)虛線所示,通過對比分析可證實(shí)算法的有效性。

(5)在原調(diào)度方案執(zhí)行過程中,在1 000 s時(shí)刻下,艦載機(jī)P11號(hào)加油任務(wù)由原定25 min延遲至40 min,動(dòng)態(tài)調(diào)度方案如圖11所示。

圖11 任務(wù)延遲動(dòng)態(tài)重調(diào)度甘特圖Fig.11 Gantt chart of task delay dynamic reschedule

由圖11可見,在1 000 s時(shí)刻重調(diào)度算法所生成的重調(diào)度甘特圖中,艦載機(jī)P11的當(dāng)前加油工序時(shí)間由初始靜態(tài)調(diào)度甘特圖圖8中的25 min延遲至40 min,如紅色方框內(nèi)所示,且各艦載機(jī)當(dāng)前正在執(zhí)行的工序未產(chǎn)生影響。在各艦載機(jī)當(dāng)前工序的釋放時(shí)刻以后,產(chǎn)生新的調(diào)度方案,通過對比分析可證實(shí)算法的有效性。

通過對比其他算法執(zhí)行結(jié)果,算法運(yùn)行的最優(yōu)解與消耗時(shí)間匯總?cè)绫?所示。

表2 算法性能對比Table 2 Algorithm performance comparison

通過仿真結(jié)果可以看出,本文算法最終所得結(jié)果近似趨同于全局搜索,得到當(dāng)前狀態(tài)下的最佳保障調(diào)度方案,且所消耗時(shí)間遠(yuǎn)小于其他算法求解所需時(shí)間,因此本文所設(shè)計(jì)的動(dòng)態(tài)調(diào)度優(yōu)化算法可在較短的時(shí)間內(nèi)提供一個(gè)較優(yōu)的甲板艦載機(jī)調(diào)度方案,是獲得甲板保障調(diào)度方案的有效算法。

5 結(jié) 論

針對多種擾動(dòng)下的艦載機(jī)多機(jī)循環(huán)批次出動(dòng)甲板作業(yè)的動(dòng)態(tài)調(diào)度問題,從甲板勤務(wù)作業(yè)視角建模,降低調(diào)度復(fù)雜性。采用基于禁忌優(yōu)化算法框架下的多重編碼、工作日志表搜索等策略,獲得了一種考慮資源分配、機(jī)位分配等因素的調(diào)度問題求解算法。

該算法不僅可用于航母保障作業(yè)調(diào)度,也可適用于器械加工、路徑選擇等擾動(dòng)事件頻發(fā)且對總消耗時(shí)間較為敏感的調(diào)度領(lǐng)域。由于算法執(zhí)行消耗時(shí)間少,可適用于工序時(shí)間短、前后工序緊密相連的密集型調(diào)度領(lǐng)域。

算法在拓展運(yùn)行至不同調(diào)度環(huán)境的過程中,需要對編碼部分及調(diào)度排班表的具體設(shè)計(jì)進(jìn)行更改,做出適合目標(biāo)運(yùn)行環(huán)境的設(shè)計(jì)。算法的總體結(jié)構(gòu)大體一致,難點(diǎn)在于算法的編寫人員需充分理解該算法在執(zhí)行過程中的算法設(shè)計(jì)內(nèi)容及原理。該算法的優(yōu)點(diǎn)在于算法的通用性較強(qiáng),無需做出較大改動(dòng),因此研究結(jié)果實(shí)現(xiàn)的可能性較大。