基于子集模擬的建設(shè)工程項(xiàng)目多資源均衡優(yōu)化算法

王家，劉可心，張學(xué)清，陳濤

（1.湖南大學(xué) 土木工程學(xué)院，湖南 長(zhǎng)沙 410082；2.湖南大學(xué)建筑安全與環(huán)境國(guó)際聯(lián)合研究中心，湖南長(zhǎng)沙 410082；3.香港科技大學(xué) 土木與環(huán)境工程系，香港 999077；4.長(zhǎng)沙市美的房地產(chǎn)開(kāi)發(fā)有限公司，湖南 長(zhǎng)沙 410082）

建設(shè)項(xiàng)目的施工過(guò)程需消耗大量的人工、材料、機(jī)械等資源.如果建設(shè)項(xiàng)目實(shí)施過(guò)程中的資源計(jì)劃（勞動(dòng)力計(jì)劃、材料進(jìn)場(chǎng)計(jì)劃、機(jī)械排班等）安排不合理，會(huì)引起建設(shè)項(xiàng)目工期內(nèi)資源消耗量的過(guò)大波動(dòng)（表現(xiàn)為施工人員的窩工或少工、材料和機(jī)械的過(guò)度使用或空置等），最終影響建設(shè)工程的生產(chǎn)效率、成本節(jié)約和項(xiàng)目管理質(zhì)量[1].作為資源調(diào)度優(yōu)化的手段之一，資源均衡問(wèn)題（Resource Leveling Problem，RLP）旨在通過(guò)調(diào)整項(xiàng)目中非關(guān)鍵工序的計(jì)劃開(kāi)始時(shí)間，在不延長(zhǎng)項(xiàng)目工期和不違反各工序間邏輯關(guān)系的前提下，降低項(xiàng)目工期內(nèi)資源消耗量的波動(dòng).

針對(duì)資源均衡問(wèn)題的研究工作可分為兩類，一類偏重于資源均衡問(wèn)題的模型構(gòu)建，一類偏重于資源均衡問(wèn)題的優(yōu)化算法.資源均衡優(yōu)化模型一般可歸結(jié)為四類：簡(jiǎn)單的平方和模型[2-3]、考慮實(shí)際資源消耗量與期望值之間差值的偏差模型[1，4-5]、考慮不同周期資源消耗量變動(dòng)的波動(dòng)模型[6-7]、以及基于熵理論的熵模型[8-9].資源均衡問(wèn)題的優(yōu)化算法主要分為精確算法和啟發(fā)式算法.其中，精確算法主要基于動(dòng)態(tài)規(guī)劃、整數(shù)規(guī)劃、分支定界法等方法[10]，而啟發(fā)式算法主要基于蟻群算法[11]、粒子群算法[12]、禁忌搜索算法[13]、遺傳算法[14-18]等算法.資源均衡問(wèn)題的復(fù)雜程度隨涉及工序數(shù)量的增加而急速上升.因此，針對(duì)工序數(shù)量較多的項(xiàng)目資源均衡問(wèn)題，精確算法并不適用，只能采用啟發(fā)式算法.但是，啟發(fā)式算法具有隨機(jī)性，其每次運(yùn)行獲得的最優(yōu)解不一定相同（不穩(wěn)定），但現(xiàn)有啟發(fā)式算法在最優(yōu)解獲取穩(wěn)定性上仍有較大的改進(jìn)空間.

本文針對(duì)建設(shè)工程項(xiàng)目的多資源均衡優(yōu)化問(wèn)題，提出一種基于子集模擬的啟發(fā)式優(yōu)化算法.同時(shí)，為避免工序間邏輯關(guān)系違反時(shí)復(fù)雜修復(fù)算子的使用，本文采用間隔率變量表示的建設(shè)工程項(xiàng)目多資源均衡優(yōu)化模型，以簡(jiǎn)化基于子集模擬的優(yōu)化算法的操作.通過(guò)算例驗(yàn)證，與應(yīng)用較廣的遺傳算法相比，本文提出的優(yōu)化算法在最優(yōu)解獲取穩(wěn)定性上有較好的改進(jìn).

1 建設(shè)工程項(xiàng)目多資源均衡優(yōu)化模型

針對(duì)建設(shè)工程項(xiàng)目的多資源均衡優(yōu)化問(wèn)題，研究者一般借助網(wǎng)絡(luò)計(jì)劃工具進(jìn)行分析，并在一定的假設(shè)下構(gòu)建模型.本文研究的多資源均衡優(yōu)化模型基于以下假設(shè)：

1）組成建設(shè)項(xiàng)目的各個(gè)工序必須連續(xù)施工，不能間斷，且各工序間的邏輯關(guān)系不隨時(shí)間改變.

2）組成建設(shè)項(xiàng)目的各個(gè)工序在實(shí)施期內(nèi)，單位時(shí)間內(nèi)耗費(fèi)資源的種類和數(shù)量保持不變.

3）建設(shè)項(xiàng)目的總工期保持不變.

考慮一個(gè)包括N 個(gè)工序、且實(shí)施過(guò)程中涉及K種資源的建設(shè)工程項(xiàng)目.設(shè)項(xiàng)目中每一個(gè)工序i 的持續(xù)時(shí)間為Di，i=1，…，N，其持續(xù)時(shí)間內(nèi)每單位時(shí)間消耗的第k 種資源為，k=1，…，K.根據(jù)各工序的持續(xù)時(shí)間和相互間的邏輯關(guān)系，可采用關(guān)鍵路徑法（Critical Path Method，CPM）計(jì)算出各工序的最早開(kāi)始時(shí)間ESi和最晚開(kāi)始時(shí)間LSi，i=1，…，N，以及項(xiàng)目的總工期T.

建設(shè)工程項(xiàng)目多資源均衡優(yōu)化的目標(biāo)是通過(guò)合理安排各工序的計(jì)劃開(kāi)始時(shí)間Si，i=1，…，N，使項(xiàng)目實(shí)施期內(nèi)資源消耗的波動(dòng)最小.考慮到各工序間的邏輯關(guān)系和項(xiàng)目總工期T 保持不變的要求，各工序的計(jì)劃開(kāi)始時(shí)間Si，i=1，…，N 需滿足下述限制：

式中：pred（i）代表工序i 的所有緊前工序的集合.

在給定各工序的計(jì)劃開(kāi)始時(shí)間S=[S1，S2，…，SN]下，項(xiàng)目在總工期T 內(nèi)任意時(shí)刻t 所消耗第k 種資源的數(shù)量（S），t=1，…，T，k=1，…，K，可由該時(shí)刻正在施工的所有工序所消耗第k 種資源的數(shù)量匯總得到，即：

式中：δt，i（S）為t 時(shí)刻工序i 是否正在實(shí)施的指示變量，δt，i（S）=1 如Si≤t ≤Si+Di（t 時(shí)刻工序i 正在實(shí)施，如圖1 所示），否則δt，i（S）=0，，k=1，…，K 為工序i 單位時(shí)間內(nèi)第k 種資源的消耗量.

圖1 資源消耗量Fig.1 Resource consumption

在得到項(xiàng)目總工期內(nèi)施工所需各資源在不同時(shí)刻的消耗量后，可計(jì)算出用于衡量項(xiàng)目資源均衡效果的指標(biāo).針對(duì)資源均衡問(wèn)題，研究者從不同角度出發(fā)，提出了反映資源消耗量不均衡程度的多種指標(biāo)，但學(xué)術(shù)界尚未在各指標(biāo)的優(yōu)劣上達(dá)成共識(shí).從統(tǒng)計(jì)學(xué)角度看，標(biāo)準(zhǔn)偏差指標(biāo)可較好地反映項(xiàng)目在不同時(shí)刻資源消耗量的不均衡程度，在資源均衡優(yōu)化問(wèn)題中采用較廣[12，16，19].因此，本文采用標(biāo)準(zhǔn)偏差指標(biāo)來(lái)構(gòu)造建設(shè)工程項(xiàng)目多資源均衡優(yōu)化模型，但文中所提出的多資源均衡優(yōu)化算法與所選指標(biāo)無(wú)關(guān)，亦適用于其他指標(biāo)的情形.基于項(xiàng)目在總工期內(nèi)任意時(shí)刻t 所消耗第k 種資源的數(shù)量（S），t=1，…，T，k=1，…，K，總工期內(nèi)第k 種資源消耗量的標(biāo)準(zhǔn)偏差 為σ（k）（S）：

在項(xiàng)目多資源均衡優(yōu)化問(wèn)題中，為消除不同資源消耗量數(shù)量級(jí)、單位等的影響，本文將標(biāo)準(zhǔn)偏差無(wú)量綱化，采用標(biāo)準(zhǔn)偏差與平均消耗量的比值σ（k）（S）/來(lái)代表每一種資源的均衡效果.同時(shí)，為反映不同資源在多資源均衡優(yōu)化問(wèn)題中的重要性，可針對(duì)不同資源分配不同的權(quán)重系數(shù)，將目標(biāo)函數(shù)定義為不同資源無(wú)量化標(biāo)準(zhǔn)偏差的線性加權(quán)：

式中：wk為第k 種資源的相對(duì)權(quán)重，滿足=1，可采用層次分析法和德?tīng)柗品?、專家模糊綜合評(píng)分法、基于專家權(quán)重聚類的權(quán)重優(yōu)選法等方法確定[19].

綜上所述，本文研究的建設(shè)工程項(xiàng)目多資源均衡優(yōu)化模型可定義為：

2 采用間隔率變量表示的建設(shè)工程項(xiàng)目多資源均衡優(yōu)化模型

針對(duì)資源均衡問(wèn)題的優(yōu)化算法中，各工序計(jì)劃開(kāi)始時(shí)間（優(yōu)化問(wèn)題的設(shè)計(jì)變量）通常直接在其最早開(kāi)始時(shí)間和最晚開(kāi)始時(shí)間之間取值，即ESi≤Si≤LSi，i=1，…，N.但是，這種設(shè)計(jì)變量的取值方式，容易違反工序間的邏輯關(guān)系（不滿足公式（8）對(duì)應(yīng)的約束條件），需要引入復(fù)雜的修復(fù)算子來(lái)調(diào)整設(shè)計(jì)變量的取值.考慮圖2 所示的簡(jiǎn)單建設(shè)工程項(xiàng)目的單代號(hào)網(wǎng)絡(luò)圖，圖中標(biāo)明了各工序的持續(xù)時(shí)間、最早開(kāi)始時(shí)間、及最晚開(kāi)始時(shí)間.由圖2 可知，該網(wǎng)絡(luò)中的非關(guān)鍵工序?yàn)楣ば? 和工序4.如直接在工序最早開(kāi)始時(shí)間和最晚開(kāi)始時(shí)間之間取值，工序2 和工序4 的計(jì)劃開(kāi)始時(shí)間可以分別取7 和8，但這樣的取值顯然違反工序2 與工序4 的邏輯關(guān)系.具體而言，因工序2為工序4 的緊前工序，在工序2 的計(jì)劃開(kāi)始時(shí)間為7的條件下，工序4 的最早開(kāi)始時(shí)間變更為9，其計(jì)劃開(kāi)始時(shí)間不能取8.

圖2 典型建設(shè)工程項(xiàng)目的單代號(hào)網(wǎng)絡(luò)圖Fig.2 Activity-on-node network of a typical construction project

為避免上述取值方式的問(wèn)題，本文采用文獻(xiàn)[16]中提出的工序計(jì)劃開(kāi)始時(shí)間的間隔率表示方法.具體而言，考慮到LSi≤maxh{Sh+Dh}，h∈pred（i），可將公式（7）和（8）對(duì)應(yīng)的約束條件合并，即工序i 的計(jì)劃開(kāi)始時(shí)間Si取值范圍為：

如將區(qū)間[0，1]等分為（LSi-max{Sh+Dh}+1）個(gè)子區(qū)間，則這些子區(qū)間與Si可取的（LSi-max{Sh+Dh}+1）個(gè)整數(shù)間存在一一對(duì)應(yīng)的關(guān)系.因此，可定義在區(qū)間[0，1]連續(xù)取值的變量xi（間隔率變量），并根據(jù)其所在子區(qū)間，映射到工序i 的計(jì)劃開(kāi)始時(shí)間Si，

式中：int（）為取整函數(shù).針對(duì)圖2 所示的簡(jiǎn)單項(xiàng)目，如工序2 和工序4 的間隔率變量分別取0.73 和0.14，利用公式（10）可求得相應(yīng)的計(jì)劃開(kāi)始時(shí)間分別為4+int（0.73×（8-4+1））=7 和9+int（0.14×（10-9+1））=9.顯然可見(jiàn)，通過(guò)工序計(jì)劃開(kāi)始時(shí)間的間隔率變量表示，可避免違背工序間的邏輯關(guān)系.

利用間隔率變量和計(jì)劃開(kāi)始時(shí)間之間的映射（公式（10）），原始的離散變量?jī)?yōu)化問(wèn)題（公式（6）～（8））可轉(zhuǎn)化為如下的連續(xù)變量?jī)?yōu)化問(wèn)題：

約束條件為：

式中：g（x）為間隔率變量x=[x1，x1，…，xN]對(duì)應(yīng)的目標(biāo)函數(shù).為計(jì)算目標(biāo)函數(shù)值g（x），可首先利用公式（10）計(jì)算給定x 對(duì)應(yīng)的各工序的計(jì)劃開(kāi)始時(shí)間S=[S1，S2，…，SN]，進(jìn)而代入原始優(yōu)化問(wèn)題的目標(biāo)函數(shù)h（S）（公式（6））.

3 基于子集模擬的多資源均衡優(yōu)化算法

子集模擬法（Subset Simulation）是Au 和Beck 提出的、針對(duì)結(jié)構(gòu)可靠度問(wèn)題的高效數(shù)值模擬算法[20].其思想是通過(guò)引入一系列中間失效事件，將偶發(fā)事件的小概率估計(jì)問(wèn)題轉(zhuǎn)化為一組較大的條件概率估計(jì)問(wèn)題，進(jìn)而提高數(shù)值模擬算法的計(jì)算效率.通過(guò)建立可靠度問(wèn)題和優(yōu)化問(wèn)題的內(nèi)在聯(lián)系，子集模擬法也在優(yōu)化設(shè)計(jì)問(wèn)題中取得了較好的應(yīng)用[21-22].

3.1 基于子集模擬的多資源均衡優(yōu)化框架

考慮如下的全局優(yōu)化問(wèn)題：

為利用子集模擬法求解上述優(yōu)化問(wèn)題，人為設(shè)定設(shè)計(jì)變量x 為隨機(jī)變量，服從可行域Ω0={x ∶0≤xi≤1，i=1，…，N}內(nèi)的均勻分布.此外，子集模擬法通過(guò)引入一系列遞減的邊界值g1＞g2＞…＞gJ，在可行域Ω0內(nèi)定義一系列逐漸收縮的區(qū)域Ωj={x ∶x∈Ω0，g（x）≤gj}，j=1，…，J.其中，每一區(qū)域?yàn)橹皡^(qū)域的子集，即Ω0?Ω1?Ω2…?ΩJ.通過(guò)依次在可行域Ω0及逐漸收縮區(qū)域Ωj（j=1，…，J）內(nèi)按均勻分布進(jìn)行隨機(jī)取樣，子集模擬法可逐漸縮窄搜索區(qū)域，最終在最優(yōu)解附近的較小區(qū)域進(jìn)行搜索，以得到問(wèn)題的最優(yōu)解.

基于子集模擬的優(yōu)化算法有兩個(gè)重要參數(shù)：在指定區(qū)域中抽樣的樣本數(shù)量M 及條件概率參數(shù)p0.參數(shù)M 和p0的選擇，需確保Mp0和1/p0均為正整數(shù).由于Mp0確定了每一迭代中收縮區(qū)域初始樣本點(diǎn)的數(shù)量，當(dāng)p0過(guò)小時(shí)，需要較大的樣本數(shù)量M 才能保證Mp0的數(shù)值不至過(guò)小，以達(dá)到對(duì)收縮區(qū)域的有效搜索.當(dāng)p0過(guò)大時(shí)，迭代中考察區(qū)域的收縮變慢，優(yōu)化算法需要較多的迭代次數(shù).綜合目前的研究成果，p0一般在0.05～0.3 區(qū)間取值，進(jìn)而根據(jù)可承受計(jì)算資源確定樣本數(shù)量M.在參數(shù)確定后，基于子集模擬的優(yōu)化算法首先在可行域Ω0內(nèi)，產(chǎn)生服從均勻分布的M 個(gè)設(shè)計(jì)變量樣本，并計(jì)算它們的目標(biāo)函數(shù)值.接著，將目標(biāo)函數(shù)值由小到大排序，并取排在第Mp0位置的目標(biāo)函數(shù)值作為定義區(qū)域Ω1={x ∶x∈Ω0，g（x）≤g1}的邊界值g.此時(shí)，之前產(chǎn)生的M 個(gè)設(shè)計(jì)變量樣本（服從可行域Ω0內(nèi)的均勻分布）中，有Mp0個(gè)落在定義的收縮區(qū)域Ω1內(nèi)（服從收縮區(qū)域Ω1內(nèi)的均勻分布）.因此，可采用馬爾科夫鏈蒙特卡羅模擬方法（Markov chain Monte Carlo simulation，MCMCS，詳見(jiàn)3.2 節(jié)），以這Mp0個(gè)設(shè)計(jì)變量樣本作為Mp0個(gè)鏈條的起點(diǎn)，并針對(duì)每一鏈條額外產(chǎn)生（1/p0-1）個(gè)狀態(tài)點(diǎn)，以產(chǎn)生區(qū)域Ω1內(nèi)服從均勻分布的M 個(gè)設(shè)計(jì)變量樣本

圖3～圖6 描述了參數(shù)M=20 和p0=0.2 時(shí)的上述流程.針對(duì)圖3 可行域Ω0內(nèi)服從均勻分布的20個(gè)設(shè)計(jì)變量樣本，圖4 給出了它們所對(duì)應(yīng)的目標(biāo)函數(shù)值的升序排列.此時(shí)，定義下一收縮區(qū)域Ω1的邊界值g1，由20 個(gè)目標(biāo)函數(shù)值中第Mp0=4 小的數(shù)值確定，見(jiàn)圖4.對(duì)應(yīng)上述確定的g1，之前可行域Ω0內(nèi)均勻分布的M=20 個(gè)設(shè)計(jì)變量樣本，有Mp0=4 個(gè)落在收縮區(qū)域Ω1={x ∶x∈Ω0，g（x）≤g1}內(nèi)，見(jiàn)圖5.為產(chǎn)生收縮區(qū)域Ω1內(nèi)均勻分布的M=20 個(gè)設(shè)計(jì)變量樣本，可采用MCMCS 方法，以目前的Mp0=4 個(gè)樣本為種子，分別產(chǎn)生4 條馬爾科夫鏈鏈條，見(jiàn)圖6.每條鏈條以其中一個(gè)種子為起點(diǎn)，額外產(chǎn)生（1/p0-1）=4 個(gè)狀態(tài)點(diǎn)，以確?？偟臉颖緮?shù)為Mp0（1/p0-1+1）=M=20.

圖3 可行域Ω0 內(nèi)均勻分布的設(shè)計(jì)變量樣本點(diǎn)（M=20）Fig.3 Samples of the vector of design variables uniformly distributed in the feasible region Ω0（M=20）

圖4 定義收縮區(qū)域Ω1 的邊界值g1（M=20，p0=0.2）Fig.4 Threshold value of g1 for the shrinking region of Ω1（M=20，p0=0.2）

圖5 收縮區(qū)域Ω1 及落入其中的初始樣本點(diǎn)（M=20，p0=0.2）Fig.5 Shrinking region of Ω1 and the seed samples in Ω1（M=20，p0=0.2）

圖6 區(qū)域Ω1 內(nèi)均勻分布的設(shè)計(jì)變量樣本點(diǎn)Fig.6 Samples uniformly distributed in Ω1

得到區(qū)域Ω1內(nèi)服從均勻分布的M 個(gè)設(shè)計(jì)變量樣本后，可依次迭代重復(fù)上述邊界值的確定和對(duì)應(yīng)收縮區(qū)域內(nèi)隨機(jī)樣本點(diǎn)的產(chǎn)生流程，直到優(yōu)化算法的迭代終止原則滿足為止.此時(shí)，選擇最終的收縮區(qū)域中隨機(jī)樣本點(diǎn)的最優(yōu)者作為問(wèn)題的最優(yōu)解.

3.2 收縮區(qū)域Ωj={x ∶x∈Ω0，g（x）≤gj}內(nèi)均勻分布樣本點(diǎn)的產(chǎn)生

如3.1 節(jié)所述，基于子集模擬的多資源均衡優(yōu)化算法中，需根據(jù)收縮區(qū)域Ωj內(nèi)均勻分布的少量樣本點(diǎn)，利用MCMCS 方法產(chǎn)生滿足要求數(shù)量的樣本點(diǎn).考慮到多資源均衡優(yōu)化問(wèn)題中設(shè)計(jì)變量的維數(shù)（對(duì)應(yīng)項(xiàng)目涉及的工序數(shù)量）可能較大，本文采用改進(jìn)Metropolis-Hasting 方法[20]完成馬爾科夫鏈的產(chǎn)生任務(wù).

采用p*（ξ/x）來(lái)表示以x 為中心點(diǎn)，以d 為寬度（即x-d/2 ≤ξ ≤x+d/2）的一維均勻分布的概率密度分布函數(shù)，d 一般可取0.2～0.4.該概率密度分布函數(shù)自動(dòng)滿足對(duì)稱性，即p*（ξ/x）=p*（x/ξ）.為產(chǎn)生給定樣本點(diǎn)x1為起點(diǎn)的馬爾科夫鏈{x1，x2，…}，本文利用改進(jìn)Metropolis-Hasting 方法的思想，采用如下xk=[xk（1），xk（2），…，xk（N）]到xk+1=[xk+1（1），xk+1（2），…，xk+1（N）]的迭代操作：

3.3 基于子集模擬的多資源均衡優(yōu)化算法總結(jié)

針對(duì)采用間隔率變量表示的建設(shè)工程項(xiàng)目多資源均衡優(yōu)化模型（公式（11）～（12）），本文基于子集模擬法，建議的優(yōu)化算法步驟總結(jié)如下：

1）確定子集模擬算法中采用的參數(shù)，即在指定區(qū)域中抽樣的樣本數(shù)量M、條件概率參數(shù)p0和改進(jìn)Metropolis-Hasting 方法中定義一維均勻概率分布的寬度d.

4）算法采用的迭代終止原則為達(dá)到預(yù)先設(shè)定的迭代次數(shù)J.如不滿足迭代終止條件，即j ＜J，令j=j+1，重復(fù)步驟3.

4 算例分析

本文采用30 個(gè)工序組成的建設(shè)工程項(xiàng)目算例，來(lái)檢驗(yàn)基于子集模擬的多資源均衡優(yōu)化算法的性能.基于標(biāo)準(zhǔn)算例庫(kù)PSPLIB（Project Scheduling Problem Library）[23]中算例j301_1 的數(shù)據(jù)，表1 給出了算例項(xiàng)目的具體信息，包括項(xiàng)目中各工序的緊前工序（第3 列）、各工序的持續(xù)時(shí)間（第4 列），各工序每天對(duì)應(yīng)需求的4 種資源（人工、水泥、碎石、自卸車）的消耗量（第5～8 列）.根據(jù)各工序的持續(xù)時(shí)間和工序間的邏輯關(guān)系，可計(jì)算出該建設(shè)工程項(xiàng)目的工期為T(mén)=38 d.因標(biāo)準(zhǔn)算例庫(kù)在模型構(gòu)建方面的信息并不充分，沒(méi)有提供項(xiàng)目管理專家所需的針對(duì)權(quán)重指標(biāo)判斷的有效信息.因此，各資源的相對(duì)權(quán)重選擇確定為[w1，w2，w3，w4]=[0.2，0.2，0.4，0.2]，如項(xiàng)目的信息足夠，需采用專家判斷法確定.

表1 算例數(shù)據(jù)Tab.1 Data of the example

為檢驗(yàn)基于子集模擬的多資源均衡優(yōu)化算法的性能，每代隨機(jī)抽樣樣本數(shù)量取M=2 000，條件概率參數(shù)取p0=0.1，改進(jìn)Metropolis-Hasting 方法中一維均勻概率分布的寬度取d=0.3.圖7 描述了基于子集模擬的建議優(yōu)化算法一次典型求解過(guò)程中，最優(yōu)目標(biāo)函數(shù)值隨迭代階段的變化.由圖7 可知，算法經(jīng)過(guò)19 代迭代后收斂到最優(yōu)解，對(duì)應(yīng)最優(yōu)目標(biāo)函數(shù)值1.115 4.該最優(yōu)解對(duì)應(yīng)的各工序計(jì)劃開(kāi)工時(shí)間Si如表2 所示.為直觀對(duì)比優(yōu)化前后各工序的開(kāi)工時(shí)間，圖8 和圖9 繪制了優(yōu)化前后的雙代號(hào)時(shí)標(biāo)網(wǎng)絡(luò)圖，各工序在圖中的雙代號(hào)表示見(jiàn)表1 第2 列.

圖7 最優(yōu)目標(biāo)函數(shù)值隨迭代階段的變化Fig.7 Optimal objective function value at different stages

表2 典型最優(yōu)解對(duì)應(yīng)的工序計(jì)劃開(kāi)工時(shí)間Tab.2 Scheduling time for the activities corresponding to the optimal solution

圖8 優(yōu)化前算例的雙代號(hào)時(shí)標(biāo)網(wǎng)絡(luò)圖Fig.8 The activity-on-arc time scaled network before optimization

圖9 優(yōu)化后算例的雙代號(hào)時(shí)標(biāo)網(wǎng)絡(luò)圖Fig.9 The activity-on-arc time scaled network after optimization

為檢驗(yàn)基于子集模擬的建議優(yōu)化算法的穩(wěn)定性，表3 給出了建議優(yōu)化算法100 次獨(dú)立運(yùn)行求解后的統(tǒng)計(jì)結(jié)果.目前，針對(duì)資源均衡問(wèn)題的啟發(fā)式算法間的對(duì)比研究較少，學(xué)界對(duì)各種啟發(fā)式算法的優(yōu)劣未達(dá)成共識(shí).同時(shí)，遺傳算法因其自行概率搜索、運(yùn)算并行性、應(yīng)用不依賴問(wèn)題種類的強(qiáng)魯棒性等特點(diǎn)，在資源均衡問(wèn)題中應(yīng)用更為廣泛[16-18].因此，本文選擇遺傳算法進(jìn)行對(duì)比分析，與其他啟發(fā)式算法的對(duì)比分析，將在后續(xù)的研究中進(jìn)行.表3 提供了遺傳算法（Genetic Algorithm，GA）100 次獨(dú)立運(yùn)行求解后的統(tǒng)計(jì)結(jié)果.考慮到交叉概率參數(shù)pc和變異概率參數(shù)pm對(duì)GA 算法求解的影響，本文依據(jù)兩個(gè)參數(shù)的一般取值范圍，進(jìn)行了大量pc和pm組合取值下GA 算法的性能檢驗(yàn).檢驗(yàn)發(fā)現(xiàn)，交叉概率pc=0.2 和變異概率pm=0.015 下GA 算法求解本算例多資源均衡問(wèn)題的性能最優(yōu)，因此表3 給出的是這組交叉概率和變異概率下GA 算法的對(duì)比結(jié)果.同時(shí)，考慮到計(jì)算資源對(duì)兩種優(yōu)化算法的影響，兩種優(yōu)化算法中每代的樣本數(shù)均取2 000，迭代次數(shù)均取30 代.

表3 基于子集模擬的優(yōu)化算法與GA 算法獨(dú)立運(yùn)行100 次獲得的最優(yōu)目標(biāo)函數(shù)值的統(tǒng)計(jì)結(jié)果Tab.3 Statistical results of 100 independent runs using subset simulation-based proposed algorithm and GA

表3 提供了兩種算法100 次獨(dú)立運(yùn)行求解獲得的最優(yōu)解的目標(biāo)函數(shù)值的統(tǒng)計(jì)結(jié)果（最小值、平均值、最大值及標(biāo)準(zhǔn)差）.對(duì)比可知，基于子集模擬的優(yōu)化算法獲得最優(yōu)目標(biāo)函數(shù)值的平均值為1.113 2，小于基于GA 的優(yōu)化算法的相應(yīng)數(shù)值（1.159 7）.同時(shí)，基于子集模擬的優(yōu)化算法獲得最優(yōu)解的目標(biāo)函數(shù)值的最大值（最差情況下）為1.121 1，小于基于GA 的優(yōu)化算法獲得最優(yōu)解的目標(biāo)函數(shù)值的最小值（最好情況下）1.132 9，且最優(yōu)目標(biāo)函數(shù)值的標(biāo)準(zhǔn)差更小.此外，圖10 給出了兩種算法100 次獨(dú)立運(yùn)行獲得的最優(yōu)解的目標(biāo)函數(shù)值的分布情況.由圖10 可見(jiàn)，基于子集模擬的優(yōu)化算法性能更優(yōu)，其獲得的最優(yōu)目標(biāo)函數(shù)值更小，且分布更為集中，有93%的最優(yōu)目標(biāo)函數(shù)值集中在[1.109，1.119]區(qū)間，表明基于子集模擬的建議優(yōu)化算法獲取最優(yōu)解的穩(wěn)定性更高.

圖10 兩種優(yōu)化算法獨(dú)立運(yùn)行100 次獲得的最優(yōu)目標(biāo)函數(shù)值的分布Fig.10 Distribution of the optimal objective function value from 100 independent runs of using subset simulation-based proposed algorithm and GA

5 結(jié)論

本文針對(duì)建設(shè)工程項(xiàng)目的多資源均衡優(yōu)化問(wèn)題，基于子集模擬法進(jìn)行啟發(fā)式優(yōu)化算法的研究，主要研究結(jié)論如下：

1）在構(gòu)造建設(shè)工程項(xiàng)目多資源均衡優(yōu)化模型時(shí)，引入間隔率變量，并在間隔率變量和工序計(jì)劃開(kāi)始時(shí)間的映射中考慮工序間邏輯關(guān)系，以避免工序邏輯關(guān)系違反時(shí)復(fù)雜修復(fù)算子的使用.

2）針對(duì)間隔率變量表示的建設(shè)工程項(xiàng)目多資源均衡優(yōu)化模型，提出基于子集模擬的建議優(yōu)化算法，并給出算法框架和具體操作步驟.

3）通過(guò)算例驗(yàn)證，與應(yīng)用較廣的遺傳算法相比，基于子集模擬的建議優(yōu)化算法在最優(yōu)解的獲取穩(wěn)定性上有較大改進(jìn).