王艷婷,何正文,索 琪

(1.青島科技大學(xué) 經(jīng)濟(jì)與管理學(xué)院,山東 青島 266061;2.西安交通大學(xué) 管理學(xué)院 過程控制與效率工程教育部重點(diǎn)實(shí)驗(yàn)室,西安 710049)

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

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

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

單獨(dú)的前攝性或反應(yīng)性調(diào)度都無法對干擾做出充分的處理以滿足項(xiàng)目穩(wěn)定性指標(biāo),因此一些學(xué)者提出前攝-反應(yīng)性項(xiàng)目調(diào)度方法,通過前攝性調(diào)度得到帶保護(hù)機(jī)制的基準(zhǔn)進(jìn)度,當(dāng)活動發(fā)生中斷時(shí)調(diào)用反應(yīng)性策略對基準(zhǔn)進(jìn)度進(jìn)行修復(fù)。該方向的文獻(xiàn)目前還比較少,可見到的有:Calhoun 等[24]將生產(chǎn)計(jì)劃中調(diào)度與再調(diào)度之間進(jìn)行聯(lián)系,在前攝性調(diào)度中最大基準(zhǔn)計(jì)劃魯棒性,反應(yīng)性調(diào)度中最小化變化的活動數(shù);Van de Vonder等[25]運(yùn)用工期與魯棒性的復(fù)合目標(biāo)來評價(jià)不同的前攝性進(jìn)度生成方法與反應(yīng)性調(diào)度策略,結(jié)果表明,運(yùn)用工期最小的基準(zhǔn)計(jì)劃輔之以解魯棒性的反應(yīng)性策略可以達(dá)到兩個(gè)目標(biāo)的綜合優(yōu)化。

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

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

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

1 問題界定

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

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

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

其中,wi為活動i實(shí)際開始時(shí)間偏離基準(zhǔn)計(jì)劃開始時(shí)間產(chǎn)生的單位損失成本。

基于上述問題定義,可以得到一個(gè)項(xiàng)目在整個(gè)計(jì)劃與執(zhí)行中產(chǎn)生的總不確定性成本TC,即

TC=Crobu(SB)+Cadju(SB)

本文研究的目的就是找到這樣一個(gè)基準(zhǔn)計(jì)劃SB,使總不確定性成本最小。因此,構(gòu)建基于總成本最優(yōu)的前攝性調(diào)度與反應(yīng)性調(diào)度集成優(yōu)化模型如下所示,為后文方便,將其記為Min-TC:

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

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

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

2 算法設(shè)計(jì)

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

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

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

2.1 解的表示與解碼

基于研究問題的特征,每個(gè)解均由活動次序列表AL和時(shí)間緩沖列表SL構(gòu)成。

活動次序列表AL。該列表由n+2個(gè)活動代號構(gòu)成,各代號在列表中的位置決定了其所對應(yīng)活動在計(jì)劃安排時(shí)的優(yōu)先次序,注意列表中活動必須滿足優(yōu)先關(guān)系約束。

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

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

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

2.2 初始解的生成

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

(1)活動導(dǎo)向型(FALS)。首先通過基于優(yōu)先規(guī)則的啟發(fā)式方法生成AL,然后在其基礎(chǔ)上尋找滿意的SL,具體步驟如下:

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

步驟2令活動k=ALl,計(jì)算活動k的候選集Ck={j|(k,j)∈A,j∈N}及候選集內(nèi)活動優(yōu)先權(quán)值PRj(j∈Ck),同時(shí),l=l+1;

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

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

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

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

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

步驟8計(jì)算活動開始時(shí)間,如果sn+1＜D,轉(zhuǎn)步驟6,否則退出,輸出列表AL和SL。

其中,活動i的優(yōu)先權(quán)PRi由下式獲得:

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

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

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

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

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

步驟4εj*=εj*+1,dj*=dj*+εj*,計(jì)算活動開始時(shí)間,如果sn+1＜D,轉(zhuǎn)步驟3,否則轉(zhuǎn)步驟5;

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

步驟6輸出列表AL和SL。

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

2.3 鄰域結(jié)構(gòu)

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

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

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

2.4 禁忌列表及終止準(zhǔn)則

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

2.5 算法流程

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

2.6 反應(yīng)性調(diào)度策略

在項(xiàng)目執(zhí)行中,當(dāng)發(fā)生中斷需要進(jìn)行調(diào)整時(shí),一方面要考慮活動工期的隨機(jī)變化情況,另一方面要選擇恰當(dāng)?shù)恼{(diào)整策略。根據(jù)調(diào)整的效率及復(fù)雜度提出如下3種反應(yīng)性策略:

(1)簡單抽樣(SS)。在每個(gè)中斷決策點(diǎn),隨機(jī)生成幾個(gè)可行進(jìn)度,然后選取其中目標(biāo)函數(shù)最優(yōu)的一個(gè)作為新的基準(zhǔn)進(jìn)度。

(2)動態(tài)優(yōu)先規(guī)則(DP)。在每個(gè)中斷決策點(diǎn),將尚未開始的活動按開始時(shí)間升序排列,由此得到優(yōu)先列表,然后按照解碼程序得到基準(zhǔn)進(jìn)度。

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

在每次活動中斷時(shí),分別應(yīng)用這3種調(diào)整策略對未完成活動進(jìn)行調(diào)整。

3 算法測試

3.1 參數(shù)設(shè)置

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

圖1 VNS-PTS流程圖

表1 參數(shù)設(shè)置

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

3.2 測試結(jié)果

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

表2 算法對比結(jié)果

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

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

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

綜上所述,針對本文提出的前攝性與反應(yīng)性調(diào)度集成模型,在均衡算法效率與質(zhì)量的前提下,VNS-PTS無疑是最優(yōu)的解決方案。

3.2.2 關(guān)鍵參數(shù)敏感性分析 為了測試算法對參數(shù)的敏感性,圖2給出了項(xiàng)目魯棒性成本、調(diào)整成本和總成本分別在參數(shù)ck、wi、RS、Dn和Dv下的變化曲線。

圖2 項(xiàng)目3種成本隨參數(shù)變化曲線

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

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

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

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

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

3.2.3 反應(yīng)性策略分析 表3以VNS-PTS為例,深入分析了不同環(huán)境復(fù)雜度下3種反應(yīng)策略對項(xiàng)目執(zhí)行過程的影響情況,這里主要通過項(xiàng)目平均中斷次數(shù)、項(xiàng)目延期概率及項(xiàng)目平均延期長度來衡量項(xiàng)目的穩(wěn)定性程度。

表3 不同反應(yīng)性策略下項(xiàng)目執(zhí)行效果

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

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

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

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

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

4 結(jié)論

本文基于前攝性調(diào)度與反應(yīng)性調(diào)度兩種方法在應(yīng)對不確定因素過程中的任務(wù)分擔(dān)情況,同時(shí)從項(xiàng)目計(jì)劃與執(zhí)行全過程出發(fā),研究了如何構(gòu)建前攝性調(diào)度與反應(yīng)性調(diào)度的集成優(yōu)化模型,從而以最經(jīng)濟(jì)的方式應(yīng)對不確定環(huán)境的擾動。得出如下結(jié)論:

(1)將前攝性調(diào)度產(chǎn)生的魯棒性成本與反應(yīng)性調(diào)度產(chǎn)生的調(diào)整成本統(tǒng)稱為不確定成本,在此基礎(chǔ)上構(gòu)建了以總不確定成本最優(yōu)為目標(biāo)的前攝性與反應(yīng)性調(diào)度的集成優(yōu)化模型。其中,通過改變基準(zhǔn)進(jìn)度中緩沖分配量,魯棒性成本與調(diào)整成本同時(shí)發(fā)生變化。通過這種方式,當(dāng)?shù)玫阶顑?yōu)基準(zhǔn)進(jìn)度時(shí),亦即獲得了最優(yōu)總成本;與此同時(shí),中斷也通過前攝性調(diào)度與反應(yīng)性調(diào)度的集成模型得到了有效處理。

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

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

(4)在實(shí)際項(xiàng)目執(zhí)行中,當(dāng)發(fā)生中斷需要進(jìn)行調(diào)整時(shí),采取動態(tài)優(yōu)先規(guī)則策略對項(xiàng)目平均中斷次數(shù)、延期概率和延期長度等方面都有著較好的表現(xiàn),同時(shí)優(yōu)化資源配置可以改進(jìn)項(xiàng)目執(zhí)行過程的效率。

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

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