基于粒子群的多目標(biāo)多執(zhí)行模式項(xiàng)目調(diào)度

周 蓉， 葉春明

（上海理工大學(xué) 管理學(xué)院，上海 200093）

在工程項(xiàng)目調(diào)度中保持工期、成本、質(zhì)量以及資源的均衡控制是構(gòu)成項(xiàng)目建設(shè)總目標(biāo)的關(guān)鍵因素，關(guān)系到整個(gè)工程的成敗.為了實(shí)現(xiàn)工程項(xiàng)目的總效益，需要對(duì)工程項(xiàng)目所要求的質(zhì)量、所規(guī)定的工期、所批準(zhǔn)的費(fèi)用等各個(gè)目標(biāo)進(jìn)行全方位的協(xié)調(diào)，因此建立一套科學(xué)有用的多目標(biāo)多模式項(xiàng)目調(diào)度綜合優(yōu)化模型十分有必要.

目前，解決工程項(xiàng)目?jī)?yōu)化問(wèn)題的基本方法主要是網(wǎng)絡(luò)計(jì)劃技術(shù)，其在解決工程費(fèi)用、工期、資源等單目標(biāo)優(yōu)化方面帶來(lái)了極大方便.然而，現(xiàn)代的工程項(xiàng)目?jī)H僅考慮單目標(biāo)的優(yōu)化是遠(yuǎn)遠(yuǎn)不行的.因此，許多專(zhuān)家希望引入最優(yōu)化技術(shù)來(lái)研究工程項(xiàng)目多目標(biāo)優(yōu)化問(wèn)題.如王首續(xù)［1］、駱剛等［2］將遺傳算法引入工程項(xiàng)目?jī)?yōu)化問(wèn)題，通過(guò)選擇、變異、雜交等操作，實(shí)現(xiàn)工程項(xiàng)目多目標(biāo)優(yōu)化.劉永淞［3］則采用動(dòng)態(tài)規(guī)劃法（DP）研究工程項(xiàng)目?jī)?yōu)化問(wèn)題.楊湘等［4］則應(yīng)用模糊數(shù)學(xué)和遺傳算法來(lái)解決工程項(xiàng)目資源均衡優(yōu)化問(wèn)題.

粒子群算法（particle swarm optimization，PSO）是一種智能演化計(jì)算技術(shù)［5］，系統(tǒng)初始化為一組隨機(jī)解，通過(guò)迭代搜索最優(yōu)值.與其它算法比較，PSO的優(yōu)勢(shì)在于算法簡(jiǎn)單和容易實(shí)現(xiàn)，同時(shí)又有深刻的智能背景，既適合科學(xué)研究，又特別適合工程應(yīng)用.因此，PSO一經(jīng)提出，立刻引起演化計(jì)算領(lǐng)域?qū)W者們的廣泛關(guān)注，并在短短的幾年時(shí)間里出現(xiàn)大量的研究成果，形成了一個(gè)研究熱點(diǎn)［6］.

因此，本文主要以工程項(xiàng)目多目標(biāo)多執(zhí)行模式優(yōu)化模型為研究對(duì)象，對(duì)項(xiàng)目調(diào)度所涉及的重要目標(biāo)建立綜合優(yōu)化模型，并將粒子群算法引入工程項(xiàng)目?jī)?yōu)化領(lǐng)域，最終實(shí)現(xiàn)工程項(xiàng)目的工期、成本、質(zhì)量以及資源的均衡性達(dá)到合理的配置.

1 項(xiàng)目?jī)?yōu)化模型建立

1.1 模型假設(shè)

根據(jù)實(shí)際情況，對(duì)工程項(xiàng)目中工期、成本、質(zhì)量以及資源等給予如下假設(shè)［7］：

a.合理工期是工程項(xiàng)目在正常的條件情況下，使項(xiàng)目的投資方和各參建單位均獲得滿(mǎn)意的經(jīng)濟(jì)效益的工期.

b.工程總成本是工程的直接成本與間接成本之和.

c.工程總質(zhì)量由各個(gè)單項(xiàng)任務(wù)的質(zhì)量加權(quán)平均得到.

d.本文的工期指工程項(xiàng)目的合理工期.

e.本文直接成本主要指各類(lèi)資源使用成本；間接成本主要指運(yùn)輸成本.

f.工程質(zhì)量與具體活動(dòng)的施工組織方式有關(guān)，施工組織方式不同，單項(xiàng)工程的質(zhì)量不同.

本文問(wèn)題具體可描述如下：一個(gè)工程中包含J項(xiàng)任務(wù)，規(guī)定任務(wù)j在其全部緊前任務(wù)i（i∈Pj，Pj為任務(wù)j的緊前任務(wù)集）完成之前不能開(kāi)始.任務(wù)1是唯一最早開(kāi)始的任務(wù)，任務(wù)J是唯一最晚完成的任務(wù)，均為虛擬任務(wù)，即不消耗資源且執(zhí)行時(shí)間為0，表示整個(gè)工程的開(kāi)始和結(jié)束.又規(guī)定任務(wù)j（j＝1，2，…，J）必須選擇Mj種執(zhí)行模式之一執(zhí)行，且在執(zhí)行過(guò)程中不能中斷或改變執(zhí)行模式.在第m（1≤m≤Mj）種模式下任務(wù)j執(zhí)行時(shí)間為djm.根據(jù)各任務(wù)在各執(zhí)行模式下的最短執(zhí)行時(shí)間，并利用傳統(tǒng)的時(shí)間參數(shù)計(jì)算方法，可計(jì)算出各任務(wù)的最早、最晚完成時(shí)間窗口［EFj，LFj］.

同時(shí)，引進(jìn)如下決策變量：

1.2 項(xiàng)目工期模型

工程項(xiàng)目的工期優(yōu)化模型為

1.3 項(xiàng)目成本模型

工程項(xiàng)目的成本優(yōu)化模型為

指整個(gè)工期內(nèi)可更新資源k的最大消耗水平；

為整個(gè)項(xiàng)目不可更新資源n的消耗量；

定義為整個(gè)工期內(nèi)可更新資源k的最大路徑運(yùn)輸量，即任務(wù)j在m模式下的路徑長(zhǎng)度ljm與資源需求量rjmk的乘積；

同理定義為整個(gè)項(xiàng)目不可更新資源n的最大路徑運(yùn)輸量.

1.4 項(xiàng)目資源均衡模型

資源均衡優(yōu)化就是在工程項(xiàng)目執(zhí)行過(guò)程中，使資源計(jì)劃使用量在整個(gè)工期內(nèi)趨于均衡［8］.在編制工程網(wǎng)絡(luò)計(jì)劃時(shí)，要對(duì)工作的實(shí)際時(shí)間進(jìn)行適當(dāng)?shù)卣{(diào)整，減少資源使用量的高峰與低谷的差值，即達(dá)到資源方差值最小.目標(biāo)函數(shù)如下

s.t. 式（2）～（6）

指項(xiàng)目的完成時(shí)間；

為項(xiàng)目中在時(shí)段t可更新資源k的消耗總量；

表示可更新資源k在整個(gè)項(xiàng)目工期內(nèi)的平均資源消耗水平；

為項(xiàng)目中在時(shí)段t不可更新資源n的消耗總量；

則表示不可更新資源n在整個(gè)項(xiàng)目工期內(nèi)的平均資源消耗水平.

1.5 項(xiàng)目質(zhì)量模型

考慮到工程質(zhì)量的特殊性，這里對(duì)工程質(zhì)量進(jìn)行重新定義和假設(shè).參照文獻(xiàn)［9－12］，本文在基本模型建立的基礎(chǔ)上，采用專(zhuān)家估測(cè)法對(duì)工程質(zhì)量進(jìn)行評(píng)分，并確定單個(gè)活動(dòng)在工程中所占的權(quán)重.具體目標(biāo)函數(shù)如下

FQ＝為項(xiàng)目質(zhì)量目標(biāo)函數(shù)，式（10）表示質(zhì)量最優(yōu).式中，wj指任務(wù)j的權(quán)重；qjm指任務(wù)j在m模式下的質(zhì)量得分.

1.6 多目標(biāo)優(yōu)化模型建立

為了能夠?qū)こ添?xiàng)目進(jìn)行綜合優(yōu)化，這里將前面的工期、成本、資源和質(zhì)量各優(yōu)化目標(biāo)函數(shù)加權(quán)求和，建立多目標(biāo)優(yōu)化函數(shù)

式中，WT、WC、WR、WQ分別為各個(gè)目標(biāo)函數(shù)的權(quán)重；由于各個(gè)模型的目標(biāo)函數(shù)值具有不同的單位和量綱，在進(jìn)行多目標(biāo)決策之前先將這些目標(biāo)無(wú)量綱化，即僅用數(shù)值的大小來(lái)反映各目標(biāo)屬性值的優(yōu)劣，式中的則是將各目標(biāo)函數(shù)通過(guò)無(wú)量綱化所得到的，具體為

其中工期、成本、資源及質(zhì)量各目標(biāo)函數(shù)分別得到的最大、最小值為FTmax，F(xiàn)Tmin，F(xiàn)Cmax，F(xiàn)Cmin，F(xiàn)Rmax，F(xiàn)Rmin和FQmax，F(xiàn)Qmin.

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

2.1 算法思想

粒子群優(yōu)化算法是由Eberhart博士與Kennedy博士發(fā)明的一種新的全局優(yōu)化進(jìn)化算法.該算法源于對(duì)鳥(niǎo)類(lèi)捕食行為的模擬［6］.粒子群優(yōu)化算法首先初始化一群隨機(jī)粒子，然后通過(guò)迭代找到最優(yōu)解.在每一次迭代中，粒子通過(guò)跟蹤兩個(gè)“極值”來(lái)更新自己.一個(gè)是粒子本身所找到的最優(yōu)解，即個(gè)體極值pbest.另一個(gè)是整個(gè)種群目前找到的最優(yōu)解，稱(chēng)之為全局極值gbest.粒子在找到上述兩個(gè)極值后，就根據(jù)下面兩個(gè)公式來(lái)更新自己的速度與位置［6］：

式中，V是粒子的速度；present是粒子的當(dāng)前位置；rand（）＊是（0，1）之間的隨機(jī)數(shù)；c1和c2被稱(chēng)作學(xué)習(xí)因子.通常，c1＝c2＝2，w是加權(quán)系數(shù)，取值在0.1～0.9之間.

根據(jù)上述公式，粒子最終飛至解空間中最優(yōu)解所在的位置，搜索過(guò)程結(jié)束.最后輸出的gbest就是全局最優(yōu)解.在更新過(guò)程中，粒子每一維的最大速率被限制為Vmax，粒子每一維的坐標(biāo)也被限制在允許范圍之內(nèi).

2.2 算法流程與步驟

粒子群算法步驟如下［13］：

步驟1 初始化群體規(guī)模為M的粒子群（在控制范圍內(nèi)隨機(jī)設(shè)定位置和速度）；

步驟2 計(jì)算每個(gè)粒子的適應(yīng)值f（p），p為粒子所處的位置；

步驟3 將每個(gè)粒子適應(yīng)值與其經(jīng)歷過(guò)的最好位置pbest作比較，如果f（pi）＜f（pbesti），則f（pbesti）＝f（pi）；

步驟4 將每個(gè)粒子適應(yīng)值與全局極值gbest作比較，如果f（pi）＜f（gbest），則f（gbest）＝f（pi）；

步驟5 根據(jù)粒子群算法的進(jìn)化方程，更新速度和位置；

步驟6 若到達(dá)最大迭代次數(shù)G，輸出結(jié)果；否則，返回步驟2.

標(biāo)準(zhǔn)PSO算法流程如圖1所示［14］.

圖1 PSO算法流程圖Fig.1 PSO procedure

2.3 粒子群算法編碼

2.3.1 粒子編碼與初始化

在多執(zhí)行模式的項(xiàng)目調(diào)度過(guò)程中，需要選擇一個(gè)可行的執(zhí)行模式和調(diào)度順序.因此，本文算法中有兩種類(lèi)型的粒子：模式粒子和優(yōu)先級(jí)粒子.其中，模式粒子用以選擇執(zhí)行模式，優(yōu)先級(jí)粒子用以選擇各個(gè)任務(wù)的調(diào)度順序.這兩種粒子數(shù)量相同，組合形成了一個(gè)調(diào)度方案.

粒子群的搜索空間維度表示項(xiàng)目中的任務(wù)數(shù)，總數(shù)為J，模式粒子xim每個(gè)維度的值ximj都是隨機(jī)值，大小不超過(guò)其對(duì)應(yīng)的任務(wù)的可選模式總數(shù)，這個(gè)值表示任務(wù)j所選擇的模式.優(yōu)先級(jí)粒子yim每個(gè)維度的值yimj都是［0，1］的隨機(jī)實(shí)數(shù)，這個(gè)值的大小表示選擇m模式的任務(wù)j調(diào)度的優(yōu)先順序，值越大越優(yōu)先調(diào)度.為方便理解和計(jì)算，取虛擬開(kāi)始任務(wù)的優(yōu)先值為1，虛擬結(jié)束任務(wù)的優(yōu)先值為0，其余任務(wù)都在（0，1）中取隨機(jī)實(shí)數(shù).經(jīng)過(guò)簡(jiǎn)單的降序排序后就得到一個(gè)調(diào)度順序，但是這個(gè)調(diào)度順序可能不符合邏輯關(guān)系約束，即緊后任務(wù)的優(yōu)先值可能大于其緊前任務(wù)的值，所以在生成一個(gè)調(diào)度順序后，需要加入一個(gè)邏輯關(guān)系判斷程序，以剔掉不符合要求的粒子.

2.3.2 調(diào)度生成方式

基于優(yōu)先規(guī)則的調(diào)度生成方式可分為兩種：串行調(diào)度方案（serial scheduling scheme，SSS）和并行調(diào)度方案（parallel scheduling scheme，PSS）［15］，本文采用的是串行調(diào)度方案.

串行調(diào)度方案的主要思路是：根據(jù)已經(jīng)確定的調(diào)度順序，按順序加工，某個(gè)任務(wù)j的實(shí)際開(kāi)始時(shí)間在其最早開(kāi)始時(shí)間EFj與最晚開(kāi)始時(shí)間LFj之間，在程序設(shè)計(jì)時(shí)，只需要判斷在EFj和LFj之間，哪個(gè)時(shí)刻首先滿(mǎn)足該任務(wù)的資源消耗量小于或等于該時(shí)刻的資源剩余總量，這個(gè)時(shí)刻便是該任務(wù)的實(shí)際開(kāi)始時(shí)間Tf.依此類(lèi)推，最后得到該調(diào)度順序各個(gè)任務(wù)的實(shí)際開(kāi)始時(shí)間、工期和成本等一系列目標(biāo)值，然后通過(guò)適應(yīng)度函數(shù)計(jì)算最優(yōu)適應(yīng)值.

2.3.3 粒子更新方式

粒子采用式（17）和式（18）對(duì)粒子速度和位置進(jìn)行更新.更新后，如果模式粒子ximj＜1，則ximj＝1；如果ximj＞M，則ximj＝M.如果優(yōu)先級(jí)粒子yimj≥1或者yimj≤0，yimj＝rand.如果Vimj＞1，則Vimj＝1；如果Vimj＜－1，則Vimj＝－1.

3 應(yīng)用實(shí)例

以國(guó)際標(biāo)準(zhǔn)問(wèn)題庫(kù)中的J1015－5.SM為測(cè)試問(wèn)題，同時(shí)以實(shí)際項(xiàng)目經(jīng)驗(yàn)所提供的基本數(shù)據(jù)為基礎(chǔ)，應(yīng)用基本粒子群算法求解上述模型下的多目標(biāo)項(xiàng)目調(diào)度問(wèn)題.作業(yè)及資源等信息如表1、表2（見(jiàn)下頁(yè)）所示.

表1 作業(yè)信息表Tab.1 Operation information

同時(shí)，規(guī)定每單位數(shù)量資源運(yùn)輸單位長(zhǎng)度所需成本為50；四大目標(biāo)函數(shù)權(quán)重分別為WT＝0.4，WC＝0.25，WR＝0.15，WQ＝0.2.根據(jù)表1給出的邏輯關(guān)系，繪制出本項(xiàng)目的單代號(hào)網(wǎng)絡(luò)圖，如圖2（見(jiàn)下頁(yè)）所示.

這里采用Matlab 7.0對(duì)以上算法編程，算法參數(shù)設(shè)置：學(xué)習(xí)因子c1＝c2＝2，由于該問(wèn)題只有12個(gè)任務(wù)，屬于比較簡(jiǎn)單的調(diào)度問(wèn)題，所以種群規(guī)模和進(jìn)化次數(shù)不用設(shè)置的太大，本文中設(shè)定種群規(guī)模M＝20，進(jìn)化次數(shù)Gmax＝500；粒子群算法迭代運(yùn)行次數(shù)為G＝500；w取慣性權(quán)重，取值w＝wmax－（wmax－wmin）／Dmax，wmax，wmin分別取0.9和0.4.通過(guò)500次迭代運(yùn)算得到了如表3所示的結(jié)果.

圖2 項(xiàng)目網(wǎng)絡(luò)圖Fig.2 Project network diagram

表3 單目標(biāo)與多目標(biāo)運(yùn)行結(jié)果比較Tab.3 Comparison between single－target ＆ multi－target running results

同時(shí)，可以得到該多目標(biāo)模型下最優(yōu)方案的具體模式選擇情況以及任務(wù)對(duì)應(yīng)的調(diào)度順序，如表4所示.

表4 最優(yōu)方案任務(wù)執(zhí)行信息表Tab.4 Details of the optimaldecision

通過(guò)500次進(jìn)化運(yùn)算，基本達(dá)到收斂性效果，計(jì)算平均運(yùn)行時(shí)間為10min，達(dá)到平均最優(yōu)值的比例為98.9%.同時(shí)，得到圖3的多目標(biāo)優(yōu)化函數(shù)在此算例下的平均最優(yōu)適應(yīng)值曲線，即收斂圖.由此可以看出，粒子群算法在求解該項(xiàng)目調(diào)度問(wèn)題時(shí)方差較小，結(jié)果比較穩(wěn)定.

圖3 算例收斂圖Fig.3 Convergence of the case

4 結(jié)束語(yǔ)

本文提出在進(jìn)行項(xiàng)目?jī)?yōu)化問(wèn)題求解時(shí)，將控制目標(biāo)有效地結(jié)合統(tǒng)一，形成一個(gè)綜合、科學(xué)、有效的數(shù)學(xué)模型，這種思想是解決實(shí)際問(wèn)題的根本和最優(yōu)化設(shè)計(jì)成敗的關(guān)鍵.

本文建立了工期—成本—資源均衡—質(zhì)量的優(yōu)化模型，并將各目標(biāo)函數(shù)加權(quán)求和，采用單目標(biāo)優(yōu)化技術(shù)求解多目標(biāo)優(yōu)化問(wèn)題，并采用粒子群優(yōu)化算法求解工程項(xiàng)目多目標(biāo)問(wèn)題，能較好地平衡全局與局部搜索能力，保持種群的多樣性，避免早熟.

項(xiàng)目實(shí)例驗(yàn)證結(jié)果表明，該綜合優(yōu)化模型具有較好的適用性，粒子群優(yōu)化算法在求解該多目標(biāo)項(xiàng)目?jī)?yōu)化模型問(wèn)題時(shí)具備可行性，并且基本達(dá)到了預(yù)期理想的結(jié)果.

［1］王首續(xù)，周學(xué)林.遺傳算法優(yōu)化施工網(wǎng)絡(luò)計(jì)劃的多種資源均衡［J］.重慶交通學(xué)院學(xué)報(bào)，2001，20（2）：39－45.

［2］駱剛，劉爾烈，王健.遺傳算法在網(wǎng)絡(luò)計(jì)劃資源優(yōu)化中的應(yīng)用［J］.天津大學(xué)學(xué)報(bào)，2004，37（2）：179－183.

［3］劉永淞.DP法工期優(yōu)化［J］.湘潭大學(xué)學(xué)報(bào)，2002，24（1）：106－108.

［4］楊湘，張連營(yíng).工程項(xiàng)目工期——成本綜合模糊優(yōu)化［J］.土木工程學(xué)報(bào)，2003，36（3）：46－50.

［5］劉寅，馬良，黃玨.基于模糊粒子群算法的非線性函數(shù)優(yōu)化［J］.上海理工大學(xué)學(xué)報(bào)，2012，34（4）：314－322.

［6］Kennedy J，Eberhart R C.Particle swarm optimization［C］∥IEEE International Conference on Neural Networks，Perth，1995.［7］與科學(xué)王維博，馮 全源.基于改進(jìn)粒子群算法的工程項(xiàng)目綜合優(yōu)化［J］.西南交通大學(xué)學(xué)報(bào)，2011，46（1）：76－83.

［8］齊東海，宋向群.工程項(xiàng)目進(jìn)度管理［M］.大連：大連理工大學(xué)出版社，2001.

［9］王健，劉爾烈，駱剛.工程項(xiàng)目管理中工期成本質(zhì)量綜合均衡優(yōu)化［J］.系統(tǒng)工程學(xué)報(bào)，2004，19（2）：148－153.

［10］楊耀紅，汪應(yīng)洛，王能民.工程項(xiàng)目工期成本質(zhì)量模糊均衡優(yōu)化研究［J］.系統(tǒng)工程理論與實(shí)踐，2006，26（7）：114－117.

［11］Kaheled E， Amr K. Time－cost－quality－trade－off analysis for highway construction［J］.Journal of Construction Engineering and Management，2005，131（4）：477－485.

［12］Afshar A，Kaveh A，Shoghli O R.Multi－objective optimization of time－cost－quality using multicolonyant algorithm ［J］.Asian Journal of Civil Engineering（Building and Housing），2007，8（2）：113－124.

［13］陳志勇，杜志達(dá)，周華.基于微粒群算法的工程項(xiàng)目資源均衡優(yōu)化［J］.土木工程學(xué)報(bào)，2007，40（2）：93－96.

［14］楊維，李歧強(qiáng).粒子群算法綜述［J］.中國(guó)工程科學(xué)，2004，6（5）：87－95.

［15］Kolisch R.Serial and parallel resource－constrained project scheduling methods revisited：theory and computation［J］.European Journal of Operational Research，1996，90（2）：320－333.