李 遷, 陶 莎, 周曉園,盛昭瀚
(南京大學(xué)工程管理學(xué)院,江蘇 南京 210093)
工程施工進(jìn)度計(jì)劃以及資源的有效配置是施工項(xiàng)目管理的重要科學(xué)問題[1-2]。除了人力、設(shè)備等資源,施工現(xiàn)場(chǎng)的空間也是重要資源之一。實(shí)踐表明,施工活動(dòng)安排不合理引起的活動(dòng)作業(yè)空間不足、作業(yè)空間相互占用易造成作業(yè)效率低下、返工、安全隱患等不良后果,大大阻礙了工程目標(biāo)的實(shí)現(xiàn)[3-5]。因此,在優(yōu)化施工調(diào)度方案時(shí)充分考慮施工活動(dòng)的空間需求以及空間約束條件對(duì)工程管理實(shí)踐具有一定的現(xiàn)實(shí)意義。
目前大多學(xué)者借助可視化仿真技術(shù)對(duì)施工中的空間干涉問題開展研究[6-8]。這類研究通常基于已知的調(diào)度方案,借助數(shù)字化技術(shù)識(shí)別空間干涉,并通過制定規(guī)則來局部地調(diào)整計(jì)劃方案,以消除或解決空間干涉問題。Moon[6]等人提出一種序列檢查算法來避免并行活動(dòng)之間發(fā)生空間干涉。Choi[7]等人設(shè)計(jì)了一種作業(yè)空間規(guī)劃的流程框架,包含識(shí)別4D BIM、識(shí)別作業(yè)空間、表征空間占用、識(shí)別空間干涉、解決空間干涉五個(gè)階段。Zhang[8]等人利用GPS定位系統(tǒng)和BIM實(shí)時(shí)地判斷人員的作業(yè)空間,進(jìn)而識(shí)別潛在的空間干涉并及時(shí)采取防范措施。然而,這類方法缺乏對(duì)調(diào)度計(jì)劃進(jìn)行預(yù)先的整體性優(yōu)化設(shè)計(jì)。此外,少部分學(xué)者對(duì)具體資源(如人、機(jī)械設(shè)備)的運(yùn)行方位和動(dòng)作軌跡等細(xì)節(jié)上進(jìn)行建模,避免其作業(yè)過程中發(fā)生沖突[3,9]。例如,Isaac[9]等人采用時(shí)間-空間圖描述員工的動(dòng)態(tài)運(yùn)動(dòng)過程,將員工作業(yè)路徑表示為粒度函數(shù),對(duì)并行活動(dòng)進(jìn)行時(shí)間和空間的分配。該類研究從資源運(yùn)動(dòng)的微觀視角,而非從整體工程項(xiàng)目的宏觀視角根據(jù)活動(dòng)的空間需求信息優(yōu)化工程調(diào)度方案。
資源受限的項(xiàng)目調(diào)度問題(RCPSP)是運(yùn)籌學(xué)和運(yùn)作管理領(lǐng)域的重要研究方向,旨在研究考慮資源供給限制的項(xiàng)目調(diào)度優(yōu)化問題,其應(yīng)用領(lǐng)域涉及建設(shè)工程、工業(yè)生產(chǎn)、物流交通等[10]。RCPSP將資源類型大致分為可再生資源(如人力資源)和非再生資源(如原料),空間資源屬于一類有限的可再生資源[11]。一些學(xué)者結(jié)合RCPSP與有限工程空間資源開展研究。Frene[12]等人設(shè)計(jì)空間資源的請(qǐng)求活動(dòng)(Call activity)、中間活動(dòng)(Interval activity)、釋放活動(dòng)(Release activity)三類活動(dòng),基于RCPSP并提出采用串行方案生成機(jī)制的啟發(fā)式算法解決問題。Semenov[13]等人在RCPSP中考慮空間擁堵和作業(yè)流擾動(dòng)約束,建立以工程工期最短為目標(biāo)的優(yōu)化模型。Tao[14]等人將空間擁堵作為優(yōu)化目標(biāo)之一,建立時(shí)間-成本-擁擠度多目標(biāo)工程調(diào)度優(yōu)化模型。
本文創(chuàng)新性地從空間干涉降低施工作業(yè)效率的現(xiàn)實(shí)出發(fā),以工期和成本為目標(biāo),基于RCPSP相關(guān)理論,建立考慮空間干涉的工程調(diào)度時(shí)間-成本雙目標(biāo)優(yōu)化模型。與以往研究假設(shè)工期已知不同,該模型定義了活動(dòng)的作業(yè)效率曲線和實(shí)際工期變量。此外,不同于傳統(tǒng)求解RCPSP算法的序列或權(quán)重編碼方式,本文針對(duì)性地設(shè)計(jì)了相對(duì)延遲編碼方式和相應(yīng)解碼機(jī)制,采用NSGA-II算法有效求解問題。
采用AON(Activity-On-Node)網(wǎng)絡(luò)表達(dá)工程項(xiàng)目,記為G={N,A}。集合N={0,1,…,n,n+1}表示n+2個(gè)活動(dòng),其中活動(dòng)0和n+1分別表示虛擬開始和結(jié)束活動(dòng)。集合P?N×N表示活動(dòng)之間的工序關(guān)系,若i是j的緊前活動(dòng),則(i,j)∈P。每個(gè)活動(dòng)i有|Mi|種可選擇的執(zhí)行模式,定義每個(gè)活動(dòng)的備選模式集合Mi={1,2,…,|Mi|},m∈Mi。假設(shè)資源有|K|種,定義資源集合K={1,2,…,|K|},k∈K。工程項(xiàng)目的計(jì)劃時(shí)間范圍(Plan Horizon)為[0,T],為方便算法設(shè)計(jì),將時(shí)間離散化成時(shí)段集合,記為T={1,…,|T|},t∈T。本研究基于假設(shè):1)活動(dòng)的作業(yè)效率僅受空間干涉影響并與空間干涉程度呈負(fù)相關(guān);2)活動(dòng)實(shí)際工期僅受作業(yè)效率影響,不考慮其它影響因素;3)每個(gè)活動(dòng)所需的作業(yè)空間已知。
本文的研究問題可概括為:在已知活動(dòng)工序、計(jì)劃工期以及作業(yè)空間需求等參數(shù)條件下,考慮活動(dòng)執(zhí)行過程中的空間干涉對(duì)作業(yè)效率和實(shí)際工期的影響,如何合理選擇各活動(dòng)的執(zhí)行模式并安排活動(dòng)執(zhí)行時(shí)間,以達(dá)到工程工期和成本均最小化的目標(biāo)。
作業(yè)空間干涉(Workspace Interference)或簡(jiǎn)稱空間干涉是指在活動(dòng)執(zhí)行過程中,其作業(yè)空間被其他活動(dòng)占用,從而對(duì)自身產(chǎn)生一定的干擾和影響??臻g干涉發(fā)生要求兩個(gè)或兩個(gè)以上的活動(dòng)在同一時(shí)間有相同的空間需求,即作業(yè)空間重疊[6]。假設(shè)任意活動(dòng)i的作業(yè)空間記為Ωi,函數(shù)v(Ωi)表示該作業(yè)空間的體積,則活動(dòng)i的資源密度表示為資源占用的空間體積與總體作業(yè)空間體積之比,如公式(1)。
(1)
其中,υk表示每單位資源k占用的空間體積。Rimk表示活動(dòng)i執(zhí)行模式m所需資源k的數(shù)量。xim為0/1決策變量,當(dāng)選擇模式m執(zhí)行活動(dòng)i時(shí),xim=1;否則,xim=0。
進(jìn)一步地,定義任意t時(shí)段上活動(dòng)i的空間干涉程度Si(t)為其它活動(dòng)在t時(shí)段內(nèi)與活動(dòng)i重疊空間內(nèi)的資源密度加和,如公式(2)[13-14]。
Si(t)=∑i′∈Ni(ρi′·v(Ωi∩Ωi′)·yit·yi′t),?i,k
(2)
其中,Ωi∩Ωj表示兩作業(yè)空間Ωi和Ωj的重疊部分。yit為0/1變量,當(dāng)活動(dòng)i在t時(shí)段上執(zhí)行時(shí),yit=1;否則,yit=0。可以看出,對(duì)于任意活動(dòng)i,i′,若v(Ωi∩Ωi′)=0(作業(yè)空間不重疊)或者yit·yi′t=0(作業(yè)時(shí)間不重疊),則空間干涉為0。
活動(dòng)的作業(yè)效率和實(shí)際工期均是受空間干涉影響的變量。在無空間干涉的理想情況下,活動(dòng)i在執(zhí)行模式m時(shí)的計(jì)劃工期為Wim,即Wim是完成活動(dòng)i所需的總工作量或總工時(shí)。而在空間干涉的影響下,活動(dòng)作業(yè)效率隨時(shí)間改變,記效率函數(shù)為ei(t)∈[0,1]。參考作業(yè)效率與其它因素(如學(xué)習(xí)速度、經(jīng)驗(yàn))的函數(shù)關(guān)系[15],本文采用Sigmoid函數(shù)定義ei(t),如公式(3)。
ei(t)
(3)
(4)
(5)
為了更容易理解,以圖1的效率函數(shù)為例,計(jì)劃工期等于效率函數(shù)曲線與時(shí)間軸圍成的陰影區(qū)域的面積??梢钥闯觯诘趖時(shí)段上活動(dòng)i是否結(jié)束與第t-1時(shí)段及之前各時(shí)段內(nèi)的累計(jì)工作量有關(guān)。當(dāng)累計(jì)工作量小于總工作量要求,則活動(dòng)i未完成,第t時(shí)段將繼續(xù)執(zhí)行活動(dòng)i;否則,活動(dòng)i完成且完工時(shí)間為t-1?;谶@一思想,初始化t為活動(dòng)i的開始時(shí)間,循環(huán)上述操作直至活動(dòng)i完成,即能確定其結(jié)束時(shí)間。下一節(jié)將基于該思想設(shè)計(jì)算法的編碼方式和解碼機(jī)制。
圖1 作業(yè)效率和實(shí)際工期的關(guān)系示意圖
本文同時(shí)考慮工期和成本兩目標(biāo),建立如下雙目標(biāo)數(shù)學(xué)規(guī)劃模型。其中,公式(6)計(jì)算項(xiàng)目工期fT,即虛擬結(jié)束活動(dòng)的開始時(shí)間。公式(7)計(jì)算總成本fC,總成本由活動(dòng)執(zhí)行成本和延期成本兩部分構(gòu)成。其中,活動(dòng)執(zhí)行成本等于所有活動(dòng)成本之和∑i,m∈Mixim·Cim(Cim表示活動(dòng)i在模式m下執(zhí)行時(shí)所需的直接成本);延期成本等于超期時(shí)間max{tn+1-Tdl,0}乘以延遲單位時(shí)間的懲罰成本CP(截止工期記為Tdl)。約束(8)是工序關(guān)系,即任意活動(dòng)的開始時(shí)間不得早于其前序活動(dòng)的完成時(shí)間。約束(9)定義0/1變量yit,即當(dāng)活動(dòng)i在t時(shí)段上正在執(zhí)行時(shí),yit=1;否則為0。由于每個(gè)活動(dòng)只能選擇一種執(zhí)行模式,因而約束(10)成立。此外,模型還包括上述介紹的公式(1)至公式(5)。
minF=(fT,fC)
(6)
fC=∑i,m∈Mixim·Cim+CP·max{fT-Tdl,0}
(7)
(8)
?i∈N,t∈T
(9)
∑i,m∈Mixim=1
(10)
約束(1)-(5)
NSGA-II是經(jīng)典的多目標(biāo)優(yōu)化算法之一,它具有全局優(yōu)化性好、通用性強(qiáng)和易于實(shí)現(xiàn)等優(yōu)勢(shì),且在算法收斂性、魯棒性等方面展現(xiàn)出良好的性能,因而在經(jīng)濟(jì)管理、工業(yè)工程等領(lǐng)域得到了廣泛應(yīng)用[16]。本文采用NSGA-II求解問題,由于未涉及改變NSGA-II算法框架和算子,關(guān)于NSGA-II算法介紹請(qǐng)參考相關(guān)文獻(xiàn),此處不再贅述。
求解RCPSP的啟發(fā)式算法的編碼方式一般包括活動(dòng)排序和活動(dòng)權(quán)重兩種,排序和權(quán)重均體現(xiàn)活動(dòng)占用資源的優(yōu)先權(quán)。傳統(tǒng)的解碼機(jī)制通常采用貪婪準(zhǔn)則,即在資源允許的情況下活動(dòng)盡早開始。這種方式難以靈活控制活動(dòng)執(zhí)行時(shí)間上的重疊程度。然而,本文研究的問題需要更精細(xì)地控制活動(dòng)執(zhí)行時(shí)間,從而調(diào)整空間干涉對(duì)作業(yè)效率及實(shí)際工期的影響。因此,傳統(tǒng)的RCPSP編碼和解碼方法難以適用本文問題。為此,本文針對(duì)性地設(shè)計(jì)了基于相對(duì)延遲編碼方式和相應(yīng)解碼機(jī)制。
編碼由2n個(gè)整數(shù)元素構(gòu)成,記為DML=(Δ1,…,Δn,m1,…,mn)。其中,前n個(gè)元素中,Δi表示活動(dòng)i的相對(duì)延遲時(shí)間,即相對(duì)于活動(dòng)i的最早可開始時(shí)間再延遲Δi單位時(shí)間,活動(dòng)i才開始執(zhí)行?;顒?dòng)i的最早可開始時(shí)間指的是活動(dòng)i的前序活動(dòng)全部完成的時(shí)刻。Δi=0表示活動(dòng)i不延遲,即其前序活動(dòng)均完成時(shí)立即開始執(zhí)行。Δi的取值范圍為{0,1,…,MAXΔ},參數(shù)MAXΔ表示最大延遲時(shí)間。DML后n個(gè)元素為活動(dòng)的模式選擇,mi∈Mi。由于NSGA-II算法的染色體x=(x1,…,x2n),x∈[Minx,Maxx]為實(shí)數(shù)向量。針對(duì)本文問題特征,設(shè)定染色體的每個(gè)基因位的取值區(qū)間分別為xj∈[0,1],?j∈{1…n}和xj∈[1,Max|Mi|],?j∈{n+1…2n}。接著,根據(jù)公式(11)和(12)對(duì)任意實(shí)數(shù)向量x進(jìn)行離散化處理,將x映射為DML。其中,函數(shù)round表示四舍五入。
Δi=round(xi·MAXΔ),?i∈{1…n}
(11)
mi=round(xi+n),?i∈{1…n}
(12)
圖2 解碼機(jī)制
某辦公樓裝飾工程由19個(gè)活動(dòng)構(gòu)成的,活動(dòng)基本信息如表1所示[3,17],各活動(dòng)的作業(yè)空間布局如圖3所示。其他參數(shù)設(shè)置如表2,不妨稱為標(biāo)準(zhǔn)參數(shù)設(shè)置。
表1 活動(dòng)參數(shù)表
表1 活動(dòng)參數(shù)表
圖3 空間示意圖
表2 實(shí)驗(yàn)的參數(shù)設(shè)置
算法在軟件MATLAB R2013a上編譯,算例實(shí)驗(yàn)在CPU主頻2.20GHz,內(nèi)存8GB,64位操作系統(tǒng)配置的個(gè)人計(jì)算機(jī)上運(yùn)行實(shí)現(xiàn)。
4.2.1 標(biāo)準(zhǔn)參數(shù)下的結(jié)果分析
基于表2參數(shù)執(zhí)行NSGA-II算法,得到一個(gè)包含7個(gè)解的Pareto集合,解集在目標(biāo)空間內(nèi)的分布如圖4所示。工期和成本在一定程度上相互沖突,尤其在工期小于125或大于144時(shí),工期與成本近乎成線性關(guān)系。當(dāng)工期小于125時(shí),成本與工期的沖突性更大,即每壓縮一單位時(shí)間所付出的成本更高。以目標(biāo)取值為(125, 259)的最優(yōu)解為例,活動(dòng)的效率曲線如圖5所示,每個(gè)活動(dòng)開始于第一次效率大于零的時(shí)刻,結(jié)束時(shí)刻是在效率再次降為零且此后始終為零時(shí),活動(dòng)的工期為活動(dòng)結(jié)束時(shí)刻與開始時(shí)刻之差。從效率曲線圖上不僅可以看出每個(gè)活動(dòng)的開始作業(yè)時(shí)間和工期,還可以看出每個(gè)活動(dòng)的作業(yè)效率隨時(shí)間和項(xiàng)目發(fā)展的變化情況,可見效率曲線圖比傳統(tǒng)甘特圖更詳盡。
圖4 Pareto解集
圖5 各活動(dòng)的效率曲線(橫軸為時(shí)間,縱軸為效率)
4.2.2 與傳統(tǒng)方法對(duì)比分析
基于表2參數(shù)設(shè)置執(zhí)行NSGA-II算法,重復(fù)實(shí)驗(yàn)10次,共計(jì)求得38個(gè)最優(yōu)解。由于空間干涉主要影響活動(dòng)調(diào)度決策,因此令所有解的模式選擇決策保持不變,采用傳統(tǒng)正向調(diào)度法求解工程調(diào)度方案,計(jì)算所得方案的時(shí)間和成本目標(biāo)值。箱線圖6統(tǒng)計(jì)了NSGA-II所得的方案相比于傳統(tǒng)方法所得方案在時(shí)間和成本兩方面的節(jié)省,計(jì)算公式為(傳統(tǒng)方案時(shí)間/成本目標(biāo)-NSGAII方案時(shí)間/成本目標(biāo))÷傳統(tǒng)方案時(shí)間/成本目標(biāo)。相比于傳統(tǒng)方法得到的方案,NSGA-II所得方案在工期目標(biāo)上平均節(jié)省3.09%,在95%的情況下NSGA-II的方案具有更短的工期;在成本目標(biāo)上,NSGA-II的方案平均節(jié)省1.01%,在26%的情況下傳統(tǒng)方法所得方案的成本更大且增加的成本是延期成本,這是由于實(shí)驗(yàn)設(shè)定活動(dòng)執(zhí)行模式不變,兩組解的活動(dòng)執(zhí)行成本相同。實(shí)驗(yàn)表明,傳統(tǒng)方法引起工程延期主要是由于在安排活動(dòng)時(shí)忽略了空間干涉的影響,使得調(diào)度方案執(zhí)行時(shí)的空間干涉增大,引起作業(yè)效率降低。綜上,本文在工程調(diào)度問題中考慮空間干涉影響,對(duì)工程進(jìn)度和成本兩方面目標(biāo)均更為有利。
圖6 考慮與不考慮空間干涉的方案目標(biāo)對(duì)比
4.2.3 最大延遲時(shí)間參數(shù)影響分析
為了評(píng)估不同MAXΔ取值下算法所得解集的優(yōu)劣,首先選擇一個(gè)解集作為比較基準(zhǔn),視為精確Pareto解集。本文通過隨機(jī)運(yùn)行算法10次,匯集所有解并從中刪除重復(fù)解和支配解,最終得到由7個(gè)非支配解構(gòu)成的Pareto解集,其目標(biāo)向量(完工時(shí)間,成本×102)分別為(123,281),(125,275),(126,259),(129,253),(130,249),(149,243),(151,241)。與精確Pareto解集相比,對(duì)不同MAXΔ取值下的NSGA-II求得的解集從五方面指標(biāo)進(jìn)行評(píng)價(jià),分別是無可行解次數(shù)、可行解數(shù)量、非支配解占比、收斂性(即離精確Pareto前沿的距離)和算法運(yùn)行時(shí)間。令參數(shù)MAXΔ=10,20,30,…,70,其它參數(shù)按標(biāo)準(zhǔn)設(shè)置。不同MAXΔ取值下,每組實(shí)驗(yàn)重復(fù)進(jìn)行10次,五個(gè)指標(biāo)的均值如下表3所示。可以看出,算法平均得到的可行解數(shù)量隨著MAXΔ增加而逐漸減少。甚至當(dāng)MAXΔ≥50時(shí),隨著MAXΔ增長(zhǎng),算法運(yùn)行失敗(即找不到可行解)的次數(shù)明顯增加。這是因?yàn)镸AXΔ增長(zhǎng)使解空間范圍大幅擴(kuò)大,算法搜索非支配解甚至可行解的難度都大大增加。然而,并非令MAXΔ取值越小就對(duì)算法性能有利,從表3的非支配解占比和收斂性指標(biāo)可以看出,盡管MAXΔ取值越小,算法得到的可行解數(shù)量更多,但解的最優(yōu)性表現(xiàn)欠佳。例如當(dāng)MAXΔ取值為10和20時(shí),算法得到的非支配解數(shù)量較少且離精確Pareto前沿距離較遠(yuǎn)。這是由于MAXΔ取值越小,搜索的解空間范圍越小,從而容易遺漏搜索范圍之外的最優(yōu)解。從表3可以看出,當(dāng)MAXΔ取值為40時(shí),非支配解占比和收斂性均是最高,分別是22.86%和0.77。在算法運(yùn)行時(shí)間方面,各組實(shí)驗(yàn)的算法平均耗時(shí)相差不大,說明對(duì)于本案例問題,MAXΔ對(duì)算法的運(yùn)行時(shí)間影響較小。綜上,MAXΔ取值過大或者過小都不利于Pareto解的質(zhì)量。針對(duì)本文案例,MAXΔ取值為40時(shí)的算法性能表現(xiàn)最好。
表3 不同MAXΔ取值的算法性能比較
*收斂性指標(biāo)的計(jì)算除去了無可行解的實(shí)驗(yàn)結(jié)果。
工程活動(dòng)的作業(yè)空間干涉會(huì)引起資源作業(yè)相互干擾,導(dǎo)致作業(yè)效率降低,從而對(duì)工程總體進(jìn)度和成本產(chǎn)生不利的影響。本文在工程調(diào)度優(yōu)化問題中考慮空間干涉對(duì)作業(yè)效率的影響,定義活動(dòng)作業(yè)效率和活動(dòng)實(shí)際工期關(guān)于空間干涉的函數(shù),建立時(shí)間-成本雙目標(biāo)優(yōu)化的工程調(diào)度模型。為有效求解模型,采用NSGA-II元啟發(fā)式算法并針對(duì)性地設(shè)計(jì)相對(duì)延遲編碼方式和解碼機(jī)制。對(duì)某一裝飾工程案例研究發(fā)現(xiàn),與傳統(tǒng)調(diào)度方法相比,本文提出的方法可以更有效地加快工程進(jìn)度,節(jié)省施工成本。通過多組對(duì)比實(shí)驗(yàn)探討算法參數(shù)MAXΔ對(duì)算法性能的影響,結(jié)果表明MAXΔ取值過大或過小都不利于算法性能。針對(duì)本文的工程案例,MAXΔ取值為40時(shí)算法性能最好。本研究對(duì)于提高施工方案質(zhì)量、改善施工作業(yè)環(huán)境、保證施工安全等方面均具有一定的理論和實(shí)踐意義。未來可進(jìn)一步將優(yōu)化模型、元啟發(fā)式算法與可視化信息技術(shù)結(jié)合,設(shè)計(jì)工程調(diào)度的計(jì)算實(shí)驗(yàn)平臺(tái),為工程實(shí)踐者提供技術(shù)支持。