隨機活動工期下基于總不確定成本的項目前攝性調度與反應性調度集成優化

王艷婷,何正文,索 琪

(1.青島科技大學 經濟與管理學院,山東 青島 266061;2.西安交通大學 管理學院 過程控制與效率工程教育部重點實驗室,西安 710049)

項目調度,作為項目管理的核心問題之一,自20世紀60年代引入中國,受到廣大學者與項目管理者的普遍關注。迄今為止,研究最廣泛、深入的是確定環境下資源約束項目調度問題(Resource Constrained Project Scheduling Problem,RCPSP),對不確定環境下的相關問題研究較少。然而,面對日益復雜而多變的項目環境,確定性方法面臨著巨大挑戰。特別是對于大型復雜項目工程,如航天航空設備研發過程、大型鐵路、工廠修建等,實施過程可能受到各種不確定因素干擾,如天氣變化導致活動工期延長、資源價格上升導致供給量短缺、業主對項目提出新的要求導致網絡結構變更等。這些不確定因素的存在,使得實際項目不可能完全按照預定的基準計劃執行,項目管理者不得不根據實際情況頻繁變更計劃,如果不能及時進行調整,可能造成項目返修或停工,增加整個項目組人員的緊張感及資源的浪費,嚴重的甚至會引起項目成本超支和進度延遲[1]。據美國Standish集團調查報告顯示[2],在近20年的項目管理發展期間,始終有50%左右的項目存在延期超支現象,有接近20%的項目完全失敗。因此,如何在不確定環境下獲得穩定的基準進度對于項目的計劃與執行顯得非常重要。

Herroelen等[3]根據項目所處階段提出不確定環境下項目調度的兩種方法:前攝性項目調度與反應性項目調度。針對這兩類調度方法,國內外已有不少學者進行了研究。Herroelen等[4]建立了基于情景的數學規劃模型并通過對偶理論將其轉化為最小費用流模型求解,并借鑒Tavares等[5]的浮動因子模型,提出適應浮動因子模型(ADFF),通過最小化累積不穩定權重和得到一個魯棒性最優的基準計劃。Van de Vonder等[6]將ADFF方法擴展到多中斷情形,并與經典的關鍵鏈方法進行對比,提出了項目工期與魯棒性兩個目標之間的權衡關系。此外,Van de Vonder等[7]進一步證明ADFF模型在資源約束情況下會產生沖突,并提出了資源流依賴因子模型(RFDFF),該模型可以很好地求解多中斷資源受限情況下的魯棒性最優化問題。Elshaer等[8]在Van de Vonder等[9]研究基礎上提出了3種新的啟發式方法生成魯棒性基準進度,并與原文中用到的算法進行了比較。Potgieter等[10]研究了資源分配方式對進度緩沖大小及其分布的影響,提出8種啟發式方法求解資源分配問題以最大化項目緩沖權重值。Deblaere等[11]結合隨機項目調度提出了一種新穎的進度生成方法,通過仿真得到開始時間分布的最小最大點,然后利用報童模型確定活動開始時間。在項目執行中,運用優先列表與活動準備時間表,在每個決策點選擇優先度最高的活動執行,通過實驗證明了該方法要優于目前最好的開始時間關鍵度模型(STC)方法。Chen等[12]將熱力學中熵的概念用于隨機工期下的資源約束項目調度問題,以獲得魯棒性最大的基準進度。馬國豐等[13]針對關鍵鏈項目提出了魯棒優化數學模型,設計了遺傳算法獲得魯棒性最優的基準進度。任世科等[14]研究了突發事件應急救援的動態調度優化問題,構建了相應的動態調度優化模型,并設計了禁忌搜索啟發式算法。盧睿等[15]提出一種迭代局部搜索方法,用于求解隨機工期下項目提前/延期懲罰的問題。張沙清等[16]針對項目執行過程中由于任務拖期而導致的調度計劃變更,提出了一種基于優化的資源流約束的反應性調度算法,并通過仿真驗證了算法的可靠性與有效性。

不同于上述單目標方法,Al-Fawzana等[17]同時考慮工期與魯棒性構建了雙目標模型,設計了禁忌搜索啟發式算法進行求解。劉鋒等[18]設計了基于有效解的兩階段混合算法求解多目標調度問題,在突發性干擾下對原目標與擾動目標進行權衡。Debleare等[19]考慮多模式情形,在工期或資源可用量中斷的情況下,分別提出精確算法及啟發式算法來修復基準進度。Godinho等[20]提出一種基于電磁理論的啟發式算法以確定最優調度策略。何正文等[21]對多模式下救援時間最短與魯棒性最大化的雙目標調度問題展開研究,構建0～1優化模型并設計禁忌搜索啟發式算法進行求解。崔南方等[22]基于STC方法提出兩種具體的魯棒性衡量指標,并結合模擬退火和禁忌搜索算法獲得質量魯棒性和解魯棒性較高的基準進度。張靜文等[23]構建了基于時差效用的雙目標魯棒性項目調度模型,并提出一種基于調整策略的快速非支配性排序多目標遺傳進化算法獲得Pareto最優解集合。

單獨的前攝性或反應性調度都無法對干擾做出充分的處理以滿足項目穩定性指標,因此一些學者提出前攝-反應性項目調度方法,通過前攝性調度得到帶保護機制的基準進度,當活動發生中斷時調用反應性策略對基準進度進行修復。該方向的文獻目前還比較少,可見到的有:Calhoun 等[24]將生產計劃中調度與再調度之間進行聯系,在前攝性調度中最大基準計劃魯棒性,反應性調度中最小化變化的活動數;Van de Vonder等[25]運用工期與魯棒性的復合目標來評價不同的前攝性進度生成方法與反應性調度策略,結果表明,運用工期最小的基準計劃輔之以解魯棒性的反應性策略可以達到兩個目標的綜合優化。

在不確定環境下,不管是采用前攝性或是反應性調度方法處理不確定因素,都會產生相應的成本。例如,當項目管理者采用前攝性調度方法并通過添加時間緩沖提高基準進度的魯棒性時,活動原先占用的資源與時間將不得不延長到緩沖期,以保證當活動實際工期發生延長時,緩沖可以完全抵消工期的延長,相應地,會產生較大的資源占用成本支出,這部分成本也可以理解為提高魯棒性的代價,定義為魯棒性成本。另一方面,當緩沖無法完全抵消工期的延長時,管理者不得不采取反應性調度方法對受損的基準進度進行修復,此時需付出額外的時間及資源,產生一定的修復成本支出,可以理解為提高魯棒性帶來的成本變化幅度,這里定義為調整成本。很明顯,魯棒性成本和調整成本都是由于不確定因素而發生的,故本文將這兩種成本統稱為不確定成本。

在前攝性調度中,如果在基準進度中添加較多的時間緩沖,則基準進度魯棒性大幅提高,增強了其應對不確定擾動的能力,在實際執行中可以降低發生中斷的概率從而減小調整成本的支出;反之,如果承包商減小基準進度中的時間緩沖,則魯棒性與魯棒性成本同時降低,帶來的直接后果就是基準進度可能會頻繁發生中斷而需要多次重新調整,由此產生的調整成本會大幅增加。因此,為了更經濟地處理不確定擾動,最大程度地減小不確定成本的發生,承包商需要對兩種調度方法進行綜合考慮,通過采取最恰當的方式實現兩種調度方式的最佳配合。雖然目前文獻中出現了較多關于前攝性與反應性的集成問題,但卻鮮少有學者對兩種調度方法在使用中產生的成本問題進行深入研究。因此,本文研究將彌補這方面的漏洞,同時幫助實際項目管理者如何高效經濟地應對不確定因素提供數量化的指導。

基于上述綜述,本文研究問題定義如下:在活動工期隨機中斷的情況下,研究前攝性項目調度與反應性項目調度的集成優化問題,目標是獲得項目總不確定成本最優的方案。首先界定問題;進而以總不確定成本為目標構建前攝性與反應性調度集成模型;針對問題NP難屬性,設計變鄰域隨機禁忌搜索啟發示算法;通過大規模算例測試驗證模型及算法的有效性,并分析在重要參數及不同調整策略下模型的敏感性;最后,總結全文給出研究結論。

1 問題界定

采用基于活動的方式,將項目表示為一個AoN(Activity-on-Node)網絡,G=(N,A),其中:N為網絡節點的集合,表示活動;A為網絡箭線的集合,表示活動之間的邏輯關系,并假設活動之間遵循0時滯結束開始型優先關系,亦即前一活動結束后其緊后活動立即開始[4]。集合N由n+2個活動構成,活動0和n+1分別是因網絡表示需要而添加的虛的開始和結束活動,表示項目的開始與結束。非虛活動i(i=1,2,…,n)的完成需要投入K種可更新資源,其中,對第k(k=1,2,…,K)種資源的需求量為rik,注意,虛活動0和n+1對任何一種資源的需求量均定義為0。每種資源的總可用量是固定且有限的,第k種資源的可用量為Rk,單位使用成本為ck。考慮到環境的不確定性,將活動i的工期di定義為一個均值為E(di)、標準差為V(di)的隨機變量。現實中,E(di)和V(di)可以基于同類活動的歷史統計數據,結合專家的分析判斷進行估計。項目的截止期限為D。

在前攝性項目調度中,基于工期均值將活動i的開始時間安排為,所有活動的開始時間集合構成項目的基準進度。為了提高基準進度應對不確定因素干擾的能力,在活動i(i=1,2,…,n)后添加一定量的時間緩沖Δi,用以抵消或減弱干擾造成的影響,定義該緩沖產生的資源占用成本為。將所有活動的資源占用成本累加,得到在該進度SB下項目的魯棒性成本,用變量Crobu(SB)表示,且

在項目實施過程中,活動工期逐步由隨機變量變成確定值,但該確定值并不一定等于其均值。特別是當活動工期變化值超過其保護緩沖時,由于資源可用量的限制,使基準進度變成一個不可行計劃,故必須對其進行反應性調整。假定項目在執行中共發生Q次中斷,設第q(q=1,2,…,Q)次中斷發生的時刻為Tq,定義在Tq時刻已經完成的活動集合為,正在進行的活動集合為,尚未開始的活動集合為。對于中的活動,由于活動的實施已經變為現實,故=di;對于中的活動,考慮到現實中其資源使用情況、活動進展及不確定因素的影響等信息已較多地為承包商所掌握,使活動的不確定性大幅降低,故亦將其視為確定性活動;對于中的活動,由于活動尚未開始,故仍取為活動的均值E(di)。假設調整過程遵循“鐵路調度”策略,亦即活動開始時間的安排不能提前于基準計劃中給定的開始時間,故在對基準進度SB進行調整時,只需改變中活動的開始時間即可,得到在Tq時刻一個新的可行基準進度,記為。需要注意的是,在每次調整后,都需將原基準計劃SB更新為新得到的,SB=,并將新的SB作為接下來活動繼續執行的基準計劃。當整個項目完全完成時,所有中斷點時刻產生的調整成本構成整個項目的總調整成本,記為Cadju(SB),且

其中,wi為活動i實際開始時間偏離基準計劃開始時間產生的單位損失成本。

基于上述問題定義,可以得到一個項目在整個計劃與執行中產生的總不確定性成本TC,即

TC=Crobu(SB)+Cadju(SB)

本文研究的目的就是找到這樣一個基準計劃SB,使總不確定性成本最小。因此,構建基于總成本最優的前攝性調度與反應性調度集成優化模型如下所示,為后文方便,將其記為Min-TC:

上述模型中,目標函數式(1)最小化項目總不確定性成本;約束條件式(2)將整個項目開始時間定義為0時刻;式(3)、(4)分別為前攝性基準計劃制定和反應性調整中各活動之間的邏輯關系約束,確保活動i的開始時間與其工期之和不晚于其緊后活動j的開始時間;式(5)為截止日期約束,即整個項目的完工時間不能超過限定的期限D;式(6)為資源約束,保證項目在實施過程中的任意一個時刻t,所有正在進行的活動對任一種資源的需求總量不超過該種資源的可用量,Pt為t時刻正在進行的所有活動的集合;式(7)為決策變量的定義域約束,保證每個活動開始時間為非負整數。

通過上述模型可以實現前攝性調度與反應性調度的集成優化問題,同時得到最優的不確定成本。具體而言,首先通過前攝性調度獲得一個基準進度SB,并由魯棒性成本公式計算得到Crobu(SB);然后對SB進行仿真,每次隨機生成一組活動的實際工期,隨著項目的進行,一旦活動發生中斷,即調用反應性策略對SB進行調整;最后,項目結束時得到相應的調整成本Cadju(SB)。改變SB中緩沖分配量,Crobu(SB)和Cadju(SB)會同時發生變化。在該過程中,如果魯棒性成本Crobu(SB)增加的速度小于調整成本Cadju(SB)減小的速度,則模型會自發地向SB中多添加時間緩沖以提高魯棒性成本;反之,模型會減小SB中添加的時間緩沖。通過這種變化方式,在得到最優SB的同時,亦即獲得了最優總成本TC;與此同時,中斷也通過前攝性調度與反應性調度的集成模型得到了有效處理。

為了更好地說明上述集成模型的特點,將其與魯棒性最大化模型(Max-Robu)[9]進行對比。Max-Robu模型的目標與本文提到的Tq時刻調整成本的計算方式相同。該模型的思想是:當調整成本達到最小時,亦即項目的魯棒性最高,雖然計算的是成本,但卻定義為魯棒性。在該模型中,由于沒有考慮魯棒性提高所付出的代價,項目經理會過度使用前攝性調度方式,通過大幅添加時間緩沖以盡可能地降低調整成本的大小。從實際成本支出看,該模型并不符合現實情況,特別是當資源比較稀缺時,通過添加緩沖所帶來的調整成本的下降幅度遠遠小于魯棒性成本的增加。而本文提出的Min-TC模型克服了這一缺點,通過集成思想綜合考慮前攝性調度與反應性調度產生的成本,以實現項目的最優調度。從這一角度看,Min-TC模型可以看作是Max-Robu模型的一般化形式。當單位資源成本ck=0時,兩模型等同。

2 算法設計

Leus等[26]證明在不確定條件下,基于項目截止日期及離散中斷情況下求基準進度魯棒性為NP難問題。本文集成模型在上述基礎上進一步考慮魯棒性成本對項目整體的影響,因此也必然為一NP難問題。雖然已有眾多啟發式算法求解不確定項目調度問題,如遺傳算法(GA)、模擬退火(SA)、禁忌搜索(TS)和粒子群算法(PSO)等,但還沒有哪種算法可以有效地求解前攝性與反應性調度的集成優化模型。鑒于這一事實,以文獻中廣泛使用并被證明行之有效的禁忌搜索為基礎,借鑒模擬退火中概率選擇鄰點方式,提出了隨機禁忌搜索算法(PTS),并將其與變鄰域搜索算法(VNS)進行組合優化,得到變鄰域隨機禁忌混合搜索算法(VNS-PTS)。其中,PTS通過禁忌表的運用加強VNS中局部搜索的能力,同時VNS的多鄰域靈活變化可視為PTS進行多樣化與集約化的一個工具。

變鄰域搜索算法(VNS)在Hansen 等[27]的基礎上進一步根據模型特征進行改進,在解的表示、鄰域生成與局部搜索等方面提出不同于一般VNS的表達形式。不同于一般的啟發式算法只采用單一鄰域,VNS算法融合了鄰域本身的確定性與不同鄰域之間變化的隨機性,通過多鄰域的組合搜索實現問題目標。VNS已經被眾多學者證明在求解大型組合優化問題時可以提供較好的結果[28]。

隨機禁忌搜索,顧名思義在鄰域生成過程中加入了隨機屬性,通過減少鄰域中需要評估的鄰點數目以降低算法運行時間。針對當前解,其鄰域的構成方式為:對每個鄰點,根據概率q(0＜q＜1)的大小決定是否進入到鄰域中,當所有鄰點都按此方式判斷后,進入鄰域中的所有鄰點將構成當前解的鄰域,記為Nq。Kochetov等[29]已經證明PTS 算法具有漸近收斂性,而且通過對鄰域進行隨機化處理可以減少相對誤差并在一定程度上放松禁忌列表的影響。

2.1 解的表示與解碼

基于研究問題的特征,每個解均由活動次序列表AL和時間緩沖列表SL構成。

活動次序列表AL。該列表由n+2個活動代號構成,各代號在列表中的位置決定了其所對應活動在計劃安排時的優先次序,注意列表中活動必須滿足優先關系約束。

時間緩沖列表SL。該列表由n+2個時間緩沖εi∈[0,LFi-EFi]構成,其中,EFi和LFi分別為活動i的最早和最晚完成時間,它們可基于活動網絡及截止日期D通過CPM(Critical Path Method)計算得到。在編制基準計劃時,εi被添加到相應的活動工期均值E(di)上,以便在活動上形成所需的時間緩沖Δi。注意,由于Δi是通過的安排形成的,故εi并不一定等于Δi,主要是由于優先關系與資源約束的存在,使活動之間自然形成一定量的緩沖,從而Δi＞εi。

給定一組AL和SL,可按照如下步驟將各活動安排在滿足資源及優先關系約束的最早時間開始,生成一個可行的基準計劃:首先,在SL所定義的εi的基礎上,生成擴展工期udi=E(di)+εi;其次,按照AL所定義的活動優先次序,基于udi利用串行進度生成機制[30]生成各活動的開始時間,由此形成基準計劃。

需要說明的是,盡管εi的取值被限制在[0,LFi-EFi]之內,但上述解的表示方式仍有可能生成違反項目截止日期D約束的基準計劃。在算法的迭代過程中,當這種情況出現時,為使正常搜索不受影響,算法不直接剔除不可行解,而是將其目標函數懲罰為一個較大值M。

2.2 初始解的生成

為提高算法效率,在生成初始解時,要求所有初始解都是可行解。大量實驗表明,初始解的優劣在很大程度上會影響算法的性能。因此,針對解的表示方式提出3種基于啟發式的方法獲得AL和SL列表,然后依據解碼方式生成初始解。

(1)活動導向型(FALS)。首先通過基于優先規則的啟發式方法生成AL,然后在其基礎上尋找滿意的SL,具體步驟如下:

步驟1l=0,εi=0(i∈N);

步驟2令活動k=ALl,計算活動k的候選集Ck={j|(k,j)∈A,j∈N}及候選集內活動優先權值PRj(j∈Ck),同時,l=l+1;

步驟3令ALl=j*,滿足條件:PRj*=maxPRj(j∈Ck),若活動優先值相同,則取序號值較小的活動;

步驟4如果l＜n,轉步驟2,否則輸出AL,轉步驟5;

步驟5計算活動i(i=0,1,…,n+1)的概率,定義活動i的累積概率為rpi,令rp0=p0,rpi=pi+rpi-1;

步驟6生成隨機數r∈(0,1),采用輪盤賭方式依次選擇需要添加緩沖的活動;

步驟7對于活動i∈N,如果rpi-1＜r＜rpi,則εi=εi+1;

步驟8計算活動開始時間,如果sn+1＜D,轉步驟6,否則退出,輸出列表AL和SL。

其中,活動i的優先權PRi由下式獲得:

參數α∈[0,1]通過權衡活動優先關系、工期不確定性和資源使用成本確定活動的重要程度,CIWi=wi+∑(i,j)∈Awj表示活動i的累積不穩定成本,也可以理解為活動的單位延遲損失。

(2)緩沖導向型(FSLA)。根據信息熵理論在項目管理中的應用,可知活動不確定度越大,其熵值越大[31-32]。因此,本文通過計算活動的熵值來衡量活動的不確定性大小并據此添加時間緩沖,生成相應緩沖列表SL,然后在此基礎上尋找滿意的AL,具體步驟如下所示。此處假設活動工期服從三角分布,概率密度函數f(x|a,b,c),其中:a表示最短工期;b表示最長工期;c表示最可能工期;p為活動中斷的概率。

步驟1εi=0(i∈N),AL={0,1,…,n+1};

步驟2計算活動i(i∈N)的熵,

步驟3選擇活動j*,滿足條件:Enj*=maxEnj(j∈N),若活動熵值相同,則取序號值較小的活動;

步驟4εj*=εj*+1,dj*=dj*+εj*,計算活動開始時間,如果sn+1＜D,轉步驟3,否則轉步驟5;

步驟5將其所有活動按照完工時間遞減的順序排列,得到一個活動列表AL;

步驟6輸出列表AL和SL。

(3)隨機型(RAND)。隨機生成AL和SL列表。如果得到的基準進度滿足截止日期,則為一可行解,否則重新生成一組AL和SL,重復上述步驟直至生成一組可行解為止。

2.3 鄰域結構

定義鄰域結構,參考Flood[33]在旅行商問題中提出的2-opt策略,本文類似地提出了m-opt策略,分別作用于AL和SL列表,表述如下:

針對AL列表的鄰域結構(N-ALm)。保持SL不變,對AL中任意一對活動執行交換次序操作,使之得到的鄰點與原列表相比僅存在m對不同的活動。注意,在交換過程中必須保證交換后的活動列表滿足優先關系約束。所有可通過這種操作得到的列表集合定義為AL的m鄰域。

針對SL列表的鄰域結構(N-SLm)。保持AL不變,類似地,對SL中任意一個活動的緩沖執行隨機擾動操作,使之得到的鄰點與原列表相比僅存在m個不同緩沖值的活動。注意,緩沖值在隨機擾動過程中要滿足緩沖范圍約束限制。所有可通過這種操作得到的列表集合定義為SL的m鄰域。

2.4 禁忌列表及終止準則

定義算法禁忌列表TL,遵循“先進先出”原則進行更新:每當算法從當前解向選定的鄰點移動時,該移動的逆向移動從底部加入到禁忌列表中,避免算法重新退回到當前解上。與此同時,最早進入列表的逆向移動從頂部移出列表,列表中其余逆向移動向上遞進一位。所有位于禁忌列表中的逆向移動都是被禁止的,但是,如果一個被禁止的逆向移動能夠生成比當前最好解還要好的鄰點時,那么,它的禁忌狀態可以被激活,以使算法能夠移動到該鄰點上,避免錯失問題的最好解。算法的終止準則設置為探測可行解的總數,即當算法搜索的可行解的總數達到設定值Numstop時,算法停止搜索并將保存的最好解輸出為滿意解。

2.5 算法流程

算法流程圖如圖1 所示。其中,Num 用來記錄搜索到的可行解數目,上標init、curr、loca和best分別表示初始解、當前解、局部最優與全局最優解。

2.6 反應性調度策略

在項目執行中,當發生中斷需要進行調整時,一方面要考慮活動工期的隨機變化情況,另一方面要選擇恰當的調整策略。根據調整的效率及復雜度提出如下3種反應性策略:

(1)簡單抽樣(SS)。在每個中斷決策點,隨機生成幾個可行進度,然后選取其中目標函數最優的一個作為新的基準進度。

(2)動態優先規則(DP)。在每個中斷決策點,將尚未開始的活動按開始時間升序排列,由此得到優先列表,然后按照解碼程序得到基準進度。

(3)固定資源流(FR)。在每個決策點,保持基準進度中資源的流向關系不變,亦即活動之間資源約束關系通過資源流的固定而預先得到了處理,在活動工期延長導致進度中斷后,在調整過程中無需再考慮資源約束,只將受影響的活動開始時間向后移動中斷時長即可,由此得到新的基準進度。

在每次活動中斷時,分別應用這3種調整策略對未完成活動進行調整。

3 算法測試

3.1 參數設置

用ProGen算例生成器[34]上獲得的數據對算法進行測試,具體參數設置如表1所示。其中:非虛活動數n設置為4種水平,其他參數如RS、Dv、ck、wi和Dn分別設置為3種水平;資源因子RF反映了活動對資源種類的平均需求,RF=1表示每個活動需要所有資源,RF=0 表示沒有活動需要資源;資源強度RS反映了資源的供給程度,RS=1表示資源供給量最大,完全滿足所有活動需求,RS=0表示資源供給量取最小值。在反應性仿真實驗中,活動實際工期di通過三角分布隨機生成。對于每種參數組合,重復生成10個算例進行研究,因此共獲得4×3×3×3×3×3×10=9 720個算例。

圖1 VNS-PTS流程圖

表1 參數設置

除了模型中的Crobu、Cadju和TC之外,還定義如下4個指標反映算法的績效:AET(s)為算法平均運行時間;AIT為項目執行過程中平均中斷次數;AIP為項目執行過程中平均中斷概率;ADL為項目執行過程中平均延期長度。其中,指標AET從時間角度反映算法運行效率,指標TC、AIT、AIP和ADL從滿意解質量和執行過程角度反映算法運行效果。所有算法代碼均采用Microsoft Visual C++2010編程軟件進行編碼,并在CPU 主頻為2.5 GHz、內存為2 GB 的戴爾個人計算機上運行。為保證結果的無偏性,規定算法在運行過程中需遵循相同的初始解和停機準則。基于預先實驗,將算法參數Numstop、mmax、α和TL的值分別設定為8 000×n、3、0.5和7。需要強調一點,為使計算結果更可靠,在實際求解過程中將SB的仿真次數設定為100,并將這100次仿真得到的調整成本平均值設置為Cadju(SB)。

3.2 測試結果

3.2.1 算法對比結果 表2給出了VNS-PTS與其他3種對比算法之間的比較結果,包括隨機禁忌搜索(PTS)、變鄰域禁忌搜索(VNS-TS)和變鄰域搜索算法(VNS)。由于PTS 已被證明優于TS 算法[27],故未考慮TS算法。

表2 算法對比結果

首先,由表2數據可以看出,VNS-PTS算法表現最好,計算所得總成本遠小于其他3種算法,其次是VNS-TS和VNS,PTS表現最差,說明混合啟發式算法可以融合單獨啟發式算法的優點從而大幅度提高解的質量。但需要注意的是,這種融合的效果取決于單獨算法本身特點之間的屬性,如VNSPTS算法績效要顯著優于VNS 和PTS 的算法績效,而VNS-TS與VNS之間的差距卻明顯要小得多;此外,對于小規模算例集(N＜60),VNS-PTS和VNS-TS算法表現結果非常接近,但對于較大規模算例集(N≥60),VNS-PTS要明顯優于VNS-TS,說明雖然采取隨機鄰域策略可以顯著提高算法搜索效率,但對于解質量的改進僅僅在鄰點數規模較大時才會體現出來。由此可知,混合啟發式算法的效率一方面與采取的算法特點有關,另一方面要考慮問題規模大小。

其次,對比3種初始解生成方法,可以看出,通過FALS方法獲得的解質量表現最優,但需要消耗較長的運算時間,而FSLA 方法所需時間最短但獲得的解質量卻最差,RAND 方式介于兩者之間。這種結果出乎意料,按照預想,通過添加時間緩沖提高基準進度魯棒性,那么,在生成初始解時采取緩沖導向型方式可以為后續緩沖搜索提供較好的基礎進而取得滿意的效果,但實驗證明這種方式不可行。可見,雖然時間緩沖的大小直接決定了魯棒性成本及調整成本的構成,但活動列表AL的排列方式卻對集成模型的最終結果起到了非常重要的作用。因此,在以后研究中對活動列表進行改進,然后在其基礎上尋找滿意的緩沖列表對提高算法績效具有較大影響。

最后,從算法時間指標看,4種算法運行時間都隨著問題規模的增大而增加。其中,VNS消耗時間最長,其次是VNS-TS和VNS-PTS,PTS消耗時間最小。這很容易理解,在搜索相同可行解的條件下,變鄰域搜索由于要頻繁改變鄰域生成方式獲得鄰點解并進行鄰域搜索,消耗了大量的時間,而在加入禁忌搜索后,雖然需要判斷禁忌列表,但時間遠遠小于鄰域變換所需的時間。因此,VNS-TS運行消耗要小于VNS。同時,考慮隨機鄰域特征大幅減小了需要判斷的可行解數目,使得VNS-PTS算法的運行時間隨之下降。

綜上所述,針對本文提出的前攝性與反應性調度集成模型,在均衡算法效率與質量的前提下,VNS-PTS無疑是最優的解決方案。

3.2.2 關鍵參數敏感性分析 為了測試算法對參數的敏感性,圖2給出了項目魯棒性成本、調整成本和總成本分別在參數ck、wi、RS、Dn和Dv下的變化曲線。

圖2 項目3種成本隨參數變化曲線

(1)隨著ck的增加,Crobu、Cadju和TC這3項成本都上升,而Crobu上升的速率遠大于Cadju上升的速率,使得總成本TC的變化趨向于Crobu變化的方向。這主要是由于在集成模型中,Crobu需要直接通過ck來計算,兩者之間存在正相關關系,故當ck值較高時,單位時間緩沖占用的資源成本增加,導致Crobu隨之上升。而在最小化總成本TC目標的驅動下,項目經理會更傾向于使用反應性調度方法,減少基準進度中插入的時間緩沖總量,但這同時也導致了Cadju的增加。由于這種影響是間接產生的,故Cadju曲線的變化趨勢要平緩得多。

(2)參數wi得到了與ck類似的變化趨勢。但是,相反地,Crobu的影響下降,而Cadju則在TC上升過程中起主導作用。此時,項目管理者更傾向于采用前攝性調度方法處理不確定性,通過最大程度地控制調整成本Cadju,實現TC最小化的目標。在這種情況下,更多的時間緩沖將被添加到基準進度中,導致Crobu相應地上升。

(3)當RS上升時,Cadju和TC下降,而Crobu上升。顯然,對于較高的RS,資源可用量變得充足,使得資源約束在一定程度上得到緩解,這為項目經理在進行基準進度安排時提供了更大的靈活性,同時緩沖的安排也變得更加靈活。因此,Crobu上升而Cadju則下降。但是Crobu的增長速率遠小于Cadju下降的速率,綜合作用的結果便是導致總成本TC的下降。需要說明的是,隨著RS的不斷增加,基準進度中可供添加的時間緩沖總量會受到項目截止日期的約束,導致資源的靈活性受到一定的限制而無法繼續發揮作用。總之,較高的RS為項目經理提供了更多的緩沖分配方案,因此更容易實現兩種調度方法的有效集成。

(4)由表2可以發現,參數Dn對算法性能有顯著的影響。當Dn上升時,Cadju和TC下降,而Crobu增加。這很容易理解,Dn的值直接決定了可以插入的時間緩沖總量。Dn越高,基準進度中可添加的時間緩沖就越多,則緩沖占用的成本Crobu就會越高;而充足的緩沖會大幅抵消中斷帶來的負面影響,使得調整成本Cadju變小。在這個變化過程中,Cadju下降的速率要明顯快于Crobu上升的速率,導致TC呈下降趨勢。然而,當繼續放松截止日期時,Crobu仍然增加,但是其變化斜率卻開始略微下降。這可以通過參數Dn和RS之間的相互作用來解釋,與上述RS分析類似,雖然較寬松的截止日期提供了更多的時間緩沖總量,但沒有足夠的可用資源支撐,這些緩沖便不能被視為有效的緩沖保護機制,因為一旦活動工期延長,卻沒有可供該活動使用的資源,依然會導致項目的中斷。而且,在實際項目調度中,過長的項目截止日期是不可接受的。因此,項目經理應把Dn和RS一起考慮,以獲得最佳結果。

(5)Dv呈現出與wi相似的變化,但Cadju與Crobu的差距更加明顯。這主要是因為隨著活動不確定度的提高,工期變化的范圍變大,導致項目在執行過程中遇到中斷的可能性及調整復雜性提高,反應性中調整成本也大幅增加。此時,項目管理者更傾向于采用前攝性調度方法處理不確定性,在基準進度中添加較多的時間緩沖提高基準進度魯棒性以應對不確定性,導致Crobu相應地上升。

3.2.3 反應性策略分析 表3以VNS-PTS為例,深入分析了不同環境復雜度下3種反應策略對項目執行過程的影響情況,這里主要通過項目平均中斷次數、項目延期概率及項目平均延期長度來衡量項目的穩定性程度。

表3 不同反應性策略下項目執行效果

由表3可以看出,DP 策略表現最優,3個指標都明顯小于其他兩種策略。由于DP策略在每次中斷調整時均采用上一次獲得的基準進度的開始時間為依據,而每次開始時間的確定都是前攝性調度在當前已知信息情況下選擇最優調度方案的結果,因而獲得的策略能在很大程度上對后續項目執行具有較高的指導意義。對比SS和FR 策略發現,SS策略在總體上要優于FR 策略,但當工期不確定較低時,SS策略的平均中斷次數要大于FR 策略;而當工期不確定較高時,SS策略的平均延期概率要大于FR 策略。同時,隨著不確定度的升高,FR 策略的衡量指標發生了明顯的變化,說明環境復雜度對FR 策略的效果影響較大。這主要是因為SS 策略的質量取決于隨機生成的可行解的質量,如果可行解中包含了魯棒性較高的基準計劃,則得到的結果將較優;反之,則結果較差。當不確定性升高時,這種策略的隨機性程度更高,導致結果的不確定性也隨之升高。而在FR 策略下,需要保持資源流向固定,一旦發生中斷,項目管理者為了不破壞原有資源分配方式,不得不將受中斷影響的活動向后移動,一方面直接導致了項目的延期,同時由于無法對其周圍活動采取有效的安排方式,浪費了大量的緩沖時間。此外,每次中斷更新后,獲得的新的策略以上一次的基準計劃為基礎,當基準計劃較差時,會將影響傳遞至后續的策略獲得中,進一步加劇了項目變差的程度,也增加了項目總成本的支出。

3.2.4 與魯棒性最大化模型對比 表4給出了本文提出的成本集成模型(Min-TC)和魯棒性最大模型(Max-Robu)在不同活動工期變化下的比較結果。

表4 Min-TC 與Max-Robu模型對比

由表4可以清楚地看到,Min-TC 模型的魯棒性成本Crobu遠小于Max-Robu模型的魯棒性成本,而兩個模型的調整成本Cadju之間的差異不是很大,導致前者的總成本TC明顯低于后者。該結論進一步證實了Min-TC模型相對于Max-Robu模型在總成本方面的優勢。由于在Max-Robu模型中,為了實現項目執行期間總調整成本最小,管理者會盡可能多地添加時間緩沖以最大化基準進度的魯棒性,然而卻忽略了該時間緩沖所占用的資源以及每次活動中斷導致的單次調整成本。因此,魯棒性成本Crobu和調整成本Cadju都隨著時間緩沖的增加而增長,造成更高的總成本TC。Min-TC模型同時考慮了前攝性調度中的魯棒性成本和反應性調度中的中間調整成本,從總體上獲得了總成本的最優。因此,如果管理者想要最經濟地處理不確定性,他/她應該采用Min-TC模型來生成項目的基準進度。

另外,考慮活動不確定性水平,兩個模型下的TC、Crobu和Cadju呈現相似的變化趨勢,隨著不確定水平的增加同步增長。這很容易理解,在一個更高的不確定性環境下,活動的實際工期偏離期望工期的概率會大大增加,而且延遲長度也更長。因此,項目在實施過程中可能更需要頻繁調用反應性調度進行調整。為了解決這個問題,項目管理者可能會傾向于添加更多的時間緩沖。但是不確定度越高,環境越復雜,前攝性調度中通過預測活動變化添加緩沖的方式也變得越來越難,使得調整不可避免地發生。因此,在雙重影響下,魯棒性成本和調整成本都上升,導致總成本也同步增加。

4 結論

本文基于前攝性調度與反應性調度兩種方法在應對不確定因素過程中的任務分擔情況,同時從項目計劃與執行全過程出發,研究了如何構建前攝性調度與反應性調度的集成優化模型,從而以最經濟的方式應對不確定環境的擾動。得出如下結論:

(1)將前攝性調度產生的魯棒性成本與反應性調度產生的調整成本統稱為不確定成本,在此基礎上構建了以總不確定成本最優為目標的前攝性與反應性調度的集成優化模型。其中,通過改變基準進度中緩沖分配量,魯棒性成本與調整成本同時發生變化。通過這種方式,當得到最優基準進度時,亦即獲得了最優總成本;與此同時,中斷也通過前攝性調度與反應性調度的集成模型得到了有效處理。

(2)針對問題的NP-hard屬性,在禁忌搜索中加強了搜索的隨機屬性,同時與變鄰域搜索算法結合,設計了混合變鄰域隨機禁忌搜索啟發式算法。根據問題特點,在初始解生成中考慮活動與緩沖的不同導向設計了3種初始解生成方案,然后以單純的隨機禁忌搜索和變鄰域搜索以及混合變鄰域禁忌搜索為比較基準,在隨機生成的大規模算例集合上對算法進行驗證與分析。結果表明,本文提出的混合變鄰域隨機禁忌搜索啟發式算法要優于單純啟發式算法,而且增強算法隨機屬性在算例規模較大時可以發揮較好的作用。

(3)算例參數的變化會對算法績效產生顯著影響,項目總成本隨著參數ck、wi和Dv的上升而提高,隨著參數RS和Dn的上升而下降,說明當資源較充足時,前攝性調度會發揮更大的保護作用,決定了總成本會隨著魯棒性成本的變化而變化。反之,當活動變化度較高時,反應性調度會占據主導位置,使總成本的變化趨向于調整成本的變化方向。

(4)在實際項目執行中,當發生中斷需要進行調整時,采取動態優先規則策略對項目平均中斷次數、延期概率和延期長度等方面都有著較好的表現,同時優化資源配置可以改進項目執行過程的效率。

(5)與魯棒性最大化模型相比,后者忽略了時間緩沖作為一種資源,同時也會產生成本。尤其是當資源比較稀缺時,通過添加緩沖所帶來的調整成本的下降反而會造成總成本的大幅上升,違背了管理者追求經濟最大化的目標。相反,集成模型雖然無法獲得基準進度魯棒性最高,但卻通過犧牲部分魯棒性的方式獲得了總成本的最優。

本文研究可以為項目管理者在面對不確定環境時如何進行高效決策提供理論支持,有助于項目經理從經濟角度對前攝性調度與反應性調度在應對不確定因素干擾時發揮的作用進行量化分析,從而更好地分配這兩種調度方法在使用中的權衡情況,提高基準進度的指導作用以及項目管理者對現場施工的管控能力。