基于禁忌算法的艦載機甲板作業動態調度優化算法

范加利, 黃 葵,*, 朱興動, 孟楊凱

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

0 引 言

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

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

針對艦載機甲板動態調度問題,本文通過建立甲板作業模型與調度數學模型,對調度過程存在的潛在擾動事件進行分析,形成不同的重調度窗口,并制定相應的重調度解決策略,同時設計了動態調度求解算法的具體內容及操作方法。

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

1 艦載機再次出動保障調度模型

1.1 艦載機甲板作業描述

艦載機保障調度目標是使批次艦載機完成甲板保障后全部起飛的所用時間最小化,記所用時間為C。典型的艦載機甲板作業流程如圖1所示。

圖1 艦載機甲板作業流程圖Fig.1 Flowchart of carrier aircraft flight deck operation

暖機、慣性導航對準等作業屬于起飛前必做的作業,調運、滑行、加油、武器加載等作業屬于視情開展的作業內容[11]。暖機是利用艦面電源起動飛機發動機,對飛機操縱等性能進行檢查[12]?；惺侵笍谋Ｕ蠙C位滑行到起飛機位的過程[13]。

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

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

(2) 慣導對準、暖機、滑行3項作業應待艦載機轉入暖機位后依次開展,且任一架艦載機的這3道工序順序是一致的。

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

(4) 飛行甲板加油保障點數量和位置均固定,各保障點所能保障的停機位范圍已知,且部分機位可活動2個或2個以上加油點保障。

(5) 暖機位當前被占用的情況下,不能被選擇作為其他飛機的目標轉運機位。

(6) 對于調運作業而言,必須確保存在可行的轉運作業路徑。

1.2 艦載機甲板作業調度的數學模型

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

根據約束條件和實際作業過程,建立抽象模型如下[22]。

符號描述:記循環出動過程中,上一次完成艦載機著艦至下一次完成最后一架艦載機起飛所需的最長保障作業時間為Cmax。一批次艦載機完成保障作業時間定義為,批次中最后一架艦載機完成機位停靠到該批次艦載機最后一架艦載機完成起飛所需的時間,也相當于再次出動準備時間。記艦載機i從實施第1道保障作業到完成起飛所用時間為Ci。

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

目標函數:

F=minCmax

(1)

約束條件:

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

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

(10)

模型中,式(1)為目標函數;式(2)～式(10)為約束條件。式(2)和式(3)為對艦載機作業工序唯一執行性的約束;式(4)是對艦載機作業工序前后關系的約束,針對作業集中艦載機的導航對準、暖機、滑行、起飛等4項作業;式(5)確保互斥工序不能同時安排執行;式(6)用于表達某一資源在飛行甲板配置的可用總數量的約束,該數量可能因為資源故障等擾動因素而變化;式(9)表達了任一保障資源不可同時服務兩架艦載機;式(8)表達了對于同一架艦載機具有緊前緊后關系的保障作業工序,開始與結束時間必須滿足的間隔時間約束;式(7)確保對于任一架艦載機的保障,加油作業和彈藥加載不能同時進行,調運與其他任何作業不同時進行;式(10)表示艦載機轉運需滿足的路徑可行條件。

2 動態調度方法

2.1 重調度窗口與策略制定

重調度窗口是調度基于突發離散事件進入重調度系統的入口分類,由于采用事件驅動作為重調度策略,因此重調度窗口的預設以及窗口下相應解決辦法的預設必不可少,具體內容如下。

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

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

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

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

(5) 保障工序完成時間發生變化。適用于當前保障工作實際完成時間早于或晚于原調度方案中預計的完成時間,或對工序保障的計劃執行所需時間發生改變,如由計劃所持的艦載導彈型號發生改變導致工序計劃時間改變的情況。該情況下,需設置偏離閥值,首先計算實際情況與原調度計劃的偏離程度。若偏離程度超出閥值,則進入重調度系統,根據甲板保障組實際釋放時間與改變工序進行的計劃所需時間,進入重調度計算。若未超出閥值,則不進入重調度系統。

2.2 時間變化偏離程度計算

在針對保障完成時間變化的重調度窗口中,當保障工作實際完成時間早于或晚于原調度方案中預計的完成時間,或工序保障的計劃執行所需時間發生改變時,須首先依據相應編碼進行偏離程度計算。在偏離程度大于相應限制情況下進入重調度系統執行重調度方案計算。否則,對原調度方案進行時間平移。偏離程度Δc計算方式具體如下。

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

Δc=edij(new)-edij

(11)

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

Δc≥sti(j+1)-edij

(12)

Δc≥rstm+1-redm

(13)

式中:redm為該保障小組在調度計劃中當前任務的計劃完成時間;sti(j+1)為保障調度計劃中艦載機出現延遲工序的后一保障工序的開始時間;rstm+1為該延遲工序的對應保障組在調度計劃中的下一保障任務的開始時間。

依據判別式計算,若滿足二者其中之一,則進入重調度算法求解優化重調度方案。

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

Δc=edij-edij(new)

(14)

對偏離程度Δc進行重調度判別計算,公式如下:

∑NRs+1

(15)

∑NRs=Ns,edij

(16)

式中:NRs+1為在艦載機工序相較于原定完成時間的提前時間段內,保障調度計劃內該艦載機所提前的工序的后一工序任務的工序保障種類在該時間段內在甲板的同時進行數量;Ns+1為后一工序任務的工序保障種類的資源總量;NRs的含義為艦載機提前工序的工序保障種類的甲板的同時進行數量;Ns為該工序種類的資源總量。

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

在任務時間提前狀態下,若據判別式計算滿足二者其中之一,則進入重調度算法求解更新優化的重調度方案。

3 求解算法

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

3.1 算法流程與描述

針對甲板調度方案優化求解,對其優化研究流程的展示如圖2所示。

圖2 改進的禁忌優化算法流程圖Fig.2 Flowchart of improvement tabu optimization algorithm

算法首先根據啟發式規則,生成甲板初始調度方案,以調度排班表及甘特圖作為方案結果。然后,基于編碼的交叉算法對工作日制進行變換,全部的變換方案構成算法優化的鄰域結構,作為下一次禁忌優化算法的路徑參考。通過對工作日制的解碼計算,從中選取最優且不在禁忌表內的變換作為優化操作。同時,將此次變換計入禁忌表內,以此循環,直至達到目標迭代次數,以最優方案調度結果生成甲板調度甘特圖。

3.2 滾動調度算法設計

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

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

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

3.3 編碼策略

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

(1) 艦載機工序編碼

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

具體的編碼構造方法如構造的編碼矩陣所示:

(17)

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

(2) 機位編碼

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

式中:B和C矩陣聯合記錄甲板機位信息,B矩陣記錄艦載機的機位信息,艦載機編號與行序列一一對應,記錄艦載機所在機位;C矩陣記錄保障組的機位信息,行序列與工序種類編號一一對應,列序列與工序內的每一保障組一一對應,記錄各保障組當前所在機位。

(3) 機位約束編碼矩陣

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

3.4 調度排班策略

調度排班策略為每一甲板保障作業工序安排相應的艦載機保障順序。調度排班策略從工序的角度分配艦載機,這種策略可以提高編碼效率和搜索效率,使得調度結果更具體。調度排班表是一個n列m行的矩陣,每一行對應某一個保障工序,行中的n個元素是完成該工序的艦載機的排列順序。由于各艦載機所要接受的保障作業工序內容不一定相同,所以對于不同工序,它所對應的需實施該工序的艦載機數量不同。表內編碼值代表艦載機的機號,針對同一工序,也就是矩陣的同一行,編碼值不可能出現重復,這是因為對于任一艦載機,假設同一作業只實施一次。工序調度排班表的解碼結果如圖3所示。

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

在工序調度排班表內,僅有各工序相對應的保障順序,保障順序內無需對應工序內各保障組。原因在于,在依據調度方案不斷尋優解碼計算時,遵守左對齊解碼規則:首先各工序均依據默認編號從小至大的保障組進行艦載機編號依次選取以進行保障,當完成首輪選取后,再依據工序內各保障組的最早完工時間選取保障順序內的下一待保障艦載機。

針對規則內同一工序存在默認的保障組選擇順序及各工序在矩陣內的行順序不同對優化結果可能帶來的不利影響,可通過交叉算法在得到優化路徑時消除此影響。

調度算法的優化搜索路徑應當覆蓋調度排班表采取某種變換策略所形成的全部變換方案。對全部搜索解實施解碼計算,獲取調度的優化結果。

3.5 基于優先規則的重調度初始調度生成

當進入重調度窗口后,針對滾動調度算法,生成初始調度方案的具體步驟如下。

步驟 1創建保障組完工時間表,初始數值為進入重調度窗口的時間數值,創建空白調度排班表,生成甲板當前艦載機、保障組的工序完成狀況及相應時間、機位等信息的編碼,用于滾動調度仿真計算。

步驟 2在完工時間表內,將正在執行甲板保障工作任務對應的完工時間數值改為工序的預計完成時間。針對不同的重調度窗口,依據其對應策略,對甲板艦載機工序編碼、保障組及停機位等信息編碼做對應刷新。

步驟 3查詢獲取加油、掛彈、轉運工序完工時間表內的最小值所對應保障小組,對此保障小組進行可保障工作內容檢查及派發。在任務派發的同時,以工序為單位,將保障艦載機編號記錄于工作日制表。若此保障小組因艦載機工序約束、甲板機位約束或自身保障范圍限制等原因沒有可進行的工作任務,則跳過此保障組,選擇次最小值的保障小組重復上述過程,進行任務派發。

步驟 4在滾動調度仿真過程中,對完成新任務選擇的保障組進行編碼信息更新,包含所在機位、完工時間、保障艦載機等信息,對被選擇的艦載機進行編碼信息更新,包含工序進行記錄、工序起止時間等信息,根據艦載機涉及的轉運機位信息,實時更新停機位占用編碼。

步驟 5對完成加油、彈藥加載、調運保障作業的艦載機,直接依次安排慣導對準、暖機、滑行作業。視起飛位可用情況安排起飛作業。

步驟 6循環執行步驟2至步驟5,直至完成所有艦載機的保障作業安排。

完成上述計算,便可獲取重調度的初始優化調度方案及所對應工作日制記錄。

3.6 鄰域結構設計

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

(1) 部分映射交叉

部分映射交叉的操作方式是在確定兩行之間的數值映射關系后,將兩行的對應數值做映射變換。部分映射交叉方法與文獻[30]中交叉方法類似,在因動態調度所產生的調度排班表中,各行之間編碼的數量及內容各不相同,部分映射交叉方案的記錄必須滿足其交叉合法條件,即在兩行之間分別選取編碼作為彼此的映射關系時,兩個編碼的所在行內也必須包含映射對象的編碼。如圖4所示,在第1行選取編碼數值1、第2行選取編碼數值4作為映射關系時,因第1行存在映射對象4,第2行也存在映射對象1,即映射交叉方案合法。對滿足合法條件的交叉方案,進行行排列關系及映射關系的記錄。

圖4 動態調度部分映射交叉示意圖Fig4 Schematic diagram of dynamic scheduling partial mapping

(2) 普通交叉

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

圖5 動態調度普通交叉示意圖Fig.5 Schematic diagram of dynamic scheduling common intersections

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

其中,由交叉方案A組成的鄰域結構,是為了在艦載機待保障的工序有兩個及以上的情況下,實現對艦載機工序的保障順序交叉互換尋優,而又不引起行內編碼重復的不合法性。由交叉方案B組成的鄰域結構,是為了在同一工序中有多架待保障艦載機情況下,實現工序對艦載機的選擇順序的交叉互換尋優。通過將兩種交叉方案結合,共同組成鄰域結構,擴大解的搜索范圍,提高解的質量。

3.7 雙重禁忌表策略

在普通調度算法中,由于鄰域結構由單一的部分映射交叉方案組成,禁忌優化算法在優化過程中,也僅需單一的禁忌表實現對優化過程中被選擇的交叉方案的禁忌記錄。而由于動態調度算法的鄰域結構由兩種不同的交叉方案組成,不同的交叉方案所產生的方案記錄矩陣不同,因此在優化的過程中,需要兩個禁忌表分別記錄兩種交叉方案中被選擇的方案的禁忌值。

3.8 解碼策略

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

詳細的解碼算法步驟如下。

步驟 1創建與調度排班表對應維度的工序完工時間表,令其所有元素均為0。

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

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

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

步驟 5對完成加油、彈藥加載、調運保障作業的艦載機,直接依次安排慣導對準、暖機、滑行作業。視起飛位可用情況安排起飛作業。

步驟 6循環執行步驟2～步驟5,直至完成所有艦載機的保障作業安排。

按上述算法解碼后,對調度排班表對應的調度解執行領域變換操作,同時在禁忌表內記錄該變換方案,在禁忌算法框架下循環搜索,至此則完成優化過程中的一次優化前進。在總的優化算法框架下多次迭代直至收斂,取最小值作為目標調度方案。

4 算例仿真

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

仿真研究基于飛行甲板12架艦載機的想定而進行,彈藥加載保障組數量NGD=5、轉運小組數量NZY=3,完好情況下飛行甲板加油保障點數量NJY=9。初始狀態下,甲板艦載機停放信息如表1所示,飛機站位數字依一定規律標號,分別與甲板停機位一一對應。

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

續表1Continued Table 1

根據艦載機在甲板上的停放位置,按啟發式規則和禁忌算法結合的方法產生靜態甲板調度方案,如圖6所示,用于后續對算法結果的對比分析。

圖6 12機動態調度初始調度甘特圖Fig.6 Gantt chart of 12 aircraft dynamic scheduling initial schedule

(1) 對原調度方案在執行過程中,在1 000 s時刻下,模擬掛彈保障第3組出現故障但可完成當前正在執行任務的情況。進入動態調度算法后,基于當前各艦載機、保障組工序執行情況,生成動態調度方案如圖7所示。

圖7 保障組故障動態重調度甘特圖Fig.7 Gantt chart of support group failure dynamic rescheduling

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

(2) 在原調度方案執行過程中,在1 000 s時刻下,增加掛彈保障第6組,所在甲板機位為12號,動態調度方案如圖8所示。

圖8 增加保障組動態重調度甘特圖Fig.8 Gantt chart of increased support group dynamic rescheduling

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

(3)在原調度方案執行過程中,在1 000 s時刻下,編號為P5的艦載機機務檢查出現故障,動態調度方案如圖9所示。

圖9 艦載機故障動態重調度甘特圖Fig.9 Gantt chart of aircraft failure dynamic reschedule

通過重調度甘特圖圖9可發現,在1 000 s時刻下艦載機P5發現故障,立即停止了當前工序的進行,101保障組即刻釋放,且艦載機P5不再參與原定的后續調度。通過對比靜態調度甘特圖圖6可見,P5艦載機原定在加油保障工序完成后進行轉運工序,由保障組302進行。在1 000 s時刻下產生的新調度方案中,302保障組負責在艦載機P11完成當前加油工序后對其進行轉運工作,通過對比分析可證實算法的有效性。

(4) 在原調度方案執行過程中,在2 200 s時刻下,增加編號為13的艦載機,機位在9號,動態調度方案如圖10所示。

圖10 新增艦載機動態重調度甘特圖Fig.10 Gantt chart of increased aircraft dynamic reschedule

由于艦載機P13所在9號機位可進行發動機的啟動、暖機工序,因此起飛前保障無需進行轉運工序,產生重調度甘特度圖圖10。雖然在2 000 s時刻下進行重調度計算,但由于當前工序執行的飽和狀態,艦載機P13加油工序由加油保障組103完成對艦載機P4的加油作業后進行,如圖10內紅色方框及對應虛線所示,通過對比分析可證實算法的有效性。

(5)在原調度方案執行過程中,在1 000 s時刻下,艦載機P11號加油任務由原定25 min延遲至40 min,動態調度方案如圖11所示。

圖11 任務延遲動態重調度甘特圖Fig.11 Gantt chart of task delay dynamic reschedule

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

通過對比其他算法執行結果,算法運行的最優解與消耗時間匯總如表2所示。

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

通過仿真結果可以看出,本文算法最終所得結果近似趨同于全局搜索,得到當前狀態下的最佳保障調度方案,且所消耗時間遠小于其他算法求解所需時間,因此本文所設計的動態調度優化算法可在較短的時間內提供一個較優的甲板艦載機調度方案,是獲得甲板保障調度方案的有效算法。

5 結 論

針對多種擾動下的艦載機多機循環批次出動甲板作業的動態調度問題,從甲板勤務作業視角建模,降低調度復雜性。采用基于禁忌優化算法框架下的多重編碼、工作日志表搜索等策略,獲得了一種考慮資源分配、機位分配等因素的調度問題求解算法。

該算法不僅可用于航母保障作業調度,也可適用于器械加工、路徑選擇等擾動事件頻發且對總消耗時間較為敏感的調度領域。由于算法執行消耗時間少,可適用于工序時間短、前后工序緊密相連的密集型調度領域。

算法在拓展運行至不同調度環境的過程中,需要對編碼部分及調度排班表的具體設計進行更改,做出適合目標運行環境的設計。算法的總體結構大體一致,難點在于算法的編寫人員需充分理解該算法在執行過程中的算法設計內容及原理。該算法的優點在于算法的通用性較強,無需做出較大改動,因此研究結果實現的可能性較大。