李夢龍，余明暉

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

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

3）每架艦載機必須在起飛之前完成所有的保障作業(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)度問題可以描述為：給定若干個工件和若干臺機器，每個工件按照預(yù)先設(shè)定的加工工藝路線，依次到各臺機器上完成加工任務(wù)。由于每臺機器上都會有若干個工件需要加工，故調(diào)度方案需要確定各臺機器的工件加工次序，以使最大完工時間（Makes?pan）最短。

車間作業(yè)調(dià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為在機器k上進行加工的約束集；M={1，2，…，m}為機器集合。

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

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

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

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

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

基于此，本文處理如下：將艦載機保障次序的約束逆向轉(zhuǎn)換為車間作業(yè)調(diào)度中工件的加工次序約束，每項保障作業(yè)與加工工序逆序?qū)?yīng)；將艦載機集合轉(zhuǎn)換為車間作業(yè)調(diào)度中的工件集合；在每個工件的第1項工序前插入一項虛擬工序，即取所有艦載機中最晚的起飛時間與該工件所代表的艦載機的起飛時間相減，差值作為該虛擬工序的加工時間（如果差值為0，則不插入虛擬工序）；在剩余相鄰工序之間插入一項虛擬工序，將艦載機轉(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，其中非灰色工序的加工時間與艦載機保障作業(yè)的時間相同；灰色節(jié)點為插入的虛擬工序，其加工機器為M0，M0是一臺可以在同一時間加工無限工件的特殊機器；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ǔ)，提出一種改進啟發(fā)式算法，用以求解艦載機的保障作業(yè)調(diào)度問題。

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

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

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

（2）如果沒有找到比當前解更優(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)先分配準則的解更加優(yōu)秀，所以本文將采用移動瓶頸法為禁忌搜索提供初始解。移動瓶頸算法是一種啟發(fā)式算法，通過在所有機器中找到最大延遲的瓶頸機器，然后對其進行單機調(diào)度，調(diào)度完成后再對剩余機器重復(fù)以上步驟。

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

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

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

3 實驗仿真結(jié)果

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

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

本實驗平臺采用Java語言開發(fā)，運行的機器環(huán)境為Core i5-6200U，CPU主頻為2.3 GHz，內(nèi)存為8 GB，操作系統(tǒng)為Windows 10。由于禁忌搜索算法對初始解的依賴程度較高，為了驗證移動瓶頸算法對禁忌搜索效率的改進效果，將以改進的禁忌搜索算法為基礎(chǔ)，分別采用隨機解（ITS-R）、FCFS規(guī)則產(chǎn)生的解（ITS-FCFS）和移動瓶頸算法產(chǎn)生的解（ITS-M）作為初始解來進行計算對比。禁忌搜索算法的終止規(guī)則為：當前最優(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)生的初始解可以有效改進禁忌搜索算法，其甘特圖如圖4所示。圖中灰色部分表示艦載機從上一個站位到下一個站位的轉(zhuǎ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進行了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）

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

表5 艦載機保障作業(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é) 語

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

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