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

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

0 引言

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

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

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

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

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

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

(1)軟邏輯類型

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

圖1 軟邏輯類型

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

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

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

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

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

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

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)絡(luò)計劃圖

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

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

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

1.2 模型構(gòu)建

采用基于活動的方式,將項(xiàng)目抽象為一個AoN(Activity-on-Node)網(wǎng)絡(luò),G=(V,E),其中V為活動集合,V={0,1,…,n,n+1},活動0和活動n+1均為虛活動,分別表示項(xiàng)目的開始與結(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)的工期均值為非負(fù)整數(shù)E(di),實(shí)際活動工期受多種不確定性因素的干擾可能在工期均值上下浮動。項(xiàng)目截止日期為δ。需要說明的是,為了充分利用軟邏輯,本文暫不考慮資源的約束。

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

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

綜上,構(gòu)建考慮軟邏輯的魯棒項(xiàng)目調(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 算法設(shè)計

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

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

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

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

3 算例分析

3.1 項(xiàng)目背景

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

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

圖6 示例工程項(xiàng)目計劃進(jìn)度網(wǎng)絡(luò)圖

3.2 結(jié)果分析

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

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

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

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

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

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

3.3 軟邏輯提高項(xiàng)目魯棒性的途徑

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

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

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

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

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

3.4 蒙特卡洛模擬分析

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

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

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

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

4 結(jié)束語

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