張立輝, 李怡菲, 鄒 鑫, 曹薔楠,3

(1.華北電力大學 經(jīng)濟與管理學院,北京 102206; 2.華北電力大學 經(jīng)濟管理系,河北 保定 071003; 3.內(nèi)蒙古大學 創(chuàng)業(yè)學院,內(nèi)蒙古 呼和浩特 010021)

0 引言

國內(nèi)外已經(jīng)對確定性環(huán)境下的項目調(diào)度問題進行了多年研究,然而,由于當前市場環(huán)境的迅速變化,復雜工程項目(如“一帶一路”跨國項目、PPP項目等)所面臨的風險和不確定性日益嚴峻,例如活動工期估計不準確、資源供應不及時、機器故障、惡劣天氣影響以及設計變更等。這些不可控因素會擾亂項目活動的有序執(zhí)行,造成組織和協(xié)調(diào)上的混亂,從而導致工期延誤、成本增加等問題。例如,港珠澳大橋由于周邊區(qū)民質(zhì)疑其環(huán)境評估,延期長達9個月,損失88億元;長沙霞凝110kV變配套線路工程執(zhí)行過程中由于設計經(jīng)常修改,導致工期延誤長達6個月。因此,在不確定環(huán)境下,制定一個具有強抗干擾能力的基準進度計劃非常有必要。

魯棒性項目調(diào)度通過充分考慮不確定性因素的干擾從而制定抗干擾能力強的進度計劃和靈活的應對策略,已經(jīng)成為近年來國內(nèi)外學者研究的熱點問題。魯棒性項目調(diào)度的優(yōu)化目標分為質(zhì)量魯棒性和解的魯棒性[1],質(zhì)量魯棒性是指調(diào)度方案對于目標函數(shù)的穩(wěn)定性,解的魯棒性是指調(diào)度方案在執(zhí)行過程中按照計劃執(zhí)行的穩(wěn)定性。在質(zhì)量魯棒性方面,大多數(shù)研究主要集中在度量方式上,其中項目工期和按時完工率[2]是最為常用的目標函數(shù)。何立華和孔云霄[3]提出了一個基于活動延期風險和前繼活動數(shù)量的質(zhì)量魯棒性衡量指標,并通過算例驗證了該指標的優(yōu)越性。在解的魯棒性方面,CHTOUROU和HAOUARI[4]考慮項目活動間的優(yōu)先關(guān)系約束,將自由時差優(yōu)先分配給緊后活動數(shù)量較多的活動。HERROELEN和LEUS[5]以活動實際與計劃開始時間的偏差損失成本最小為目標,利用活動總時差提升進度計劃的魯棒性。何正文等[6]用活動的時間緩沖與其權(quán)重系數(shù)的乘積之和衡量解的魯棒性,將時間緩沖分配給工期變化性較高的活動。一些研究也集中于質(zhì)量魯棒性和解的魯棒性的權(quán)衡優(yōu)化。Al-FAWZAN和HAOUARI[7]以自由時差之和表示解魯棒性,構(gòu)建工期最短和魯棒性最大的雙目標模型,并采用禁忌搜索算法進行求解。HOOGEVEEN[8]采用即時完工率最大和活動開始時間偏差最小兩個目標,通過賦權(quán)加和的方式將其轉(zhuǎn)化為一個復合函數(shù)求解。張靜文等[9]從時差效用函數(shù)新視角衡量調(diào)度方案的魯棒性,建立工期-魯棒性雙目標資源約束型魯棒調(diào)度優(yōu)化模型,并設計了快速非分配性排序多目標遺傳算法。

軟邏輯是指項目工序可采用與預先施工邏輯順序不同的方式進行施工的一種進度計劃組織方式。例如,“地基挖掘1→地基挖掘2→…→地基挖掘I”,上述活動在工藝和技術(shù)上相互獨立,可以互換施工順序,也可以選擇同時進行。TAMIMI和DIEKMANN[10]首次在CPM中提出軟邏輯概念,并將其應用于突發(fā)事件引起的網(wǎng)絡計劃圖更新。El-SERSY[11]進一步將軟邏輯分為三個子類型:SOFT,OR和EXCLUSIVE-OR,同樣應用于網(wǎng)絡計劃圖的更新。FAN[12]在項目延遲分析中提出了一種基于軟邏輯的項目調(diào)度更新算法,使工期延長的計算更加合理、準確。在調(diào)度優(yōu)化方面,WANG[13]探究了在活動工期不確定條件下,三種軟邏輯對項目工期的影響,并提出估算項目總工期的PROSOFT模型。FAN等[14]提出了一種基于軟邏輯的重復性項目優(yōu)化模型的遺傳算法,旨在幫助管理者根據(jù)不同的工作效率和邏輯順序?qū)で笞畹偷目偝杀?。張立輝等[15]綜合考慮軟邏輯對項目總工期和成本的影響,建立了多模式時間-費用權(quán)衡問題模型。綜上所述,軟邏輯已被應用于項目工期和費用的優(yōu)化研究,但尚未發(fā)現(xiàn)將軟邏輯應用于不確定環(huán)境下項目魯棒調(diào)度優(yōu)化的研究。

基于以上事實,本文將探究軟邏輯對項目魯棒調(diào)度的影響,建立基于軟邏輯的雙目標魯棒項目調(diào)度優(yōu)化模型,并設計e-約束算法對其進行求解,以求進一步提升項目魯棒性,從而為項目管理者提供相關(guān)決策支持。

1 考慮軟邏輯的雙目標魯棒項目調(diào)度優(yōu)化模型

1.1 軟邏輯類型及其對項目調(diào)度方案的影響

(1)軟邏輯類型

EI-SERSY[11]將活動間的軟邏輯關(guān)系分為三種類型:OR,EXCLUSIVE-OR和SOFT,如圖1所示,其中(a)表示活動A和B的軟邏輯關(guān)系為“OR”型,即活動A和B可以同時進行,但不可以互換施工順序;(b)表示活動A和B的軟邏輯關(guān)系為“EXCLUSIVE-OR”型,即活動A和B可以互換施工順序,但不可以同時進行;(c)表示活動A和B的軟邏輯關(guān)系為“SOFT”型,即活動A和B間的關(guān)系同時具備“OR”型和“EXCLUSIVE-OR”型的性質(zhì),既可以同時進行,也可以互換施工順序。

圖1 軟邏輯類型

(2)軟邏輯對項目工期和解魯棒性的影響

在項目調(diào)度方案中,關(guān)鍵路線的長度直接決定了項目的總工期,不確定環(huán)境下每個活動的自由時差由于能起到緩沖的作用而與項目的解魯棒性直接相關(guān)。軟邏輯為項目調(diào)度提供了更大的靈活性,一方面通過合理地調(diào)整軟邏輯的順序,可以改變項目調(diào)度的關(guān)鍵路線從而影響總工期;另一方面軟邏輯順序的變化,可以改變活動間的優(yōu)先關(guān)系,進而對活動的自由時差的計算產(chǎn)生影響,并最終影響解魯棒性的大小?？紤]如圖2所示的一個活動間存在軟邏輯的簡單項目,當不考慮軟邏輯時,即采用固定邏輯施工時,項目的關(guān)鍵路線為1-3-5,總工期為12天,活動4有6個單位的自由時差,如圖2(a)所示;當考慮軟邏輯時,活動3和5同時進行,活動2和4互換施工順序,項目的關(guān)鍵路線變?yōu)?-2-5,總工期縮短為11天,此時活動1和3都有2個單位的自由時差,如圖2(b)所示。

(3)軟邏輯對緊后活動數(shù)量的影響

魯棒性指標是魯棒項目調(diào)度研究中較為關(guān)鍵的環(huán)節(jié),大多數(shù)研究在建立魯棒性指標時都會考慮緊后活動數(shù)量這一要素。因此,有必要探究軟邏輯對緊后活動數(shù)量的影響。

當活動i及其緊后活動j之間的順序發(fā)生變化,活動i,j以及j的潛在緊前活動的緊后活動數(shù)量都會發(fā)生變化。以圖3所示網(wǎng)絡計劃圖為例,分析三種類型軟邏輯對緊后活動數(shù)量的具體影響,作為構(gòu)建魯棒優(yōu)化模型的基礎:

圖3 某工程項目網(wǎng)絡計劃圖

1)OR型軟邏輯對緊后活動數(shù)量的影響。如圖4所示,活動i的緊后活動數(shù)量變?yōu)?NDSi-1+PSi),其中NDSi為活動i的初始緊后活動數(shù)量,PSi為活動i潛在的緊后活動數(shù)量;若活動j存在潛在緊前活動,則該潛在緊前活動的緊后活動數(shù)量變?yōu)?NDSpprej+1),其中pprej為活動j的潛在緊前活動,NDSpprej為活動j潛在緊前活動的初始緊后活動數(shù)量。

圖4 OR軟邏輯順序變化后的網(wǎng)絡計劃圖

2)EXCLUSIVE-OR型軟邏輯對緊后活動數(shù)量的影響。如圖5所示,活動i的緊后活動數(shù)量變?yōu)?NDSi-1+PSi);活動j增加一個緊后活動i,若活動i存在潛在的緊后活動,此時活動j將失去對該活動的實際約束,則活動j的緊后活動數(shù)量變?yōu)?NDSj+1-PSi);若活動j存在潛在緊前活動,則該潛在緊前活動增加一個緊后活動j,但此時該活動也會失去對活動i的實際約束,因此,該活動的緊后活動數(shù)量可視為不變。

圖5 EX-CLUSIVE-OR軟邏輯順序變化后的網(wǎng)絡計劃圖

3)SOFT型軟邏輯對緊后活動數(shù)量的影響。由于SOFT型軟邏輯同時具備OR和EX-CLUSIVE-OR型軟邏輯的性質(zhì),因此其對緊后活動數(shù)量的影響與上述兩類軟邏輯相同。

1.2 模型構(gòu)建

采用基于活動的方式,將項目抽象為一個AoN(Activity-on-Node)網(wǎng)絡,G=(V,E),其中V為活動集合,V={0,1,…,n,n+1},活動0和活動n+1均為虛活動,分別表示項目的開始與結(jié)束。E為有向弧的集合,表示活動間的邏輯關(guān)系,其中,E1為固定邏輯關(guān)系集合,既包括具有固定邏輯施工順序的活動間的邏輯關(guān)系,也包括軟邏輯活動與其他活動的潛在固定邏輯關(guān)系,(i,j)∈E1表示活動i結(jié)束后活動j才能開始;E2為OR型軟邏輯關(guān)系集合,(i,j)∈E2表示活動i和j可平行施工,但施工順序不可互換;E3為EXCLUSIVE-OR型軟邏輯關(guān)系集合,(i,j)∈E3表示活動i和j的施工順序可互換,但不可平行施工;E4為SOFT型軟邏輯關(guān)系集合,(i,j)∈E4表示活動i和j既可改變施工順序,也可平行施工?；顒觟(i=0,1,…,n+1)的工期均值為非負整數(shù)E(di),實際活動工期受多種不確定性因素的干擾可能在工期均值上下浮動。項目截止日期為δ。需要說明的是,為了充分利用軟邏輯,本文暫不考慮資源的約束。

式中,wi表示經(jīng)過歸一化的風險權(quán)重,項目管理者根據(jù)實際工程經(jīng)驗或者其他判斷依據(jù)給予活動延誤風險權(quán)重。

基于上述分析,本文考慮軟邏輯的魯棒調(diào)度優(yōu)化問題可界定為:在活動網(wǎng)絡優(yōu)先關(guān)系和項目截止日期約束條件下,確定軟邏輯的順序,并利用時間緩沖添加策略進行主動調(diào)度,實現(xiàn)項目工期和魯棒性的權(quán)衡優(yōu)化。

綜上,構(gòu)建考慮軟邏輯的魯棒項目調(diào)度優(yōu)化模型:

(1)

minT=sn+1

(2)

s.t.si+E(di)+Δi≤sj,(i,j)∈E1

(3)

si+E(di)+Δi≤sj+Mxij,(i,j)∈E2

(4)

si

(5)

sj

(6)

NDSi=NDSi-1+PSi,

NDSpprej=NDSpprej+1,(i,j)∈E2,xij=1

(7)

si+E(di)+Δi≤sj+Myij,(i,j)∈E3

(8)

sj+E(di)+Δj≤si+M(1-yij),(i,j)∈E3

(9)

DNSi=NDSi-1+PSi,NDSj=NDSj+1-PSi,(i,j)∈E3,yij=1

(10)

(11)

(12)

(13)

(14)

(15)

(16)

NDSi=NDSi-1+PSi,NDSj=NDSj+1-PSi,

(17)

sn+1≤δ

(18)

si∈R+,i∈V

(19)

xij∈{0,1},(i,j)∈E2

(20)

yij∈{0,1},(i,j)∈E3

(21)

(22)

2 算法設計

該模型的目標是同時最小化項目工期和最大化進度計劃魯棒值,故其最優(yōu)解將會是由多個相互之間無占優(yōu)關(guān)系的單個解組成的Pareto最優(yōu)解集。e-約束算法具有求解多目標優(yōu)化問題的能力,可以在有限的步驟中得到所有精確的帕累托解,在文獻中得到了廣泛的應用,也尤其適合本問題的求解。

e-約束算法的基本理念是:將其中一個目標函數(shù)轉(zhuǎn)化為約束,并通過逐步增大e值建立一連串單目標優(yōu)化問題進行求解。為描述e-約束算法,還需定義以下3類點:

基于本文建立的雙目標優(yōu)化模型中一個目標為最小化,另一個目標為最大化,可以表達e-約束算法如下:

步驟4通過將被支配的點從集合F′中移除,得到Pareto最優(yōu)前沿F。

3 算例分析

3.1 項目背景

本文采用FAN[12]和FAN等[14]共同使用的一個室內(nèi)建設實際工程案例進行說明,該實際工程案例包括22個活動,圖6展示了該項目的計劃進度網(wǎng)絡,項目合同期限為50天。其中,活動8存在潛在緊后活動20,活動11存在潛在緊前活動5,活動6存在潛在緊后活動9和14,活動17存在潛在緊后活動20。相較于原始案例,本文增加考慮了各活動面臨的延誤風險大小,并對所有活動的風險權(quán)重進行歸一化處理。項目相關(guān)信息如表1所示。

表1 實際工程案例相關(guān)信息

圖6 示例工程項目計劃進度網(wǎng)絡圖

3.2 結(jié)果分析

為了分析軟邏輯對項目工期和魯棒性的影響,分別求解軟邏輯和固定邏輯假設下的雙目標魯棒調(diào)度優(yōu)化問題。在個人電腦(i5-1135G7 CPU,2.4GHz,8G內(nèi)存)上使用IBM ILOG優(yōu)化編程語言OPL建模,并用CPLEX V12.8的求解引擎CP Optimizer進行求解。歷時約9s,得到該案例的Pareto解集和工期-魯棒性權(quán)衡曲線如表2和圖7所示。

表2 雙目標優(yōu)化Pareto解集

圖7 最優(yōu)Pareto前沿曲線對比

從圖7中可以明顯看出,在工期相同的情況下,軟邏輯情形下求得的項目調(diào)度方案的魯棒性都優(yōu)于固定邏輯情形下得到的方案。以工期為45～50天時的基準調(diào)度方案為例,從表2可知,相比固定邏輯,軟邏輯情形下的調(diào)度方案的解魯棒值平均增加了87.34%。這是因為軟邏輯通過調(diào)整活動間的優(yōu)先關(guān)系,使得可添加的緩沖大大增加,從而提高了調(diào)度方案的解魯棒性。

由表2可知,軟邏輯情形下得到的調(diào)度方案的項目工期最多可以縮短到40天,相比固定邏輯情形下的最短工期45天,項目總工期縮短了12.50%。軟邏輯情形下OR型和SOFT型軟邏輯順序都被調(diào)整為同時進行,項目網(wǎng)絡的關(guān)鍵路線從6→1→9→17→19→20變?yōu)?→9→17→19→20。因此,關(guān)鍵路線上的OR型軟邏輯可確保項目工期的縮短,這也為時間緩沖的添加騰出更多的空間。

此外,從表2中看出,在項目截止日期50天的約束下,考慮軟邏輯得到的可行魯棒項目調(diào)度方案有11個,而不考慮軟邏輯得到的可行調(diào)度方案只有6個,可行的項目調(diào)度方案數(shù)量增加了87.8%,因此,考慮軟邏輯使項目具有更多可選擇的可行調(diào)度方案,大大增強了調(diào)度的靈活性,這有利于決策者根據(jù)項目的實際需求來調(diào)整項目的進度計劃。

3.3 軟邏輯提高項目魯棒性的途徑

為了探究軟邏輯提高魯棒性的具體途徑,在兩種邏輯施工順序假設下得到的魯棒性最優(yōu)項目調(diào)度中,按照CPM網(wǎng)絡計算得到項目的關(guān)鍵路線及其長度,如表3所示。可以看出,固定邏輯條件下,關(guān)鍵路線始終保持不變,而在考慮軟邏輯情形下,項目網(wǎng)絡的關(guān)鍵路線有所改動,或縮短或延長,但最終都使得調(diào)度方案的魯棒性得以提升。

表3 兩種邏輯類型假設下的關(guān)鍵路線

在利用時間緩沖方法得到的魯棒性最優(yōu)基準進度計劃中,各活動的時間緩沖由兩部分組成:網(wǎng)絡自發(fā)形成的時間緩沖和項目管理者人為添加的時間緩沖。固定邏輯假設下,項目活動優(yōu)先關(guān)系不能改變,因此增加活動的時間緩沖以增強魯棒性的途徑只有一種,即不斷地增加人為添加的時間緩沖,與此同時,這會導致工期的不斷延長,在項目截止日期的約束下,該途徑提升魯棒性的程度有限?？紤]軟邏輯情況下,活動優(yōu)先關(guān)系可以改變,除了與固定邏輯一樣以延長工期為代價以外,還有以下兩種不影響項目工期提高魯棒性的途徑:

1)通過軟邏輯減少網(wǎng)絡自發(fā)形成的時間緩沖,但為人為緩沖的添加留下了空間。如表3中(1)(2)所示,軟邏輯通過改變關(guān)鍵路線壓縮了項目的工期,工期的縮短一方面會導致項目網(wǎng)絡自身形成的時間緩沖減少,另一方面也會帶來可插入時間緩沖的增加,當前者對活動自由時差的影響小于后者時,就能提高項目調(diào)度的魯棒性。

2)通過軟邏輯增加網(wǎng)絡自發(fā)形成的時間緩沖。不改變關(guān)鍵路線的情況下,軟邏輯可以通過改變非關(guān)鍵路線上的軟邏輯順序,增加非關(guān)鍵活動的時間緩沖,從而提高項目調(diào)度的魯棒性;改變關(guān)鍵路線延長工期的情況下,如表3中(3)所示,工期的延長一方面會導致項目網(wǎng)絡自身形成的時間緩沖增加,另一方面也會導致可插入的時間緩沖減少,當前者對活動自由時差的影響大于后者時,也能提高項目調(diào)度的魯棒性。

3.4 蒙特卡洛模擬分析

選取基于軟邏輯的最優(yōu)調(diào)度方案以及基于固定邏輯的最優(yōu)調(diào)度方案作為仿真的初始進度計劃,計劃完工時間都為45天,項目截止日期為50天。假設項目活動延誤時間服從自由度為2的卡方分布,由于本算例規(guī)模較小,分別將活動工期延誤2～6次,并隨機生成發(fā)生延誤的活動編號,利用Matlab 2016a對項目的執(zhí)行進行模擬,一共模擬1000次,統(tǒng)計結(jié)果如表4和圖8所示?？梢钥闯?相比固定邏輯,運用本文提出的基于軟邏輯的雙目標優(yōu)化模型所求得的基準調(diào)度方案,其項目活動執(zhí)行的穩(wěn)定性和按時完工的穩(wěn)定性都更好,抵抗風險的能力也更強,并且隨著延誤次數(shù)的增加,這種差距越來越明顯。

表4 蒙特卡洛模擬結(jié)果

圖8 R1和R2隨延誤次數(shù)變化曲線

上述結(jié)果表明,本文提出的基于軟邏輯的雙目標魯棒優(yōu)化模型優(yōu)化了項目進度計劃的解魯棒性,插入活動的時間緩沖較好地吸收了不確定性因素的干擾,同時也保證了項目在截止日期前完工,使項目調(diào)度具有一定的抗風險能力。

4 結(jié)束語

本文將軟邏輯應用于不確定環(huán)境下的項目調(diào)度研究,進一步提高調(diào)度方案的魯棒性。論文基于三種類型的軟邏輯構(gòu)建魯棒性項目調(diào)度的雙目標優(yōu)化模型,最小化項目總工期和最大化項目魯棒值,并運用e-約束算法將雙目標模型轉(zhuǎn)換為工期約束下的魯棒值最大化子模型進行求解。通過一個實際案例對研究問題進行說明,得到了軟邏輯能同時優(yōu)化項目工期和解魯棒性的結(jié)論,并揭示了軟邏輯提高魯棒性的具體途徑。最后,通過蒙特卡洛模擬進一步驗證模型的有效性。本文研究可以為存在軟邏輯的項目的魯棒進度計劃制定提供定量化的決策支持。但是,在工程實際執(zhí)行過程中,資源的可用量往往是有限的,軟邏輯的改變也會導致資源需求量的變化,因此后續(xù)將進行考慮軟邏輯的資源約束型魯棒項目調(diào)度問題研究。