基于SDVRPTW 模型的項(xiàng)目設(shè)備優(yōu)化調(diào)度方法

饒衛(wèi)振 ，劉鋒 ，金淳，侯艷輝

（1.山東科技大學(xué) 經(jīng)濟(jì)管理學(xué)院，山東 青島 266590；2.東北財(cái)經(jīng)大學(xué) 管理科學(xué)與工程學(xué)院，遼寧 大連 116025；3.大連理工大學(xué) 系統(tǒng)工程研究所，遼寧 大連 116024）

資源約束下項(xiàng)目調(diào)度問題（Resource-Constrained Project Scheduling Problem，RCPSP）基于大型工程項(xiàng)目施工背景，需要將其細(xì)分為不同工序，并采用優(yōu)化方法，基于各種有限資源數(shù)量以及項(xiàng)目工序先后次序要求科學(xué)確定工序的最早和最晚開工時(shí)間，以保證整個(gè)項(xiàng)目的按期完成、達(dá)到成本最小或者收益最大。

由于RCPSP的求解復(fù)雜性為NP-hard，并且在工程項(xiàng)目中具有廣泛的應(yīng)用[1]。國(guó)內(nèi)外學(xué)者對(duì)該問題進(jìn)行了研究，并且重點(diǎn)針對(duì)在現(xiàn)實(shí)工程中，工序完成時(shí)間經(jīng)常不確切的情況，研究了隨機(jī)[2]、模糊[3]或不確定[4]完成時(shí)間的RCPSP 問題。另外，有部分學(xué)者針對(duì)RCPSP 問題進(jìn)行了優(yōu)化方法方面的研究[5-6]。但現(xiàn)有RCPSP 的研究主要假設(shè)資源有限的情況下如何優(yōu)化工期，并且假設(shè)各個(gè)工序?qū)τ谫Y源的需求獨(dú)立進(jìn)行滿足。然而，由于經(jīng)濟(jì)、社會(huì)和政治等外在因素的影響，一些大規(guī)模項(xiàng)目的各工程環(huán)節(jié)的開工和完工時(shí)間基本確定，而主要的問題是如何在工序中有效調(diào)度資源，以優(yōu)化資源消耗量。本文研究大規(guī)模項(xiàng)目設(shè)備調(diào)度問題（Equipmentscheduling Problems on Large-scale Project，ESPLP），假設(shè)項(xiàng)目總工期和其中各工序最早及最晚開工時(shí)間已經(jīng)確定，設(shè)備屬于非消耗資源且數(shù)量有限。在該條件下，如何在各個(gè)工序之間合理調(diào)度這些設(shè)備，因此，確切地說，ESPLP 與RCPSP 具有類似的工程背景，但問題的約束條件與優(yōu)化目標(biāo)均具有明顯區(qū)別。

ESPLP問題可以歸結(jié)為需求可拆分、帶時(shí)間窗的車輛路徑問題（Split-Delivery Vehicle Routing Problem with Time Windows，SDVRPTW）。項(xiàng)目中的工序等價(jià)于待服務(wù)的客戶、設(shè)備類似服務(wù)車輛，工序最早和最晚開工時(shí)間等價(jià)于時(shí)間窗，每個(gè)工序可先后接受多個(gè)設(shè)備，相當(dāng)于客戶需求可以拆分。

需求可拆分的車輛路徑問題（Split-Delivery Vehicle Routing Problem，SDVRP）由Dror 等 提出[7]，他們發(fā)現(xiàn)，客戶需求接受多輛車的服務(wù)有時(shí)能夠節(jié)約成本，并針對(duì)該問題提出了求解的構(gòu)建型算法[8]。隨后，有學(xué)者研究了SDVRP 的下界[9-10]，以及求解該問題的算法，Archetti等對(duì)該問題從模型分析[11]、復(fù)雜度比較[12]和有效算法方面進(jìn)行了較為全面的研究[13-15]。Frizzell等[16]在SDVRP 的基礎(chǔ)上考慮了時(shí)間窗約束，研究了SDVRPTW，并提出了求解的構(gòu)建型算法。針對(duì)SDVRPTW 問題，Desaulniers[17]研究了求解該問題的分支定界法；Archetti等[18]在Desaulniers的研究基礎(chǔ)上，提出了分支定界算法的改進(jìn)策略，進(jìn)一步提高了該算法求解SDVRPTW 的性能。孟凡超等[19]研究了求解SDVRP問題的禁忌搜索算法。楊亞璪等[17]采用三階段啟發(fā)式算法求解該問題，并取得了較為滿意的結(jié)果。劉旺盛等[21]證明了客戶需求不宜拆分應(yīng)滿足的條件，并設(shè)計(jì)了符合解的特征的聚類算法。

通過分析以上研究發(fā)現(xiàn)：①SDVRPTW 問題中客戶的時(shí)間窗是相互獨(dú)立的；②車輛對(duì)每個(gè)客戶服務(wù)的時(shí)間是提前設(shè)計(jì)的常量，與車輛的送貨量無關(guān)；③當(dāng)前鮮見將SDVRPTW 模型應(yīng)用于項(xiàng)目設(shè)備優(yōu)化調(diào)度的文獻(xiàn)。本文研究項(xiàng)目設(shè)備調(diào)度優(yōu)化問題，部分工序之間存在先后次序關(guān)系，緊前工序的實(shí)際開工時(shí)間會(huì)直接影響緊后工序的最早開工時(shí)間，因此，本問題中每個(gè)工序的最早開工時(shí)間并不是相互獨(dú)立的；另外，工序中需求某種設(shè)備的量一般采用“輛（臺(tái)）˙天”表示，即工序?qū)υO(shè)備的需求量與時(shí)間密切相關(guān)。本文基于SDVRPTW 模型和問題本身特征，構(gòu)建了數(shù)學(xué)模型，并證明了項(xiàng)目設(shè)備最優(yōu)調(diào)度方案應(yīng)具備的特征，針對(duì)模型提出了求解該問題的遠(yuǎn)緣雜交遺傳算法。最后，通過實(shí)際問題驗(yàn)證了本模型和算法的有效性。

1 問題定義與數(shù)學(xué)模型

1.1 問題定義

ESPLP問題定義：在屬于相同項(xiàng)目或不同項(xiàng)目的n個(gè)工序中，均需要使用存在指定倉(cāng)庫(kù)的某種設(shè)備（使用完成后設(shè)備需要運(yùn)回倉(cāng)庫(kù)），已知每個(gè)工序的最早開工時(shí)間ei與最晚開工時(shí)間li、持續(xù)時(shí)間ai及工序間的緊前關(guān)系矩陣Sn×n，當(dāng)工序i是j的緊前工序時(shí)，sij=1，否則等于0（sij∈Sn×n），且每個(gè)工序?qū)υ撛O(shè)備的需求量為qi（臺(tái)˙單位時(shí)間），且設(shè)在任意兩工序i、j間調(diào)度設(shè)備的耗時(shí)和成本分別為tij和cij，如何在保證各工序需求得到完全滿足的前提下，確定需要的設(shè)備數(shù)量以及分別在n個(gè)工序和倉(cāng)庫(kù)間服務(wù)的次序和持續(xù)時(shí)間，并使所有設(shè)備在項(xiàng)目工期T結(jié)束之前回到倉(cāng)庫(kù)，且總調(diào)度成本最低。

ESPLP問題的假設(shè)：

（1）調(diào)度的設(shè)備是工序使用的關(guān)鍵資源，如果設(shè)備沒有到對(duì)應(yīng)工序則不能開工。

（2）每個(gè)工序的設(shè)備需求可拆分，即可以調(diào)度多臺(tái)設(shè)備供其使用。

（3）任意節(jié)點(diǎn)間的調(diào)度成本和調(diào)度耗時(shí)符合三角不等式。

SDVRPTW 問題：設(shè)有n＇個(gè)客戶的需求量為，每個(gè)客戶接受服務(wù)的時(shí)間窗為，現(xiàn)配送中心有載量為Q的若干車輛，設(shè)客戶需求可以由多輛車滿足，任意兩客戶間的車輛移動(dòng)成本和耗時(shí)已知，問題的優(yōu)化目標(biāo)為車輛的總行駛成本最低。

項(xiàng)目設(shè)備調(diào)度問題與SDVRPTW 的相同點(diǎn)：①工序等價(jià)于客戶；②倉(cāng)庫(kù)等價(jià)于配送中心；③設(shè)備等價(jià)于配送車輛；④工序最早開工時(shí)間與最晚開工時(shí)間，等價(jià)于客戶接受服務(wù)的時(shí)間窗。

項(xiàng)目設(shè)備調(diào)度問題與SDVRPTW 的不同點(diǎn)：①工序間有緊前關(guān)聯(lián)（只有緊前工序完工后，工序才能開工），而客戶之間的時(shí)間窗是相互獨(dú)立的；②設(shè)備滿足工序需求表現(xiàn)為使用時(shí)間長(zhǎng)度，而配送車輛滿足客戶需求表現(xiàn)為送貨量。

由于本文研究的ESPLP問題與SDVRPTW 存在上述區(qū)別，故不能直接采用SDVRPTW 模型來解決本問題。

1.2 數(shù)學(xué)模型

數(shù)學(xué)模型符號(hào)：

N——工序節(jié)點(diǎn)集合｛1，2，…，n｝

υ——設(shè)備所在倉(cāng)庫(kù)節(jié)點(diǎn)0、n+1與工序節(jié)點(diǎn)集合，即｛0，n+1｝∪N

ai——工序i的持續(xù)時(shí)間，a0=an+1=0

ei——工序和倉(cāng)庫(kù)i的最早開工時(shí)間，其中，0≤i≤n+1，e0=en+1=0

T——項(xiàng)目總工期，且

li——工序和倉(cāng)庫(kù)i的最晚開工時(shí)間，其中，0≤i≤n+1，l0=ln+1=T

cij——設(shè)備由節(jié)點(diǎn)i調(diào)度至j的成本

qi——工序和倉(cāng)庫(kù)i的設(shè)備服務(wù)需求量（臺(tái)˙單位時(shí)間），其中，q0=qn+1=0

bef（i）——為工序i緊前工序集合

Sn×n——sij∈Sn×n表示工序i、j間的緊前關(guān)系，當(dāng)工序i是j的緊前工序時(shí)，sij=1；否則，sij=0

tij——設(shè)備由節(jié)點(diǎn)i調(diào)度至j的耗時(shí)

A——A∩V×V，（ij）∈A表示節(jié)點(diǎn)i～j可行，即ei+min｛ai，qj｝+tij≤lj

A（N）——A∩N×N，其中N×N為任意兩工序間的弧集合

A*（N）——A*（N）?A（N），如果（i，j）∈A*（N）必定（j，i）?A*（N），且（i，j）∈A*（N）的弧為

ku——｝

A-（u）——

P（N）——N中元素個(gè)數(shù)及需求車輛數(shù)均大于2的子集的集合

V+（i）——為在弧集合A中由節(jié)點(diǎn)i可直接調(diào)度的目的地節(jié)點(diǎn)集合

F——設(shè)備集合

H——調(diào)度方案中使用設(shè)備的數(shù)量

數(shù)學(xué)模型目標(biāo)函數(shù)為：

目標(biāo)函數(shù)式（1）表示最小化調(diào)度設(shè)備的總成本；約束條件式（2）表示滿足所有工序的需求量；式（3）約束了服務(wù)每個(gè)工序的最少設(shè)備數(shù)量；式（4）用于計(jì)算當(dāng)前調(diào)度方案用到的設(shè)備數(shù)量；式（5）表示調(diào)度方案中使用設(shè)備數(shù)量的取值范圍；式（6）是Kohl[22]在VRPTW 模型研究中證明的k-path不等式，表示服務(wù)工序數(shù)量和最少需求設(shè)備數(shù)量均大于等于2的任意工序集u，應(yīng)滿足的不等式。

約束條件式（7）～（9）約束了調(diào)度方案的設(shè)備服務(wù)路徑結(jié)構(gòu)，每臺(tái)設(shè)備服務(wù)的路徑均由節(jié)點(diǎn)0出發(fā)，經(jīng)過若干工序節(jié)點(diǎn)后回到節(jié)點(diǎn)n+1，式（7）表示任意設(shè)備開始只能調(diào)度至某個(gè)工序中；式（8）表示任意工序調(diào)度進(jìn)來和調(diào)度出去的設(shè)備數(shù)必須相等；式（9）表示所有設(shè)備最后均要回到倉(cāng)庫(kù)節(jié)點(diǎn)n+1。約束條件式（10）～（13）約束了設(shè)備調(diào)度至工序中使用時(shí)需要滿足的時(shí)間窗，式（10）表示設(shè)備調(diào)度至目標(biāo)工序到達(dá)時(shí)間必須早于或等于開始服務(wù)的時(shí)間；式（11）約束了任何設(shè)備到達(dá)目標(biāo)工序的服務(wù)時(shí)間必須在最早開工時(shí)間與最晚開工時(shí)間范圍內(nèi)；式（12）表示任何設(shè)備的服務(wù)工序時(shí)間的累加和不超過項(xiàng)目總工期；式（13）約束了設(shè)備服務(wù)的時(shí)間長(zhǎng)度不超過目標(biāo)工序的持續(xù)時(shí)間；式（14）表示任何工序的開工時(shí)間應(yīng)該晚于所有緊前工序的最早完工時(shí)間；式（15）表示本模型中的決策變量為0，1變量。

2 問題求解的難度分析

如前所述，本文研究的 ESPLP 類似于SDVRPTW，但也存在一定的區(qū)別。對(duì)于不帶時(shí)間窗的SDVRP問題其求解復(fù)雜度Archetti[11]做了比較深入的分析和研究。SDVRP 的求解難度要高于VRP問 題[11-12]，SDVRPTW 是SDVRP 的 一 般 化，其求解難度更大[17-18，23]。在SDVRP中，Dror等證明了定理1和推論成立[7-8]。

定理1在SDVRP 和SDVRPTW 的最優(yōu)解中，如果任意兩節(jié)點(diǎn)間的車輛行駛成本和耗時(shí)符合三角不等式，則任意兩配送車輛共同服務(wù)的客戶數(shù)量至多為1個(gè)。

推論如果任意兩節(jié)點(diǎn)間的車輛行駛成本和耗時(shí)符合三角不等式，則任意兩配送車輛的行駛路線包括m個(gè)（m≥2）共同服務(wù)的客戶，則一定可以找到一個(gè)共同服務(wù)客戶為m-1個(gè)、且更優(yōu)的可行配送方案。

Desaulniers[17]指出，定理1和推論在SDVRPTW 中同樣適用。

如前所述，ESPLP 與SDVRPTW 存在兩點(diǎn)區(qū)別：①工序間有緊前關(guān)聯(lián)（只有緊前工序完工后，工序才能開工），而客戶之間的時(shí)間窗是相互獨(dú)立的；②設(shè)備滿足工序需求表現(xiàn)為使用時(shí)間長(zhǎng)度，而配送車輛滿足客戶需求表現(xiàn)為送貨量。這導(dǎo)致本問題的工序時(shí)間窗為變量，且設(shè)備在工序的停留時(shí)間與工序需求量成正比，這也導(dǎo)致推論在本問題中不成立，即如定理2描述。

定理2如果任意兩設(shè)備可行服務(wù)路線包括m個(gè)（m≥2）共同服務(wù)的工序，則不一定可以找到一個(gè)共同服務(wù)工序?yàn)閙-1個(gè)、且更優(yōu)的可行調(diào)度方案。

證明不失一般性，做如下假設(shè)：

（1）兩設(shè)備分別用f1、f2表示。

（2）兩設(shè)備服務(wù)共同工序?yàn)椋?，2，…，m｝。

（3）設(shè)備f1、f2服務(wù)路線經(jīng)過的節(jié)點(diǎn)集合分別為V（f1）、V（f2）（包 括0 和n+1 節(jié) 點(diǎn)，顯 然，，服務(wù)路線閉回路的弧集合用S（f1）、S（f2）表示。

（4）設(shè)備f1在共同服務(wù)工序｛1，2，…，m｝的服務(wù)時(shí)間有。

要證明定理2等價(jià)于證明減少1個(gè)共同服務(wù)工序后，通過調(diào)整調(diào)度方案能夠同時(shí)使f1、f2服務(wù)方案可行（滿足服務(wù)時(shí)間窗，且累計(jì)服務(wù)時(shí)間、調(diào)度時(shí)間和等待時(shí)間不高于項(xiàng)目總周期T），且總調(diào)度成本較原來更低。

設(shè)備f1、f2總服務(wù)調(diào)度 時(shí)間T1、T2可由下式計(jì)算：

現(xiàn)任選公共服務(wù)工序i，i∈｛1，2，…，m-1｝，令設(shè)備f1放棄服務(wù)該工序，設(shè)備f2服務(wù)工序i的時(shí)長(zhǎng)由變?yōu)?，并設(shè)工序i在原設(shè)備f1服務(wù)路線中之前的節(jié)點(diǎn)為i+之后的節(jié)點(diǎn)為i-。

顯然，f1在取消1個(gè)服務(wù)工序后，到達(dá)節(jié)點(diǎn)i-的時(shí)間會(huì)提前Δt=ti+i+tii--ti+i-，由于耗時(shí)符合三角不等式，故必定有Δt≥0，即此時(shí)f1的服務(wù)路線可行；另外，由于調(diào)度成本也符合三角不等式，故取消工序i后，調(diào)度f(wàn)1節(jié)約的成本為

然而設(shè)備f2服務(wù)工序i的時(shí)長(zhǎng)由變?yōu)?，?dāng)下式成立時(shí)，設(shè)備到達(dá)下一個(gè)服務(wù)節(jié)點(diǎn)j的時(shí)間將超過最晚開工時(shí)間lj，即

因此，定理2成立。

與SDVRPTW 相比，ESPLP問題的最優(yōu)解結(jié)構(gòu)不具規(guī)律，在求解過程中難以發(fā)現(xiàn)方案的顯著缺陷。這導(dǎo)致ESPLP 問題與SDVRPTW 相比更加難以求解，并且至少也是NP-hard問題。

3 遠(yuǎn)緣雜交遺傳算法

遺傳算法是由Holland等在20世紀(jì)70年代提出的，現(xiàn)在已廣泛應(yīng)用于求解包括VRP 問題在內(nèi)的各種優(yōu)化問題。當(dāng)前，已經(jīng)有部分學(xué)者采用遺傳算法求解了VRPTW 問題，并取得了良好的效果[24-27]。本文研究的 ESPLP 問題類似于SDVRPTW 問 題，SDVRPTW 是VRPTW 的 擴(kuò) 展問題，并且針對(duì)遺傳算法容易較早收斂的缺點(diǎn)，設(shè)計(jì)了遠(yuǎn)緣雜交遺傳算法（Distance-cross Genetic Algorithm，DCGA）。

3.1 調(diào)度方案編碼

本文研究的問題較SDVRPTW 問題更加難以求解，不僅需要確定設(shè)備服務(wù)不同工序的路線，而且要確定設(shè)備在不同工序中服務(wù)的時(shí)間。在此，分別采用2個(gè)組數(shù)表示上述信息，如圖1所示，表示一個(gè)2臺(tái)設(shè)備服務(wù)5個(gè)工序的調(diào)度方案，且設(shè)項(xiàng)目總周期為10時(shí)間單位。

圖1 調(diào)度方案編碼示意圖

3.2 算法設(shè)計(jì)思想

傳統(tǒng)GA算法經(jīng)常過早收斂于質(zhì)量一般的求解結(jié)果，本文基于遺傳學(xué)中“父母基因互異，后代基因趨優(yōu)”的思想設(shè)計(jì)了DCGA。即父代方案在交叉變異的過程中，不僅考慮父代方案的質(zhì)量，并且考慮方案之間的結(jié)構(gòu)差異，從而在進(jìn)行父代方案兩兩分組過程中，將結(jié)構(gòu)差異較大的方案之間進(jìn)行交叉產(chǎn)生新方案。

因此，DCGA 算法與傳統(tǒng)GA 的主要區(qū)別在于交叉變異父代解選擇階段，前者父代選擇同時(shí)考慮了個(gè)體的結(jié)構(gòu)差異和適應(yīng)度值，而后者僅根據(jù)適應(yīng)度值大小選擇交叉變異的父代解。

3.3 DCGA算法步驟

（1）生成初始種群。采用快速貪婪算法[28]與插入算法[29]生成規(guī)模為NumofSolution（為偶數(shù)）的初始方案種群。

（2）計(jì)算適應(yīng)度函數(shù)值。令NumIter=1（NumIter參數(shù)為目標(biāo)函數(shù)連續(xù)未改進(jìn)的迭代數(shù)），適應(yīng)度評(píng)價(jià)函數(shù)為方案總成本的倒數(shù)。根據(jù)適應(yīng)度函數(shù)計(jì)算種群中每個(gè)方案的適應(yīng)度值。

（3）計(jì)算結(jié)構(gòu)差異程度。計(jì)算種群中任意2個(gè)方案的結(jié)構(gòu)差異程度值，計(jì)算公式如式（19）所示，可以得到NumofSolution×NumofSolution的差異程度矩陣數(shù)據(jù)。

（4）父代方案匹配?；冢?）計(jì)算的差異程度結(jié)果矩陣，采用文獻(xiàn)[30]中的快速算法進(jìn)行兩兩匹配，以最大化總差異程度值為目標(biāo)。

（5）進(jìn)行交叉變異。采用雙交叉點(diǎn)操作，基于父代解匹配分組方案，采用PIX[31]和OX[32]法進(jìn)行交叉得到下一代種群，并且以概率Pc進(jìn)行變異。

（6）修復(fù)不可行方案。檢查交叉后方案的可行性，對(duì)于不可行方案，采用插入法調(diào)整修復(fù)。

（7）優(yōu)勝劣汰。為了保持種群規(guī)模，淘汰質(zhì)量最差的NumofSolution/2方案，使種群大小保持為NumofSolution，計(jì)算當(dāng)前最優(yōu)解，如果沒有改進(jìn)，則NumIter=NumIter+1。

（8）終止條件判斷。如果NumIter大于設(shè)定參數(shù)NumofSolution或運(yùn)行時(shí)間達(dá)Tmax，符合終止條件，則轉(zhuǎn)（2），否則轉(zhuǎn)（9）。

（9）輸出最優(yōu)方案。輸出種群中最優(yōu)方案。

DCGA 算法的流程圖如圖2所示。

圖2 DCGA 算法的流程圖

量化任意2個(gè)可行方案差異程度的計(jì)算方法：

式中：IdeNum Arc（xi，xj）為方案xi、xj之間相同弧的數(shù)量；Num Arc（xi）為方案xi中總的弧數(shù)量，顯然，按照式（19）計(jì)算的任意兩方案之間的差異程度取值范圍在[0，1]之間。

4 案例求解與分析

以某建筑集團(tuán)公司在青島工程項(xiàng)目調(diào)度挖掘機(jī)為例，其數(shù)據(jù)來源為作者實(shí)際調(diào)研取得。具體信息為，本項(xiàng)目共100多個(gè)工序，其中有25個(gè)工序涉及到使用挖掘機(jī)。25個(gè)工序開始施工地點(diǎn)和設(shè)備所在庫(kù)區(qū)如圖3所示（A 為位置標(biāo)識(shí)）。由圖3可見，25個(gè)工序和挖掘機(jī)所在倉(cāng)庫(kù)（調(diào)配中心，用0表示）的位置大概分布在3～5 km2的施工區(qū)域，為了確切表示其所在位置，以倉(cāng)庫(kù)所在地為原點(diǎn)建立一個(gè)直角坐標(biāo)系，然后計(jì)算25個(gè)工序在此坐標(biāo)系中的坐標(biāo)位置，具體坐標(biāo)信息及各工序相關(guān)數(shù)據(jù)如表1所示。項(xiàng)目計(jì)劃所有挖掘工作應(yīng)在20個(gè)工作日之內(nèi)完成，即T=20。表1中各工序時(shí)間點(diǎn)表示結(jié)束時(shí)間，如工序1的最早開工時(shí)間e2=2，表示第2個(gè)工作日結(jié)束時(shí)間，即第3個(gè)工作日開始時(shí)間。

圖3 項(xiàng)目及工序施工地所在位置

注意在表1中，當(dāng)ei=li時(shí)，表示關(guān)鍵工序，即工序需要的設(shè)備必須在ei=li之前到達(dá)，如工序5、9、12均為關(guān)鍵工序；在非關(guān)鍵工序中，工序19是24的緊前工序，因此，當(dāng)設(shè)備調(diào)度至工序19的時(shí)間t早于e19時(shí)，有

成立；當(dāng)設(shè)備調(diào)度至工序19的時(shí)間t在e19～l19時(shí)，工序24的最早開工時(shí)間將變?yōu)閑24=t+a19。

實(shí)際工作中，當(dāng)前調(diào)度設(shè)備的方法為人工調(diào)度法，并且假設(shè)各工序之間的調(diào)度和裝配檢修時(shí)間、不同工序施工地點(diǎn)之間調(diào)度成本相同，如假設(shè)各工序之間調(diào)度和設(shè)備檢修時(shí)間均為0.5天。人工調(diào)度方法步驟：①根據(jù)各工序最早開工時(shí)間和最晚開工時(shí)間的平均值（ei+li）/2，并根據(jù)（ei+li）/2+ai取值按升序方式將工序排序；②根據(jù)排序?qū)⒐ば虬才胖镣诰驒C(jī)，找到第1臺(tái)挖掘機(jī)的服務(wù)路線；③不考慮已滿足需求的工序，基于剩下的工序重復(fù)②，直至所有工序滿足需求。

根據(jù)人工調(diào)度方法，本實(shí)例的調(diào)度方案需要8臺(tái)挖掘機(jī)，服務(wù)工序順序分別為：

挖掘機(jī)在每個(gè)工序的停留時(shí)間為需求量qi，其中工序2、25、14在工序的持續(xù)時(shí)間ai＜qi，因此，單臺(tái)挖掘機(jī)無法滿足其需求，工序2挖掘機(jī)2、3服務(wù)時(shí)間分別為2、1；工序25挖掘機(jī)5、7服務(wù)時(shí)間分別為2、0.5；工序14挖掘機(jī)6、8服務(wù)時(shí)間分別為1、1。

表1 包含25個(gè)工序的ESPLP實(shí)例相關(guān)數(shù)據(jù)

按照人工調(diào)度方法必定可以找到一個(gè)可行調(diào)度方案，使所有的工序均能夠在要求時(shí)間內(nèi)完成施工。但人工調(diào)度法簡(jiǎn)單假設(shè)任意工序之間調(diào)度耗時(shí)和成本相同是不合理的，本文基于實(shí)際調(diào)度中耗費(fèi)的人力及根據(jù)施工地點(diǎn)之間距離信息，得到任意2個(gè)工序間調(diào)度1 臺(tái)挖掘機(jī)的成本和耗時(shí)矩陣，如表2 所示，其中調(diào)度耗時(shí)包括設(shè)備的檢修時(shí)間。

表2 包含25個(gè)工序的ESPLP實(shí)例的任意工序之間調(diào)度成本（下三角）和耗時(shí)（上三角）

表2中成本單位為元，耗時(shí)單位為工作日。按照表2，可以計(jì)算得到人工調(diào)度方法得到的總成本為16 310元。

基于本實(shí)例，采用本文提出的模型和DCGA 算法求解，其中DCGA 中的相關(guān)參數(shù)如表3所示。編程語(yǔ)言為 MatlabR 2012b，運(yùn)行平臺(tái)為CPU 為Inter（R）core（TM）2 Duo，內(nèi)存為2.0 GB，主頻為2.93 GHz。

表3 DCGA算法參數(shù)取值

求解得到的調(diào)度方案共需要4臺(tái)挖掘機(jī)，其服務(wù)路線分別為：

其中工序2、25、14在工序的持續(xù)時(shí)間ai＜qi，因此，單臺(tái)挖掘機(jī)無法滿足其需求，工序2挖掘機(jī)1、2服務(wù)時(shí)間分別為1.5、1.5；工序25挖掘機(jī)3、4服務(wù)時(shí)間分別為1、1.5；工序14挖掘機(jī)3、4服務(wù)時(shí)間分別為1、1。根據(jù)表2調(diào)度成本矩陣計(jì)算得到總調(diào)度成本為6 960元，遠(yuǎn)低于人工調(diào)度方案的16 310元，其挖掘機(jī)服務(wù)路線如圖4所示。

圖4 DCGA 求解的調(diào)度方案

通過求解結(jié)果表明，采用本文提出的模型和算法得到的調(diào)度方案，與實(shí)踐中人工調(diào)度方法相比能大幅度減少設(shè)備數(shù)量和總調(diào)度成本，充分利用設(shè)備資源。

為了驗(yàn)證本文設(shè)計(jì)的DCGA 算法步驟（4）中父代方案匹配策略的有效性，在此，分別采用標(biāo)準(zhǔn)DCGA 算法和在步驟（4）中采用隨機(jī)匹配方式的DCGA（為了方便描述用DCGA-1 表示）求解本問題，兩者求解的收斂過程如圖5所示。

圖5 DCGA 與DCGA-1收斂過程對(duì)比示意圖

由圖5 可知，雖然DCGA-1 收斂更快，但求解質(zhì)量低于DCGA。因此，在遺傳算法中選擇父代方案進(jìn)行交叉變異時(shí)，考慮父代方案結(jié)構(gòu)差異能夠提升遺傳算法的求解質(zhì)量，可以克服傳統(tǒng)遺傳算法過早收斂的缺陷。

由于當(dāng)前國(guó)際公認(rèn)的SDVRPTW 標(biāo)準(zhǔn)算例比較鮮見，為了進(jìn)一步驗(yàn)證DCGA，本文采用DCGA（參數(shù)取值與表3 一致）求解了部分國(guó)際標(biāo)準(zhǔn)SDVRP算例，并與文獻(xiàn)[11，33]中的算法求解結(jié)果進(jìn)行了比較。

由求解結(jié)果發(fā)現(xiàn)，DCGA 的優(yōu)化質(zhì)量非常具有競(jìng)爭(zhēng)力，求解20個(gè)算例中的15個(gè)算例結(jié)果優(yōu)于文獻(xiàn)[11，33]中的算法（表4中DCGA 求解最優(yōu)算例結(jié)果加粗顯示），且總體平均改進(jìn)在5%左右。

表4 DCGA與文獻(xiàn)[11，33]中算法求解結(jié)果對(duì)比

5 結(jié)論

在大型項(xiàng)目中經(jīng)常涉及多個(gè)不同工序使用共同有限資源設(shè)備，資源設(shè)備在不同工序中的有效調(diào)度能夠有效降低施工成本，提高設(shè)備利用率。本文將該設(shè)備調(diào)度問題ESPLP歸結(jié)為類似SDVRPTW 的問題，并建立了數(shù)學(xué)模型，設(shè)計(jì)了DCGA 算法求解本問題，得到如下結(jié)論：

（1）ESPLP 也 是 NP-hard 問 題 并 且 與SDVRPTW 相比更加難以求解。

（2）ESPLP 問 題 的 最 優(yōu) 解 與SDVRPTW 不同，兩臺(tái)設(shè)備服務(wù)的共同工序可以超過2。

（3）DCGA 算法能夠有效求解ESPLP問題，通過求解實(shí)例發(fā)現(xiàn)，DCGA 得到的求解方案，與實(shí)際中的人工調(diào)度方法相比，能夠大幅度節(jié)約使用的設(shè)備數(shù)量和總調(diào)度成本，并且求解SDVRP 標(biāo)準(zhǔn)算例的性能具有較強(qiáng)競(jìng)爭(zhēng)力。