秦敏敏，劉立芳，齊小剛

（1. 西安電子科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 陜西 西安 710071; 2. 西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 陜西西安 710071; 3. 西安市網(wǎng)絡(luò)建模與資源調(diào)度重點(diǎn)實(shí)驗(yàn)室, 陜西 西安 710071）

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

在實(shí)際維修任務(wù)中，不難發(fā)現(xiàn)關(guān)于設(shè)備的維修任務(wù)的資源調(diào)度問(wèn)題隸屬于經(jīng)典資源受限項(xiàng)目調(diào)度問(wèn)題[9-10]的范疇。

在國(guó)外的研究中，Oztemel 等[11]為求解單資源的RCPSP 問(wèn)題，提出了人工蜂群算法；為了更好地處理基于無(wú)線通信與雷達(dá)系統(tǒng)的多核心的任務(wù)調(diào)度平臺(tái)，Krishnakumar 等[12]提出了一種關(guān)于模仿學(xué)習(xí)的方法；基于多模式的資源受限的項(xiàng)目調(diào)度問(wèn)題，Kosztyan 等[13]提出了一種基于矩陣的新思路；針對(duì)具有優(yōu)先級(jí)先后順序約束的多任務(wù)的資源受限的項(xiàng)目調(diào)度問(wèn)題，Chakrabortty 等[14]提出一種變鄰域的啟發(fā)式搜索算法；Zaman 等[15]提出一種將浮動(dòng)資源進(jìn)行合理安排的方案。

在國(guó)內(nèi)的研究中，田啟華等[16]在多目標(biāo)理想方法的基礎(chǔ)上進(jìn)行拓展，構(gòu)建了任務(wù)的評(píng)價(jià)指標(biāo)函數(shù)；鑒于資源存在空窗期的特性，陸志強(qiáng)等[17]針對(duì)作業(yè)的開(kāi)始時(shí)間，提出了一種改進(jìn)的遺傳算法。事實(shí)上，實(shí)際任務(wù)的工期只是一個(gè)預(yù)期值，并不是確定的，針對(duì)這種實(shí)際情況，謝芳等[18]建立了基于資源受限項(xiàng)目調(diào)度問(wèn)題的馬爾可夫決策過(guò)程模型；最近，張宇哲等[19]針對(duì)所研究的問(wèn)題，將傳統(tǒng)的整數(shù)規(guī)劃模型細(xì)化為約束主問(wèn)題以及子問(wèn)題，并且提出一種列生成的方法用于求解模型。最后通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)，所提出的新算法擁有較好的求解性能。

通過(guò)對(duì)國(guó)內(nèi)外任務(wù)調(diào)度技術(shù)的相關(guān)研究不難發(fā)現(xiàn)，現(xiàn)階段還存在以下問(wèn)題：

1）與維修設(shè)備的任務(wù)調(diào)度相關(guān)的研究較少；

2）經(jīng)典靜態(tài)模型已難以滿(mǎn)足當(dāng)下實(shí)際需求，對(duì)其進(jìn)行拓展，使其更符合實(shí)際場(chǎng)景要求已迫在眉睫；

3）模型進(jìn)行拓展之后，提出適用于新模型的改進(jìn)算法至關(guān)重要。

結(jié)合多維修中心系統(tǒng)的優(yōu)勢(shì)，以維修資源為研究對(duì)象，采用適應(yīng)當(dāng)下實(shí)際需求的優(yōu)化目標(biāo)，以合理高效的資源調(diào)度策略，建立相應(yīng)的資源調(diào)度模型并提出更好的求解算法，進(jìn)而更加出色地完成所部署的維修任務(wù)。

1 維修任務(wù)中的資源調(diào)度

1.1 問(wèn)題描述與概念解釋

維修任務(wù)是安全保障體系的重要組分之一，是受損設(shè)備經(jīng)維修操作后恢復(fù)其作戰(zhàn)狀態(tài)的過(guò)程。資源調(diào)度則是指在任務(wù)的流水作業(yè)執(zhí)行過(guò)程中，運(yùn)用計(jì)算機(jī)、人工智能以及智能優(yōu)化算法等相關(guān)技術(shù)，對(duì)所涉及的維修資源進(jìn)行合理地監(jiān)管與分配，以盡可能地提高維修效率，降低維修成本。

在維修任務(wù)的資源調(diào)度中，會(huì)涉及如下概念：

1）工件

工件是指所要維修的目標(biāo)，可能是設(shè)備、備品備件，也可能是設(shè)備的零部件。

2）工序

工序是完成一項(xiàng)維修任務(wù)的最小單元。就維修一個(gè)小型設(shè)備而言，包括運(yùn)輸工序、修復(fù)工序、檢驗(yàn)工序等。值得一提的是，工序之間存在嚴(yán)格的優(yōu)先級(jí)關(guān)系，一旦工序順序發(fā)生改變，很可能導(dǎo)致維修任務(wù)的失敗；另外，工序一旦開(kāi)始便不可中斷，否則會(huì)直接影響后續(xù)工序的執(zhí)行。

3）資源

依據(jù)不同的分類(lèi)標(biāo)準(zhǔn)，資源可以劃分為不同的類(lèi)型。資源大致可分為兩大類(lèi)，具體如圖1所示。

圖1 資源的分類(lèi)Fig. 1 Classification of resources

1.2 約束條件的分析

在實(shí)際維修保障體系中，維修任務(wù)是紛繁復(fù)雜的，其發(fā)布時(shí)間具有一定的隨機(jī)性，進(jìn)入維修隊(duì)列的任務(wù)也會(huì)受到新任務(wù)的影響。除此之外，多維修中心系統(tǒng)主要是按照維修任務(wù)管理中心的維修檢修計(jì)劃來(lái)工作的。因此，一般是在當(dāng)前設(shè)備使用的空閑期進(jìn)行維修，并且還得確保一定的時(shí)效性。

顯然，面向多維修中心的維修任務(wù)隸屬于動(dòng)態(tài)任務(wù)發(fā)布模式范疇，在執(zhí)行當(dāng)前任務(wù)時(shí)，有極大可能受到新加入任務(wù)的干涉，這使得其資源約束條件相較于靜態(tài)調(diào)度問(wèn)題更加嚴(yán)苛與抽象。

通過(guò)對(duì)維修任務(wù)的深入研究與分析，資源分配調(diào)度中的約束條件主要可以概括為以下4 種：

1）時(shí)間約束

多維修中心的任務(wù)是不定時(shí)發(fā)布的，任務(wù)一經(jīng)發(fā)布，系統(tǒng)通過(guò)維修任務(wù)分析預(yù)測(cè)模塊對(duì)其需求的資源以及排隊(duì)時(shí)間等指標(biāo)進(jìn)行預(yù)測(cè)，并依據(jù)設(shè)備具體使用時(shí)間等指標(biāo)，綜合考慮該待修設(shè)備進(jìn)行維修任務(wù)的開(kāi)始和截止時(shí)間。此外，維修任務(wù)必須在該時(shí)間范圍內(nèi)執(zhí)行，否則會(huì)造成不可估量的損失。

2）資源約束

多維修中心系統(tǒng)以設(shè)備的維修為主，而設(shè)備的維修過(guò)程復(fù)雜多變，通常需要多種不同類(lèi)型的資源的同時(shí)參與。因維修難度以及設(shè)備需求時(shí)間等差異，維修所需資源也不盡相同。一般而言，同一時(shí)間某維修資源僅為某工序所有，在該工序執(zhí)行結(jié)束后，不可再生資源被消耗，有限的資源數(shù)量減少；而可再生資源在一定范圍內(nèi)可重復(fù)利用，總數(shù)量恒定?；诳稍偕Y源可重復(fù)使用的特性，可以初步將可再生資源粗分為“空閑”與“忙碌”兩種狀態(tài)，以便后續(xù)建模等工作的順利開(kāi)展。

3）模式約束

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

4）優(yōu)先級(jí)約束

對(duì)于維修設(shè)備而言，維修次序不是隨意的，而是具有嚴(yán)格要求的。設(shè)備的生產(chǎn)以及維修是廠商依據(jù)一定的規(guī)范條約嚴(yán)格執(zhí)行的，維修工人必須嚴(yán)格按照要求進(jìn)行損壞設(shè)備的維修，比如先拆解再分塊維修，最后整裝調(diào)試。顯然，維修工序在時(shí)序上具有優(yōu)化級(jí)約束。

2 資源分配調(diào)度模型的建立

2.1 模型概述與資源調(diào)度策略

鑒于經(jīng)典的RCPSP 模型已經(jīng)難以滿(mǎn)足當(dāng)下多維修中心系統(tǒng)保障體系的實(shí)際需求。所以，本文結(jié)合維修設(shè)備動(dòng)態(tài)發(fā)布維修任務(wù)的特征，將維修任務(wù)涉及的維修資源簡(jiǎn)單劃分為可再生資源（renewable resource，RR)和不可再生資源NRR（non-renewable resource，NRR），將維修任務(wù)抽象為RCPSP 模型中的項(xiàng)目，維修工序抽象為RCPSP模型中的活動(dòng)。另外，本文還考慮了不同模式的選擇問(wèn)題，進(jìn)而構(gòu)建了多模式的動(dòng)態(tài)資源分配調(diào)度模型，但有如下限制：

1）考慮到維修任務(wù)具有發(fā)布時(shí)間隨機(jī)等動(dòng)態(tài)任務(wù)相關(guān)的特性，故可將其視為可以實(shí)時(shí)進(jìn)入維修任務(wù)管理中心并隨時(shí)等待安排維修處理的任務(wù)。另外，維修任務(wù)的執(zhí)行時(shí)間必須在發(fā)布時(shí)間之后。

2）由于本文涉及的是資源受限類(lèi)相關(guān)問(wèn)題，所以資源并不是理想狀態(tài)下的無(wú)限資源，而是有限數(shù)量的資源。具體為使用前后數(shù)量保持不變的RR 和不可以重復(fù)使用，使用頻次與剩余數(shù)量成反比的NRR。

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

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

5）由于實(shí)際的維修任務(wù)紛繁復(fù)雜，影響維修任務(wù)的因素頗多，所以很難準(zhǔn)確保證維修任務(wù)所需時(shí)間，一般在維修任務(wù)規(guī)定的到期時(shí)間前后小范圍波動(dòng)，則表明當(dāng)前維修任務(wù)能夠順利完成。若在任務(wù)規(guī)定時(shí)間之前完成，則有一定的獎(jiǎng)勵(lì)，否則，會(huì)有相應(yīng)的懲罰。

如圖2 所示，本文所建立的多模式動(dòng)態(tài)受限資源分配調(diào)度模型主要涉及這幾部分：不定時(shí)工件維修任務(wù)的發(fā)布、依據(jù)工序優(yōu)先級(jí)關(guān)系所確定的作業(yè)執(zhí)行次序以及不同模式的選擇與需求資源的配置。

圖2 多模式動(dòng)態(tài)受限資源分配調(diào)度模型結(jié)構(gòu)Fig. 2 Structure chart of multimode dynamic constrained resource allocation and scheduling model

2.2 數(shù)學(xué)模型的建立

鑒于同一符號(hào)參數(shù)被多次使用，為了方便管理與查閱，現(xiàn)對(duì)所建立的數(shù)學(xué)模型所涉及的符號(hào)參數(shù)進(jìn)行詳細(xì)地介紹，以便理解后續(xù)相關(guān)公式的具體含義，具體如表1、2 所示。

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

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

本文參考了不少學(xué)者采用的多目標(biāo)加權(quán)優(yōu)化的方法，采用專(zhuān)家評(píng)分系統(tǒng)進(jìn)行權(quán)重的估量，具體得到如下結(jié)果：時(shí)間成本40%、經(jīng)濟(jì)成本30%、資源利用率30%，所以依次可以得到1.2、0.9、0.9 這樣的系數(shù)，取三者之和記為總成本C。

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

3 遺傳-長(zhǎng)鼻浣熊混合優(yōu)化算法

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

3.1 食物位置的編碼與解碼

1）編碼策略

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

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

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

在圖3 中，第一維行向量I代表維修任務(wù)，其中各數(shù)字代表維修任務(wù)的編號(hào)；第二維行向量J代表維修工序，其數(shù)字代表工序編號(hào)；第三維行向量M代表執(zhí)行模式，其數(shù)字表示工序所選擇的具體執(zhí)行模式。另外，不同的顏色對(duì)應(yīng)不同的維修任務(wù)。

2）解碼策略

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

解碼是基于編碼而來(lái)，故解碼策略需要根據(jù)編碼策略的特點(diǎn)來(lái)進(jìn)行，也即按照編碼策略中從左至右的順序?yàn)榫唧w任務(wù)的每道工序依照不同執(zhí)行模式的不同要求進(jìn)行資源的合理配置。

算法鬣蜥位置解碼偽代碼

輸入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 // 對(duì)應(yīng)可進(jìn)行資源調(diào)度的開(kāi)始和結(jié)束時(shí)間,更新當(dāng)前可用資源的剩余量。

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

2) whileT＜Tmaxdo // 資源分配調(diào)度循環(huán)計(jì)時(shí)條件

3) ifT＞=DRelease.get(i) then // 判斷當(dāng)前時(shí)間是否不早于任務(wù)的發(fā)布時(shí)間

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

5) 根據(jù)工序具體資源需求情況進(jìn)行資源的分配，并更新[T,T+DExecution.get(i)]這個(gè)時(shí)間段對(duì)應(yīng)需求資源的剩余量Rsurplus

6)PStart.set(T) // 確定當(dāng)前工序的開(kāi)始時(shí)間

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

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

9)STime.set(T) // 確定任務(wù)的開(kāi)始時(shí)間

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

11)FTime.set(T+DExecution.get(i)) // 確定第i任務(wù)的完成時(shí)間 // 值得注意的是，這里的T對(duì)應(yīng)第i任務(wù)的最后一道工序的開(kāi)始時(shí)間

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

13) 該調(diào)度方案不合理，需要重新進(jìn)行資源分配調(diào)度的安排

14) end if

15) else

16)T++// 當(dāng)前沒(méi)有足夠的空閑資源可分配，當(dāng)前工序進(jìn)入等待隊(duì)列，進(jìn)入掛起等待狀態(tài)，并且調(diào)度開(kāi)始時(shí)間仍然持續(xù)推進(jìn)

17) end if

18) else

19)T++// 時(shí)間持續(xù)推進(jìn)，直至不早于任務(wù)的發(fā)布時(shí)間

20) end if

21) end while // 結(jié)束調(diào)度時(shí)間的預(yù)分配

22) end for // 結(jié)束遍歷維修任務(wù)的工序集

23) end

3.2 算法核心要素

1）活動(dòng)范圍

在COA 中，候選解是在長(zhǎng)鼻浣熊的獵取鬣蜥區(qū)以及逃避天敵區(qū)的范圍內(nèi)隨機(jī)生成的，所以不難發(fā)現(xiàn)，長(zhǎng)鼻浣熊活動(dòng)范圍內(nèi)候選解的數(shù)量也即鬣蜥的總數(shù)量Nsum對(duì)解的質(zhì)量影響較大。由于獵取鬣蜥區(qū)域是長(zhǎng)鼻浣熊的主要捕食區(qū)，而逃避天敵區(qū)域的核心目標(biāo)是躲避天敵?；诖?，在本文所提出的GCOA 中，設(shè)置獵取鬣蜥區(qū)域中食物鬣蜥數(shù)量為Nhunt，而逃避天敵區(qū)域中鬣蜥數(shù)量為Nescape，它們之間的具體關(guān)系為

2）適應(yīng)度函數(shù)

由于本文所建立的多模式動(dòng)態(tài)受限資源分配調(diào)度模型的優(yōu)化目標(biāo)是最小化總成本，所以更高適應(yīng)度的解也就意味著總的調(diào)度成本更低，相應(yīng)的解的質(zhì)量也就越高，適應(yīng)度也就越高，具體表現(xiàn)為

其中：C(i)表示在所有候選解中第i候選解所對(duì)應(yīng)的目標(biāo)函數(shù)值的大小，也即對(duì)應(yīng)本文所建立的數(shù)學(xué)模型的第i候選解所對(duì)應(yīng)的調(diào)度策略的總成本；f(i)則表示該候選解的適應(yīng)度大小。

3）遷移因子和保留頻次

若長(zhǎng)鼻浣熊在連續(xù)多次迭代過(guò)程中其位置始終保持不變，那么該算法很有可能陷入局部最優(yōu)。對(duì)此，引入了遷移因子（migration factor，MF）的概念，當(dāng)長(zhǎng)鼻浣熊在連續(xù)的遷移因子M次迭代中其位置始終保持不變，那么便將長(zhǎng)鼻浣熊強(qiáng)制遷移至臨近的一個(gè)隨機(jī)位置處，增大其搜索范圍，以使其盡可能跳出局部最優(yōu)狀態(tài)。

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

4）優(yōu)化的選擇操作

本文采用精英保留與輪盤(pán)賭相結(jié)合的策略來(lái)進(jìn)行算法的選擇操作，這樣不但保留了優(yōu)秀個(gè)體而且還極大地豐富了種群基因的多樣性，從而使算法盡快朝著預(yù)期方向進(jìn)行收斂。

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

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

5）交叉操作

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

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

6）變異操作

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

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

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

7）引入貪婪算子

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

①在新生成的長(zhǎng)鼻浣熊活動(dòng)范圍中隨機(jī)選取一定數(shù)量的鬣蜥位置作為貪婪算子的候選解；

②按照從左至右的順序依次檢查各個(gè)候選解的不同維修工序所對(duì)應(yīng)的執(zhí)行模式，篩選出包含2 種或2 種以上工作模式的維修工序；

③分別計(jì)算這些維修工序的各個(gè)模式所對(duì)應(yīng)的不同資源配置下的總維修成本；

④若該工序其他模式的資源使用成本中，存在小于當(dāng)前編碼執(zhí)行模式資源使用成本的模式，修改當(dāng)前維修工序的執(zhí)行模式為最小總維修成本所對(duì)應(yīng)的執(zhí)行模式；

⑤判斷當(dāng)前工序是否為最后一道工序，若不是鬣蜥位置編碼中的最后一道工序，則轉(zhuǎn)到3），繼續(xù)后一道維修工序的執(zhí)行模式的貪婪搜索；若是，則輸出當(dāng)前最優(yōu)的解決方案。

3.3 可行性分析與維護(hù)

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

不難發(fā)現(xiàn)，可行性分析與維護(hù)主要包含以下3 部分：1）任務(wù)優(yōu)先順序的檢查與維護(hù)；2）工序優(yōu)先級(jí)的檢查與維護(hù)；3）資源供需關(guān)系的檢查與修正。

3.4 GCOA 算法流程圖

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

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

4 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

4.1 實(shí)驗(yàn)數(shù)據(jù)與算法參數(shù)

鑒于目前還沒(méi)有公開(kāi)的可供研究使用的設(shè)備維修數(shù)據(jù)，此次研究將PSPLIB 標(biāo)準(zhǔn)問(wèn)題庫(kù)中的部分?jǐn)?shù)據(jù)進(jìn)行按需改造，進(jìn)而展開(kāi)相應(yīng)的仿真實(shí)驗(yàn)。PSPLIB 標(biāo)準(zhǔn)問(wèn)題庫(kù)是Project Scheduling Problem Library 的縮寫(xiě)，由Kolisch 等[24]通過(guò)設(shè)計(jì)ProGen 軟件首次產(chǎn)出擁有不同目標(biāo)的項(xiàng)目調(diào)度問(wèn)題集；隨后，Schwindt 等[25]結(jié)合資源性質(zhì)、模式類(lèi)別以及倒換時(shí)間等因素，設(shè)計(jì)出更符合實(shí)際需求的新軟件ProGen/Max，進(jìn)而得到PSPLIB 標(biāo)準(zhǔn)問(wèn)題庫(kù)。

本文參考了文獻(xiàn)[26]的數(shù)據(jù)處理方式，具體則是選取PSPLIB 標(biāo)準(zhǔn)問(wèn)題庫(kù)的j10.mm、j14.mm以及j30.mm 的基準(zhǔn)實(shí)例進(jìn)行整合從而得到此次研究所需要的數(shù)據(jù)，依據(jù)數(shù)據(jù)來(lái)源與規(guī)模的差異，從而得到如表3 所示的4 種不同大小規(guī)模的仿真實(shí)驗(yàn)算例。

表3 仿真實(shí)驗(yàn)算例詳細(xì)信息Table 3 Detailed information of simulation experiment examples

為了模擬多維修中心系統(tǒng)中維修任務(wù)管理中心不定時(shí)發(fā)布新維修任務(wù)的過(guò)程，此次仿真實(shí)驗(yàn)所采用的實(shí)驗(yàn)算例中所涉及的所有維修任務(wù)也均是按照隨機(jī)時(shí)間發(fā)布的。由于此次實(shí)驗(yàn)涉及兩大類(lèi)不同的資源：可再生資源RR 和不可再生資源NRR，而每類(lèi)資源又可細(xì)分為兩種資源，所以為每種資源分別設(shè)定相應(yīng)的調(diào)度成本是很有必要的。為便于求解以及后續(xù)不同算法間性能的比較，此次調(diào)度成本具體設(shè)定詳情如表4 所示。

表4 調(diào)度成本參數(shù)值詳情T(mén)able 4 Details of dispatch cost parameter values

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

表5 GCOA 各參數(shù)取值參考Table 5 Reference for GCOA parameter values

4.2 算法性能的對(duì)比分析

由于涉及的算法都屬于元啟發(fā)式算法，故皆受隨機(jī)因素的影響，所以選擇在各個(gè)算例上運(yùn)行10 次取均值的方式來(lái)提高算法的可靠性。此外，秉持對(duì)比實(shí)驗(yàn)的公平性，同一算例下的算法保持相同的初始解、迭代次數(shù)以及食物數(shù)量等信息。

1）算法收斂性能對(duì)比

為更加直觀地比對(duì)不同算法在不同規(guī)模的算例上的收斂情況，此次實(shí)驗(yàn)選擇對(duì)不同大小規(guī)模的算例進(jìn)行實(shí)驗(yàn)，得到如圖8 所示的較小規(guī)模算例收斂曲線以及圖9 所示的較大規(guī)模算例收斂曲線。

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

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

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

值得一提的是，本文所提出的GCOA 算法在收斂性能方面較其他幾種適用性較強(qiáng)的算法而言是最優(yōu)的。之所以在部分算例中會(huì)出現(xiàn)GCOA算法初次找到滿(mǎn)意解方面晚于GA 算法和COA算法，是因?yàn)镚A 算法和COA 算法過(guò)早收斂，陷入了局部最優(yōu)，這也正是最終所得的目標(biāo)函數(shù)值不如GCOA 算法的根本。另外，雖然在較簡(jiǎn)單的維修任務(wù)層面，GA 算法與COA 算法的表現(xiàn)與GCOA算法相差不大，但是在較復(fù)雜的維修任務(wù)方面，本文所提出的 GCOA 算法以絕對(duì)的優(yōu)勢(shì)勝于其他幾種算法，這也正是本文所提新算法的價(jià)值所在。此外，本文所提出的新GCOA 算法可以在較小的迭代次數(shù)內(nèi)獲得調(diào)度成本最小的解決方案，這是其他幾種算法不可比擬的，但卻是多維修中心系統(tǒng)最為重視的，這也進(jìn)一步說(shuō)明了本文所提出的新算法更符合多維修中心系統(tǒng)保障體系的需求。

2）算法求解質(zhì)量的對(duì)比

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

相對(duì)百分比偏差VRPD的具體計(jì)算方式為

式中：分子首項(xiàng)表示第n個(gè)算法的目標(biāo)函數(shù)的平均值；Cbest表示所有算法中目標(biāo)函數(shù)值的平均值中最小的值，也即對(duì)應(yīng)于最優(yōu)算法的目標(biāo)函數(shù)值的平均值。

本文所指的資源利用率RRU具體是指單位時(shí)間內(nèi)對(duì)資源的利用程度，具體計(jì)算方式為

表6 ～9 給出了這些不同規(guī)模算例的算法求解質(zhì)量結(jié)果對(duì)比。

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

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

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

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

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

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

5 結(jié)束語(yǔ)

本文主要研究了面向多維修中心的維修任務(wù)的動(dòng)態(tài)資源分配調(diào)度[27]問(wèn)題。首先，介紹了設(shè)備維修任務(wù)的相關(guān)概念以及限制條件，明確了此次研究的主要目標(biāo)是選擇合適的執(zhí)行模式在盡可能降低維修任務(wù)時(shí)間成本的同時(shí)，最小化維修任務(wù)的經(jīng)濟(jì)成本，并且最大程度地利用已分配到的資源來(lái)完成當(dāng)下所要完成的維修任務(wù)；然后，在經(jīng)典靜態(tài)RCPSP 的基礎(chǔ)上結(jié)合多維修中心系統(tǒng)不定時(shí)發(fā)布任務(wù)的特點(diǎn)以及不同資源配置所對(duì)應(yīng)的不同執(zhí)行模式問(wèn)題，建立了一種多模式動(dòng)態(tài)受限資源分配調(diào)度的數(shù)學(xué)模型。

為了更好地求解此次所建立的數(shù)學(xué)模型，本章提出了一種遺傳-長(zhǎng)鼻浣熊混合優(yōu)化算法。該算法是在2022 年新提出的長(zhǎng)鼻浣熊優(yōu)化算法的基礎(chǔ)之上加入了遺傳算法以及貪婪算法的相關(guān)思想優(yōu)化而來(lái)。基于遺傳思想的相關(guān)操作擴(kuò)大了候選解的搜索范圍，豐富了候選解的多樣性；而基于貪婪思想的相關(guān)操作提高了候選解的質(zhì)量，也契合了最小化總維修成本的目標(biāo)。最后，本文對(duì)PSPLIB 基準(zhǔn)問(wèn)題庫(kù)中的部分?jǐn)?shù)據(jù)進(jìn)行改造，得到不同規(guī)模的算例，在這些不同規(guī)模的算例上進(jìn)行同類(lèi)型算法的仿真實(shí)驗(yàn)，通過(guò)從不同角度對(duì)實(shí)驗(yàn)結(jié)果的對(duì)比分析，發(fā)現(xiàn)不論是從收斂速度還是求解質(zhì)量等方面，新提出的GCOA 混合優(yōu)化算法均以絕對(duì)的優(yōu)勢(shì)優(yōu)于其他算法，這也進(jìn)一步說(shuō)明了新提出的算法在求解該模型方面的優(yōu)勢(shì)所在。