李 遷, 陶 莎, 周曉園，盛昭瀚

(南京大學(xué)工程管理學(xué)院，江蘇 南京 210093)

1 引言

工程施工進(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算法有效求解問題。

2 問題定義與數(shù)學(xué)模型

采用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)。

2.1 作業(yè)空間干涉

作業(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。

2.2 作業(yè)效率函數(shù)

活動(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)系示意圖

2.3 數(shù)學(xué)模型

本文同時(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)

3 元啟發(fā)式算法

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ī)制

4 案例分析

4.1 案例描述和參數(shù)設(shè)置

某辦公樓裝飾工程由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 實(shí)驗(yàn)結(jié)果分析

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é)果。

5 結(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ù)支持。