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

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

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

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

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

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

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

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

1.1 問題定義

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

ESPLP問題的假設：

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

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

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

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

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

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

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

1.2 數(shù)學模型

數(shù)學模型符號：

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

υ——設備所在倉庫節(jié)點0、n+1與工序節(jié)點集合，即｛0，n+1｝∪N

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

ei——工序和倉庫i的最早開工時間，其中，0≤i≤n+1，e0=en+1=0

T——項目總工期，且

li——工序和倉庫i的最晚開工時間，其中，0≤i≤n+1，l0=ln+1=T

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

qi——工序和倉庫i的設備服務需求量（臺˙單位時間），其中，q0=qn+1=0

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

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

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

A——A∩V×V，（ij）∈A表示節(jié)點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中元素個數(shù)及需求車輛數(shù)均大于2的子集的集合

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

F——設備集合

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

數(shù)學模型目標函數(shù)為：

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

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

2 問題求解的難度分析

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

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

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

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

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

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

證明不失一般性，做如下假設：

（1）兩設備分別用f1、f2表示。

（2）兩設備服務共同工序為｛1，2，…，m｝。

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

（4）設備f1在共同服務工序｛1，2，…，m｝的服務時間有。

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

設備f1、f2總服務調(diào)度 時間T1、T2可由下式計算：

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

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

然而設備f2服務工序i的時長由變?yōu)?，當下式成立時，設備到達下一個服務節(jié)點j的時間將超過最晚開工時間lj，即

因此，定理2成立。

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

3 遠緣雜交遺傳算法

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

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

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

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

3.2 算法設計思想

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

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

3.3 DCGA算法步驟

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

（2）計算適應度函數(shù)值。令NumIter=1（NumIter參數(shù)為目標函數(shù)連續(xù)未改進的迭代數(shù)），適應度評價函數(shù)為方案總成本的倒數(shù)。根據(jù)適應度函數(shù)計算種群中每個方案的適應度值。

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

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

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

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

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

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

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

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

圖2 DCGA 算法的流程圖

量化任意2個可行方案差異程度的計算方法：

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

4 案例求解與分析

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

圖3 項目及工序施工地所在位置

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖5 DCGA 與DCGA-1收斂過程對比示意圖

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

由于當前國際公認的SDVRPTW 標準算例比較鮮見，為了進一步驗證DCGA，本文采用DCGA（參數(shù)取值與表3 一致）求解了部分國際標準SDVRP算例，并與文獻[11，33]中的算法求解結(jié)果進行了比較。

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

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

5 結(jié)論

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

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

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

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