張國富

(滁州職業(yè)技術(shù)學(xué)院 土木工程系，安徽 滁州 239000)

建筑工程計(jì)劃管理涉及多個(gè)緊密相關(guān)的任務(wù)，人員和設(shè)備資源分配的決策會(huì)影響項(xiàng)目成本和完成時(shí)間[1-2]。諸如關(guān)鍵路徑方法(Critical Path Method，CPM)和程序評(píng)估與審查技術(shù)(Program Evaluation and Review Technique，PERT)之類的傳統(tǒng)項(xiàng)目計(jì)劃方法假定資源的無限可用性。然而在許多建筑環(huán)境中，無限制地使用各種資源的假設(shè)可能不成立，因?yàn)橹挥泄潭〝?shù)量的資源可用，或者獲取額外資源的成本非常高[3]。同時(shí)，資源的可用性也可能影響活動(dòng)持續(xù)時(shí)間，影響決策者對(duì)于執(zhí)行模式的選擇。因此，本文在資源有限的情況下，通過設(shè)計(jì)一種基于遺傳算法的計(jì)劃管理優(yōu)化模型來平衡工期和成本之間的矛盾。

1 問題建模

建筑工程項(xiàng)目由一系列活動(dòng)j組成，用G(V,E)表示活動(dòng)和活動(dòng)之間的關(guān)系。其中，節(jié)點(diǎn)集合V表示活動(dòng)的集合，弧集合E表示優(yōu)先關(guān)系。在項(xiàng)目網(wǎng)絡(luò)G(V,E)中，活動(dòng)從0開始編號(hào)，第J+1號(hào)位置。其中活動(dòng)0和J+1是“虛擬”活動(dòng)，用來表示項(xiàng)目的開始和結(jié)束?；顒?dòng)之間的優(yōu)先關(guān)系能夠約束活動(dòng)的開始，例如活動(dòng)j需要在所有先前的活動(dòng)Pj完成后才開始[4]。用Mj表示活動(dòng)j的執(zhí)行模式，當(dāng)活動(dòng)的執(zhí)行模式確定后就不能更改了。假設(shè)共有K種可再生資源類型，用Rk表示資源類型k的可用量。在模式m中執(zhí)行活動(dòng)j需要花費(fèi)時(shí)間為djm，需要的資源類型集合為Rjm和對(duì)資源k的需求表示為rjmk。

本研究的目的是確定一組非支配計(jì)劃，以減少項(xiàng)目時(shí)間和成本為目標(biāo)，同時(shí)滿足優(yōu)先級(jí)和資源約束。第一個(gè)目標(biāo)是最小化項(xiàng)目的總工時(shí)Ft。在為每個(gè)活動(dòng)選擇執(zhí)行模式后，確定相應(yīng)的活動(dòng)持續(xù)時(shí)間、直接費(fèi)用和資源需求。然后將活動(dòng)模式信息輸入到多模型的第二階段。搜索引擎將遺傳算法與進(jìn)度表生成方案集成在一起，以搜索最佳的序列，從而根據(jù)給定的約束為所有活動(dòng)生成可行的進(jìn)度表。

第二個(gè)目標(biāo)是將總項(xiàng)目成本FC降至最低。項(xiàng)目成本分為直接成本和間接成本，其計(jì)算方式為FC=∑j∑mxjmcjm+fjci。直接成本(即∑j∑mxjmcjm)與項(xiàng)目活動(dòng)的執(zhí)行直接相關(guān)，并與項(xiàng)目資源的可用性密切相關(guān)。其中，cjm是活動(dòng)j以模式m執(zhí)行的直接成本，xjm是決策變量。間接成本(即fjci)與項(xiàng)目活動(dòng)的執(zhí)行無關(guān)。在這項(xiàng)研究中，假設(shè)每個(gè)時(shí)期的間接費(fèi)用是固定的(即ci為常量)，而一個(gè)項(xiàng)目的總間接費(fèi)用取決于項(xiàng)目工期fj。項(xiàng)目的總直接成本是活動(dòng)執(zhí)行成本的總和，直接費(fèi)用總額取決于所選的執(zhí)行模式。

2 基于遺傳算法的優(yōu)化模型

2.1 算法概述

本優(yōu)化模型采用一種基于種群的算法，通過進(jìn)行直接搜索解決全局優(yōu)化問題[5]。該算法簡要描述如下：

令S?R為問題的搜索空間，向量Xi,G為種群。初始種群是隨機(jī)生成的，并且覆蓋整個(gè)參數(shù)空間。在每一代中，算法應(yīng)用兩個(gè)算子(突變和交叉重組)為每個(gè)目標(biāo)向量Xi,G產(chǎn)生一個(gè)試驗(yàn)向量Ui,G+1。然后，選擇階段確定試驗(yàn)向量是否進(jìn)入下一代。使用以下公式為每個(gè)目標(biāo)向量Xi,G確定一個(gè)突變向量Vi,G+1：

Vi,G+1=Xr1,G+F(Xr2,G-Xr3,G

(1)

其中，r1、r2和r3是從種群中隨機(jī)選擇的個(gè)體，F(xiàn)是比例因數(shù)，取值范圍是0到1。

在突變階段之后，采用交叉算子來增加種群的多樣性。對(duì)于每一個(gè)突變向量Vi,G+1，其對(duì)應(yīng)的試驗(yàn)向量Ui,G+1中的元素按照以下規(guī)則生成：

(2)

其中，CR是自定義的交叉常數(shù)，其取值范圍是0到1。jrand是從種群中隨機(jī)選擇的個(gè)體索引。

為了確定是否將試驗(yàn)向量Ui,G+1加入到下一代種群中，使用貪婪算法將該向量與其對(duì)應(yīng)的目標(biāo)向量Xi,G進(jìn)行比較。選擇算子表示如下：

(3)

算法的進(jìn)化循環(huán)將反復(fù)進(jìn)行，直到滿足停止條件為止。

2.2 基于混沌技術(shù)的初始化

本研究同時(shí)優(yōu)化了項(xiàng)目成本和項(xiàng)目工期。在優(yōu)化之前，該模型需要項(xiàng)目信息輸入，包括活動(dòng)關(guān)系、每天的可用性資源、活動(dòng)持續(xù)時(shí)間、成本、資源類型以及每個(gè)活動(dòng)的執(zhí)行模式。另外，還需要對(duì)以下的參數(shù)進(jìn)行設(shè)置：種群大小NP、決策變量的數(shù)量D、目標(biāo)函數(shù)的數(shù)量K、突變常數(shù)F和交叉概率常數(shù)CR。

種群初始化是進(jìn)化算法中重要的一個(gè)步驟，結(jié)合均勻隨機(jī)分布和混沌技術(shù)生成初始種群。

(4)

在使用混沌生成個(gè)體之后，選擇NP個(gè)最佳的解決方案，并將其輸入到模型的主循環(huán)中?？梢詫栴}的候選解決方案表示為具有D個(gè)元素的向量，即xi=[Xi,1,…,Xi,D]。向量Xi,j表示活動(dòng)j的一種執(zhí)行模式，索引i表示種群中的第i個(gè)個(gè)體。執(zhí)行模式Xi,j的取值范圍是[1,Mj]。使用一個(gè)函數(shù)將那些活動(dòng)的執(zhí)行模式選項(xiàng)從實(shí)際值轉(zhuǎn)換為可行域內(nèi)的整數(shù)值，即

Xi,j=ceil(rand[0,1]×UB(j))

(5)

其中，rand[0,1]是0到1之間的隨機(jī)數(shù)，UB(j)是活動(dòng)j的執(zhí)行模式的數(shù)量。ceil是向上取整的函數(shù)。

采用快速的非支配排序技術(shù)將種群分類為非支配集合(F1,F2,…)。選擇屬于最佳非支配集合(集合F1)的解，并將其輸入到種群中。如果F1小于NP，則按照排序?qū)⑵渌侵浣?F2,F3,…)加入到種群。假設(shè)Fk是最后一個(gè)加入的非支配的集合。通常，集合F1,…,Fk中解的數(shù)量會(huì)大于NP。因此使用熵排序技術(shù)選擇最佳NP個(gè)種群成員。

2.3 突變和交叉操作

初始化后，算法對(duì)種群進(jìn)行突變操作。突變向量Vi,G+1的生成公式如下所示：

Vi,G+1=Xr1,G+F(Xr2,G-Xr3,G)

(6)

為了提升算法的收斂速度，選擇適應(yīng)度最高的向量作為突變操作的基向量。

針對(duì)算法的三個(gè)階段設(shè)計(jì)了三種選擇機(jī)制：

(1)g≤ms×Gmax：采用隨機(jī)選擇機(jī)制，在種群中隨機(jī)選擇Xr1、Xr2和Xr3。在進(jìn)化過程的開始，所有用于突變的個(gè)體都是隨機(jī)選擇的，隨機(jī)選擇可以確保種群的多樣性。

(2)ms×Gmax

(3)g>2×ms×Gmax：在優(yōu)化過程的最后階段，算法必須加速收斂。用于突變的所有向量Xr1、Xr2和Xr3均是適應(yīng)度值較高的個(gè)體。

其中：ms是突變選擇系數(shù)，Gmax是最大迭代次數(shù)。

交叉操作交換目標(biāo)向量和突變向量的元素，使種群多樣化。把交叉操作得到的向量稱為后代向量，如下所示：

(7)

2.4 資源受限子系統(tǒng)

后代向量首先定義每個(gè)活動(dòng)的執(zhí)行模式，然后確定相應(yīng)的成本、持續(xù)時(shí)間和資源需求。將執(zhí)行模式信息輸入到資源受限的子系統(tǒng)中，該子系統(tǒng)將基于給定的約束條件生成可行的時(shí)間表。在資源受限的子系統(tǒng)運(yùn)行之前，隨機(jī)均勻分布生成器會(huì)創(chuàng)建包含M個(gè)個(gè)體的初始種群。資源受限問題的解決方案是一個(gè)具有D個(gè)元素的向量，即Xs=[Xs1,…,XsD]。其中D是當(dāng)前問題中決策變量的數(shù)量，同時(shí)也是項(xiàng)目網(wǎng)絡(luò)中的活動(dòng)數(shù)量。

將基于優(yōu)先級(jí)的調(diào)度與串行轉(zhuǎn)換方案相結(jié)合，針對(duì)資源受限的項(xiàng)目調(diào)度問題，設(shè)計(jì)遺傳算法中個(gè)體的編碼表示方式。作為D維空間中的一個(gè)點(diǎn)，DE個(gè)體中的第D個(gè)元素可以表示項(xiàng)目中的D活動(dòng)。向量Xs(t)中的D個(gè)參數(shù){xs1(t),…,xsD(t)}表示D個(gè)活動(dòng)的D維優(yōu)先值。對(duì)向量中的元素按照其優(yōu)先值排序，得到新的向量。

串行方法包含n個(gè)階段，每個(gè)階段中選擇一項(xiàng)活動(dòng)進(jìn)行調(diào)度。當(dāng)一項(xiàng)活動(dòng)的當(dāng)前可用資源量足夠時(shí)，該活動(dòng)將會(huì)在最早的優(yōu)先時(shí)間被調(diào)度。所設(shè)計(jì)的串行方法如下所示：

步驟1：根據(jù)優(yōu)先級(jí)約束將個(gè)體優(yōu)先級(jí)轉(zhuǎn)移到活動(dòng)計(jì)劃中。假設(shè)項(xiàng)目活動(dòng)集合為j={1,2,…,n}。用集合C={(i,j)}表示集合J={1,2,…,n}中活動(dòng)的優(yōu)先級(jí)關(guān)系，其中(i,j)表示活動(dòng)i必須在活動(dòng)j之前執(zhí)行。引入二元關(guān)系矩陣V=(vij,1≤i,j≤n)：當(dāng)(imj)∈C時(shí)，vij=1；否則vij=0。同時(shí)引入優(yōu)先級(jí)關(guān)系矩陣G=(gij,1≤i,j≤n)來描述所有優(yōu)先級(jí)關(guān)系鏈：當(dāng)(k,k1),(k1,k2),…,(kj-1,kj)都屬于集合C，那么有g(shù)kj=1。因此，可以根據(jù)集合C來構(gòu)建矩陣G。

步驟2：根據(jù)活動(dòng)時(shí)間表計(jì)算項(xiàng)目工期。在應(yīng)用串行方法之前，必須考慮兩個(gè)重要點(diǎn)：首先，活動(dòng)A在所有前繼活動(dòng)完成后開始；其次，活動(dòng)開始時(shí)間取決于資源的可用性。因此，當(dāng)活動(dòng)A的前繼活動(dòng)完成后且有足夠的資源時(shí)，活動(dòng)A立刻會(huì)被執(zhí)行。

2.5 精英庫更新

項(xiàng)目總工期和每個(gè)執(zhí)行模式的成本會(huì)被輸入到子系統(tǒng)以進(jìn)行評(píng)估。多目標(biāo)優(yōu)化的一個(gè)重要步驟是選擇機(jī)制，采用基于帕累托支配的選擇機(jī)制。該選擇機(jī)制首先評(píng)估后代向量Ui,G，然后將該向量與目標(biāo)向量Xi,G進(jìn)行行比較：當(dāng)Xi,G支配Ui,G，則將Ui,G丟棄；當(dāng)Ui,G支配Xi,G且Xi,G=Ui,G，更新外部精英庫；對(duì)于其他情況，采用熵排序選擇個(gè)體。

在選擇操作過程中選擇的向量稱為選擇向量。如果所有精英庫個(gè)體都支配選擇向量，則不將選擇向量加入到精英庫中。如果選擇向量支配一個(gè)或多個(gè)精英庫成員，則刪除該精英庫成員，并將選擇向量加入到精英庫。

當(dāng)算法滿足停止條件時(shí)，優(yōu)化過程終止。一個(gè)停止條件是最大迭代次數(shù)Gmax，即算法迭代次數(shù)達(dá)到Gmax，算法就停止。另一個(gè)停止條件是最大評(píng)估次數(shù)，即適應(yīng)度函數(shù)的計(jì)算次數(shù)。在優(yōu)化過程終止后，就會(huì)輸出一組最佳的解決方案。

3 實(shí)驗(yàn)評(píng)估

采用案例來評(píng)估本方法的有效性，并將本方法獲得的結(jié)果與通過多目標(biāo)差分進(jìn)化算法(MODE)和非支配排序遺傳算法(NSGA-II)的結(jié)果進(jìn)行比較。實(shí)驗(yàn)采用MATLAB R2020a仿真平臺(tái)，實(shí)驗(yàn)在工作站上進(jìn)行，該工作站的配置為：CPU采用Intel 酷睿i7-10700 5.3 GHz，內(nèi)存的大小為16 G，硬盤容量為256 G SSD + 1 T 機(jī)械硬盤。實(shí)驗(yàn)采用了一個(gè)倉庫建筑工程的案例數(shù)據(jù)來驗(yàn)證本文算法。該案例一共有37個(gè)活動(dòng)，各個(gè)活動(dòng)之間的優(yōu)先級(jí)關(guān)系如圖1所示。案例數(shù)據(jù)中，每項(xiàng)活動(dòng)的屬性包括了活動(dòng)序號(hào)、活動(dòng)的具體描述、工期、前繼活動(dòng)以及成本，部分活動(dòng)的時(shí)間成本如表1所示。

圖1 活動(dòng)優(yōu)先級(jí)圖

表1 部分活動(dòng)的信息

分別將本文算法、MODE算法和NSGA-II算法運(yùn)行20次，并取平均值。分別從三種算法所獲得的帕累托前沿中選取較好的結(jié)果，并將結(jié)果呈現(xiàn)在表2中。

表2 三種算法結(jié)果對(duì)比

由表2可知，解決方案1的工程總成本是最高的，但其工期是最短的；而解決方案3的工期較長，成本卻是最低的。對(duì)比三種算法的結(jié)果可知，相同工期的情況下，本算法能夠獲得最低的成本；而當(dāng)成本相近時(shí)，本算法的工期是最短的。由此可知，本算法能獲得最佳的綜合性能。

4 結(jié)論

本研究提出了一種基于遺傳算法的優(yōu)化模型，以解決資源受限的建筑工程計(jì)劃管理問題，實(shí)現(xiàn)了工期和成本的均衡。該模型生成的帕累托最優(yōu)解有助于決策者在項(xiàng)目時(shí)間和成本限制下做出最佳工程計(jì)劃。實(shí)驗(yàn)結(jié)果表明，本模型可以有效地解決計(jì)劃管理問題，并可以找到多目標(biāo)帕累托最優(yōu)解。擬議的模型使決策者能夠根據(jù)時(shí)間和成本偏好作出及時(shí)、知情的決定。未來的工作集中在將本模型應(yīng)用于更多的實(shí)際案例中，以進(jìn)一步評(píng)估本模型的性能。