摘要：針對(duì)船舶維修工程存在的維修項(xiàng)目交叉耦合作業(yè)、維修流程復(fù)雜、資源需求量大等特點(diǎn)，將船舶維修調(diào)度問(wèn)題歸納為在合理規(guī)劃維修任務(wù)序列和多資源分配的前提下，實(shí)現(xiàn)維修工期最佳的多資源受限項(xiàng)目調(diào)度問(wèn)題。為了充分剖析問(wèn)題特征，首先，以維修工期為目標(biāo)，以維修任務(wù)序列和資源分配為決策變量，建立多資源下船舶維修調(diào)度混合整數(shù)規(guī)劃模型；其次，提出一種改進(jìn)變鄰域搜索算法的多資源船舶維修項(xiàng)目工期優(yōu)化框架；最后，以50組標(biāo)桿案例驗(yàn)證該方法的優(yōu)越性，并與遺傳算法、粒子群算法進(jìn)行對(duì)比分析。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的變鄰域搜索算法具有顯著優(yōu)越性，可為船舶維修計(jì)劃制訂提供參考。

關(guān)鍵詞：船舶維修；變鄰域搜索算法；多資源；項(xiàng)目調(diào)度；鄰域結(jié)構(gòu)

0"引言

船舶維修工程存在任務(wù)量巨大、項(xiàng)目交叉耦合作業(yè)問(wèn)題突出、技術(shù)密集程度高、維修流程復(fù)雜等特點(diǎn)，因此，船舶維修工程項(xiàng)目管理屬于復(fù)雜的系統(tǒng)工程[1]。

船舶維修工程工期優(yōu)化受不同工種數(shù)量的限制，如鉗工、管工等，因此需要合理安排工種和維修任務(wù)，從而達(dá)到最佳工期的目的。船舶維修工程工期優(yōu)化被認(rèn)為是典型的多資源受限項(xiàng)目調(diào)度問(wèn)題，需要考慮多資源間的依賴關(guān)系，是經(jīng)典資源受限項(xiàng)目調(diào)度問(wèn)題的擴(kuò)展，具有較高的實(shí)用價(jià)值，因此受到越來(lái)越多的學(xué)者及企業(yè)管理者的關(guān)注[2]。

多資源受限項(xiàng)目調(diào)度問(wèn)題[3-4]可采用精確方法、啟發(fā)式算法和元啟發(fā)式算法。精確算法[5]包括數(shù)學(xué)規(guī)劃和分支定界兩個(gè)步驟，被認(rèn)為是獲得問(wèn)題下界的最好方法。然而，該算法僅適用于小規(guī)模的項(xiàng)目調(diào)度問(wèn)題。對(duì)于維修任務(wù)巨大的船舶維修工程，該方法無(wú)法在多項(xiàng)式時(shí)間內(nèi)獲取問(wèn)題解，在實(shí)際過(guò)程中無(wú)法應(yīng)用。

啟發(fā)式算法[6]是按照一定的優(yōu)先規(guī)則生成合理的維修任務(wù)序列和資源分配決策。該方法需要現(xiàn)場(chǎng)管理人員或工作人員具有較高的專業(yè)技能，在實(shí)際應(yīng)用中具有一定困難[7]。

元啟發(fā)式算法綜合了精確算法和啟發(fā)式算法的優(yōu)勢(shì)，以盡可能短的時(shí)間獲取近優(yōu)解，滿足船舶維修工程實(shí)際需要[8-9]。元啟發(fā)式算法包括粒子群算法[10]、蟻群算法[11]、多目標(biāo)類(lèi)電磁機(jī)制算法[12]等，在求解多資源受限項(xiàng)目調(diào)度問(wèn)題中得到廣泛應(yīng)用。然而，針對(duì)船舶維修工程任務(wù)多、資源種類(lèi)多等特點(diǎn)，本文提出一種改進(jìn)的變鄰域搜索算法以求解多資源船舶維修項(xiàng)目調(diào)度問(wèn)題。

1"問(wèn)題描述與模型構(gòu)建

多資源船舶維修項(xiàng)目調(diào)度問(wèn)題可抽象為經(jīng)典的多資源受限項(xiàng)目調(diào)度問(wèn)題。具體描述如下：船舶維修工程包含I項(xiàng)維修任務(wù)I={1，2，…，I}。其中，1和I是唯一的維修開(kāi)始任務(wù)和結(jié)束任務(wù)，可定義為虛活動(dòng)，不占用資源和工時(shí)，僅用來(lái)表示優(yōu)先關(guān)系，即每項(xiàng)維修任務(wù)同時(shí)需要一定數(shù)量的多類(lèi)資源在一定工時(shí)內(nèi)完成。每項(xiàng)維修任務(wù)一旦開(kāi)始就不能中斷，且必須在其緊前維修任務(wù)均完工之后才能開(kāi)始。多資源船舶維修項(xiàng)目調(diào)度的目的是通過(guò)合理決策維修任務(wù)序列和資源分配，實(shí)現(xiàn)維修工程工期最短。

定義每類(lèi)資源k的總供應(yīng)量為Rk，F(xiàn)Ti為維修任務(wù)i的結(jié)束時(shí)間，di為維修任務(wù)i所需工時(shí)，rik為維修任務(wù)i所需資源k的數(shù)量，Pi為維修任務(wù)i所有緊前維修任務(wù)集合，

t為時(shí)刻，可以為預(yù)設(shè)值，但必須大于工期，

xit為0～1的變量（1表示維修任務(wù)i在時(shí)刻t維修，0表示維修任務(wù)i不在時(shí)刻t進(jìn)行維修）。由此，得到多資源船舶維修項(xiàng)目調(diào)度問(wèn)題的數(shù)學(xué)公式如下

（1）目標(biāo)函數(shù)。公式為

（2）約束條件。主要包括：

1）開(kāi)工時(shí)間約束。維修任務(wù)1的開(kāi)工時(shí)間定義為從0時(shí)刻開(kāi)始。公式為

2）優(yōu)先關(guān)系約束。維修任務(wù)i必須在所有緊前維修任務(wù)完工后才能開(kāi)始。公式為

3）多資源約束。任意單位時(shí)間內(nèi)所有資源的需求量均小于等于資源供應(yīng)量。公式為

由此可知：式（1）是目標(biāo)函數(shù)，工期等于維修任務(wù)I的完工時(shí)間；式（2）要求維修任務(wù)從0時(shí)刻開(kāi)始；式（3）表示所有維修任務(wù)必須在其維修任務(wù)完工后才能開(kāi)始，即優(yōu)先關(guān)系約束；式（4）要求任意單位時(shí)間內(nèi)的資源總量不能超過(guò)供應(yīng)量，即資源約束。

2"工期優(yōu)化流程

本文以最小化船舶維修工期為目標(biāo)，采用變鄰域搜索算法進(jìn)行求解，以獲取船舶維修調(diào)度方案。該工期優(yōu)化流程的主要步驟包括編碼設(shè)計(jì)與解碼設(shè)計(jì)，即采用工期值作為適應(yīng)度值評(píng)價(jià)個(gè)體優(yōu)劣性，基于三種鄰域結(jié)構(gòu)不斷迭代更新個(gè)體，直至產(chǎn)生滿足條件的個(gè)體，得到最優(yōu)船舶維修調(diào)度方案。

2.1"編碼設(shè)計(jì)

編碼與解碼直接影響船舶維修項(xiàng)目調(diào)度的可行性，決定了算法的求解空間。高效的編碼與解碼設(shè)計(jì)可指引算法快速收斂于最優(yōu)解。

本文采用雙層實(shí)數(shù)編碼，上層編碼為對(duì)應(yīng)維修任務(wù)的緊前維修任務(wù)數(shù)，下層編碼對(duì)應(yīng)維修任務(wù)編號(hào)。以11個(gè)維修任務(wù)為例，雙層實(shí)數(shù)編碼如圖1所示。上層編碼依次為維修任務(wù)1，2，…，11的緊前維修任務(wù)數(shù)；下層編碼為維修任務(wù)1至11的亂序，模式列表中的模式與活動(dòng)列表中的活動(dòng)編號(hào)一一對(duì)應(yīng)。

該編碼設(shè)計(jì)的最大優(yōu)勢(shì)在于能夠高效表征維修任務(wù)間的優(yōu)先關(guān)系。現(xiàn)有文獻(xiàn)中通常采用單層編碼，即只有下層編碼，在解碼過(guò)程中需要不間斷地判斷緊前維修任務(wù)是否完工。本文增加了上層編碼，在解碼初始時(shí)刻是確定的一串序列，即根據(jù)維修任務(wù)網(wǎng)絡(luò)獲取的緊前維修任務(wù)數(shù)。下層編碼生成過(guò)程是維修任務(wù)1到11的亂序，無(wú)須關(guān)心其緊前關(guān)系，只需在解碼過(guò)程中判斷其緊前維修任務(wù)數(shù)是否為零，減少了初始化種群的復(fù)雜度。

2.2"解碼設(shè)計(jì)

解碼采用并行解碼設(shè)計(jì)，從左到右依次讀取，仍以上述編碼為例進(jìn)行說(shuō)明。

解碼過(guò)程包括三個(gè)步驟：首先，確定候選集；其次，以最大資源供應(yīng)量為約束，確定候選集中的資源分配和維修任務(wù)序列；最后，更新候選集，直至維修任務(wù)已分配。

步驟1：隨機(jī)選擇一個(gè)個(gè)體，維修任務(wù)列表以1至11的亂序排列，即1，3，2，5，7，4，6，8，9，10，11。一般而言，初始時(shí)刻只有維修任務(wù)1沒(méi)有緊前維修任務(wù)，其他維修任務(wù)都有緊前維修任務(wù)。按照維修任務(wù)1至11，其緊前維修任務(wù)數(shù)為0，1，1，1，1，1，1，1，1，1，2，1，由此得到編碼候選集，如圖2所示。候選集為緊前維修任務(wù)數(shù)為0的維修任務(wù)，當(dāng)前候選集是1。

步驟2：以最大資源供應(yīng)量為約束，確定候選集的資源分配和維修任務(wù)序列。仍以步驟1的個(gè)體為例，當(dāng)前候選集為維修任務(wù)1。因維修任務(wù)1不消耗資源和工時(shí)，僅表征優(yōu)先關(guān)系，維修任務(wù)1直接進(jìn)入維修任務(wù)序列。為了清楚表達(dá)如何進(jìn)行資源分配和維修任務(wù)序列，進(jìn)一步假設(shè)當(dāng)前候選集為維修任務(wù)2和3，維修任務(wù)2需要資源1和2的數(shù)量分別為3和4，維修任務(wù)3需要資源1和2的數(shù)量分別為2和5，得到?jīng)Q策資源和維修任務(wù)序列，如圖3所示。

如果資源1和資源2的總供應(yīng)量分別為5和10，維修任務(wù)2和維修任務(wù)3可同時(shí)安排，資源1正好等于供應(yīng)量，資源2剩余量為1。如果資源1和資源2的總供應(yīng)量分為5和7，則資源2的供應(yīng)量不能同時(shí)滿足維修任務(wù)2和3，維修任務(wù)2和3必須串行。根據(jù)圖3中的維修任務(wù)列表可知，維修任務(wù)3在維修任務(wù)2之前，當(dāng)資源不能滿足候選集維修任務(wù)同時(shí)進(jìn)行時(shí)，應(yīng)按照維修任務(wù)列表中的順序進(jìn)行，即優(yōu)先安排維修任務(wù)3，其次安排維修任務(wù)2。

步驟3：將候選集的維修任務(wù)推至已完成集合，更新緊前維修任務(wù)數(shù)。若緊前維修任務(wù)數(shù)為0的重新賦值為-1，若候選集中維修任務(wù)是未完成的維修任務(wù)的緊前任務(wù)，則未完成的維修任務(wù)的緊前數(shù)減1。重復(fù)上述步驟，直至候選集為空，完成維修計(jì)劃生成過(guò)程。

2.3"交換鄰域結(jié)構(gòu)設(shè)計(jì)

交換鄰域結(jié)構(gòu)是指交換維修任務(wù)列表中的兩個(gè)基因位的值。為了增加交換鄰域解的多樣性，本文在交換前進(jìn)行了預(yù)判。若兩個(gè)基因位上的維修任務(wù)存在優(yōu)先關(guān)系，則不進(jìn)行交換；否則，進(jìn)行交換。因?yàn)槿魞蓚€(gè)基因位上的維修任務(wù)存在優(yōu)先關(guān)系，交換前后解碼產(chǎn)生的維修計(jì)劃是相同的。交換鄰域結(jié)構(gòu)示意圖如圖4所示。隨機(jī)選中基因位4和5、8和9，因?yàn)樗鼈冎g不存在優(yōu)先關(guān)系，可進(jìn)行交換。

2.4"插入鄰域結(jié)構(gòu)

插入鄰域結(jié)構(gòu)是指隨機(jī)選擇某基因，將其插入到其他基因位，獲取新維修任務(wù)列表的鄰域構(gòu)造方式。以11個(gè)維修任務(wù)案例為例，插入鄰域構(gòu)造的過(guò)程演示如圖5所示。隨機(jī)選擇位置4的基因，將其插入到維修任務(wù)8之前。

2.5"均勻交叉鄰域結(jié)構(gòu)

均勻交叉鄰域結(jié)構(gòu)旨在實(shí)現(xiàn)鄰域的逐步移動(dòng)操作，一是實(shí)現(xiàn)鄰域跳轉(zhuǎn)，克服局部最優(yōu)；二是在跳轉(zhuǎn)的過(guò)程中繼續(xù)進(jìn)行搜索，找到優(yōu)于當(dāng)前解的新解。

均勻交叉鄰域跳轉(zhuǎn)搜索可描述如下：隨機(jī)生成一個(gè)新個(gè)體S，其所對(duì)應(yīng)的活動(dòng)列表為FFALnew，與最優(yōu)個(gè)體S*所對(duì)應(yīng)的活動(dòng)列表FFAL*進(jìn)行均勻交叉操作生成FFAL。對(duì)于FFAL中的每一個(gè)基因aj，產(chǎn)生一個(gè)均勻0～1分布的隨機(jī)數(shù)γ。若γ≤α（α為預(yù)定參數(shù)，α∈［0，1］），則aj繼承FFAL*的第一位基因。否則，繼承FFALnew的第一位基因。將aj同時(shí)從FFAL*和FFALnew中刪除，不斷循環(huán)，直至確定FFAL中的每一個(gè)活動(dòng)。

以11個(gè)活動(dòng)為例，設(shè)置參數(shù)a=0.6，均勻交叉鄰域結(jié)構(gòu)構(gòu)造過(guò)程如圖6所示。參與均勻交叉鄰域跳轉(zhuǎn)搜索的新個(gè)體采用交換鄰域和插入鄰域產(chǎn)生，而圖6中給出了當(dāng)前最優(yōu)個(gè)體和隨機(jī)生成的新個(gè)體。

隨機(jī)產(chǎn)生[0，1]的隨機(jī)數(shù)，從左向右依次讀取，如果產(chǎn)生的隨機(jī)數(shù)大于a，則均勻交叉鄰域跳轉(zhuǎn)搜索后的新個(gè)體選擇最優(yōu)個(gè)體S*中的對(duì)應(yīng)位置基因。否則，選擇新個(gè)體S中的對(duì)應(yīng)位置基因。需要注意的是，當(dāng)前位置基因可能存在重復(fù)情形，此時(shí)當(dāng)前基因位置賦值為0。均勻交叉領(lǐng)域跳轉(zhuǎn)搜索后的結(jié)果如圖7所示。

因均勻交叉鄰域結(jié)構(gòu)的新個(gè)體存在0值，是不完備的基因表達(dá)，通過(guò)與最優(yōu)個(gè)體S*進(jìn)行對(duì)比，順次補(bǔ)全缺少的基因值。修復(fù)后的基因個(gè)體如圖8所示。

3"性能分析

本文以最小化船舶維修工期為目標(biāo)，選取遺傳算法、蟻群算法、變鄰域搜索算法三種算法進(jìn)行求解。所有算法均采用Visual Studio 2019編程軟件。變鄰域搜索算法參數(shù)設(shè)置如下：種群為50，迭代次數(shù)為1000，固定值為0.6。

在本文中，測(cè)試案例來(lái)源于項(xiàng)目調(diào)度問(wèn)題網(wǎng)站。根據(jù)包含活動(dòng)數(shù)目的不同，從該網(wǎng)站案例庫(kù)中選取J10、J20、J30三種案例，每種案例隨機(jī)選取其中的50個(gè)作為測(cè)試案例。為了對(duì)比不同算法的性能，設(shè)置三種算法的種群數(shù)量均為50、迭代次數(shù)均為1000，結(jié)果見(jiàn)表1。

由表1可知：變鄰域搜索算法在47組案例中獲得最優(yōu)解；蟻群算法可獲得較多的最優(yōu)解，且多數(shù)案例測(cè)試結(jié)果優(yōu)于遺傳算法。由此可見(jiàn)，變鄰域搜索算法具有優(yōu)良的性能。

4"案例分析

某船舶維修工程包括30個(gè)維修任務(wù)，采用本文提出的變鄰域搜索算法，其甘特圖如圖9所示，算法收斂圖如圖10所示。

因該工程受多種資源限制，人為制訂工期方案時(shí)需不斷均衡各類(lèi)資源。通常，以某類(lèi)資源為主線，一旦資源沖突則采用串行開(kāi)展。因此，人為制定的工期為78d。采用變鄰域搜索算法，得到該案例的工期為37d，比原始工期減少42d，縮短了52.3%的計(jì)劃工期。

由圖10可知，算法收斂曲線在前20代迅速下降，在480代左右收斂于最優(yōu)解。這說(shuō)明該算法具有良好的收斂性，能夠快速獲得較優(yōu)的方案。

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

本文以船舶維修工程工期優(yōu)化為研究對(duì)象，在提煉該工程問(wèn)題科學(xué)屬性的基礎(chǔ)上，構(gòu)建船舶維修工程工期算法數(shù)學(xué)模型。針對(duì)船舶維修工程維修任務(wù)多、流程復(fù)雜等特點(diǎn)，提出變鄰域搜索算法并進(jìn)行求解。以工程案例驗(yàn)證該算法的有效性，以期為船舶維修工程工期計(jì)劃制訂提供參考。

參考文獻(xiàn)

[1]王俊龍， 樓京俊， 阮旻智."基于不確定性需求的船舶維修資源調(diào)度優(yōu)化[J]."海軍工程大學(xué)學(xué)報(bào)， 2022， 34（2）： 96-101.

[2]崔建雙， 呂玥， 徐子涵."基于Q-學(xué)習(xí)的超啟發(fā)式模型級(jí)算法求解多模式資源約束項(xiàng)目調(diào)度問(wèn)題[J]."計(jì)算機(jī)集成制造系統(tǒng)， 2022， 28（5）： 1472-1481.

[3]劉士新， 王夢(mèng)光， 聶義勇.多執(zhí)行模式資源受限工程調(diào)度問(wèn)題的優(yōu)化算法[J].系統(tǒng)工程學(xué)報(bào)， 2001， 16（ 1） ： 55-60.

[4]胡月， 陳志敏， 夏源， 等."基于關(guān)鍵鏈技術(shù)的艦船維修項(xiàng)目工期優(yōu)化[J]."項(xiàng)目管理技術(shù)， 2022，20（1）：14-20.

[5]張宇哲，董興業(yè)，周正．求解資源受限項(xiàng)目調(diào)度問(wèn)題的分支定界算法[J]．計(jì)算機(jī)科學(xué)， 2022（8）： 1-13.

[6]BUDDHAKULSOMSIRI J， KIM D S."Priority rule-based heuristic for multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting[J]."European Journal of Operational Research， 2006（178）： 374-"390.

[7]楊耀紅， 宋一鳴."資源約束型魯棒性項(xiàng)目調(diào)度的多目標(biāo)優(yōu)化[J]".項(xiàng)目管理技術(shù)， 2019， 17（12）： 37-42.

[8]EL-RAYES K， JUN D H."Optimizing resource leveling in construction projects[J]."Journal of Construction Engineering and Management， 2009， 135（11）： 1172-1180.

[9]郭曉劍，胡方勇．基于深度強(qiáng)化學(xué)習(xí)的隨機(jī)資源受限多項(xiàng)目動(dòng)態(tài)調(diào)度策略[J]．計(jì)算機(jī)應(yīng)用研究， 2022， 39（9）： 1-6.

[10]GHOBADI S， PARNAK S."Solving the resource constraint project scheduling problem （RCPSP） by the particle swarm optimization （PSO） method[J]."International Industrial Engineering Conference， 2018， 6（1）： 236-243.

[11]嚴(yán)珍珍，陳英武，邢立寧.基于改進(jìn)蟻群算法設(shè)計(jì)的敏捷衛(wèi)星調(diào)度方法[J].系統(tǒng)工程理論與實(shí)踐，2014，34（3）：793-801.

[12]XIAO J， WU Z， HONG X， et al."Integration of electromagnetism with multi-objective evolutionary algorithms for RCPSP[J].European Journal of Operational Research， 2016， 251（1）： 22-35.

收稿日期：2022-11-15

作者簡(jiǎn)介：

陳志敏（1982—），男，高級(jí)工程師，博士，研究方向：船舶維修工程、項(xiàng)目管理。

夏源（1992—），女，工程師，研究方向：船舶維修保障。

王鵬（1979—），男，工程師，研究方向：項(xiàng)目管理。

王正湖（1983—），男，高級(jí)工程師，研究方向：船舶維修計(jì)劃。

張利平（1983—），女，教授，博士，研究方向：智能調(diào)度、項(xiàng)目管理。