胡雪君,梁 盛,王建江,崔南方

(1.湖南大學 工商管理學院,湖南 長沙 410082; 2.國防科技大學 系統(tǒng)工程學院,湖南 長沙 410073;3.華中科技大學 管理學院,湖北 武漢 430074)

0 引言

全球經(jīng)濟活動中有30%是采用項目形式執(zhí)行,涉及年產(chǎn)值約27萬億美元。在項目管理過程中不可避免地會涉及到資源的使用,包括可更新資源(如勞動力、設(shè)備)和不可更新資源(如物料、資金)。資源受限項目調(diào)度問題(Resource-Constrained Project Scheduling Problem,RCPSP)研究的是在滿足活動優(yōu)先關(guān)系和資源約束(主要指可更新資源)的前提下,制定出滿足項目預期目標(比如完工時間最短)的基準調(diào)度計劃(baseline schedule),作為資源分配、活動開工的基礎(chǔ)以及項目各利益方協(xié)調(diào)的依據(jù),科學有效的項目調(diào)度計劃與資源配置方案有助于提高企業(yè)項目管理的效率[1-2]?，F(xiàn)實中,如果資源在項目間或活動間的時移時間與活動工期相比無法忽略,就有必要在制定項目調(diào)度計劃時考慮資源的轉(zhuǎn)移時間,例如建筑工程項目中重型機械設(shè)備(起重機等)從一個位置移動到另一個位置需要移動和調(diào)試時間。此外,資源必須根據(jù)活動內(nèi)容進行調(diào)整時也需要相應的準備時間,例如機器生產(chǎn)不同的產(chǎn)品時須進行清洗、IT項目中人力資源往往需要時間熟悉新工作等[3-4]。這類問題稱為帶轉(zhuǎn)移時間的資源受限項目調(diào)度問題(RCPSP with Transfer Times,RCPSP-TT)。

目前,針對RCPSP-TT問題,只有少數(shù)學者進行了研究。KRüGER等[4]根據(jù)可更新資源是否可以自主轉(zhuǎn)移,將轉(zhuǎn)移資源劃分為不同的類型,并考慮資源轉(zhuǎn)移成本建立了混合整數(shù)規(guī)劃模型;KRüGER等[5]分別以最小化項目總工期和項目平均工期為目標建立RCPSP-TT優(yōu)化模型,提出了基于活動列表的串行調(diào)度和并行調(diào)度啟發(fā)式算法;POPPENBORG等[6]針對RCPSP-TT問題設(shè)計了一種基于資源流的禁忌搜索算法,該算法利用資源流表示問題的解,并基于串行調(diào)度和并行調(diào)度機制提出了資源流鄰域算子;胡雪君等[7]在文獻[6]研究工作的基礎(chǔ)上,以找到時間最短的關(guān)鍵路徑為基準,合理改進了鄰域算子的選擇方式,進一步設(shè)計了改進的禁忌搜索算法和貪心隨機自適應搜索算法,模擬實驗表明兩種算法均可針對更多的項目實例求得最優(yōu)解;KADRI等[8]結(jié)合調(diào)度生成機制和優(yōu)先級規(guī)則提出一種遺傳算法求解RCPSP-TT問題,采用活動列表編碼對調(diào)度方案進行描述,設(shè)計了基于雙點交叉和概率變異的遺傳操作;文獻[9-10]提出一種內(nèi)嵌分支定界尋優(yōu)搜索的遺傳算法,設(shè)計了一種適應算法結(jié)構(gòu)的基于活動絕對順序的編碼策略;文獻[11]針對帶資源轉(zhuǎn)移時間的多技能RCPSP問題開展研究,考慮資源技能的不確定性建立了一個魯棒優(yōu)化模型,提出了一種新的遺傳算法求解模型。此外,文獻[12-15]針對多項目環(huán)境下帶資源轉(zhuǎn)移時間的項目調(diào)度問題開展了研究。

然而,上述研究絕大多數(shù)都是在確定條件下開展的,大都以項目完工期最短為優(yōu)化目標,不能適應復雜環(huán)境中不確定性對項目的規(guī)劃和調(diào)度提出的高要求。魯棒性項目調(diào)度作為解決不確定條件下項目調(diào)度問題的有效方法,近些年來受到了學者們的廣泛關(guān)注[16-17]。該方法在充分挖掘和利用不確定信息的基礎(chǔ)上,主動采取一些必要措施,生成“受到保護的”、抗干擾能力強的前攝調(diào)度計劃,使不確定性因素對方案執(zhí)行的影響最小化。學術(shù)界將項目調(diào)度的魯棒性分為質(zhì)魯棒性和解魯棒性兩種:質(zhì)魯棒性(quality robustness)是指基準計劃對應的目標函數(shù)值(如項目工期、成本等)對干擾因素的不敏感性;解魯棒性(solution robustness)是指基準計劃與項目實際執(zhí)行時進度計劃之間的差別大小[18-19]。

為提升項目調(diào)度方案的解魯棒性,文獻中廣泛探討了兩種主要方法,即時間緩沖(time buffering)和魯棒資源分配(robust resource allocation)。前者是指在項目活動前加入緩沖時間用以吸收各種不確定因素的干擾,阻止其在調(diào)度計劃中的傳播,保證項目盡可能按基準計劃進行[20];后者旨在通過優(yōu)化項目活動間可更新資源傳遞的路徑(資源流網(wǎng)絡)來提升調(diào)度計劃的穩(wěn)健性[2,21]。針對魯棒資源分配問題,LEUS等[21]提出保護基準計劃不受活動工期變動干擾的資源流網(wǎng)絡優(yōu)化模型,采用分支定界算法求解單資源小規(guī)模問題,其目標函數(shù)是最小化活動實際開始時刻偏離計劃開始時刻的懲罰成本;DEBLAERE等[22]考慮活動工期的不確定性,為了提升項目調(diào)度計劃的魯棒性,分別提出了三種混合整數(shù)規(guī)劃模型和一種MABO(myopic activity-based optimization)啟發(fā)式算法,該算法通過仿真模擬和局部尋優(yōu)的方式構(gòu)建穩(wěn)定的資源流網(wǎng)絡?？紤]到模擬方法不能保證資源分配方案的唯一性,文獻[2]和文獻[23]對MABO算法進行了改進,采用一種拖期懲罰成本指標來評估可行資源分配方案的魯棒性,仿真實驗證明該方法獲得的資源流網(wǎng)絡具有唯一性,并且大大降低了算法計算量;文獻[24]提出一種基于前向活動優(yōu)先級的魯棒資源分配啟發(fā)式算法,實驗證明該方法可以減少資源傳輸形成的額外工序約束,提升調(diào)度計劃的魯棒性。此外,胡雪君等[26]、WANG等[27]考慮資源轉(zhuǎn)移成本建立魯棒資源分配優(yōu)化模型,不同于以往研究均采用基于活動的資源流描述,他們定義了基于資源的二元決策變量來表示資源在活動間的傳輸次序。需要指出的是,上述研究都是基于活動開始時間已知的調(diào)度計劃對資源流進行決策(兩階段),忽略了活動安排和資源轉(zhuǎn)移決策的相互影響及協(xié)調(diào)。

資源流網(wǎng)絡優(yōu)化為研究不確定項目調(diào)度問題提供了一種新的思路。但是,現(xiàn)有魯棒資源分配相關(guān)文獻都是針對傳統(tǒng)RCPSP開展研究,忽略了資源轉(zhuǎn)移時間對活動進度計劃和資源分配方案魯棒性的影響,難以適用于帶轉(zhuǎn)移時間的RCPSP-TT問題。針對已有研究的局限性,本文同時考慮資源轉(zhuǎn)移時間和活動工期的不確定性,將問題建模為集成的魯棒項目調(diào)度問題,即針對活動調(diào)度和資源轉(zhuǎn)移同時進行決策。本文的主要研究貢獻體現(xiàn)在以下三個方面:①針對RCPSP-TT問題特征,分別從資源轉(zhuǎn)移關(guān)系、活動時差、隨機活動工期3個不同角度設(shè)計了三種解魯棒性代理指標,構(gòu)建了兩個混合整數(shù)規(guī)劃模型(minEA,maxPF)和一個隨機規(guī)劃模型(minTPC);②通過引入輔助變量將maxPF模型線性化為可采用CPLEX優(yōu)化軟件求得最優(yōu)解,并設(shè)計了求解minTPC模型的改進禁忌搜索啟發(fā)式算法;③設(shè)計大規(guī)模仿真實驗對不同優(yōu)化模型及算法的有效性進行對比分析,并給出了相應的管理啟示。

1 問題描述

采用節(jié)點式網(wǎng)絡G(N,A)表示一個項目,記活動集合為N={0,1,…,n,n+1},其中序號0和n+1分別代表虛擬首活動和虛擬尾活動,A代表活動之間的結(jié)束-開始型工序優(yōu)先關(guān)系(i,j)的集合。記資源種類集合為K,第k(k=1,2,…,K)種資源的可用量為ak。由于資源的約束性,有限的資源在項目活動節(jié)點間傳輸會形成資源驅(qū)動的新工序約束,假設(shè)活動i完工后,其占用的資源部分或全部分配給了活動j,則活動i和j之間就存在一條資源流,fijk(i,j∈N,k∈K)表示從活動i流向活動j的資源k的數(shù)量。fijk>0表示活動i和j之間存在資源轉(zhuǎn)移關(guān)系,以一條資源弧(i,j)k連接活動i和j;將所有的資源弧集合定義為AR,構(gòu)成了項目資源流網(wǎng)絡G(N,AR)。資源k從活動i流向活動j需要一定的資源轉(zhuǎn)移時間Δijk≥0,且滿足三角形規(guī)則,即Δihk+Δhjk≥Δijk,?i,j,h∈N。

本文所研究的魯棒RCPSP-TT具體表述為:項目決策者需要同時考慮工序優(yōu)先關(guān)系、資源可用量約束、項目交付期限以及隨機活動時間,確定如何安排活動執(zhí)行順序及資源轉(zhuǎn)移次序,以使調(diào)度計劃的解魯棒性(穩(wěn)定性)最強。問題相關(guān)參數(shù)及含義如表1所示。

圖1描述了一個帶資源轉(zhuǎn)移時間的項目網(wǎng)絡示例,其中實箭線表示活動之間的工序優(yōu)先關(guān)系。該項目包括8個活動(其中0和7為虛擬活動),只用到一種可更新資源(下文省略下標k),資源總量為10。

圖2a和圖3a分別給出了兩個可行的資源轉(zhuǎn)移方案,其中虛箭線表示資源驅(qū)動的新工序約束(額外資源弧),實箭線弧和虛箭線弧上數(shù)字均代表資源轉(zhuǎn)移數(shù)量。采用文獻[4]中的并行調(diào)度(Parallel Schedule Generation Scheme,PSGS)策略與最早開始時間(Earliest Starting Time,ES)優(yōu)先規(guī)則對資源流網(wǎng)絡G(N,A∪AR)進行解碼,則可得到如圖2b和圖3b所示的項目調(diào)度計劃,對應的項目工期均為14。

分析圖2和圖3可知,由于兩個可行方案中資源轉(zhuǎn)移關(guān)系及轉(zhuǎn)移時間的不同,同等程度的工期擾動對兩個方案的魯棒性具有不同的影響。例如,第一種情況,假設(shè)活動5的實際工期拖延1個時間單位,對于方案I,將導致活動6的開始時間推遲一個單位,項目完工期保持14不變;而對于方案Ⅱ,同樣導致活動6的開始時間推遲一個單位,并且導致項目延遲一個單位時間完工(即項目完工期為15)。第二種情況,假設(shè)活動1的實際工期拖延1個時間單位,對于方案Ⅰ,將導致活動4的開始時間延遲一個單位,最終導致項目延遲一個單位時間完工(即項目完工期為15);而對于方案Ⅱ,將導致活動4、活動5、活動6的開始時間都推遲一個單位,項目同樣延遲一個單位時間完工。值得注意的是,第二種情況下雖然項目完工期都是延遲1個單位時間,但是對后續(xù)活動調(diào)度計劃的影響不同,方案Ⅰ僅影響了后續(xù)一個活動(活動4),方案Ⅱ影響了后續(xù)三個活動(活動4,5,6),因此對項目調(diào)度計劃的擾動差異導致不同調(diào)度方案的解魯棒性不同。那么,如何判斷上述哪一種調(diào)度方案應對活動拖期風險的能力更強?為此,需要設(shè)計合理的魯棒性衡量指標,并在此基礎(chǔ)上建立集成的RCPSP-TT前攝調(diào)度優(yōu)化模型。

2 混合整數(shù)規(guī)劃模型

本節(jié)分別以最小化資源弧數(shù)量和最大化活動成對時差為魯棒性代理指標,構(gòu)建RCPSP-TT前攝調(diào)度模型。模型決策變量定義為:

sj為活動j的計劃開始時間(sj∈Z+),j∈N;

?t=1,…,T,j∈N;

fijk為活動i流向活動j的第k種資源的數(shù)量,i,j∈N,k∈K;

2.1 最小化資源弧數(shù)量(MinEA)

DEBLAERE等[22]的研究表明,項目活動之間由于資源轉(zhuǎn)移而施加的額外優(yōu)先關(guān)系(資源弧)的數(shù)量越少,進度計劃執(zhí)行通常越穩(wěn)定;但是他們的研究是基于活動開始時間已知的初始調(diào)度計劃構(gòu)建資源流網(wǎng)絡,且沒有考慮資源轉(zhuǎn)移時間對項目調(diào)度方案的影響。為此,本節(jié)補充定義0-1決策變量zij,如果任一資源k∈K從活動i流向活動j,zij=1;否則,zij=0。以最小化額外資源弧(Extra Arcs,EA)數(shù)量為優(yōu)化目標,針對RCPSP-TT建立MinEA模型如下:

(1)

s.t.

si+di-sj≤0,?i∈J∪{0},j∈Succi;

(2)

si+di+Δijk-sj≤T(1-yijk),
?i∈J∪{0},j∈Jri,k∈K;

(3)

(4)

(5)

(6)

fijk≤yijk×min{rik,rjk},
?i∈N,j∈Jri,k∈K;

(7)

yijk≤fijk,?i∈N,j∈Jri,k∈K;

(8)

(9)

sn+1≤D;

(10)

xjt={0,1},?t=0,…,T,j∈N;

(11)

fijk∈Z+,yijk={0,1},
?i∈J∪{0},j∈Jri,k∈K;

(12)

(13)

yijk≤zij,?i∈J∪{0},j∈Jri,k∈K;

(14)

zij∈{0,1},?i∈J∪{0},j∈Jri。

(15)

式(2)是活動優(yōu)先關(guān)系約束,即活動i完成之前,其緊后活動j不能開始;式(3)表示活動開始時間與資源轉(zhuǎn)移時間的關(guān)系,即如果資源k從活動i與轉(zhuǎn)移到活動j,則活動j必須在活動i結(jié)束且資源轉(zhuǎn)移完成之后才能開始;式(4)表示任意活動j只能在一個時間點開始;式(5)表示活動開始時間sj與決策變量xjt的關(guān)系;式(6)是資源流平衡約束,表示流入活動j的資源k的總量與流出該活動的資源k的總量須相等,且等于該活動對資源k的需求量;式(7)和式(8)共同定義了yijk和fijk之間的關(guān)系,即當活動之間存在資源轉(zhuǎn)移時,yijk=1,否則yijk=0;式(9)是資源需求約束,表示任意時刻正在進行的活動對于資源k的消耗量不超過資源總供應量;式(10)為項目交付日期約束;式(11)～式(12),(15)定義了決策變量的可行域;式(13)表示對任意資源k∈K,從虛擬首活動流出的資源數(shù)量等于流入虛擬尾活動的資源數(shù)量,并且都等于該資源的可用量ak;式(14)表示對任意資源k∈K,只要yijk取值為1(即fijk>0),則zij=1。

2.2 最大化成對時差(MaxPF)

基于時差的魯棒性代理指標具有不需要考慮不確定事件的相關(guān)信息、不依賴于模型仿真等優(yōu)勢,是一種衡量解魯棒性的主要方法[20]。一般而言,如果活動i和j之間的自由時差越大,其吸收工期擾動的能力越強,即前序活動i拖期對后序活動j的影響越小。因此,部分學者考慮增加具有前后序關(guān)系的兩兩配對活動之間的時差,以達到提高調(diào)度方案魯棒性的目的[28]。針對RCPSP問題,DEBLAERE等[22]對于所有滿足si+di≤sj的活動對(i,j),定義了一個成對時差(pairwise float)指標,其值等于活動j的開始時間與活動i的結(jié)束時間之差,PFij=sj-(si+di)。需要注意的是,文獻[22]關(guān)于時差的定義不適用于本文研究的RCPSP-TT問題。首先,文獻[22]是在活動開始時間sj(j∈J)已知的基礎(chǔ)上定義活動時差,即所有活動前后序關(guān)系已知,因此活動對(i,j)的時差PFij可以作為參數(shù),在問題建模前計算獲得。

例如,針對圖3所示的資源流網(wǎng)絡與項目調(diào)度方案Ⅱ,從活動2到活動6存在兩條資源轉(zhuǎn)移路徑。路徑2-4-6的成對時差之和為PF2,4,1+PF4,6,1=0+2=2;另一條路徑2-5-6的成對時差之和為PF2,5,1+PF5,6,1=2+0=2。因此,MSPF2,6,1=min{2,2}=2,由于該案例僅包含一種資源,所以pf26=MSPF2,6,1=2。這意味著活動2可以拖期2個單位完工而不影響活動6的開始。顯然,pfij值越大,對應的項目調(diào)度計劃及其資源流網(wǎng)絡越穩(wěn)定。

基于以上定義,以最大化活動成對時差總和為目標,建立MaxPF模型如下。

(16)

s.t.約束(2)～約束(12);

PFijk=max{0,sj-(si+di+yijkΔijk)},
i∈J∪{0},j∈Jri,k∈K;

(17)

MSPFijk≤PFilk+MSPFljk,i∈J∪{0},
j∈Jri,l∈Succi∩Jsj,k∈K;

(18)

MSPFijk≤PFilk+MSPFljk+M(1-yilk),
i∈J∪{0},j∈Jri,l∈Jri∩Jsj,k∈K;

(19)

MSPFijk≤PFijk,i∈J∪{0},j∈Succi,k∈K;

(20)

MSPFijk≤PFijk+M(1-yijk),
i∈J∪{0},j∈Jri,k∈K;

(21)

MSPFiik=0,i∈J∪{0},k∈K;

(22)

MSPFijk≤C,i∈J∪{0},j∈Jri,k∈K;

(23)

pfij≤MSPFijk,k∈K;

(24)

MSPFijk∈Z+,i∈J∪{0},
j∈Jri,k∈K。

(25)

式(16)為目標函數(shù),表示最大化所有可能發(fā)生資源轉(zhuǎn)移的活動對(i,j)的成對時差之和。式(17)表示對任意資源k∈K,如果活動j在活動i完成之后開始,則時差PFijk=sj-(si+di+yijkΔijk),否則PFijk=0;式(18)～式(19)以遞歸的方式計算(i,j)k的成對時差,式(18)對于(i,j)k定義了三角不等式,其中活動l是活動i的直接緊后工序,式(19)中如果可能的資源弧(i,l)k不存在(yilk=0),則式(19)不具有約束力,其中M是一個充分大的常數(shù)(下同);式(20)針對活動j是活動i的直接緊后工序的情況,給出了(i,j)k成對時差的上限;類似地,式(21)中如果可能的資源路徑(i,j)k不存在,則式(21)不具有約束力;式(22)表示每個活動相對于其自身的成對時差為0。需要指出的是,對于(i,j)k,如果所有的MSPFijk相關(guān)約束都不具有約束力,則說明活動i和j是工序優(yōu)先關(guān)系獨立且資源關(guān)系獨立的一對活動,此時MSPFijk將達到一個最大值C,如式(23)所示;式(24)表示成對時差pfij值等于所有資源種類k∈K中MSPFijk的最小值;式(25)為變量MSPFijk的可行域。需要注意的是,任意(i,j)k之間只要存在可能的資源路徑即可計算成對時差PFijk和MSPFijk,不需要存在直接的資源弧。

顯然,由于約束(17)是非線性約束,上述模型不能直接求解。因此,需要將約束(17)重新表述為:

PFijk≥max{0,sj-(si+di+yijkΔijk)},
i∈J∪{0},j∈Jri,k∈K;

(26)

PFijk≤max{0,sj-(si+di+yijkΔijk)},
i∈J∪{0},j∈Jri,k∈K。

(27)

對于式(26),很容易將其線性化如下:

PFijk≥0,i∈J∪{0},j∈Jri,k∈K;

(28)

PFijk≥sj-(si+di+yijkΔijk),
i∈J∪{0},j∈Jri,k∈K。

(29)

但是,對于式(27),則需要引入輔助變量φijk,i∈J∪{s},j∈Jri,k∈K。如果sj-(si+di+yijkΔijk)≥0,φijk=1;否則,φijk=0。因此,可以將式(27)重新表述如下:

PFijk≤sj-(si+di+yijkΔijk)+M(1-φijk),
i∈J∪{0},j∈Jri,k∈K;

(30)

PFijk≤Mφijk,i∈J∪{0},
j∈Jri,k∈K;

(31)

sj-(si+di+yijkΔijk)+M(1-φijk)≥0,
i∈J∪{0},j∈Jri,k∈K;

(32)

sj-(si+di+yijkΔijk)-Mφijk<0,
i∈J∪{0},j∈Jri,k∈K。

(33)

式(30)表示如果活動j在活動i完成之后開始,則PFijk=sj-(si+di+yijkΔijk);否則,PFijk=0,如式(31)所示。式(32)～式(33)表示如果sj-(si+di+yijkΔijk)≥0,則φijk=1;如果sj-(si+di+yijkΔijk)<0,則φijk=0。

3 隨機規(guī)劃模型與禁忌搜索算法

3.1 隨機規(guī)劃模型MinTPC

上述MinEA和MaxPF模型分別采用基于資源流和基于時差的魯棒性代理指標構(gòu)建優(yōu)化模型,其優(yōu)化目標和約束條件中均不包含隨機變量,并沒有顯性考慮活動工期的不確定性。本節(jié)綜合考慮隨機活動工期、資源轉(zhuǎn)移關(guān)系和轉(zhuǎn)移時間、活動開始時間偏離成本等項目特征,針對RCPSP-TT提出一種總拖期懲罰成本(Tardiness Penalty Cost,TPC)指標,從概率論的角度衡量項目計劃解魯棒性?；顒觠的tpcj定義為活動延遲開工造成的期望損失,表示為[25-27]:

(34)

據(jù)此,以最小化項目總拖期懲罰成本為優(yōu)化目標,建立MinTPC模型如下:

(35)

滿足約束(2)～約束(12)。

3.2 禁忌搜索算法

上述MinTPC模型中含有隨機變量,目標函數(shù)非凸且不具有明確的表達式,不能采用規(guī)劃軟件或者精確算法直接求解。元啟發(fā)式算法(或稱智能算法,metaheuristics)為求解優(yōu)化問題提供了通用的算法框架,其通常能在可接受的時間內(nèi)求得大規(guī)模問題的滿意解(甚至最優(yōu)解),能夠較好地滿足實際應用需求。其中,禁忌搜索(Tabu Search,TS)智能優(yōu)化算法是一種全局性鄰域搜索算法,該算法不論在RCPSP還是魯棒項目調(diào)度中都得到了廣泛應用,在該領(lǐng)域呈現(xiàn)了較強的適用性和優(yōu)秀的性能[3,29-31]。因此本文在POPPENBORG等[6]、胡雪君等[7]研究工作的基礎(chǔ)上,設(shè)計了改進的禁忌搜索算法對模型求解。

3.2.1 編碼與解碼設(shè)計

針對RCPSP-TT問題,文獻[6-7]以資源流量fijk(i,j∈N,k∈K)作為解向量進行編碼(記為資源流列表ResF),并從理論上證明了資源流編碼方式一定能夠得到最短工期問題的最優(yōu)解。本文MinTPC模型旨在給定完工期限約束下最小化項目總拖期懲罰成本,因此為了進一步增加調(diào)度方案的魯棒性,采用在項目活動前插入時間緩沖的方法來吸收工期擾動,即在資源流列表ResF基礎(chǔ)上,定義一組時間緩沖列表Buf=(B0,B1,…Bn,Bn+1),其中元素Bj∈Z+表示活動j∈N之前插入的緩沖大小,Bj=0表示活動j之前沒有緩沖。采用“資源流-緩沖”列表的混合編碼表示可行解的結(jié)構(gòu),記為Ind={ResF,Buf}。

對以上編碼進行解碼時,按照改進的并行調(diào)度策略與ES優(yōu)先規(guī)則進行,獲得工序和資源可行的項目調(diào)度計劃。解碼之后需要判斷解方案是否可行,判斷準則為項目是否在截止期D之前完工:如果是,則為可行解;否則為非法解。

3.2.2 鄰域操作

本文TS算法分別針對資源流列表ResF和緩沖列表Buf進行鄰域操作,以獲得當前解的鄰域解。其中,當前緩沖列表的鄰域解由每個活動前的緩沖大小增加或者減小一個單位產(chǎn)生;當前資源流列表的鄰域解由重構(gòu)算子Nreroute和反轉(zhuǎn)算子Nreverse生成。其中,反轉(zhuǎn)鄰域算子詳見文獻[6-7],此處不再贅述。

重構(gòu)領(lǐng)域算子操作如下所述。選擇兩條資源弧(i,j)k和(u,v)k,其中資源弧(i,j)k從關(guān)鍵路徑中選擇,(u,v)k任意選擇,滿足如下條件:①資源轉(zhuǎn)移量fijk>0,fuvk>0;②在集成資源流的網(wǎng)絡(N,A∪AR)中,活動j與活動u之間、活動v與活動i之間均不存在緊前關(guān)系。然后,按照以下方式對資源流網(wǎng)絡進行重構(gòu):f′ijk=fijk-q,f′uvk=fuvk-q,f′ivk=fivk+q,f′ujk=fujk+q,取q=min{fijk,fuvk}?；趫D1所示的RCPSP-TT項目案例,圖5給出了對一個可行資源流網(wǎng)絡進行重構(gòu)操作的示例,其中點狀虛線表示關(guān)鍵路徑,選定的兩條資源弧分別為(1,4)和(2,5)。

類似地,采用改進的PSGS策略與ES優(yōu)先規(guī)則對插入緩沖的網(wǎng)絡G(N,A∪AR)進行解碼,如果得到的項目完工期在截止期限以內(nèi),該鄰域解為候選解;否則,該鄰域解不成立。此外,當流入某活動的可用資源總量超過該活動所需資源數(shù)量時,還須定義相應的資源轉(zhuǎn)移優(yōu)先規(guī)則,本文采用minGAP規(guī)則,即選擇資源最早到達時間與活動開始時間之差最小的活動進行資源轉(zhuǎn)移。

3.2.3 TS算法流程

基于以上編碼、解碼和鄰域操作,本文設(shè)計了帶精英解策略的禁忌搜索算法對MinTPC模型求解,算法流程如圖6所示。

本文實驗中,TS算法終止條件設(shè)定為最大迭代次數(shù)Iter=10 000。每次迭代中,最多訪問50個重構(gòu)鄰域解Nreroute,以及5個反轉(zhuǎn)鄰域解Nreverse。算法搜索過程中最多保留1個精英解,當最優(yōu)解未改進代數(shù)達到閾值p=750或不存在可行鄰域解時,則搜索過程從當前精英解重啟;如果當前最優(yōu)解未改進代數(shù)達到閾值q=1 500時,則采用并行調(diào)度算法重新生成初始解,重啟搜索過程。禁忌表的長度設(shè)為Ttabu=rand(a)+a·|N|,其中|N|為鄰域解數(shù)量,a=5,a=0.3[7]。

3.3 MinTPC與MaxPF混合優(yōu)化模型

上述MinEA和MaxPF模型均為混合整數(shù)線性規(guī)劃模型,可以采用CPLEX優(yōu)化軟件進行求解,但是求解時間隨著問題規(guī)模呈線性增長。通過預實驗結(jié)果可知,由于MaxPF模型結(jié)構(gòu)復雜,變量數(shù)多,難以在有限的時間和空間內(nèi)求解得到模型最優(yōu)解(活動數(shù)量為30),針對部分復雜問題實例甚至難以直接求解得到可行解。因此,本節(jié)提出MinTPC與MaxPF混合優(yōu)化策略,對MaxPF模型進行降維:首先,通過求解MinTPC獲得一個初始資源流網(wǎng)絡和初始調(diào)度計劃;然后,將初始調(diào)度計劃中的活動開始時間作為已知參數(shù),代入MaxPF模型,以最大化活動成對時差總和為優(yōu)化目標(公式(16)),進一步優(yōu)化資源流決策,進而生成抗干擾能力強的前攝調(diào)度集成優(yōu)化方案,該方法記為MinTPC+MaxPF。

3.4 具體算例

本節(jié)以圖1所示的帶資源轉(zhuǎn)移時間的項目網(wǎng)絡為例,分別采用MinTPC、MinTPC+MaxPF、MinEA、MaxPF方法獲得活動開始時間與資源分配方案(取σ1=0.5),調(diào)度結(jié)果如圖7所示。

其中,圖7a和圖7b是采用MinTPC和MinTPC+MaxPF方法生成的解方案,二者對應的項目調(diào)度計劃具有相同的活動開始時間,但是資源轉(zhuǎn)移方式不相同。例如,圖7a中活動5所需資源由活動1和活動3提供,活動3的完工時間是6,活動5的開始時間是7,資源從活動3流向活動5需要的轉(zhuǎn)移時間為△35=1,因此活動3、活動5之間沒有時間緩沖,活動3一旦拖期一定會影響活動5的正常開工;而采用MinTPC+MaxPF方法基于相同的活動進度計劃進一步優(yōu)化資源轉(zhuǎn)移決策(如圖7b),活動5所需資源由活動1和活動2提供,活動2的完工時間是2,資源從活動2流向活動5需要的轉(zhuǎn)移時間為△25=1,因此活動2、活動5之間有4個單位的時間緩沖,活動2至少發(fā)生4個時間單位的拖期才會影響到活動5按計劃開工?？梢?針對本例圖7a和圖7b兩種資源分配方案,采用MinTPC+MaxPF方法可以更有效應對活動的拖期風險,提升調(diào)度計劃的魯棒性。

圖7c和圖7d是采用MinEA和MaxPF方法生成的解方案,二者對應的資源流網(wǎng)絡完全相同(只有一條額外資源弧(5,6)),但是活動開始時間不一樣。圖7c中活動5的開始時間是4,圖7d中活動5的開始時間是3;這意味著圖7d中活動2一旦拖期一定會導致活動5不能按照基準計劃開工(△25=1),而圖7c中活動2、活動5之間有一個單位的時間緩沖,活動2延遲一個時間單位完工不影響活動5正常開始。可見,針對本例圖7c和圖7d兩個調(diào)度方案,MinEA方法比MaxPF方法應對活動拖期風險的能力更強。

以上分析進一步表明,現(xiàn)有魯棒資源分配相關(guān)研究基于活動開始時間已知的項目調(diào)度計劃去優(yōu)化資源分配決策,實際上具有一定的局限性,不能保證從全局角度獲得魯棒性最優(yōu)的解方案,因而有必要對活動進度安排和資源轉(zhuǎn)移決策進行集成優(yōu)化。

4 模擬實驗

為進一步評價上述4種優(yōu)化方法得到的項目調(diào)度計劃和資源分配方案的魯棒性優(yōu)劣,本章設(shè)計了一系列仿真實驗,模擬工期不確定環(huán)境下的項目實際運行情況。所選取的測試集為KRüGER等[4]基于PSPLIB標準例庫[32]構(gòu)建的RCPSP-TT標準問題集[6,8],其中由30個活動組成的J30例庫包含480個項目實例,每10個為一組,每組具有相同的網(wǎng)絡參數(shù)和資源參數(shù)。

MinTPC模型及禁忌搜索算法采用MATLAB編譯程序;MinEA和MaxPF模型采用CPLEX優(yōu)化軟件求解,軟件求解時間限制為5分鐘。程序運行在CPU為Intel(R)Core(TM)i7-1165G7@2.80 GHz、內(nèi)存為16G的個人電腦,操作系統(tǒng)為Windows 10。

4.1 實驗設(shè)置

仿真實驗相關(guān)參數(shù)的設(shè)置如表2所示。需要注意的是,由式(34)可知,總拖期懲罰成本TPC值與工期不確定水平有關(guān),不同的不確定水平下MinTPC方法獲得的解方案可能不相同。本文假設(shè)活動工期服從均值為基準計劃時間dj、標準差為σ的對數(shù)正態(tài)分布[23,26-27],以σ1來衡量計劃階段預估的工期波動水平,以σ2來衡量模擬執(zhí)行階段的實際不確定水平?？紤]到項目管理者在制定計劃時通常很難準確預知項目在執(zhí)行階段的實際不確定水平,本文將計劃階段的工期不確定水平分別設(shè)置為低(L)、中(M)、高(H)3個等級(σ1={0.3,0.5,0.8}),不同等級對應的優(yōu)化模型分別記為MinTPCL、MinTPCM、MinTPCH。

表2 仿真實驗參數(shù)設(shè)置

模擬實驗定義了以下兩種魯棒性績效評價指標:

4.2 實驗結(jié)果及分析

對以上6種RCPSP-TT前攝調(diào)度方法所得解方案進行仿真實驗,表3和表4分別給出了項目交付日期D=1.1Cmax時的實驗結(jié)果。兩表中加粗數(shù)字表示分別按照3種不確定水平(σ1∈{L,M,H})制定前攝調(diào)度計劃時,三種MinTPC方法中魯棒性績效最優(yōu)的一種;加粗數(shù)字表示6種方法中魯棒績效最優(yōu)的一種(下同)。

表3 D=1.1Cmax時不同方法的SC值對比結(jié)果

表4 D=1.1Cmax時不同方法的PCT值對比結(jié)果

通過對表3和表4統(tǒng)計數(shù)據(jù)的分析,可以得到以下結(jié)論:

(1)隨著項目執(zhí)行時不確定水平σ2的增大,每種方法的進度不穩(wěn)定懲罰成本SC均增大,模擬完工期PCT均變長,這一結(jié)果與預期相符。顯然,活動時間波動性越大,項目執(zhí)行時偏離原定計劃的可能性越大,導致懲罰成本增加;另外,隨不確定性增大前序活動工期延遲帶來的累積效應越強,最終導致項目完工期變長。

(2)在3種計劃不確定水平下,分析MinTPCL、MinTPCM和MinTPCH所得結(jié)果可知:如果項目決策者更加追求解魯棒性(即最小化懲罰成本),則按照低不確定水平(σ1=0.3)制訂計劃可以獲得更加穩(wěn)定的調(diào)度方案;如果追求更短的項目完工期,建議按照高不確定水平(σ1=0.8)制訂計劃。此外,三種MinTPC方法的SC值、PCT值之間的差距并不顯著,說明即使項目管理者不能準確預知工期不確定水平,采用MinTPC方法也能夠有效規(guī)避隨機活動工期對優(yōu)化模型的影響,從而指導管理者制訂具備參考價值的前攝調(diào)度計劃。

(3)相同σ2水平下,SC指標的優(yōu)劣順序為MinTPC+MaxPF?MinEA?MinTPC?MaxPF,PCT指標的優(yōu)劣順序為MinTPC+MaxPF?MinTPC?MinEA?MaxPF,其中“?”表示“優(yōu)于”。

一方面,在3種不確定水平下,采用MinTPC+MaxPF方法都能得到最短的項目完工期和最低的懲罰成本,而MaxPF方法所得基準方案的模擬完工期最長、懲罰成本最高。如前所述,采用CPLEX工具求解MaxPF模型所需時間較長,實驗中將單個算例求解時間限定在5分鐘以內(nèi),對于部分項目算例該方法在規(guī)定時間內(nèi)不能求得最優(yōu)解,只能得到近優(yōu)解。為解決這一問題,本文提出了MinTPC+MaxPF混合優(yōu)化方法,首先以最小化總拖期懲罰成本為目標生成初始活動調(diào)度和資源轉(zhuǎn)移方案,其次以初始調(diào)度計劃中的活動開始時間為已知變量,以最大化活動間成對時差總和為目標進一步優(yōu)化資源流決策,仿真結(jié)果表明該方法所得項目調(diào)度方案的解魯棒性和質(zhì)魯棒性績效都是最好的。

另一方面,對于MinEA和MinTPC方法,解魯棒性和質(zhì)魯棒性呈現(xiàn)相互沖突的關(guān)系:MinEA方法獲得的基準方案最穩(wěn)定,懲罰成本SC最小,說明以最小化額外資源弧數(shù)量為解魯棒性替代指標要優(yōu)于采用總拖期懲罰成本指標。

進一步地,模擬實驗測試了項目交付日期分別取為D=1.2Cmax時D=1.3Cmax時各個模型和算法的魯棒性績效,結(jié)果分別列于表5和表6。為了直觀顯示三種交付期限下項目魯棒性績效指標的變化趨勢,圖8綜合展示了表3～表6中σ2=0.5情況下的數(shù)據(jù)(另外兩種不確定水平下的變化趨勢與此相似)。

表5 D=1.2Cmax時不同方法的魯棒績效對比結(jié)果

表6 D=1.3Cmax時不同方法的魯棒績效對比結(jié)果

分析表5和表6可知,上述第(1)和第(3)條結(jié)論仍然成立,MinTPC+MaxPF方法相比其它方法產(chǎn)生的進度偏差最小且模擬完工期最短;與D=1.1Cmax結(jié)果不同之處在于,當項目完工期限最為寬松(D=1.3Cmax)時,運用MinTPC方法時按照高不確定水平(σ1=0.8)做計劃,生成的活動調(diào)度和資源轉(zhuǎn)移方案其解魯棒性和質(zhì)魯棒性整體最優(yōu)。此外,從圖8可以看出,隨著項目交付期限的延長,MinTPC和MinTPC+MaxPF方法的懲罰成本SC呈下降趨勢,即項目穩(wěn)定性增強,其中MinTPC+MaxPF集成優(yōu)化方法的降幅最大;MaxPF方法的穩(wěn)定性呈現(xiàn)先下降后增強的變化趨勢;MinEA方法的SC值隨項目交付日期延長變化不大,因為MinEA模型的優(yōu)化目標是最小化額外資源弧的數(shù)量,與活動開始時間早晚沒有直接關(guān)系。

我們知道,RCPSP-TT是RCPSP的拓展問題,因此,為了顯示所提優(yōu)化模型應用于基礎(chǔ)RCPSP問題的普適性與差異性,另以PSPLIB_J30標準例庫(資源轉(zhuǎn)移時間均為0)為測試集進行仿真實驗。表7列出了項目交付日期D=1.2Cmax的實驗結(jié)果,由于項目交付日期D=1.1Cmax和D=1.3Cmax所得結(jié)論相類似,此處不再贅述。

表7 不同方法應用于基礎(chǔ)RCPSP的魯棒績效對比結(jié)果(D=1.2Cmax)

從表7可以看出,針對不考慮資源轉(zhuǎn)移時間的RCPSP問題,MinTPC+MaxPF方法在3種仿真不確定水平下仍然都能獲得最低的懲罰成本和最短的項目模擬完工期,說明本文針對RCPSP-TT提出的MinTPC+MaxPF混合優(yōu)化方法同樣適用于求解RCPSP問題,并且能在很大程度上保證獲得魯棒性能最優(yōu)的活動調(diào)度計劃與資源分配方案。此外,對于MinTPC方法,當決策者在計劃階段不能明確預知項目實際執(zhí)行時的工期不確定水平時,按照高不確定水平(σ1=0.8)制訂計劃能夠獲得魯棒性更強的調(diào)度方案。將這一結(jié)果與表3和表4對比可知:不考慮資源轉(zhuǎn)移時間的RCPSP調(diào)度決策通常更為保守,按照高不確定水平制訂計劃時在項目活動之間預留了更多的時間緩沖,故而可以更有效地應對活動拖期風險。

5 結(jié)束語

本文針對帶資源轉(zhuǎn)移時間的RCPSP問題,考慮活動工期的不確定性,分別從資源轉(zhuǎn)移關(guān)系、活動時差、隨機活動工期三個不同角度設(shè)計了3種解魯棒性衡量指標,構(gòu)建了MinTPC、MinEA、MaxPF和MinTPC+MaxPF多個RCPSP-TT魯棒調(diào)度與資源分配集成優(yōu)化模型,并分別提出了模型求解方法。通過仿真實驗對各方法所得項目方案的魯棒績效進行對比分析,實驗結(jié)果表明,混合優(yōu)化策略MinTPC+MaxPF能夠得到解魯棒性和質(zhì)魯棒性均最優(yōu)的調(diào)度方案。研究工作延伸了資源受限項目調(diào)度的問題領(lǐng)域,也進一步豐富了魯棒項目調(diào)度研究的內(nèi)容,擴充了資源流網(wǎng)絡優(yōu)化在項目調(diào)度領(lǐng)域的應用。

本文研究旨在工期不確定條件下實現(xiàn)RCPSP-TT問題解魯棒性最強的單目標優(yōu)化,實際中還有很多方面因素和領(lǐng)域問題需要考慮,比如資源不確定環(huán)境、多目標優(yōu)化(如資源轉(zhuǎn)移成本、現(xiàn)金流、資源均衡等目標)、活動可拆分、多模式(時間-資源權(quán)衡)等,這些問題值得進一步探索研究。此外,未來有必要結(jié)合RCPSP-TT實踐問題開展應用研究,將研究成果應用于基礎(chǔ)設(shè)施建設(shè)、工程建筑、大型復雜產(chǎn)品制造與裝配等行業(yè),從而驗證所提模型方法的實際效果,并進行評估與反饋改進。

致謝

感謝席勒·耶拿大學(Friedrich Schiller University)Armin Scholl教授為本研究提供了RCPSP-TT問題項目例庫。