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

劉新博，劉曉偉，郭 誠(chéng)，張 巍

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

劉新博1，劉曉偉1，郭 誠(chéng)2，張 巍3

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

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

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

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

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

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

1 問(wèn)題介紹及建模

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

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

圖1 DAG實(shí)例

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

表1 相關(guān)符號(hào)

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

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

≤（5）

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

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

2.1 算法通用框架

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

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

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

2.2 求解RCMPS問(wèn)題的PSO算法

2.2.1 粒子編碼方式

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

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

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

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

2.2.2 運(yùn)算符重載

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

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

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

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

算法1 PSO中的加法操作

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

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

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

步驟2： for each 1≤≤

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

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

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

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

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

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

算法2 求解RCMPS問(wèn)題的PSO算法

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

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

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

步驟3：(≤500)

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

步驟5：++；

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

3 實(shí)例分析

3.1 實(shí)例描述

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

表2 實(shí)例參數(shù)

3.2 PSO運(yùn)算結(jié)果

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

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

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

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

4 結(jié)論

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

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

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

[2] 徐運(yùn)明, 鄧宗國(guó). 建筑施工組織設(shè)計(jì)[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é)任編校：劉亞兵