面向維修資源分配調度的遺傳-長鼻浣熊混合優化算法

秦敏敏，劉立芳，齊小剛

（1. 西安電子科技大學 計算機科學與技術學院, 陜西 西安 710071; 2. 西安電子科技大學 數學與統計學院, 陜西西安 710071; 3. 西安市網絡建模與資源調度重點實驗室, 陜西 西安 710071）

多維修中心系統[1]以多個維修中心的優勢脫穎而出，它涉及維修檢查、維修資源供應調度和維修資源分配調度等部分，在很大程度上降低了由于系統故障[2]或者串行維修[3]所導致的長時間的維修停滯問題[4]。多維修中心系統具有兩大鮮明的優勢，其一是多維修中心系統進行維修任務時，可以并行沒有優先級限制[5]的維修任務，極大地提高維修效率，節約維修成本；另外，由于所要維修的設備所處的位置并不固定，所以單一維修系統可能會拉長維修時間，但多維修中心系統采用“就近原則”進行維修，盡可能地降低了損失，提高了維修成功的機會。另一大優勢在于多維修中心系統結合了區塊鏈的核心思想[6]，是一種“去中心化”[7]的系統。多維修系統不但彌補了單維修系統維修效率低的問題，而且還分散了敵方的攻擊目標，解決了以往單一維修后勤保障系統受到攻擊而失去后勤保障能力[8]的弊病。

在實際維修任務中，不難發現關于設備的維修任務的資源調度問題隸屬于經典資源受限項目調度問題[9-10]的范疇。

在國外的研究中，Oztemel 等[11]為求解單資源的RCPSP 問題，提出了人工蜂群算法；為了更好地處理基于無線通信與雷達系統的多核心的任務調度平臺，Krishnakumar 等[12]提出了一種關于模仿學習的方法；基于多模式的資源受限的項目調度問題，Kosztyan 等[13]提出了一種基于矩陣的新思路；針對具有優先級先后順序約束的多任務的資源受限的項目調度問題，Chakrabortty 等[14]提出一種變鄰域的啟發式搜索算法；Zaman 等[15]提出一種將浮動資源進行合理安排的方案。

在國內的研究中，田啟華等[16]在多目標理想方法的基礎上進行拓展，構建了任務的評價指標函數；鑒于資源存在空窗期的特性，陸志強等[17]針對作業的開始時間，提出了一種改進的遺傳算法。事實上，實際任務的工期只是一個預期值，并不是確定的，針對這種實際情況，謝芳等[18]建立了基于資源受限項目調度問題的馬爾可夫決策過程模型；最近，張宇哲等[19]針對所研究的問題，將傳統的整數規劃模型細化為約束主問題以及子問題，并且提出一種列生成的方法用于求解模型。最后通過實驗發現，所提出的新算法擁有較好的求解性能。

通過對國內外任務調度技術的相關研究不難發現，現階段還存在以下問題：

1）與維修設備的任務調度相關的研究較少；

2）經典靜態模型已難以滿足當下實際需求，對其進行拓展，使其更符合實際場景要求已迫在眉睫；

3）模型進行拓展之后，提出適用于新模型的改進算法至關重要。

結合多維修中心系統的優勢，以維修資源為研究對象，采用適應當下實際需求的優化目標，以合理高效的資源調度策略，建立相應的資源調度模型并提出更好的求解算法，進而更加出色地完成所部署的維修任務。

1 維修任務中的資源調度

1.1 問題描述與概念解釋

維修任務是安全保障體系的重要組分之一，是受損設備經維修操作后恢復其作戰狀態的過程。資源調度則是指在任務的流水作業執行過程中，運用計算機、人工智能以及智能優化算法等相關技術，對所涉及的維修資源進行合理地監管與分配，以盡可能地提高維修效率，降低維修成本。

在維修任務的資源調度中，會涉及如下概念：

1）工件

工件是指所要維修的目標，可能是設備、備品備件，也可能是設備的零部件。

2）工序

工序是完成一項維修任務的最小單元。就維修一個小型設備而言，包括運輸工序、修復工序、檢驗工序等。值得一提的是，工序之間存在嚴格的優先級關系，一旦工序順序發生改變，很可能導致維修任務的失敗；另外，工序一旦開始便不可中斷，否則會直接影響后續工序的執行。

3）資源

依據不同的分類標準，資源可以劃分為不同的類型。資源大致可分為兩大類，具體如圖1所示。

圖1 資源的分類Fig. 1 Classification of resources

1.2 約束條件的分析

在實際維修保障體系中，維修任務是紛繁復雜的，其發布時間具有一定的隨機性，進入維修隊列的任務也會受到新任務的影響。除此之外，多維修中心系統主要是按照維修任務管理中心的維修檢修計劃來工作的。因此，一般是在當前設備使用的空閑期進行維修，并且還得確保一定的時效性。

顯然，面向多維修中心的維修任務隸屬于動態任務發布模式范疇，在執行當前任務時，有極大可能受到新加入任務的干涉，這使得其資源約束條件相較于靜態調度問題更加嚴苛與抽象。

通過對維修任務的深入研究與分析，資源分配調度中的約束條件主要可以概括為以下4 種：

1）時間約束

多維修中心的任務是不定時發布的，任務一經發布，系統通過維修任務分析預測模塊對其需求的資源以及排隊時間等指標進行預測，并依據設備具體使用時間等指標，綜合考慮該待修設備進行維修任務的開始和截止時間。此外，維修任務必須在該時間范圍內執行，否則會造成不可估量的損失。

2）資源約束

多維修中心系統以設備的維修為主，而設備的維修過程復雜多變，通常需要多種不同類型的資源的同時參與。因維修難度以及設備需求時間等差異，維修所需資源也不盡相同。一般而言，同一時間某維修資源僅為某工序所有，在該工序執行結束后，不可再生資源被消耗，有限的資源數量減少；而可再生資源在一定范圍內可重復利用，總數量恒定。基于可再生資源可重復使用的特性，可以初步將可再生資源粗分為“空閑”與“忙碌”兩種狀態，以便后續建模等工作的順利開展。

3）模式約束

在維修活動中包含著不同種類的維修工人和維修設備，由于維修人員所掌握的技能和熟練程度的差異，所以維修人員的級別可簡單分為高級工、中級工和普通工；由于工作強度與維修難度的不同，維修設備的維修效率也存在差異。對于同一道工序，使用不同類型的資源配置方式，其實際執行時間不盡相同。假設就執行某道維修工序而言，高級工配置高效率設備只需要0.5 h 就能完成，但普工配置低效率設備則可能需要2 h 才能完成。同一工序的不同類型的資源配置方式稱為工序模式，而不同的工序模式意味著不同的維修工期。

4）優先級約束

對于維修設備而言，維修次序不是隨意的，而是具有嚴格要求的。設備的生產以及維修是廠商依據一定的規范條約嚴格執行的，維修工人必須嚴格按照要求進行損壞設備的維修，比如先拆解再分塊維修，最后整裝調試。顯然，維修工序在時序上具有優化級約束。

2 資源分配調度模型的建立

2.1 模型概述與資源調度策略

鑒于經典的RCPSP 模型已經難以滿足當下多維修中心系統保障體系的實際需求。所以，本文結合維修設備動態發布維修任務的特征，將維修任務涉及的維修資源簡單劃分為可再生資源（renewable resource，RR)和不可再生資源NRR（non-renewable resource，NRR），將維修任務抽象為RCPSP 模型中的項目，維修工序抽象為RCPSP模型中的活動。另外，本文還考慮了不同模式的選擇問題，進而構建了多模式的動態資源分配調度模型，但有如下限制：

1）考慮到維修任務具有發布時間隨機等動態任務相關的特性，故可將其視為可以實時進入維修任務管理中心并隨時等待安排維修處理的任務。另外，維修任務的執行時間必須在發布時間之后。

2）由于本文涉及的是資源受限類相關問題，所以資源并不是理想狀態下的無限資源，而是有限數量的資源。具體為使用前后數量保持不變的RR 和不可以重復使用，使用頻次與剩余數量成反比的NRR。

3）維修工序不可輕易中斷，維修任務一旦開始，涉及的資源將被占用，直至所有的維修工序均已完成，其所占用的RR 才能被釋放。

4）在資源配置階段，倘若當前可用的RR 不能滿足當前需求，那么當前工序便被掛起，直至可用的RR 數量滿足當下需求才可被重新喚醒。

5）由于實際的維修任務紛繁復雜，影響維修任務的因素頗多，所以很難準確保證維修任務所需時間，一般在維修任務規定的到期時間前后小范圍波動，則表明當前維修任務能夠順利完成。若在任務規定時間之前完成，則有一定的獎勵，否則，會有相應的懲罰。

如圖2 所示，本文所建立的多模式動態受限資源分配調度模型主要涉及這幾部分：不定時工件維修任務的發布、依據工序優先級關系所確定的作業執行次序以及不同模式的選擇與需求資源的配置。

圖2 多模式動態受限資源分配調度模型結構Fig. 2 Structure chart of multimode dynamic constrained resource allocation and scheduling model

2.2 數學模型的建立

鑒于同一符號參數被多次使用，為了方便管理與查閱，現對所建立的數學模型所涉及的符號參數進行詳細地介紹，以便理解后續相關公式的具體含義，具體如表1、2 所示。

表1 變量釋義與索引范圍Table 1 Variable definition and index range

表2 決策變量及其含義Table 2 Decision variables and their meanings

本文參考了不少學者采用的多目標加權優化的方法，采用專家評分系統進行權重的估量，具體得到如下結果：時間成本40%、經濟成本30%、資源利用率30%，所以依次可以得到1.2、0.9、0.9 這樣的系數，取三者之和記為總成本C。

其中，式（1）表示最小化總成本這一目標函數，第1 項表示時間成本、第2 項表示經濟成本、最后一項表示資源利用率；式（2～14）為約束條件，式（2）要求只有當j工序的前驅工序j′完成后才能開始；式（3）要求某一任務的某道工序一旦采用某種模式開始執行，則中途不允許進行模式的切換；式（4）和（5）指出某一任務的實際開始時間由最早工序的開始時間所決定，而某一任務的實際完成時間則由最晚工序的完成時間所決定；式（6）和（7）要求某一維修任務的實際開始時間不能早于該任務的發布時間；而某一維修任務的實際完成時間不能晚于該任務的到期時間；式（8）指出第i維修任務的工序j的實際完成時間一般由工序j開始工作時對應的時間與完成工序j所耗費的執行時間共同決定；另外，若當前閑置的可再生資源的數量不能滿足第i任務的j′工序的需求，那么需要耗費額外的等待時間lij′去等待可再生資源的釋放。與此同時，式（9）要求工序j′的實際開始運行時間Ais j′應當不早于其前驅工序j中最晚結束的時間與等待可再生資源所額外耗費的時間之和；就維修隊列中連續的兩個維修任務而言，式（10）指出第i+1維修任務的首個工序的實際開始工作時間由第i+1任務的發布時間第i任務的首個工序的實際開始執行時間以及第i+1任務的首道工序所要耗費的額外可再生資源的等待時間l(i+1)1來綜合決定；式（11）指出當第i任務的j工序在0 時刻開始執行，此時對應的空閑可再生資源的數量從不滿足需求到滿足需求所耗費的時間t即為空閑資源等待時間lij；式（12）要求每道工序有且僅有一次調度機會；式（13）要求不可再生資源在維修任務中的使用總量不應超過其總的庫存量；式（14）要求某一時刻下該類資源的使用量不應超過當下庫存總量

3 遺傳-長鼻浣熊混合優化算法

眾所周知，受限資源的優化調度問題是經典的NP 難問題，那么開展關于設備維修任務的動態多模式的資源分配調度問題的研究無疑是個極具挑戰力的事情，看似是簡單地將經典靜態資源調度問題變成動態多模式的受限資源調度問題，但實際上其研究難度倍增，約束條件也會變得異常復雜，同濟大學丁雪楓等[20]在文獻中也曾指出，若采用精確求解算法求解該類問題其算法復雜程度空前絕后，隨著任務數量的增加，求解時間指數級倍增。本文就2022 年提出的長鼻浣熊優化算法[21]（coati optimization algorithm，COA）所存在的問題，結合遺傳算法[22]及貪心算法[23]的相關思想進行改進，提出了一種新穎的算法-遺傳-長鼻浣熊混合優化算法（hybrid genetic and coati optimization algorithm，GCOA）。

3.1 食物位置的編碼與解碼

1）編碼策略

在GCOA 中，每一個食物位置都代表著一個候選解，而每個候選解對應一個具體的調度策略，本文所建立的多模式動態受限資源分配調度模型中的調度方案主要包含具體的設備維修任務、維修工序以及維修的執行模式等部分。采用變量i表示維修任務，變量j表示維修工序，變量m則表示具體的某項維修任務的某道工序所選擇的執行模式。將（i,j,m）三元組構成的向量抽象為本章所建數學模型的一個具體的調度策略。鬣蜥位置的具體生成方式可以概括如下：

首先根據維修任務管理中心的維修等待隊列中任務的數量隨機生成I向量；隨后將同一任務的不同工序經全排列后插入對應位置從而得到工序向量J；最后，將3 種不同資源配置的模式隨機分配給各道工序，每道工序有且僅有一種模式，這樣就得到了與工序向量對應的模式向量M，具體如圖3 所示。

圖3 食物位置編碼圖Fig. 3 Food location coding chart

在圖3 中，第一維行向量I代表維修任務，其中各數字代表維修任務的編號；第二維行向量J代表維修工序，其數字代表工序編號；第三維行向量M代表執行模式，其數字表示工序所選擇的具體執行模式。另外，不同的顏色對應不同的維修任務。

2）解碼策略

從上述編碼階段不難發現，該階段僅涉及維修任務向量I、維修工序向量J、執行模式向量M，并沒有關于維修任務的資源剩余情況以及任務調度要求等相關信息，但是在解碼中需要結合實際設備維修任務的發布時間DRelease、維修任務的到期時間DDue、具體任務的具體工序在不同執行模式下的工作時間DExecution以及資源的需求情況RRequirement等，對開始調度時間T、要求的最晚調度結束時間Tmax以及資源的剩余數量Rsurplus等參數進行初始化操作是解碼策略的前提，具體可以參見鬣蜥位置解碼的偽代碼。

解碼是基于編碼而來，故解碼策略需要根據編碼策略的特點來進行，也即按照編碼策略中從左至右的順序為具體任務的每道工序依照不同執行模式的不同要求進行資源的合理配置。

算法鬣蜥位置解碼偽代碼

輸入TTask=I,PProcedure=J,Mmode=M,DRelease= RD,

DExecution= ED，RRequirement= RR，DDue= DD

輸出STime,FTime,PStart,PEnd,Rsurplus

初始化T= 0,Tmax= 2 000,Rsurplus= RS // 對應可進行資源調度的開始和結束時間,更新當前可用資源的剩余量。

1) fori←0 toPProcedure.length do // 遵循編碼策略的特點遍歷每道工序

2) whileT＜Tmaxdo // 資源分配調度循環計時條件

3) ifT＞=DRelease.get(i) then // 判斷當前時間是否不早于任務的發布時間

4) ifRsurplus＞=RRequirement.get(Mmode.get(i)) then

5) 根據工序具體資源需求情況進行資源的分配，并更新[T,T+DExecution.get(i)]這個時間段對應需求資源的剩余量Rsurplus

6)PStart.set(T) // 確定當前工序的開始時間

7)PEnd.set(T+DExecution.get(i)) // 確定當前工序的完成時間

8) ifPProcedure.get(i) = 1 then // 判斷是否為第i任務的首道工序

9)STime.set(T) // 確定任務的開始時間

10) else ifPProcedure.get(i) =PProcedure.max then //判斷是否為第i任務的最后一道工序

11)FTime.set(T+DExecution.get(i)) // 確定第i任務的完成時間 // 值得注意的是，這里的T對應第i任務的最后一道工序的開始時間

12) if (T+DExecution.get(i)) ＞=DDuethen

13) 該調度方案不合理，需要重新進行資源分配調度的安排

14) end if

15) else

16)T++// 當前沒有足夠的空閑資源可分配，當前工序進入等待隊列，進入掛起等待狀態，并且調度開始時間仍然持續推進

17) end if

18) else

19)T++// 時間持續推進，直至不早于任務的發布時間

20) end if

21) end while // 結束調度時間的預分配

22) end for // 結束遍歷維修任務的工序集

23) end

3.2 算法核心要素

1）活動范圍

在COA 中，候選解是在長鼻浣熊的獵取鬣蜥區以及逃避天敵區的范圍內隨機生成的，所以不難發現，長鼻浣熊活動范圍內候選解的數量也即鬣蜥的總數量Nsum對解的質量影響較大。由于獵取鬣蜥區域是長鼻浣熊的主要捕食區，而逃避天敵區域的核心目標是躲避天敵。基于此，在本文所提出的GCOA 中，設置獵取鬣蜥區域中食物鬣蜥數量為Nhunt，而逃避天敵區域中鬣蜥數量為Nescape，它們之間的具體關系為

2）適應度函數

由于本文所建立的多模式動態受限資源分配調度模型的優化目標是最小化總成本，所以更高適應度的解也就意味著總的調度成本更低，相應的解的質量也就越高，適應度也就越高，具體表現為

其中：C(i)表示在所有候選解中第i候選解所對應的目標函數值的大小，也即對應本文所建立的數學模型的第i候選解所對應的調度策略的總成本；f(i)則表示該候選解的適應度大小。

3）遷移因子和保留頻次

若長鼻浣熊在連續多次迭代過程中其位置始終保持不變，那么該算法很有可能陷入局部最優。對此，引入了遷移因子（migration factor，MF）的概念，當長鼻浣熊在連續的遷移因子M次迭代中其位置始終保持不變，那么便將長鼻浣熊強制遷移至臨近的一個隨機位置處，增大其搜索范圍，以使其盡可能跳出局部最優狀態。

為了便于記錄長鼻浣熊隨著迭代次數的增加其當前位置保持不變的迭代次數，本文引入了保留頻次（retention frequency，RF）這一概念，若當前迭代后發現長鼻浣熊的位置仍然保持在迭代前的位置，那么保留頻次F加1，否則須將F置為0；若長鼻浣熊在連續的M次迭代中其位置始終保持不變，那么需要將長鼻浣熊遷移至當前活動范圍外的臨近隨機位置處，具體強制遷移條件如下所示：

4）優化的選擇操作

本文采用精英保留與輪盤賭相結合的策略來進行算法的選擇操作，這樣不但保留了優秀個體而且還極大地豐富了種群基因的多樣性，從而使算法盡快朝著預期方向進行收斂。

首先，采取精英選擇策略來保留候選解中質量較高的Nsingle個個體，具體流程為：對當前活動范圍的各個候選解進行適應度大小的排列，選擇適應度較高的前Nsingle個個體不經過遺傳而直接通過復制的方式進入子代，而Nsingle的具體計算方式為式中：G表示區間(0,1)范圍內的代溝值，Nsum反映了種群的大小規模。

不難發現，精英選擇策略可以有效保留種群中較優秀的個體，避免最優個體被交叉操作而破壞。Nsingle個質量較高的個體通過精英選擇策略進行保留，而剩余的G·Nsum個個體則采用輪盤賭的方式進行抉擇：首先，利用式（17）計算每個個體的適應度；其次，通過式（21）計算第i個體的保留概率然后，使用式（22）計算出各個個體的累積概率最后，隨機生成G·Nsum個(0,1] 區間的隨機數，依據所落區間個數的多少，擇優選擇對應的個體。不難發現，保留概率較小的個體也有被選中的概率，這樣便極大地豐富了候選解的多樣性，同時也增大了算法搜索到更優質解的能力。

5）交叉操作

選取當前活動范圍的兩個鬣蜥位置作為父本，引入隨機向量R，按照隨機向量的約束，交叉重組得到子代所對應的候選解。本文所設計的算法的交叉操作主要針對維修工序J和執行模式M而言，具體如圖4 所示。

圖4 交叉操作示意Fig. 4 Schematic diagram of cross operation

6）變異操作

本文主要采用了一種隨機多點交換的策略來實現算法的變異操作，其實質上一種基于進化逆轉操作來實現的變異方式。由于任務之間是相互獨立的，不同任務的維修工序之間不存在優先級約束，所以將維修任務I、維修工序J以及執行模式M構成的鬣蜥位置編碼三元組（i,j,m）按照維修任務的不同，隨機選擇4 個不同的位置進行兩兩交換，從而來實現GCOA 算法的變異操作，具體如圖5 變異操作示意圖所示。

圖5 變異操作示意Fig. 5 Schematic diagram of variation operation

不難發現，采用這種變異操作的方式可以較大程度的保留任務內部維修工序的約束關系，在一定程度上增強了候選解的可行性，同時也增加了候選解的多樣性。另外，針對實際設備維修任務所設計的食物位置的編碼方式受諸多約束條件的限制，所以并非對候選解進行多重疊加操作就會有更好的結果，反而可能造成候選解逆向退化。據此，以變異執行概率Pm隨機選擇Pm·Nsum個鬣蜥位置實現變異操作；再在剩余的候選解中以交叉執行概率Pc隨機選擇Pc·Nsum個候選解進行交叉操作。

7）引入貪婪算子

為了提高候選解的質量，也即進一步優化求解目標，降低總維修成本，本文基于貪婪思想提出了一種貪心算子的操作。貪婪操作的對象是鬣蜥位置編碼三元組中的維修工序J和執行模式M，具體過程如下：

①在新生成的長鼻浣熊活動范圍中隨機選取一定數量的鬣蜥位置作為貪婪算子的候選解；

②按照從左至右的順序依次檢查各個候選解的不同維修工序所對應的執行模式，篩選出包含2 種或2 種以上工作模式的維修工序；

③分別計算這些維修工序的各個模式所對應的不同資源配置下的總維修成本；

④若該工序其他模式的資源使用成本中，存在小于當前編碼執行模式資源使用成本的模式，修改當前維修工序的執行模式為最小總維修成本所對應的執行模式；

⑤判斷當前工序是否為最后一道工序，若不是鬣蜥位置編碼中的最后一道工序，則轉到3），繼續后一道維修工序的執行模式的貪婪搜索；若是，則輸出當前最優的解決方案。

3.3 可行性分析與維護

新提出的GCOA 是采用隨機生成的方式生成維修任務的，并且調度中存在大量的約束條件，所以初始解中存在大量不可行解，需要將其剔除或者修正。此外，原來的維修工序也是通過全排列的隨機生成的方式插入到對應任務中去的，而且3 種不同資源配置的執行模式也是隨機分配給各道工序的，所以勢必存在大量不可行解，對于這些不可行解的分析檢查與修正是必要的，具體如圖6 所示。

不難發現，可行性分析與維護主要包含以下3 部分：1）任務優先順序的檢查與維護；2）工序優先級的檢查與維護；3）資源供需關系的檢查與修正。

3.4 GCOA 算法流程圖

GCOA 算法可以簡單概括為初始化、全局捕食和局部避敵3 部分，GCOA 算法具體流程圖如圖7 所示。

圖7 GCOA 算法流程Fig. 7 Flow of genetic and coati hybrid optimization algorithm

4 實驗設計與結果分析

4.1 實驗數據與算法參數

鑒于目前還沒有公開的可供研究使用的設備維修數據，此次研究將PSPLIB 標準問題庫中的部分數據進行按需改造，進而展開相應的仿真實驗。PSPLIB 標準問題庫是Project Scheduling Problem Library 的縮寫，由Kolisch 等[24]通過設計ProGen 軟件首次產出擁有不同目標的項目調度問題集；隨后，Schwindt 等[25]結合資源性質、模式類別以及倒換時間等因素，設計出更符合實際需求的新軟件ProGen/Max，進而得到PSPLIB 標準問題庫。

本文參考了文獻[26]的數據處理方式，具體則是選取PSPLIB 標準問題庫的j10.mm、j14.mm以及j30.mm 的基準實例進行整合從而得到此次研究所需要的數據，依據數據來源與規模的差異，從而得到如表3 所示的4 種不同大小規模的仿真實驗算例。

表3 仿真實驗算例詳細信息Table 3 Detailed information of simulation experiment examples

為了模擬多維修中心系統中維修任務管理中心不定時發布新維修任務的過程，此次仿真實驗所采用的實驗算例中所涉及的所有維修任務也均是按照隨機時間發布的。由于此次實驗涉及兩大類不同的資源：可再生資源RR 和不可再生資源NRR，而每類資源又可細分為兩種資源，所以為每種資源分別設定相應的調度成本是很有必要的。為便于求解以及后續不同算法間性能的比較，此次調度成本具體設定詳情如表4 所示。

表4 調度成本參數值詳情Table 4 Details of dispatch cost parameter values

鑒于本文所提出的GCOA 算法的求解性能受遷移因子、交叉算子、變異算子以及貪心算子等參數的影響，所以在表5 給出了GCOA 各參數具體取值詳情。

表5 GCOA 各參數取值參考Table 5 Reference for GCOA parameter values

4.2 算法性能的對比分析

由于涉及的算法都屬于元啟發式算法，故皆受隨機因素的影響，所以選擇在各個算例上運行10 次取均值的方式來提高算法的可靠性。此外，秉持對比實驗的公平性，同一算例下的算法保持相同的初始解、迭代次數以及食物數量等信息。

1）算法收斂性能對比

為更加直觀地比對不同算法在不同規模的算例上的收斂情況，此次實驗選擇對不同大小規模的算例進行實驗，得到如圖8 所示的較小規模算例收斂曲線以及圖9 所示的較大規模算例收斂曲線。

圖8 較小規模算例收斂曲線Fig. 8 Convergence curves for smaller scale examples

圖9 較大規模算例收斂曲線Fig. 9 Convergence curves for larger scale examples

從不同規模算例的收斂曲線不難發現：本文所提出的GCOA 算法不論是在較小規模的算例1 和算例2 上還是在較大規模的算例3 和算例4上，在迭代初期下降速率較遺傳算法GA 和改進前COA 算法都是最快的；另外，就首次找到滿意解方面，GCOA 算法表現也是比較突出的，可以在較小迭代次數下找到滿意解，但不可否認的是，不論是在較小規模算例2 上，還是在較大規模算例3 和算例4 上，GA 算法相較于GCOA 算法和COA 算法而言，它均可以在更小的迭代次數內初次找到滿意解，并且在較大規模算例3 中COA算法較GCOA 算法可以在更小的迭代次數內初次找到滿意解；然而，就最終所得到的目標函數值方面，不論是在較小規模算例1 和算例2 上，還是在較大規模算例3 和算例4 上，GCOA 算法均以絕對的優勢勝于其他算法。

值得一提的是，本文所提出的GCOA 算法在收斂性能方面較其他幾種適用性較強的算法而言是最優的。之所以在部分算例中會出現GCOA算法初次找到滿意解方面晚于GA 算法和COA算法，是因為GA 算法和COA 算法過早收斂，陷入了局部最優，這也正是最終所得的目標函數值不如GCOA 算法的根本。另外，雖然在較簡單的維修任務層面，GA 算法與COA 算法的表現與GCOA算法相差不大，但是在較復雜的維修任務方面，本文所提出的 GCOA 算法以絕對的優勢勝于其他幾種算法，這也正是本文所提新算法的價值所在。此外，本文所提出的新GCOA 算法可以在較小的迭代次數內獲得調度成本最小的解決方案，這是其他幾種算法不可比擬的，但卻是多維修中心系統最為重視的，這也進一步說明了本文所提出的新算法更符合多維修中心系統保障體系的需求。

2）算法求解質量的對比

盡管從前面所介紹的收斂速度曲線圖中可以直觀地對比不同算法的優劣，但是卻不能進行數字化的定量分析，所以為了更加全面地分析不同算法的求解性能，本文還從初次找到滿意解的平均所需時間、目標函數值的平均值、目標函數值的最優值、對資源的利用率（resource utilization，RU）以及目標函數值的相對百分比偏差（relative percentage deviation，RPD）等角度進行了不同算法的對比。

相對百分比偏差VRPD的具體計算方式為

式中：分子首項表示第n個算法的目標函數的平均值；Cbest表示所有算法中目標函數值的平均值中最小的值，也即對應于最優算法的目標函數值的平均值。

本文所指的資源利用率RRU具體是指單位時間內對資源的利用程度，具體計算方式為

表6 ～9 給出了這些不同規模算例的算法求解質量結果對比。

表6 算例1 算法求解質量對比Table 6 Comparison of algorithm solution quality for example 1

表7 算例2 算法求解質量對比Table 7 Comparison of algorithm solution quality for example 2

表8 算例3 算法求解質量對比Table 8 Comparison of algorithm solution quality for example 3

表9 算例4 算法求解質量對比Table 9 Comparison of algorithm solution quality for example 4

從表6～9 不難得到以下結論：從整體來看，不論是目標函數值的平均值還是目標函數值的最優值方面，本文新提出的GCOA算法均以絕對的優勢勝于同類型的GA 算法與COA算法，并且相對百分比偏差在不同規模的4 個算例上均為0；在資源利用率方面，新提出的GCOA算法也是相較GA 算法與COA 算法更優。從局部來看，本文新提出的GCOA 算法在初次找到滿意解平均所需時間方面也是比較好的，尤其在較小規模算例1 和算例2 上所耗費時間較同類型其他算法更短，但是在較大規模算例3 和算例4 上所耗費的時間要略大于同類型的其他算法，這是一種在時間成本可控的前提下盡可能提高求解質量的思想，結果也是不失所望，舍棄了一些時間成本但是換來了較同類型的GA 算法與COA 算法更高的求解質量，這在某種意義上也進一步反映出本文所提出的GCOA 算法的有效性。

本文采用了遺傳算法思想中的遺傳算子、變異算子以及貪婪算法思想中的貪婪算子，這在一定程度上極大地提高了候選解的質量，使得全局搜索能力得到提升，從而盡可能得到更高質量的全局最優解，這也與此次維修任務盡可能降低維修任務最大完工時間、最小化維修任務成本的目標相契合。

5 結束語

本文主要研究了面向多維修中心的維修任務的動態資源分配調度[27]問題。首先，介紹了設備維修任務的相關概念以及限制條件，明確了此次研究的主要目標是選擇合適的執行模式在盡可能降低維修任務時間成本的同時，最小化維修任務的經濟成本，并且最大程度地利用已分配到的資源來完成當下所要完成的維修任務；然后，在經典靜態RCPSP 的基礎上結合多維修中心系統不定時發布任務的特點以及不同資源配置所對應的不同執行模式問題，建立了一種多模式動態受限資源分配調度的數學模型。

為了更好地求解此次所建立的數學模型，本章提出了一種遺傳-長鼻浣熊混合優化算法。該算法是在2022 年新提出的長鼻浣熊優化算法的基礎之上加入了遺傳算法以及貪婪算法的相關思想優化而來。基于遺傳思想的相關操作擴大了候選解的搜索范圍，豐富了候選解的多樣性；而基于貪婪思想的相關操作提高了候選解的質量，也契合了最小化總維修成本的目標。最后，本文對PSPLIB 基準問題庫中的部分數據進行改造，得到不同規模的算例，在這些不同規模的算例上進行同類型算法的仿真實驗，通過從不同角度對實驗結果的對比分析，發現不論是從收斂速度還是求解質量等方面，新提出的GCOA 混合優化算法均以絕對的優勢優于其他算法，這也進一步說明了新提出的算法在求解該模型方面的優勢所在。