劉新博，劉曉偉，郭 誠，張 巍

建設(shè)項目多目標(biāo)調(diào)度優(yōu)化的粒子群算法

劉新博1，劉曉偉1，郭 誠2，張 巍3

（1.遼寧工業(yè)大學(xué) 管理學(xué)院，遼寧 錦州 121001; 2. 國網(wǎng)錦州供電公司，遼寧 錦州 121000; 3. 遼寧廣播電視大學(xué) 錦州分校，遼寧 錦州 121000）

考慮建設(shè)項目多目標(biāo)調(diào)度優(yōu)化問題，將最小化工期和資源均衡作為優(yōu)化目標(biāo)，通過有向無環(huán)圖表述一項具體工程項目，進而結(jié)合資源約束構(gòu)造問題的數(shù)學(xué)模型?；趩栴}的NP難解性，設(shè)計粒子群算法以優(yōu)化施工方案。通過定義粒子編碼方式、設(shè)計運算符重載策略、設(shè)置算法運行參數(shù)、設(shè)定初始化及停止準(zhǔn)則以完成算法整體流程設(shè)計。以某公司建設(shè)項目為實例，驗證表明，該算法能夠有效地解決文中所考慮的問題，可以為施工者在制定施工方案過程中提供有效的策略支持。

項目調(diào)度；最小化工期；資源均衡；粒子群算法

為了保證建設(shè)項目高質(zhì)量、低成本、短工期、重安全地完成，良好的施工組織設(shè)計尤為重要[1]。其中，進度控制作為施工組織設(shè)計中不可忽略的一個重要環(huán)節(jié)，影響到施工過程能否被合理地調(diào)度、所需資源能否被均衡地利用、施工團隊能否被合理地組織，等等，從而決定了能否優(yōu)質(zhì)、高效、低耗地達到施工目的，以滿足企業(yè)和社會的需求[2]。

隨著信息科技的發(fā)展，利用計算機技術(shù)對建設(shè)項目的施工方案進行分析設(shè)計，從而達到項目資源調(diào)度、施工組織優(yōu)化的目的，已成為工程管理領(lǐng)域的研究熱點之一[3]。一方面，研究人員將數(shù)學(xué)建模、算法設(shè)計等技術(shù)融入到項目調(diào)度的理論模型之上，豐富了理論層面的研究成果；另一方面，將這些理論結(jié)果應(yīng)用到實際工程之中，很好地指導(dǎo)了實際工程建設(shè)項目的施工過程。例如：Kellenbrink和Helber[4]考慮了資源受限且活動間含有先后序約束關(guān)系的項目調(diào)度問題，設(shè)計了一個遺傳算法對問題進行求解；Elbeltagi等[5]人研究了考慮施工工期、建設(shè)成本等多個目標(biāo)的施工進度優(yōu)化問題，為該問題設(shè)計了一個基于帕累托前沿折衷進化策略的粒子群優(yōu)化算法進行求解；Chakrabortty等[6]人考慮了具有已知確定性可再生資源、但活動持續(xù)時間具有隨機性的資源受限的項目調(diào)度問題，提出了一種基于魯棒優(yōu)化的方法；近期Kadri和Boctor[7]考慮了帶有傳輸時間的資源受限項目調(diào)度問題，他們研究了非搶占模式、且任務(wù)之間先后序關(guān)系是零滯后的情況，為其設(shè)計了一種使用兩點交叉算子的改進遺傳算法；Habibi等[8]人考慮了項目實施成本和項目費用之間的權(quán)衡與關(guān)聯(lián)，設(shè)計了兩個多目標(biāo)元啟發(fā)式算法（多目標(biāo)遺傳算法和多目標(biāo)粒子群算法）進行求解。最后，將所得方案應(yīng)用于伊朗鐵路建設(shè)項目之中，獲得了很好的施工效果。

本文針對建設(shè)項目常見的模型——帶資源約束的多目標(biāo)項目調(diào)度（resource constrained multi-objective project Scheduling，RCMPS）問題，設(shè)計了一個基于粒子群算法的施工優(yōu)化方案。論文主要結(jié)構(gòu)為：第二部分介紹了帶資源約束的多目標(biāo)項目調(diào)度問題，并通過數(shù)學(xué)模型對其進行形式化表述；第三部分為問題設(shè)計了一個多目標(biāo)粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）；第四部分以某公司建設(shè)項目的某項子工程為實例，證實PSO算法可以有效地求解RCMPS問題，為施工者提供合理決策；最后總結(jié)并指出未來的研究方向。

1 問題介紹及建模

實際工程中需要考慮的優(yōu)化目標(biāo)是多方面的，如工期最短、成本最低、資源均衡等等。然而，上述幾個目標(biāo)往往是相互矛盾的，也就是說，任何一種施工方案均無法同時使得這些目標(biāo)達到最優(yōu)，這就需要對各個目標(biāo)之間進行取舍，選擇較為合理的一種施工方案。

利用計算機技術(shù)優(yōu)化施工方案的過程中，一項具體工程往往可以通過一個有向無環(huán)圖（Directed acyclic graph，DAG）= (,)來表示。其中為圖的節(jié)點集合，表示該工程各道工序的開始或結(jié)束事件。為的邊集合，表示需要消耗一定施工時間的某個環(huán)節(jié)（即工序）；若有邊E∈（即VV），則說明工程中具有一道工序(,)（在不影響理解的前提下，用E表示這道工序），其開始事件為V，結(jié)束事件為V；同時，V和V也可能是其他工序的開始或結(jié)束事件，通過這種形式就能夠表示工序之間的先后序約束關(guān)系。一個DAG實例如圖1所示。

圖1 DAG實例

若用圖1中的DAG圖表示一個工程項目，則該項目包括1~9等9個事件，其中1號事件（1）代表工程的開始、9號事件（9）代表工程的結(jié)束；此外，該工程具有12、23、24等10道工序，以24為例，其前序工序為12、后繼工序為46和48。此外，為了形式化地表述文中考慮的問題，介紹其他符號如表1所示。

表1 相關(guān)符號

本文考慮的施工優(yōu)化目標(biāo)為兩個：最小化工期與資源使用均衡。其中前者很容易理解，因為施工甲乙雙方都希望在滿足施工質(zhì)量的前提下，項目的工期越短越好；而后者主要指的是施工過程中各種資源的使用應(yīng)該盡量保持均衡，避免出現(xiàn)過多資源緊張或閑置的情況，本文使用最小方差法作為資源均衡的度量標(biāo)準(zhǔn)。

基于上述分析，構(gòu)造本文所研究問題RCMPS的數(shù)學(xué)模型如下：

≤（5）

2 粒子群優(yōu)化算法

最簡單的平行機調(diào)度問題已經(jīng)是NP難問題，而本文所考慮的RCMPS問題是其更為復(fù)雜的情況，因此也無疑是NP難的。對于該問題，本文設(shè)計了一個粒子群算法（particle swarm optimization，PSO）對其進行求解。

2.1 算法通用框架

粒子群（PSO）算法模仿了自然界生物群體如鳥群、魚群的覓食過程，是一類由種族智慧啟發(fā)而來的基于種群的隨機搜索啟發(fā)式算法[9]，被廣泛地應(yīng)用在求解項目調(diào)度、路徑規(guī)劃等優(yōu)化問題。

在PSO算法的通用框架中，整體種群包含個粒子，每個粒子將表達所求解問題的一個候選解。粒子具有其位置x（表達一種可行方案）和速度v（表達其更新趨勢），算法的優(yōu)化過程就是利用了這些粒子之間的相互作用，即粒子所找到的“最優(yōu)位置”將會影響其他粒子的運動方向，使得種群中每個粒子均通過兩個因素持續(xù)調(diào)整自己的位置以靠近全局最優(yōu)（粒子自身訪問過的最佳位置pbest和整個種群訪問過的最佳位置）。對于粒子而言，其速度和位置的更新方式為：

其中，各個參數(shù)的上標(biāo)表示算法迭代的輪次；為權(quán)重系數(shù)，反映了上一代速度對本輪更新的影響；1和2為學(xué)習(xí)因子，反應(yīng)局部最優(yōu)解和全局最優(yōu)解對本輪更新的影響；1和2為保證搜索隨機性的隨機變量。使用PSO算法求解某一具體優(yōu)化問題（如本文的RCMPS問題）時，需要定義粒子位置x和速度v的編碼方式，重載式（8）、（9）中的減法、乘法、加法等運算操作，以及定義算法的停止準(zhǔn)則，在完成若干輪迭代之后，算法輸出運算過程中找到的最好解。

2.2 求解RCMPS問題的PSO算法

2.2.1 粒子編碼方式

在PSO中，粒子的位置信息表示所求解問題的可行解，就本文所研究的RCMPS問題而言，粒子的位置x是其一個可行的施工方案。本文用一個||×矩陣作為粒子位置信息的編碼方案，其中||是圖中邊的數(shù)量（即工程中工序的數(shù)量），為施工甲方所規(guī)定的最長工期；矩陣中的元素為0或1，表示當(dāng)前工序在第天是否有施工行為。采用這種編碼方式的優(yōu)勢在于，其可以快速直接地轉(zhuǎn)換成項目施工所對應(yīng)的甘特圖，圖1中DAG所對應(yīng)的一個有效位置編碼（即施工方案）如圖2所示。

12...d12d12+1............D E121111000000 E230000110000 ... E890000000110

在本文考慮的問題中，工序E的施工時間為輸入常數(shù)d，因此，在E所對應(yīng)行向量中，取值為1的元素共有d個。此外，根據(jù)工序之前的先后續(xù)關(guān)系，E所對應(yīng)的行向量中第一個取值為1的元素，不得早于E所對應(yīng)的行向量中最后一個取值為1的元素（1≤,,≤）。

粒子的速度v用于與其位置x做加法運算，以便在PSO迭代的過程中更新位置的編碼。本文中，粒子的速度采用與位置相同的編碼形式，即通過一個||×矩陣為粒子速度進行編碼；矩陣內(nèi)元素的取值范圍也在{0, 1}選擇，具體計算方法將在2.2.2中介紹。

2.2.2 運算符重載

公式（8）和（9）中的減法、乘法、加法運算是保證粒子位置更新的基本操作，針對問題特性，需要對這些運算符進行重載。重載方案既要保證編碼的可用性、又要保證更新的有效性，也就是說，粒子的更新應(yīng)該向其局部最優(yōu)和全局最優(yōu)方向靠攏，且新生成的編碼依然是一種有效的調(diào)度方式。

（1）減法運算。用于計算當(dāng)前位置距離局部最優(yōu)或全局最優(yōu)的“差距”，根據(jù)這些差距來計算/調(diào)整粒子下一步的運動方向。由公式（8）可知，參與減法計算的被減數(shù)（用表示）和減數(shù)（用表示）均為粒子的某一位置編碼（即一個||×矩陣），定義它們的差（用表示）依然為一個||×矩陣，其(,)位置上的元素為、對應(yīng)位置元素之差的絕對值，即：若=-，則c= |a-b|, 其中,a∈,b∈,c∈且1≤≤||, 1≤≤。

（2）乘法運算。作用于隨機變量（1和2）與減法所得的差值之間，表示對減法操作結(jié)果的一次隨機重定位。本文PSO中1和2的結(jié)構(gòu)與粒子位置編碼方式相同，即元素為0或1的隨機||×矩陣。因此對于乘法運算=×，其結(jié)果為:

其中，1≤≤||，1≤≤。

算法1 PSO中的加法操作

輸入： 加數(shù)、（均為||×矩陣）

輸出：、之和（依然為||×矩陣）

步驟1：對于矩陣中的每一行向量C（1≤≤||），記其所對應(yīng)的施工工序為E，做步驟2~5：

步驟2： for each 1≤≤

步驟3：c=a+b；\對應(yīng)位置加和

步驟5：依據(jù)概率p，從C中選擇d個元素將其值置為1；其余元素置為0；

步驟6：重復(fù)步驟2~5直至遍歷中的所有行向量；

步驟7：若出現(xiàn)工序之間違背先后序約束的情況，則后繼工序向后順延。

2.2.3 參數(shù)設(shè)置及算法流程

本文PSO算法構(gòu)造種群大小為30，即種群中共有30個粒子進行迭代，采用隨機形式生成初始編碼；定義算法停止準(zhǔn)則為迭代500次，即當(dāng)?shù)喆未笥?00時，算法停止；設(shè)置權(quán)重系數(shù)、學(xué)習(xí)因子1、2均為1，隨機變量1和2為隨機生成的{0, 1}矩陣（大小為||×）。由于文中考慮的RCMPS問題為雙目標(biāo)問題，因此50%的粒子以最小化工期為主目標(biāo)、以資源均衡為次目標(biāo)，另外50%的粒子恰好相反。綜上，本文PSO算法的整體流程如算法2所示。

算法2 求解RCMPS問題的PSO算法

輸入： 圖= (,)（描述某一工程的DAG圖）；輸出：遍歷過程中找到的最優(yōu)施工方案（可能不止1個）。

步驟1：生成30個粒子，按照2.2.1中的編碼方式隨機初始化；

步驟2：設(shè)置迭代輪次變量= 1；

步驟3：(≤500)

步驟4：根據(jù)式（8）、（9）和2.2.2中的運算符重載規(guī)則對種群進行更新；

步驟5：++；

步驟6：輸出遍歷過程中找到的最優(yōu)施工方案（可能不止1個）。

3 實例分析

3.1 實例描述

本節(jié)通過具體實例驗證所設(shè)計的PSO算法的有效性，說明其可以在施工前期輔助管理者制定合理的施工方案。事實上，圖1中的DAG來自于某公司正在實施的建設(shè)項目中的某項子工程，表示了廠房施工過程中的土建工程施工、鋼結(jié)構(gòu)主體工程施工、傳動系統(tǒng)施工、機電安裝工程施工、覆蓋系統(tǒng)施工、整體測試等各項工序；工程所需資源包括人力資源以及砼振搗器、攪拌機等施工設(shè)備。項目抽象化后的參數(shù)如表2所示。

表2 實例參數(shù)

3.2 PSO運算結(jié)果

在未使用PSO的情況下，通過傳統(tǒng)的網(wǎng)絡(luò)工程計劃方法（如雙代號網(wǎng)絡(luò)圖），可得實例的施工甘特圖如圖3所示。然而，圖3中的施工方案未考慮資源約束，也沒有考慮資源均衡這一優(yōu)化目標(biāo)，所以并不符合實際的項目需求（不可行方案）。

圖3 未考慮資源約束和資源均衡的施工方案

而PSO算法給出的施工方案如圖4所示?？梢园l(fā)現(xiàn)，由于資源約束的存在，圖4方案比圖3方案的工期要多5天（34天），但是圖4方案是可行的，且在此基礎(chǔ)追求工期最小化。另外，計算可得圖4方案所對應(yīng)的資源均衡度為=4.0447。事實上，可以通過延長工期以縮小資源均衡度（意味著人力、設(shè)備、保障等資源分配的更加均勻），PSO算法會生成多組可行方案，供施工管理者選擇。最后，PSO算法的運行時間在5 s左右，完全符合計算需要。

圖4 PSO算法給出的施工方案

4 結(jié)論

本文考慮了帶資源約束的建設(shè)項目施工調(diào)度中的多目標(biāo)優(yōu)化（RCMPS）問題，將最小化工期和資源均衡作為施工的優(yōu)化目標(biāo)。首先構(gòu)建了能夠描述問題的數(shù)學(xué)模型，進而設(shè)計了一個粒子群（PSO）算法對其進行求解。粒子的位置和速度信息均采用矩陣形式表現(xiàn)，可以方便進行編、解碼操作；根據(jù)問題特性重載了通用框架中的減法、乘法、加法運算，從而保證算法迭代的有效性。運算實例表明，PSO算法可以作為求解RCMPS問題的有效方法。

未來工作可以從3個方面開展：（1）雖然本文算法可以有效求解RCMPS問題，但由于其編碼往往形成稀疏矩陣，可能造成計算空間的浪費；因此，更適合的編碼方式可以作為未來研究內(nèi)容之一。（2）PSO算法運算過程中可能陷入局部最優(yōu)，因此，可以設(shè)置一定機制擴展其在搜索空間的尋優(yōu)范圍。（3）對于小規(guī)模問題實例，可以嘗試為其設(shè)計精確算法，在可接受的時間范圍內(nèi)求其精確解。

[1] 曹吉鳴. 工程施工管理學(xué)[M]. 北京: 中國建筑工業(yè)出版社, 2015.

[2] 徐運明, 鄧宗國. 建筑施工組織設(shè)計[M]. 北京: 北京大學(xué)出版社, 2019.

[3] Pellerin R, Perrier N, Berthaut F. A survey of hybrid metaheuristics for the resource-constrained project scheduling problem[J]. European Journal of Operational Research, 2020, 280(2): 395-416.

[4] Kellenbrink C, Helber S. Scheduling resource-constrained projects with a flexible project structure[J]. European Journal of Operational Research, 2015, 246(2): 379-391.

[5] Elbeltagi E, Ammar M, Sanad H, et al. Overall multiobjective optimization of construction projects scheduling using particle swarm[J]. Engineering, Construction and Architectural Management, 2016, 23(3): 265-282.

[6] Chakrabortty R K, Sarker R A, Essam D L. Resource constrained project scheduling with uncertain activity durations[J]. Computers & Industrial Engineering, 2017, 112: 537-550.

[7] Kadri R L, Boctor F F. An efficient genetic algorithm to solve the resource-constrained project scheduling problem with transfer times: The single mode case[J]. European Journal of Operational Research, 2018, 265(2): 454-462.

[8] Habibi F, Barzinpour F, Sadjadi S J. A mathematical model for project scheduling and material ordering problem with sustainability considerations: A case study in Iran[J]. Computers & Industrial Engineering, 2019, 128: 690-710.

[9] Kennedy J, Eberhart R. Particle swarm optimization[C]. Proceedings of IEEE International Conference on Neural Networks,1995,4: 1942-1948.

Particle Swarm Optimization for Construction Project Scheduling with Multi Criteria

LIU Xin-bo1, LIU Xiao-wei1, GUO Cheng2, ZHANG Wei3

（1. School of Management, Liaoning University of Technology, Jinzhou 121001, China;2. State Grid Jinzhou Electronic Power Supply Company, Jinzhou 121000, China;3. Jinzhou Branch of Liaoning Radio and TV University, Jinzhou 121000, China）

Considering a multi-objective scheduling problem for construction projects with the goals of minimizing the makespan and balancing the project resources, a specific construction project is presented by a directed acyclic graph, and then the mathematical model is constructed considering the resource constraints. Since the NP problem is hard to solve, a particle swarm optimization approach is proposed to form a construction plan. By particle encoding, operators overloading, parameters tuning, as well as initialization and termination criteria setting, the completed design of the algorithm is given. Finally, an actual construction project is taken as the example, and the experiments show that the method can solve the considered problem effectively, which can provide some reasonable strategies for the managers in a construction project.

project scheduling; minimizing makespan; resource balance; particle swarm optimization

F224

A

1674-3261(2021)01-0063-05

2020-02-20

劉新博(1982-)，女，遼寧錦州人，碩士生。

劉曉偉(1964-)，男，遼寧錦州人，教授，碩士。

責(zé)任編校：劉亞兵