王秋全，李向，王嶺玲

1．中國(guó)交通建設(shè)股份有限公司西北區(qū)域總部，陜西西安 710065

2．中國(guó)地質(zhì)大學(xué)計(jì)算機(jī)學(xué)院，湖北武漢 430074

3．武漢工程科技學(xué)院機(jī)械與電子信息學(xué)部，湖北武漢 430200

基于粒子群算法的多項(xiàng)目資源均衡方法研究

王秋全1，李向2，王嶺玲3

1．中國(guó)交通建設(shè)股份有限公司西北區(qū)域總部，陜西西安 710065

2．中國(guó)地質(zhì)大學(xué)計(jì)算機(jī)學(xué)院，湖北武漢 430074

3．武漢工程科技學(xué)院機(jī)械與電子信息學(xué)部，湖北武漢 430200

針對(duì)傳統(tǒng)粒子群算法容易陷入局部最優(yōu)的缺點(diǎn)，提出利用動(dòng)態(tài)慣性權(quán)重參數(shù)和模擬退火算法修改突變概率，進(jìn)而改進(jìn)傳統(tǒng)粒子群算法，探討各項(xiàng)目工期最短情況下的多項(xiàng)目資源均衡分配問(wèn)題。通過(guò)對(duì)比試驗(yàn)表明，改進(jìn)的粒子群優(yōu)化（particle swarm optimization，PSO）算法很好地實(shí)現(xiàn)了多項(xiàng)目的資源均衡優(yōu)化，通過(guò)同比試驗(yàn)驗(yàn)證了改進(jìn)PSO算法在解決不同規(guī)模多項(xiàng)目的資源均衡問(wèn)題時(shí)的算法時(shí)間復(fù)雜度的線性增長(zhǎng)性，很好地表達(dá)了人們的調(diào)度意圖。

粒子群優(yōu)化；調(diào)度網(wǎng)絡(luò)；均衡優(yōu)化；多項(xiàng)目

工業(yè)設(shè)計(jì)中的優(yōu)化問(wèn)題經(jīng)常遇到，許多問(wèn)題最后都可以歸結(jié)為優(yōu)化問(wèn)題。解決優(yōu)化問(wèn)題主要涉及2個(gè)方面：一是要求尋找全局最小點(diǎn)，二是要求有較高的收斂速度。為了解決各種各樣的優(yōu)化問(wèn)題，人們提出了許多優(yōu)化算法，比較著名的有爬山法、人工神經(jīng)網(wǎng)絡(luò)、遺傳算法［1］、粒子群算法等。近些年國(guó)外對(duì)于研究?jī)?yōu)化的問(wèn)題有很大進(jìn)步。2009年Yen等［2］重點(diǎn)研究了動(dòng)態(tài)調(diào)整粒子群的數(shù)量。在國(guó)內(nèi)，2008年，建勛等［3］提出了基于熵權(quán)和粒子群解決資源均衡問(wèn)題的新方法。同年，Li Xiang［4］提出了利用遺傳算法解決多項(xiàng)目資源均衡問(wèn)題，取得了較好的效果。然而對(duì)于多資源任務(wù)調(diào)度，李間鋒等［5］針對(duì)云計(jì)算的編程模型框架，提出了一種具有雙適應(yīng)度的遺傳算法，使調(diào)度結(jié)果的任務(wù)平均完成時(shí)間縮短，解決了一些重要的問(wèn)題。許川佩等［6］采用量子粒子群算法在解決功耗約束下實(shí)現(xiàn)了SOC測(cè)試的調(diào)度優(yōu)化，縮短了測(cè)試的時(shí)間，算法實(shí)現(xiàn)簡(jiǎn)單。2013年，劉立冬［7］結(jié)合蟻群算法和遺傳算法優(yōu)勢(shì)和特點(diǎn)，對(duì)TSP問(wèn)題將2種算法按獨(dú)特的方式融合生成遺傳蟻群算法，實(shí)驗(yàn)證明該融合算法的穩(wěn)定性優(yōu)于2種單獨(dú)的算法。本文針對(duì)傳統(tǒng)粒子群算法容易陷入局部最優(yōu)的缺點(diǎn)，提出利用動(dòng)態(tài)慣性權(quán)重參數(shù)和模擬退火算法修改突變概率方法改進(jìn)傳統(tǒng)粒子群算法，探討各項(xiàng)目工期最短情況下的多項(xiàng)目資源均衡分配問(wèn)題。

1 多項(xiàng)目并行調(diào)度資源均衡問(wèn)題模型

調(diào)度是指對(duì)工程進(jìn)行系統(tǒng)的編排、決策和控制，協(xié)調(diào)各道工序，合理安排各種資源，在滿足工程總工期的條件，發(fā)揮各種資源最大經(jīng)濟(jì)效益。優(yōu)化過(guò)程是利用時(shí)差，不斷改進(jìn)初始網(wǎng)絡(luò)方案，在滿足既定條件下，按某一個(gè)或幾個(gè)衡量指標(biāo)來(lái)尋求最優(yōu)的方案。對(duì)資源均衡的優(yōu)化目前主要采用“消峰填谷”法，利用工序的時(shí)差，反復(fù)調(diào)整，拉平資源消耗的高峰。這種方法計(jì)算過(guò)程復(fù)雜，對(duì)于工序繁多的大型工程，即使采用計(jì)算機(jī)求解也需要較長(zhǎng)時(shí)間，而且計(jì)算結(jié)果是近似最優(yōu)解，誤差比較大，下面討論多資源調(diào)度的數(shù)據(jù)模型。

1．1 數(shù)學(xué)建模的建立

設(shè)有P個(gè)獨(dú)立的項(xiàng)目，每個(gè)項(xiàng)目均包含不同件數(shù)的工作，即第i個(gè)項(xiàng)目包含Pi件工作；在資源庫(kù)中有M種資源，第m種資源的總量為Wm；T為所有項(xiàng)目的總的預(yù)定完成工期，Tk為第k個(gè)項(xiàng)目的預(yù)定完成工期；Wm（t）為第t件工作日所有項(xiàng)目對(duì)第m種資源的需求量；Wij，m（t）為第i個(gè)項(xiàng)目中第j件工作在第t件工作日對(duì)第m個(gè)資源的需求量；Tij為第i個(gè)項(xiàng)目中第j件工作的開(kāi)始時(shí)間；dij為第i個(gè)項(xiàng)目中第j件工作的持續(xù)時(shí)間；Sij為第i個(gè)項(xiàng)目中第j件工作的的富余時(shí)間；Ri表示第i個(gè)項(xiàng)目的工作集；Rij表示第i個(gè)項(xiàng)目中第j件工作；Uij為它所有緊前工作的緊前工作集，i∈［1，n］，i∈［1，Pi］，ˉWm。 為所有項(xiàng)目的對(duì)第m種資源的平均消耗量。針對(duì)所述問(wèn)題，文中采用取方差最小的方法，建立如下數(shù)學(xué)模型：

式（1）為目標(biāo)函數(shù)，要求項(xiàng)目資源分配均衡，并且還要根據(jù)項(xiàng)目的優(yōu)先級(jí)來(lái)合理分配資源，?為各個(gè)項(xiàng)目的優(yōu)先級(jí)權(quán)重。式（2） ～（6）為約束條件，約束條件（2）表示第i個(gè)項(xiàng)目中第j件工作第t時(shí)刻的資源消耗量，必須小于該資源的的供應(yīng)量；約束條件（3）保證t時(shí)刻進(jìn)行的工作Uij沒(méi)有超出工期范圍；約束條件（4）保證決策變量為正整數(shù)；約束條件（5）ˉWm為第m種資源的平均需求量；約束條件（6）考慮到不同項(xiàng)目的重要程度不同，用?k表示第k個(gè)項(xiàng)目的權(quán)重，所有項(xiàng)目的權(quán)重的總和為1。

1．2 方差和峰差

一個(gè)項(xiàng)目在不同時(shí)刻t對(duì)某種資源的單需求量W（t）是不同的，t＝（0，1，…，T），T是項(xiàng)目的預(yù)定完成工期。在預(yù)定完成工期內(nèi)，對(duì)某種資源在單位時(shí)間內(nèi)的平均需求量稱為平均單需量，記為ˉW。則

式中：Q為項(xiàng)目對(duì)資源的需求總量；單需量W（t）圍繞平均單需量ˉW上下波動(dòng)。波動(dòng)幅度越大，表明資源利用越不均衡；反之則表明資源的利用較均衡。

衡量不均衡程度有2種標(biāo)準(zhǔn)：一是用方差σ2w，一是峰差dw。

2）峰差。資源利用不均衡的峰差dw由式（8）定義：為使資源均衡利用，dw要盡可能小，也就是使maxW（t）最小。

2 項(xiàng)目并行調(diào)度粒子群算法設(shè)計(jì)與優(yōu)化

2．1 粒子的設(shè)計(jì)

由于本文的問(wèn)題描述只是目標(biāo)由工期最短改為資源最優(yōu)，所以，在設(shè)計(jì)粒子時(shí)，只考慮資源的問(wèn)題，建立一個(gè)粒子長(zhǎng)度為Q的三維粒子，第1維表示項(xiàng)目，并以自然數(shù)1，2，3，…，Q表示不同的項(xiàng)目；第2維是粒子位置xj，第i個(gè)項(xiàng)目的工作號(hào)集合；第3維是粒子位置Yxj，表示資源分配。三維維粒子的表示如表1、2所示。

表1 項(xiàng)目數(shù)與工作編號(hào)的映射

表2 工作編號(hào)與資源分配的映射

表1為項(xiàng)目數(shù)與工作編號(hào)的映射關(guān)系。在表2中，xij為第i個(gè)項(xiàng)目第j件工作的工作編號(hào)，xij∈［1，Qi］，Qi第i個(gè)項(xiàng)目的工作數(shù)，第三維粒子Yxij，k為占用的第 Rk資源量，Yxij，k∈［1，Rm＋1］，k［1，m］。 在解碼過(guò)程中，對(duì)占用同種資源的工作進(jìn)行比較，如果資源分配在占用同種資源的工作之間出現(xiàn)沖突，比較Yxij，k與?k相乘的結(jié)果，值最大的粒子位置不變，其他粒子更新粒子位置，否則粒子位置不變。

2．2 適應(yīng)值函數(shù)

由于本節(jié)討論的是資源均衡的問(wèn)題，所以目標(biāo)函數(shù)有2種，分別是方差最小和峰差最小。在本節(jié)中，取方差最小為目標(biāo)函數(shù)：

2．3 粒子群優(yōu)化算法的改進(jìn)

由于基本的PSO算法精度低、易發(fā)散等原因往往出現(xiàn)早熟收斂或收斂緩慢等缺點(diǎn)。因此，設(shè)計(jì)PSO算法的參數(shù)以及操作，應(yīng)主要針對(duì)如何保證種群的多樣性，以提高算法精度，從而提高算法的搜索效率，避免早熟收斂現(xiàn)象。本文在前人研究成果的基礎(chǔ)上，借鑒文獻(xiàn)［6］關(guān)于混合算法和文獻(xiàn)［8］改進(jìn)慣性權(quán)重的思想，設(shè)計(jì)了一種改進(jìn)PSO算法，來(lái)平衡全局搜索能力和局部搜索能力，提高收斂速度，從而減少獲得最優(yōu)解所需的運(yùn)行代數(shù)。

2．3．1 結(jié)合模擬退火算法

模擬退火（simulated annealing，SA）算法是1982年由Kirkpatriek等提出的一種隨機(jī)優(yōu)化方法，它模擬了物理中金屬的降溫過(guò)程。SA也被改進(jìn)用于求解多目標(biāo)優(yōu)化問(wèn)題，由于它具有很強(qiáng)的全局搜索能力，在搜索中具有概率突跳的特性，所以對(duì)搜索非劣解集非常有利，能夠有效避免搜索陷入局部極小解。簡(jiǎn)單的說(shuō)，就是SA算法在搜索過(guò)程中不但接受好的解，而且也允許以一定概率接受差的解。同時(shí)，可以通過(guò)溫度參數(shù)設(shè)置突跳概率，即突跳概率隨著溫度的下降而減小，當(dāng)溫度趨于0時(shí)，突跳概率值也趨于0，理論上已經(jīng)證明，SA算法在一定條件下以概率1收斂到全局最優(yōu)解。

由于在基本粒子群算法中，速度更新采用了群體最佳位置，所有粒子都傾向于群體最佳位置。如果群體的最佳位置處于局部極小解，那么，所有的粒子都將趨向于局部極小解，從而導(dǎo)致搜索的分散性變差，使得全局探索能力減弱。為了使算法在運(yùn)行過(guò)程中，盡可能少的陷入局部極小解，本文將從Pi中選取一個(gè)位置，記作Pgnew，來(lái)代替更新公式中的Pg。 改進(jìn)后的更新公式為

為了性能好的Pi有較高的概率被選中，借用SA算法的機(jī)制，從而可計(jì)算問(wèn)題t時(shí)Pi相對(duì)Pg的突跳概率——e－（fpi－fpg）／t，f為目標(biāo)函數(shù)值，然后將此突跳概率值當(dāng)做Pi的適配值，則Pi代替Pg的概率公式為

式中N為種群大小。根據(jù)上述替代概率，采用輪盤(pán)賭策略隨機(jī)確定哪個(gè)Pi將成為Pgnew。

2．3．2 慣性權(quán)重參數(shù)的修改

在PSO算法的參數(shù)中，慣性權(quán)重w用來(lái)調(diào)整全局和局部搜索的能力。w值越大越容易實(shí)現(xiàn)全局搜索，w值越小越有利于局部搜索算法進(jìn)行初期，全局搜索能力較強(qiáng)，但是如果找不到最好點(diǎn)，隨著w的減小，局部搜索能力變強(qiáng)，容易陷入局部極值。為了既能在進(jìn)化初期得到大的搜索空間避免陷入局部最優(yōu)，又能在進(jìn)化后期進(jìn)行更精細(xì)的搜索以加快收斂速度，需用不斷更新慣性權(quán)重參數(shù)w：式中：i為當(dāng)前迭代次數(shù)，imax為最大迭代次數(shù)，wn為初始慣性權(quán)重值，we為運(yùn)行至最大迭代次數(shù)時(shí)的慣性權(quán)重值。在基本粒子群算法中，由于步長(zhǎng)較小，w的變化幅度也較小，因此不易陷人局部最優(yōu)。

2．3．3 改進(jìn)后的粒子群算法

改進(jìn)后的PSO算法的步驟：

1）在需要求解的問(wèn)題的解空間中，初始化一個(gè)粒子群，即隨機(jī)產(chǎn)生各粒子的初始位置和速度；

2）根據(jù)目標(biāo)函數(shù)計(jì)算每個(gè)粒子對(duì)應(yīng)的“適應(yīng)值”，用以衡量粒子在該位置所達(dá)到的優(yōu)化程度；

3）令各粒子的自身最佳位置Pi及其適應(yīng)值為當(dāng)前位置及其適應(yīng)值，令群體最佳位置 及其適應(yīng)值為所有Pg中的最佳位置及其適應(yīng)值；

4）確定初始溫度；

5）根據(jù)式（10）確定當(dāng)前溫度下各Pi的適配值；

6）采用輪盤(pán)賭策略從所有Pi中確定NPg，然后根據(jù)公式（9）更新各粒子的速度和位置；

7）計(jì)算各粒子新位置對(duì)應(yīng)的適應(yīng)值；

8）更新各粒子的Pi及其適應(yīng)值，更新群體的Pg及其目標(biāo)值；

9）根據(jù)式（11）計(jì)算出慣性權(quán)重；

10）退溫操作；

11）如達(dá)到迭代終止條件（通常為一個(gè)預(yù)設(shè)的最大迭代代數(shù)），則程序終止輸出及其適應(yīng)值，否則返回5）進(jìn)行新一輪迭代。

要在資源限制條件下進(jìn)行多項(xiàng)目調(diào)度優(yōu)化，使各項(xiàng)目的工期最短，對(duì)所有項(xiàng)目進(jìn)行資源均衡優(yōu)化，即對(duì)所有工作的資源分配重新進(jìn)行調(diào)整，使得最終的工期和資源分配趨向于均衡?；静襟E如下：

1）根據(jù)有項(xiàng)目的基本信息，求出各種相關(guān)參數(shù)；

2）運(yùn)用改進(jìn)的PSO算法，對(duì)項(xiàng)目進(jìn)行優(yōu)化，使工期最短；

3）將優(yōu)化所得結(jié)果傳入時(shí)間／資源數(shù)學(xué)模型；

4）運(yùn)用改進(jìn)的PSO算法，根據(jù)時(shí)間／資源數(shù)學(xué)模型，對(duì)項(xiàng)目進(jìn)行優(yōu)化。求得最終的工期和資源分配解。

3 算法驗(yàn)證與實(shí)驗(yàn)結(jié)果分析

項(xiàng)目的雙代號(hào)網(wǎng)絡(luò)結(jié)構(gòu)如圖1所示。但是由于實(shí)例中，許多工作的資源單需量與可提供資源的總量相比較大，而每種資源的提供量都限制在很小的范圍內(nèi)，進(jìn)行資源限制下調(diào)度優(yōu)化后，再進(jìn)行時(shí)間／資源綜合優(yōu)化的效果不是很明顯。因此，需要對(duì)各種資源的供給量進(jìn)行重新設(shè)置，其中選取設(shè)計(jì)、采購(gòu)、工藝、程序員、熱處理、電加工、數(shù)控、裝配、數(shù)模等人員分別為40、24、12、10、21、48、32、15、12，重新設(shè)置后各項(xiàng)目的工作所需資源類(lèi)型、需求量及工作持續(xù)時(shí)間如表3所示。

圖1 項(xiàng)目的雙代號(hào)網(wǎng)絡(luò)結(jié)構(gòu)

表3 各項(xiàng)目工作所需資源類(lèi)型、需求量及工作持續(xù)時(shí)間

圖2 平均響應(yīng)時(shí)間

為驗(yàn)證改進(jìn)的PSO算法在大規(guī)模數(shù)據(jù)下的可實(shí)現(xiàn)性和優(yōu)越性，用改進(jìn)的PSO算法分別進(jìn)行3、5、10直至100個(gè)項(xiàng)目同時(shí)運(yùn)行，每個(gè)項(xiàng)目的工作數(shù)為50個(gè)左右，每組數(shù)據(jù)測(cè)試5次取平均值，然后用未改進(jìn)的PSO算法進(jìn)行相同的測(cè)試，再將2種算法所得結(jié)果相比較。

在圖2中，當(dāng)同時(shí)執(zhí)行的項(xiàng)目個(gè)數(shù)為5、10、20、40、60、80和100時(shí)，圖中標(biāo)出了2種算法的平均響應(yīng)時(shí)間。用10個(gè)、20個(gè)和40個(gè)項(xiàng)目進(jìn)行比對(duì)時(shí)，改進(jìn)的PSO算法比未改進(jìn)的PSO的平均優(yōu)化時(shí)間分別降低了4．1%、4．7%和5．3%，當(dāng)用60個(gè)、80個(gè)和100個(gè)項(xiàng)目進(jìn)行比對(duì)時(shí)，改進(jìn)的PSO算法比未改進(jìn)的PSO的平均優(yōu)化時(shí)間分別降低了7．2%、8．15%和9．29%。從比較可以得出當(dāng)項(xiàng)目數(shù)為1～40個(gè)時(shí)，改進(jìn)的PSO算法的優(yōu)勢(shì)并不明顯，相比未優(yōu)化的PSO算法，求解時(shí)間只降低了4．7%左右，算法效率的提高不是很明顯；當(dāng)項(xiàng)目數(shù)為60～100個(gè)時(shí)，求解時(shí)間降低了8%左右，并且隨著項(xiàng)目個(gè)數(shù)的增加，改進(jìn)的PSO算法節(jié)約的時(shí)間呈遞增趨勢(shì)，這說(shuō)明，改進(jìn)的PSO的算法對(duì)于求解資源受限的多項(xiàng)目計(jì)劃調(diào)度問(wèn)題的時(shí)間／資源綜合優(yōu)化時(shí)適合的，并且，數(shù)據(jù)規(guī)模越大，改進(jìn)的PSO的算法優(yōu)勢(shì)就越明顯。

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

在調(diào)度工作中，為了節(jié)約成本，提高工作效率，充分利用各種資源，總希望每天資源使用量越均衡越好，以達(dá)到資源的最佳利用率。本文提出的改進(jìn)粒子群優(yōu)化算法很好地解決了多項(xiàng)目資源均衡問(wèn)題，并驗(yàn)證了不同數(shù)據(jù)規(guī)模對(duì)改進(jìn)PSO算法性能的線性影響。

［1］SUN C L，ZENG J C，PAN J S．An improved vector particle swarm optimization for constrained optimization problems［J］．Information Sciences，2011，181（6）：1153-1163．

［2］YEN G G，LEONG W F．Dynamic multiple swarms in mul-tiobjective particle swarm optimization［J］．IEEE Transac-tions on Systems，Man and Cybernetics，Part A：Systems and Humans，2009，39（4）：890-911．

［3］乞建勛，王強(qiáng)，賈海紅．基于熵權(quán)和粒子群的資源均衡新方法研究［J］．中國(guó)管理科學(xué)，2008（1）：90-95．

［4］李向，譚偉，康立山．基于遺傳算法的資源均衡優(yōu)化研究［J］．計(jì)算機(jī)工程與設(shè)計(jì)，2008，29（7）：4447-4449，4583．

［5］李建鋒，彭艦．云計(jì)算環(huán)境下基于改進(jìn)遺傳算法的任務(wù)調(diào)度算法［J］．計(jì)算機(jī)應(yīng)用，2011，31（1）：184-186．

［6］許川佩，胡紅波．基于量子粒子群算法的SOC測(cè)試調(diào)度優(yōu)化研究［J］．儀器儀表學(xué)報(bào)，2011，32（1）：113-119．

［7］劉立東，蔡淮．融入遺傳算法的混合蟻群算法［J］．計(jì)算機(jī)工程與設(shè)計(jì)，2008，29（5）：1248-1249．

［8］樊瑋．粒子群優(yōu)化方法及其實(shí)現(xiàn)［J］．航空計(jì)算技術(shù)，2004（9）：39-42．

The research for the multi-project resource equalized methods based on particle swarm optimization

WANG Qiuquan1，LI Xiang2，WANG Lingling3
1．West Section Headquarters，China Transportation Construction Co．，Ltd，Xi’an 710065，China
2．School of Computer，China University of Geosciences，Wuhan 430074，China
3．Mechanical and Electronic Information Department，Wuhan University of Engineering Science，Wuhan 430200，China

For the traditional particle swarm optimization easily falling into local optimum，this paper proposes a method that dynamic inertia weight parameter and simulated annealing algorithm are applied to modify the mutation probability to improve the traditional particle swarm optimization，and investigates the balanced allocation problem of multi-project resource under the circumstances that each project has the shortest duration．The comparative exper-iments indicate that the improved particle swarm optimization can nicely achieve the resource balanced optimization of multi-project，and year-on-year experiments verify the linear growth of time complexity of the improved PSO when solving resource balanced optimization of multi－project in different sizes，which can better express the inten-tion of scheduling．

particle swarm optimization；scheduling network；balanced optimization；multi-project

TP3．5

A

1009-671X（2014）03-0055-05

10．3969／j．issn．1009-671X．201312009

http：／／www．cnki．net／kcms／doi／10．3969／j．issn．1009－671X．201312009．html

2013-12-17．

日期：2014-06-05．

中國(guó)地質(zhì)大學(xué)（武漢）橫向科研基金資助項(xiàng)目（2012196539）；湖北省自然科學(xué)基金資助項(xiàng)目（2012195075）．

王秋全（1962-），男，工程師；

王嶺玲（1989-），女，碩士。

王嶺玲，E-mail：2219887348＠qq．com．