基于變鄰域搜索算法的多資源船舶維修項目工期優(yōu)化

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

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

0"引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1"編碼設(shè)計

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

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

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

2.2"解碼設(shè)計

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

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

步驟1：隨機(jī)選擇一個個體，維修任務(wù)列表以1至11的亂序排列，即1，3，2，5，7，4，6，8，9，10，11。一般而言，初始時刻只有維修任務(wù)1沒有緊前維修任務(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的個體為例，當(dāng)前候選集為維修任務(wù)1。因維修任務(wù)1不消耗資源和工時，僅表征優(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可同時安排，資源1正好等于供應(yīng)量，資源2剩余量為1。如果資源1和資源2的總供應(yīng)量分為5和7，則資源2的供應(yīng)量不能同時滿足維修任務(wù)2和3，維修任務(wù)2和3必須串行。根據(jù)圖3中的維修任務(wù)列表可知，維修任務(wù)3在維修任務(wù)2之前，當(dāng)資源不能滿足候選集維修任務(wù)同時進(jìn)行時，應(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ù)上述步驟，直至候選集為空，完成維修計劃生成過程。

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

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

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

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

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

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

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

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

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

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

3"性能分析

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

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

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

4"案例分析

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

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

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

5"結(jié)語

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

參考文獻(xiàn)

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

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

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

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

[5]張宇哲，董興業(yè)，周正．求解資源受限項目調(diào)度問題的分支定界算法[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]楊耀紅， 宋一鳴."資源約束型魯棒性項目調(diào)度的多目標(biāo)優(yōu)化[J]".項目管理技術(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ī)資源受限多項目動態(tài)調(diào)度策略[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è)計的敏捷衛(wèi)星調(diào)度方法[J].系統(tǒng)工程理論與實踐，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

作者簡介：

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

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

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

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

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