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

摘要：為高效、穩(wěn)定地求解建設(shè)工程項(xiàng)目管理過(guò)程中的多資源均衡問(wèn)題，提出一種基于子集模擬的優(yōu)化算法.多資源均衡問(wèn)題中，如直接采用工序計(jì)劃開(kāi)始時(shí)間作為決策變量，在優(yōu)化算法的實(shí)現(xiàn)時(shí)易違反工序間的邏輯關(guān)系.為避免該問(wèn)題，本文采用工序計(jì)劃開(kāi)始時(shí)間的間隔率變量表示（在二者的映射中考慮工序間的邏輯關(guān)系），并據(jù)此建立間隔率變量表示的建設(shè)工程項(xiàng)目多資源均衡優(yōu)化模型，以簡(jiǎn)化基于子集模擬的優(yōu)化算法的操作流程.通過(guò)算例驗(yàn)證，與目前應(yīng)用較廣的遺傳算法相比，本文提出的優(yōu)化算法在最優(yōu)解的獲取穩(wěn)定性上有較大改進(jìn).

關(guān)鍵詞：資源均衡問(wèn)題；子集模擬；馬爾科夫鏈蒙特卡羅；間隔率；遺傳算法

中圖分類(lèi)號(hào)：TU722文獻(xiàn)標(biāo)志碼：A

基金項(xiàng)目：中國(guó)博士后科學(xué)基金資助項(xiàng)目（2017M622575），China Postdoctoral Science Foundation（2017M622575）

Optimization Algorithm for Resource Leveling of Construction Projects with Multiple Resources Based on Subset Simulation

WANG Jia1，2，LIU Kexin1，ZHANG Xueqing3，CHEN Tao4

（1. College of Civil Engineering，Hunan University，Changsha 410082，China；2. National Center for International Research Collaboration in Building Safety and Environment，Hunan University，Changsha 410082，China；3. Department of Civil and Environmental Engineering，Hong Kong University of Science and Technology，Hong Kong 999077，China；4. Changsha Midea Real Estate Development Co Ltd，Changsha 410082，China）

Abstract：In this paper，an efficient optimization algorithm based on subset simulation is proposed for solving the resource leveling problem of construction projects with multiple resources. In the resource leveling problem，if the de-cision variables are chosen to be the scheduled starting time for the involved activities，the logical relationship be-tween the activities may be violated during the implementation of the optimization algorithm. In order to avoid this problem，the interval rate variables are introduced to substitute the scheduled starting time in modeling the resource leveling problem of construction projects with multiple resources so as to simplify the procedures of the proposed opti-mization algorithm based on subset simulation. As shown in the illustrative example，compared with the widely used genetic algorithm，the proposed optimization algorithm can obtain higher improvement in the stability of achieving the optimal solution.

Key words：resource levelling problem；subset simulation；Markov chain Monte Carlo simulation；interval rate；genetic algorithm

建設(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)題的研究工作可分為兩類(lèi)，一類(lèi)偏重于資源均衡問(wèn)題的模型構(gòu)建，一類(lèi)偏重于資源均衡問(wèn)題的優(yōu)化算法.資源均衡優(yōu)化模型一般可歸結(jié)為四類(lèi)：簡(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)資源的種類(lèi)和數(shù)量保持不變.

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

為檢驗(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列.

為檢驗(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)題種類(lèi)的強(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提供了兩種算法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)定性更高.

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).

參考文獻(xiàn)

[1]EASA S M. Resource leveling in construction by optimization[J]. Journal of Construction Engineering and Management，1989，115（2）：302—316.

[2]HEGAZY T. Optimization of resource allocation and leveling using genetic algorithms[J]. Journal of Construction Engineering and Management，1999，125（3）：167—175.

[3]NEUMANN K，ZIMMERMANN J. Procedures for resource leveling and net present value problems in project scheduling with general temporal and resource constraints[J]. European Journal of Opera-tional Research，2000，127（2）：425—443.

[4]CHAN W T，CHUA D K H，KANNAN G. Construction resource scheduling with genetic algorithms[J]. Journal of Construction En-gineering and Management，1996，122（2）：125—132.

[5]AKPAN E O P. Resource smoothing：a cost minimization approach[J]. Production Planning & Control，2000，11（8）：775—780.

[6]SENOUCI A B，ELDIN N N. Use of genetic algorithms in resource scheduling of construction projects[J]. Journal of Construction En-gineering and Management，2004，130（6）：869—877.

[7]EL-RAYES K，JUN D H. Optimizing resource leveling in construc-tion projects[J]. Journal of Construction Engineering and Manage-ment，2009，135（11）：1172—1180.

[8]CHRISTODOULOU S E，ELLINAS G，MICHAELIDOU -KAME-NOU A. Minimum moment method for resource leveling using en-tropy maximization[J]. Journal of Construction Engineering and Management，2010，136（5）：518—527.

[9]QIAO J F，LI Y. Resource leveling using normalized entropy and relative entropy[J]. Automation in Construction，2018，87：263—272.

[10]李洪波，熊勵(lì)，劉寅斌.項(xiàng)目資源均衡研究綜述[J].控制與決策，2015，30（5）：769—779. LI H B，XIONG L，LIU Y B. A literature survey of project resource leveling[J]. Control and Decision，2015，30（5）：769—779.（In Chinese）

[11]ALSAYEGH H，HARIGA M. Hybrid meta-heuristic methods for the multi-resource leveling problem with activity splitting[J]. Automa-tion in Construction，2012，27：89—98.

[12]ZHANG H X，YANG Z L. Accelerated particle swarm optimization to solve large-scale network plan optimization of resource-leveling with a fixed duration[J]. Mathematical Problems in Engineering，2018，2018：1—11.

[13]KOULINAS G K，ANAGNOSTOPOULOS K P. A new tabu searchbased hyper -heuristic algorithm for solving construction leveling problems with limited resource availabilities[J]. Automation in Construction，2013，31：169—175.

[14]LEU S S，YANG C H，HUANG J C. Resource leveling in construc-tion by genetic algorithm-based optimization and its decision sup-port system application[J]. Automation in Construction，2000，10（1）：27—41.

[15]PONZ-TIENDA J L，YEPES V，PELLICER E，et al. The Resource Leveling Problem with multiple resources using an adaptive genetic algorithm[J]. Automation in Construction，2013，29：161—172.

[16]歐陽(yáng)紅祥，陳偉偉，李欣.基于間隔率和遺傳算法的多資源均衡優(yōu)化研究[J].武漢理工大學(xué)學(xué)報(bào)（信息與管理工程版），2014，36（1）：82—85. OUYANG H X，CHEN W W，LI X. Leveling optimization of multipleresources based on interval rate and genetic algorithm[J]. Journal of Wuhan University of Technology（Information & Management Engi-neering），2014，36（1）：82—85.（In Chinese）

[17]LI H B，DEMEULEMEESTER E. A genetic algorithm for the robust resource leveling problem[J]. Journal of Scheduling，2016，19（1）：43—60.

[18]LI H B，XIONG L，LIU Y B，et al. An effective genetic algorithm for the resource levelling problem with generalised precedence relations[J]. International Journal of Production Research，2018，56（5）：2054—2075.

[19]何立華，王櫟綺，張連營(yíng).多資源均衡優(yōu)化中基于專(zhuān)家權(quán)重聚類(lèi)的權(quán)重優(yōu)選法[J].系統(tǒng)工程，2014，32（12）：124—132. HE L H，WANG L Q，ZHANG L Y.The weight optimal choice method based on experts’weights clustering analysis in multi-re-source leveling optimization[J].Systems Engineering，2014，32（12）：124—132.（In Chinese）

[20]AU S K，BECK J L. Estimation of small failure probabilities in high dimensions by subset simulation[J]. Probabilistic Engineering Me-chanics，2001，16（4）：263—277.

[21]LI H S，AU S K. Design optimization using Subset Simulation algo-rithm[J].Structural Safety，2010，32（6）：384—392.

[22]朱俊杰，余雄慶.基于子集模擬優(yōu)化的空天飛機(jī)再入軌跡混合優(yōu)化方法[J].航天控制，2015，33（6）：51—56. ZHU J J，YU X Q. A hybrid optimization method for reentry trajecto-ry of space plane based on subset simulation optimization[J]. Aerospace Control，2015，33（6）：51—56.（In Chinese）

[23]KOLISCH R，SPRECHER A. PSPLIB - A project scheduling prob-lem library[J].European Journal of Operational Research，1997，96（1）：205—216.