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

王家 劉可心 張學清 陳濤

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

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

中圖分類號：TU722文獻標志碼：A

基金項目：中國博士后科學基金資助項目（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

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

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

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

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

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

1）組成建設項目的各個工序必須連續(xù)施工，不能間斷，且各工序間的邏輯關系不隨時間改變.

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

3）建設項目的總工期保持不變.

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

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

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

5結論

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

1）在構造建設工程項目多資源均衡優(yōu)化模型時，引入間隔率變量，并在間隔率變量和工序計劃開始時間的映射中考慮工序間邏輯關系，以避免工序邏輯關系違反時復雜修復算子的使用.

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

3）通過算例驗證，與應用較廣的遺傳算法相比，基于子集模擬的建議優(yōu)化算法在最優(yōu)解的獲取穩(wě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]李洪波，熊勵，劉寅斌.項目資源均衡研究綜述[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ōu)化研究[J].武漢理工大學學報（信息與管理工程版），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ōu)化中基于專家權重聚類的權重優(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)化的空天飛機再入軌跡混合優(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.