基于改進(jìn)禁忌搜索算法的艦載機(jī)保障作業(yè)調(diào)度

李夢龍，余明暉

華中科技大學(xué)自動化學(xué)院，湖北武漢430074

0 引 言

艦載機(jī)作為艦空母艦（簡稱“航母”）的核心作戰(zhàn)裝備，對其綜合作戰(zhàn)能力的影響很大［1］，且艦載機(jī)的出動能力是判斷航母綜合作戰(zhàn)能力的關(guān)鍵指標(biāo)［2］。因此，航母的總體設(shè)計始終圍繞著如何有效提高艦載機(jī)的出動能力這一戰(zhàn)技指標(biāo)而展開［3］。當(dāng)艦載機(jī)通過彈射器起飛執(zhí)行任務(wù)之前，必須嚴(yán)格按照預(yù)先制定的甲板作業(yè)流程進(jìn)行艦面保障［4］，故艦載機(jī)的出動能力與航母甲板上的保障作業(yè)調(diào)度策略密切相關(guān)。航母甲板上的有限保障資源、多變作業(yè)環(huán)境和復(fù)雜作業(yè)流程等決定了艦載機(jī)保障作業(yè)調(diào)度是制約艦載機(jī)出動能力的關(guān)鍵因素［5］。

艦載機(jī)的保障作業(yè)調(diào)度問題，即是在有限的甲板空間和保障資源等約束條件下，為艦載機(jī)提供合理的保障站位和保障次序，以縮短艦載機(jī)的牽引距離并減少保障作業(yè)總時間，從而確保在艦載機(jī)起飛之前完成保障任務(wù)，這實際上屬于資源約束的優(yōu)化調(diào)度問題［5］。

目前，國內(nèi)外學(xué)者針對航母甲板保障作業(yè)調(diào)度問題開展了廣泛的研究。例如，美國麻省理工學(xué)院計算機(jī)科學(xué)與人工智能實驗室開發(fā)了可以人機(jī)交互的航母甲板作業(yè)規(guī)劃決策支持系統(tǒng)（Deck Course of Action Planner，DCAP），可用于對艦載機(jī)保障作業(yè)調(diào)度進(jìn)行智能決策［6］；Dastidar等［7］提出了基于排隊網(wǎng)絡(luò)的分布式策略，可用于解決航母甲板的調(diào)度問題；韓慶田等［8］運用遺傳算法來解決艦載機(jī)的保障作業(yè)問題，直觀地提出了艦載機(jī)的保障流程方案；司維超等［9］建立了艦載機(jī)出動調(diào)度的基礎(chǔ)模型，并利用融合了多種群和混沌局部搜索后改進(jìn)的粒子群算法對調(diào)度問題進(jìn)行了求解；韓維等［10］建立了多目標(biāo)的多機(jī)一體化機(jī)務(wù)保障模型，提出了一種自適應(yīng)混合差分進(jìn)化算法，可以提高多目標(biāo)艦載機(jī)的機(jī)務(wù)保障效率。

目前，國內(nèi)外主要采用計算仿真方法和智能優(yōu)化算法來求解艦載機(jī)的保障作業(yè)調(diào)度問題。其中，計算仿真方法一般通過邏輯關(guān)系和參數(shù)選擇來構(gòu)建模型，但不同的系統(tǒng)模型會導(dǎo)致不同的結(jié)論；智能優(yōu)化算法的計算速度較快，能夠和其他算法相結(jié)合，和仿真方法相比更具優(yōu)勢。同時，現(xiàn)有的研究工作主要集中在艦載機(jī)的保障站位分配上，鮮有針對資源沖突時保障次序調(diào)度方面的研究，也沒有考慮到各架次艦載機(jī)的起飛時間對保障計劃的影響。本文將綜合考慮艦載機(jī)保障作業(yè)、起飛時間和轉(zhuǎn)運時間等因素，對保障次序進(jìn)行調(diào)度優(yōu)化，用以在較短的計算時間內(nèi)求解可行的調(diào)度方案。鑒于艦載機(jī)保障作業(yè)調(diào)度和車間作業(yè)調(diào)度非常相似，擬將艦載機(jī)保障作業(yè)調(diào)度問題轉(zhuǎn)換成車間作業(yè)調(diào)度問題，并通過智能優(yōu)化算法對其進(jìn)行求解，從而提出一種效率更高的基于禁忌搜索的改進(jìn)算法。

1 模型描述與轉(zhuǎn)換

1.1 艦載機(jī)保障作業(yè)調(diào)度問題

本文將以“尼米茲”級航母的傳統(tǒng)多站式保障作為參考，并對其進(jìn)行適當(dāng)?shù)暮喕幚恚床豢紤]保障作業(yè)時的干擾因素和多個波次之間的影響，并假設(shè)各架艦載機(jī)完成保障作業(yè)的站位和次序已提前由調(diào)度人員制定完畢。

假設(shè)在一個波次中有2架艦載機(jī)（設(shè)為F1和F2）需起飛執(zhí)行任務(wù)，該波次的起飛時間為8：00，起飛時間間隔為10 min（即F1的起飛時間不應(yīng)晚于8：00，F(xiàn)2的起飛時間不應(yīng)晚于8：10），且在起飛之前需要完成補(bǔ)充燃料/滑油/特種液體和氣體、充電、掛載彈藥等保障任務(wù)［11］。執(zhí)行保障任務(wù)分串行和并行2種關(guān)系：串行指多個保障任務(wù)只能依次完成，總的完成時間等于單個保障任務(wù)完成時間之和；并行指多個保障任務(wù)可以同時進(jìn)行，總的完成時間等于單個保障任務(wù)完成時間的最大值。由于真實的保障作業(yè)完成時間會在某個范圍內(nèi)動態(tài)變化，并具有一定的隨機(jī)性，故本文僅考慮時間波動區(qū)間較小的情況，并取近似值作為保障完成時間。假設(shè)2架艦載機(jī)的保障任務(wù)分別在5個站位（A1，A2，A3，A4，A5）上完成，每個站位可以提供若干項保障服務(wù)，但在同一時間只能給1架艦載機(jī)提供保障。假設(shè)調(diào)度流程為：F1依次到A1，A2，A4站位完成保障服務(wù)；F2依次到 A3，A2，A5站位完成保障服務(wù)。每架艦載機(jī)完成保障作業(yè)的次序、站位、任務(wù)及時間如表1所示。當(dāng)艦載機(jī)在一個站位上完成保障作業(yè)之后，就會被牽引到下一個保障站位，故牽引的轉(zhuǎn)運時間和牽引距離成正比。本文忽略艦載機(jī)的彈射起飛時間，故其保障作業(yè)完成時間即起飛時間。

表1 艦載機(jī)的保障作業(yè)Table 1 Support operation of carrier-based aircraft

由于每個站位在同一時間只能給1架艦載機(jī)提供保障服務(wù)，當(dāng)2架艦載機(jī)需要在5個站位上完成各自的保障作業(yè)時，如果不進(jìn)行調(diào)度，就有可能出現(xiàn)2架艦載機(jī)同時在同一個站位上進(jìn)行保障作業(yè)的問題，如圖1所示的A2站位陰影段。為了解決站位沖突問題，必須使保障作業(yè)總時間盡可能短，并且需同時滿足以下條件：

1）每架艦載機(jī)需按照預(yù)先設(shè)定的保障作業(yè)次序，依次到每個站位上完成保障作業(yè)。

2）單個站位在同一時刻只能服務(wù)1架艦載機(jī)，且單架艦載機(jī)在同一時刻只能在1個站位上進(jìn)行保障。

3）每架艦載機(jī)必須在起飛之前完成所有的保障作業(yè)。

圖1 不可行解Fig.1 Infeasible schedule

1.2 車間作業(yè)調(diào)度問題

車間作業(yè)調(diào)度問題（Job-shop Scheduling Problem，JSP）是一個經(jīng)典的生產(chǎn)調(diào)度問題，也是一個典型的NP-hard問題，其中NP是指非確定性多項式（Non-deterministic Polynomial，NP）。該問題起源于加工制造行業(yè)，目前在交通運輸、網(wǎng)絡(luò)通信等領(lǐng)域也得到了廣泛應(yīng)用。車間作業(yè)調(diào)度問題可以描述為：給定若干個工件和若干臺機(jī)器，每個工件按照預(yù)先設(shè)定的加工工藝路線，依次到各臺機(jī)器上完成加工任務(wù)。由于每臺機(jī)器上都會有若干個工件需要加工，故調(diào)度方案需要確定各臺機(jī)器的工件加工次序，以使最大完工時間（Makes?pan）最短。

車間作業(yè)調(diào)度問題的目標(biāo)函數(shù)為

車間作業(yè)調(diào)度問題的約束條件為：

式（1）～式（4）中：tn為最大完工時間；ti和tj分別為工序i和工序j的開始時間；O={0，1，…，n}，為工序i和工序j的集合，其中0和n為虛擬工序，工序0為起點，工序n為終點；D={d1，d2，…，dn}，為各工序的加工時間集合，其中(di，dj)∈D；A為工件本身工藝路線決定的加工次序的約束集；Ek為在機(jī)器k上進(jìn)行加工的約束集；M={1，2，…，m}為機(jī)器集合。

式（1）表示調(diào)度目標(biāo)為令最大完工時間最小化，式（2）表示工序的開始時間必須大于0，式（3）表示一個工件必須按照工藝路線依次加工，式（4）表示一臺機(jī)器在同一時間只能加工1個工件。

1.3 2個模型之間的差異及轉(zhuǎn)換

由上文可知，艦載機(jī)保障作業(yè)調(diào)度問題與車間作業(yè)調(diào)度問題非常相似，但這2個模型之間有2個不同點：

1）在車間作業(yè)調(diào)度問題中，每個工件都是從固定起始點出發(fā)，按照加工次序在不同機(jī)器上加工并到達(dá)終點，因此在不同的調(diào)度方案中，每個工件完成所有工序到達(dá)終點的時間各不相同；而在艦載機(jī)保障作業(yè)調(diào)度問題中，每架艦載機(jī)的起飛時間不同，且每架艦載機(jī)必須在起飛時間之前完成所有的保障作業(yè)。簡單而言，車間作業(yè)調(diào)度問題可以視為從固定起點到非固定終點的排序，而艦載機(jī)保障作業(yè)調(diào)度問題則將起飛時間視為固定終點，如果將其單純地轉(zhuǎn)換為車間作業(yè)調(diào)度問題，很可能得不到有效解。

2）在車間作業(yè)調(diào)度問題模型中，沒有考慮一個工件完成一項工序后，從上一臺機(jī)器移動到下一臺機(jī)器的運輸時間；而在艦載機(jī)保障作業(yè)調(diào)度問題中，轉(zhuǎn)運時間對最終調(diào)度方案的影響不容忽視，所以在調(diào)度過程中應(yīng)考慮轉(zhuǎn)運時間。

基于此，本文處理如下：將艦載機(jī)保障次序的約束逆向轉(zhuǎn)換為車間作業(yè)調(diào)度中工件的加工次序約束，每項保障作業(yè)與加工工序逆序?qū)?yīng)；將艦載機(jī)集合轉(zhuǎn)換為車間作業(yè)調(diào)度中的工件集合；在每個工件的第1項工序前插入一項虛擬工序，即取所有艦載機(jī)中最晚的起飛時間與該工件所代表的艦載機(jī)的起飛時間相減，差值作為該虛擬工序的加工時間（如果差值為0，則不插入虛擬工序）；在剩余相鄰工序之間插入一項虛擬工序，將艦載機(jī)轉(zhuǎn)運時間作為該工序的加工時間。

按照以上處理步驟，圖1即可轉(zhuǎn)換為圖2。圖2中：JOB1對應(yīng) F1，JOB2對應(yīng)F2；M1，M2，M3，M4，M5分別對應(yīng)A1，A2，A3，A4，A5，其中非灰色工序的加工時間與艦載機(jī)保障作業(yè)的時間相同；灰色節(jié)點為插入的虛擬工序，其加工機(jī)器為M0，M0是一臺可以在同一時間加工無限工件的特殊機(jī)器；JOB1中第1個灰色工序的加工時間為F2與F1起飛時間的差值，其他灰色工序的加工時間為相鄰站位之間的轉(zhuǎn)運時間。

圖2 模型轉(zhuǎn)換Fig.2 Model transformation

2 求解算法

車間作業(yè)調(diào)度問題的求解方法主要可以分為最優(yōu)化算法和和啟發(fā)式算法2種。其中最優(yōu)化算法（例如，分支定界法）的計算量非常大，難以應(yīng)用于航母甲板環(huán)境。而啟發(fā)式算法中：模擬退火算法的收斂速度過慢，搜索空間過于龐大，且溫度難以掌控；遺傳算法則有早熟和效率低下的問題；禁忌搜索（Tabu Search，TS）算法在解決了初始解、搜索策略和禁忌列表長度等問題之后，其計算效率在可接受范圍內(nèi)。故本文將以禁忌搜索算法為基礎(chǔ)，提出一種改進(jìn)啟發(fā)式算法，用以求解艦載機(jī)的保障作業(yè)調(diào)度問題。

禁忌搜索算法采用局部鄰域搜索的思想，在全局逐步尋優(yōu)，其搜索過程如圖3所示。禁忌搜索的主要思想是對初始解的鄰域進(jìn)行搜索，并找到候選解作為當(dāng)前解，采用禁忌列表存儲已搜索過的區(qū)域信息，從而在之后的迭代搜索中避免回到原先已搜索過的區(qū)域。禁忌搜索算法主要有6個基本要素：初始解和目標(biāo)函數(shù)、鄰域結(jié)構(gòu)、候選解、禁忌列表及長度、藐視準(zhǔn)則、終止規(guī)則［12］。本文提出的改進(jìn)禁忌搜索算法（Improved Tabu Search，ITS）將主要圍繞禁忌列表的長度、產(chǎn)生初始解、加入分散搜索策略和集中搜索策略等開展工作。

1）禁忌列表。禁忌列表用于存儲被禁忌的對象，以防止重復(fù)搜索之前已搜索過的區(qū)域。如果禁忌列表的長度過長，搜索將被抑制；如果長度過短，則將導(dǎo)致重復(fù)搜索并進(jìn)入循環(huán)［13］。改進(jìn)的禁忌搜索算法將采用動態(tài)的禁忌列表長度L，其值將在Lmin和Lmax這2個極限值之間動態(tài)變化，具體如下：

（1）如果找到比當(dāng)前解更優(yōu)的解，將L-1作為禁忌列表的長度，并保持L≥Lmin。

（2）如果沒有找到比當(dāng)前解更優(yōu)的解，將L+1作為禁忌列表的長度，并保持L≤Lmax。

圖3 禁忌搜索流程Fig.3 Tabu search process

（3）假設(shè)禁忌列表長度L的初始值為Lmin，其中Lmin=2w/3，Lmax=2w，w為加工車間的工件數(shù)量。

2）產(chǎn)生初始解。在禁忌搜索之前必須給定一個初始解，而一個好的初始解可以顯著提升禁忌搜索算法的性能［12］?？紤]到移動瓶頸法不僅可以快速求解車間作業(yè)問題，而且其得出的解比SPT和FCFS等優(yōu)先分配準(zhǔn)則的解更加優(yōu)秀，所以本文將采用移動瓶頸法為禁忌搜索提供初始解。移動瓶頸算法是一種啟發(fā)式算法，通過在所有機(jī)器中找到最大延遲的瓶頸機(jī)器，然后對其進(jìn)行單機(jī)調(diào)度，調(diào)度完成后再對剩余機(jī)器重復(fù)以上步驟。

3）分散搜索策略。分散搜索策略可以對解集的區(qū)域進(jìn)行廣泛搜索，以避免陷入局部搜索。如果在某個區(qū)域一直沒有找到比當(dāng)前最優(yōu)解更好的解，則將重新在新的區(qū)域開始搜索。如果在某次搜索中一直沒有找到比當(dāng)前調(diào)度方案的最大完工時間更短的方案，則應(yīng)記錄其迭代搜索次數(shù)，當(dāng)該次數(shù)達(dá)到預(yù)先設(shè)定的上限時，就找到一個新的解作為下一次迭代的初始解，然后清空禁忌列表。

4）集中搜索策略。當(dāng)最優(yōu)解被更新時，如果進(jìn)一步搜索當(dāng)前區(qū)域，則有可能找到更多的最優(yōu)解。如果在局部區(qū)域中發(fā)現(xiàn)了比當(dāng)前最優(yōu)解更好的解，應(yīng)將最優(yōu)解更新并清空禁忌列表，用以使當(dāng)前區(qū)域的后期搜索更加自由。

在將艦載機(jī)保障作業(yè)調(diào)度問題轉(zhuǎn)換為車間作業(yè)調(diào)度問題的過程中，本文引入了1臺虛擬機(jī)器M0。由于M0的容量無限大，允許在同一時間加工無限工件，故M0的工件加工次序?qū)⒉挥绊懣偟募庸r間。因此，在改進(jìn)禁忌搜索算法中將不調(diào)換M0上的工件加工次序，以節(jié)省計算時間。

3 實驗仿真結(jié)果

為了驗證本文算法的改進(jìn)效果，參考“尼米茲”級航母在1997年的“高潮演習(xí)”資料和相關(guān)文獻(xiàn)［14-15］，設(shè)計了2個實例。實例1中艦載機(jī)保障作業(yè)的站位和時間如表2所示，艦載機(jī)到下一個站位的轉(zhuǎn)運時間與站位之間的距離成正比。假設(shè)在某個波次需要出動6架艦載機(jī)（F1～F6），每架艦載機(jī)起飛前必須完成加油、飛行準(zhǔn)備、充電、掛彈這4項保障任務(wù)，每項保障作業(yè)均有2個保障站位（Y1/Y2，P1/P2，S1/S2，G1/G2）提供服務(wù)。該波次的起飛時間起點為10：35，起飛間隔為5 min。

表2 艦載機(jī)保障作業(yè)次序（實例1）Table 2 Deck operation（case 1）

本實驗平臺采用Java語言開發(fā)，運行的機(jī)器環(huán)境為Core i5-6200U，CPU主頻為2.3 GHz，內(nèi)存為8 GB，操作系統(tǒng)為Windows 10。由于禁忌搜索算法對初始解的依賴程度較高，為了驗證移動瓶頸算法對禁忌搜索效率的改進(jìn)效果，將以改進(jìn)的禁忌搜索算法為基礎(chǔ)，分別采用隨機(jī)解（ITS-R）、FCFS規(guī)則產(chǎn)生的解（ITS-FCFS）和移動瓶頸算法產(chǎn)生的解（ITS-M）作為初始解來進(jìn)行計算對比。禁忌搜索算法的終止規(guī)則為：當(dāng)前最優(yōu)解的更新次數(shù)不超過60次。表3所示為10次重復(fù)獨立計算的對比結(jié)果，其中：ITS-R對應(yīng)的最優(yōu)解平均值為110，計算時間平均值為0.964 s；ITS-FCFS對應(yīng)的最優(yōu)解平均值為110，計算時間平均值為0.825 s；ITS-M對應(yīng)的最優(yōu)解平均值為110，計算時間平均值為0.682 s。

由表3可知，雖然3種初始解對應(yīng)的最優(yōu)解相同，但采用移動瓶頸算法產(chǎn)生初始解的計算效率最高。因此，移動瓶頸算法產(chǎn)生的初始解可以有效改進(jìn)禁忌搜索算法，其甘特圖如圖4所示。圖中灰色部分表示艦載機(jī)從上一個站位到下一個站位的轉(zhuǎn)運過程。改進(jìn)算法求解的保障作業(yè)方案總時間為110 min，整個保障作業(yè)流程從9：10（F2加油）一直持續(xù)到11：00（F6起飛）。

表3 不同初始解的計算結(jié)果對比Table 3 Comparison of calculation results of different initial solutions

圖4 實例1的甘特圖Fig.4 Gantt chart of case 1

為了對比ITS算法和傳統(tǒng)TS算法的計算效率，分別采用這2種算法對實例1進(jìn)行了10次重復(fù)獨立計算，其對比結(jié)果如表4。由表4可知：ITS算法對應(yīng)的最優(yōu)解平均值為110，計算時間平均值為0.682 s；TS算法對應(yīng)的最優(yōu)解平均值為110.1，計算時間平均值為1.029 s。因此，ITS算法的計算速度比TS算法更快，且TS算法偶爾無法找到最優(yōu)解110。

表4 ITS算法和TS算法的對比（實例1）Table 4 Comparison between ITS algorithm and TSalgorithm（case 1）

為進(jìn)一步驗證不同數(shù)量艦載機(jī)出動情況下的計算性能，本文還設(shè)計了實例2。假設(shè)出動10架艦載機(jī)，起飛時間為10：42，起飛間隔為2 min，保障作業(yè)安排如表5所示。

表5 艦載機(jī)保障作業(yè)次序（實例2）Table 5 Deck operation（case 2）

針對實例2，ITS算法和傳統(tǒng)TS算法的計算性能對比如表6所示。其中：ITS算法對應(yīng)的最優(yōu)解平均值為145，計算時間平均值為3.73 s；TS算法對應(yīng)的最優(yōu)解平均值為146.6，計算時間平均值為4.613 s。因此，ITS算法的計算效率和優(yōu)化效果均優(yōu)于TS算法。

表6 ITS算法和TS算法的對比（實例2）Table 6 Comparison between ITS algorithm and TSalgorithm（case 2）

4 結(jié) 語

本文將艦載機(jī)保障作業(yè)調(diào)度問題轉(zhuǎn)換成車間作業(yè)調(diào)度問題，建立了保障作業(yè)調(diào)度模型，并提出了一種改進(jìn)的禁忌搜索算法對該模型進(jìn)行求解。相對于傳統(tǒng)禁忌搜索算法，改進(jìn)算法采用了移動

瓶頸算法得出初始解，增加了分散搜索策略和集中搜索策略，并使禁忌列表的長度隨搜索進(jìn)行動態(tài)變化。不同規(guī)模的實例驗證計算結(jié)果表明，改進(jìn)的禁忌搜索算法能夠有效優(yōu)化艦載機(jī)的保障作業(yè)流程，并且其優(yōu)化結(jié)果和計算速度均優(yōu)于傳統(tǒng)的禁忌搜索算法。