基于混沌差分進化粒子群算法的模糊資源受限項目調度問題

何立華， 馬芳麗

?

基于混沌差分進化粒子群算法的模糊資源受限項目調度問題

何立華， 馬芳麗

(中國石油大學(華東) 經濟管理學院，山東 青島 266580)

本文研究了工期模糊情況下的資源受限項目調度問題，采用一種基于區(qū)間數(shù)距離的模糊取最大運算比較模糊工期的大小，解決了以往研究中忽略的工期模糊情況下，項目關鍵路徑可能會發(fā)生改變，相應地各活動的模糊調度時間以及項目的模糊最短工期也可能隨之發(fā)生改變的問題。引入一種基于混沌和差分進化的混合粒子群優(yōu)化算法，并對算法的慣性權重進行改進來求解上述問題。通過一個算例驗證了所建立模型及提出方法的有效性。

模糊資源受限項目調度問題； 模糊數(shù)排序； 粒子群算法； 混沌； 差分進化

HE Lihua, MA Fangli

(School of Economics and Management, China University of Petroleum (East China), Qingdao 266580, China)

資源受限項目調度問題(resource constrained project scheduling problem, RCPSP)研究在滿足一定的時序約束和資源約束條件下，安排各項任務的開始和完成時間，以實現(xiàn)項目的特定目標[1]。在任務工期確定的情況下，對RCPSP的研究已經取得了大量的成果[2]。然而實際環(huán)境中，項目往往受一些不確定因素的影響，使得項目工期具有模糊性，從而引出了對模糊資源受限項目調度問題(fuzzy resource constrained project scheduling problem, FRCPSP)的研究[3]。

在FRCPSP的調度過程中，考慮到任務的時序約束，需要對任務的模糊工期進行比較，因此，許多模糊數(shù)弱比較方法被應用于FRCPSP的求解中。文獻[4]采用PERT技術，文獻[5]采用重心距離法和積分值法將模糊工期轉化為精確值。文獻[6]提出用積分值法、符號距離法以及基于面積的排序方法進行模糊數(shù)之間的排序比較運算。文獻[7]利用可能性測度和必然性測度衡量任務模糊工期，并通過比較二者的權重和來確定兩個模糊工期的大小。文獻[8]計算出不同置信水平下模糊工期的下限和上限值，將其分別代入精確模型來求解問題。文獻[9]基于一種區(qū)間數(shù)距離的排序方法比較模糊工期。上述文獻采取了不同的方法來比較項目模糊工期的大小，對FRCPSP的求解均做出了貢獻。但是這些方法都未考慮到任務工期模糊的環(huán)境下，項目關鍵路徑有可能發(fā)生改變，各活動的模糊調度時間以及項目的模糊最短工期也可能隨之相應地發(fā)生改變的問題。

另一方面，在算法求解過程中，由于粒子群優(yōu)化方法(particle swarm optimization, PSO)易于實施，能快速得到問題的解，是有效解決FRCPSP的一種群智能算法[10]。但是傳統(tǒng)PSO由于算法自身的局限性，容易出現(xiàn)粒子早熟現(xiàn)象，使算法陷入局部最優(yōu)。針對傳統(tǒng)PSO的諸多不足，文獻[11]將混沌算法嵌入PSO中，通過對比粒子群和混沌算法返回的全局極值大小，不斷更新算法的全局極值，避免算法陷入局部極小值。文獻[12]引入向量相似度法建立粒子速度的更新模型。文獻[13]將重疊對齊技術引入到粒子調度生成機制中，改進了搜索過程中解的質量。上述方法分別從避免算法陷入局部極值以及提高迭代過程中解的質量方面對PSO進行改進，有效改善了算法的全局搜索能力。但是這些方法的優(yōu)化結果與理想結果之間仍存在一定的差距。

為了解決上述問題，本文采用文獻[14]提出的一種改進的模糊取最大運算來比較模糊工期的大小。同時，為了進一步提高求解這一問題的PSO的全局搜索能力，本文針對文獻[15]提出的基于混沌和差分進化的混合粒子群優(yōu)化算法，通過對算法慣性權重進行動態(tài)調整改進，將其引入到FRCPSP的求解中。

1 模糊資源受限項目調度問題

FRCPSP的數(shù)學模型如下所示[16]：

(1)

(2)

(3)

其中，式(1)為目標函數(shù)，表示項目的模糊工期取最??；式(2)為活動間的時序約束；式(3)為活動的資源約束。

2 模糊數(shù)排序

由于上述模型中式(1)目標函數(shù)表示的項目工期為模糊數(shù)，式(2)所示時序約束中要確定任意活動的模糊開始時間也要比較其所有緊前活動的模糊完成時間，這都需要比較兩個模糊數(shù)之間的大小。針對這一問題，本文引入一種改進的基于區(qū)間數(shù)距離測度的模糊取最大運算[14]來比較模糊數(shù)間的大小，解決了以往研究中忽略的工期模糊情況下，項目關鍵路徑有可能發(fā)生改變，相應地FRCPSP最終調度結果中項目的模糊最短工期以及各活動的模糊調度時間也可能隨之發(fā)生改變的問題。

(4)

(5)

(6)

(7)

3 混沌差分進化粒子群算法

本文將文獻[15]提出的基于混沌和差分進化的混合粒子群優(yōu)化算法(chaos and differential evolution particle SWARM optimization algorithm, CDEHPSO)引入到FRCPSP的求解中，該算法利用混沌技術初始化種群，基于一種早熟判斷機制識別出早熟粒子，并對其進行差分變異、交叉和選擇以維持種群多樣性。為了進一步提高算法的優(yōu)化性能，本文對算法慣性權重進行動態(tài)調整改進，提出了混沌差分進化粒子群算法。

3.1 標準粒子群算法

PSO的數(shù)學描述如下：設種群規(guī)模為M，搜索空間維數(shù)為N，種群中第i個粒子迭代到第t代時其位置向量為Xi(t)=(xi1(t),xi2(t),…,xiN(t))，速度向量為Vi(t)=(vi1(t),vi2(t),…,viN(t))。粒子個體極值可以表示為lbesti(t)，全局極值為gbest(t)，每個粒子分別按照公式(8)和(9)來更新其速度和位置[18]：

vij(t+1)=wvij(t)+c1r1·[lbestij(t)-xij(t)]+c2r2·[gbestj(t)-xij(t)],

(8)

xij(t+1)=xij(t)+vij(t+1),

(9)

其中，i=1,2,…,M，j=1,2,…,N。c1和c2為學習因子，r1和r2為分布在[0,1]之間的隨機數(shù)，t為迭代數(shù)，w為慣性權重。

3.2 混沌差分進化粒子群算法

1)混沌初始化

設粒子群第j(j∈N)維空間變量的取值范圍為[aj,bj]，在(0,1)之間隨機生成一個初始向量h0=(h0,1,…,h0,j,…,h0,N)，其中(h0,j≠0.25,0.5,0.75)，向量h0作為混沌Logistic映射的初始值，根據(jù)式(10)得到混沌序列hn+1,j(μ為控制參數(shù))：

hn+1,j=f(μ,hn,j)=μhn,j(1-hn,j)，

(10)

再根據(jù)式(11)將混沌序列hn+1,j映射到位置向量xn+1,j，如下所示：

xn+1,j=aj+(bj-aj)hn+1,j，

(11)

同理，可以得到粒子速度向量的初始化值。

2)慣性權重更新策略

在迭代初期，算法慣性權重w取值應該較大，使算法進行全局搜索，迭代后期w取值應該較小，使算法快速收斂。針對這一問題，本文在文獻[15]所提出算法的基礎上引入一種非線性動態(tài)自適應慣性權重更新策略[19]，其計算過程如下所示：

(12)

其中，t為當前迭代數(shù)，tmax為最大的迭代次數(shù)，wmax和wmin分別為慣性權重的最大和最小值，k為控制因子，控制w與t變化曲線的平滑度，通常取3。

3)粒子早熟判斷機制

文獻[15]引入種群適應度方差來判斷早熟粒子，適應度方差σ2的求解公式如下：

(13)

(14)

4)對早熟粒子的差分進化操作

針對識別出的早熟粒子，對其進行差分進化算法中的變異、交叉以及選擇運算，從而維持種群多樣性[15]，具體如公式(15)、(16)和(17)所示：

zi,j(t+1)=xr3,j(t)+F(xr1,j(t)-xr2,j(t),)

(15)

ui,j(t+1)=

(16)

Xi(t+1)=

(17)

其中，xi,j(t)代表第t代中第i條染色體的第j個基因，F(xiàn)為變異規(guī)模因子，Cr為交叉概率，zi,j(t+1)代表變異向量，ui,j(t+1)代表試驗向量，randj是0到1之間均勻分布的一個數(shù)，rnb(i)是從1到N之間隨機選擇的數(shù)。

4 求解FRCPSP的混沌差分進化粒子群算法

本文采用基于活動優(yōu)先值的粒子表示方式，同時，F(xiàn)RCPSP的調度生成機制有并行和串行兩種方法，串行方法生成的是積極計劃，并行方法生成的是非延遲計劃，但其有可能會錯過最優(yōu)解[12]，因此為了保證解的質量，本文采用串行調度生成機制，將由活動優(yōu)先值表示的粒子轉化為可行調度。

4.1 粒子表示方式

將每一個N維粒子與項目的N個活動相對應，用粒子位置向量Xi(t)=(xi1(t),xi2(t),…,xiN(t))的N個參數(shù)值分別表示項目N個活動調度的優(yōu)先值。

4.2 串行調度生成機制

1)設CS是已排列的活動集合，DS是沒有參加排列的活動集合。初始條件下，CS=?，DS=(1,2,…,N)。對各活動優(yōu)先值進行降序排列，選擇優(yōu)先值最大的活動進行時序約束判斷，若滿足則進行下一步；不滿足，則按優(yōu)先值大小選擇下一個活動判斷，直到找出一個滿足時序約束的活動為止；

2)對所選活動進行資源約束判斷，判斷所選活動能否與已安排活動并行調度，可以則轉下一步；不行，則將該活動安排到CS中，計算該活動的模糊開始時間，更新CS和DS，并返回第1)步；

3)對上一步所選活動進行并行調度安排，根據(jù)式(7)比較各活動模糊工期大小，確定該活動的模糊開始時間，并將其安排到CS中，更新CS和DS，返回第 1)步，直到安排完所有活動。

4.3 算法參數(shù)調整

在迭代過程中，為了避免不可行的粒子位置以及粒子由于速度過大運動到可行搜索空間的外部，對粒子的位置向量和速度向量進行調整，如下所示。

(18)

(19)

4.4 FRCPSP的求解步驟

步驟2 令t=t+1，根據(jù) 式(12)計算當前迭代次數(shù)下的慣性權重w(t)值，再根據(jù) 式(8)和(9)更新粒子的速度和位置，并根據(jù) 式(18)和(19)對其進行調整；

步驟4 根據(jù)公式(15)、(16)和(17)，對早熟粒子進行差分變異、交叉和選擇操作；

步驟5 將由優(yōu)先值表示的粒子轉化為可行調度，得出項目模糊工期大小。根據(jù)式(7)計算出各粒子適應度值，更新此代粒子lbesti(t)和gbest(t)；

步驟6 檢查算法是否滿足終止條件，若滿足則停止迭代，輸出此時的最優(yōu)解，否則，轉到步驟2繼續(xù)搜索最優(yōu)解。算法整體流程如圖1所示。

圖1 基于混沌差分進化粒子群算法求解FRCPSP流程圖

5 算例分析

圖2 某項目網絡圖

活動緊前工作模糊持續(xù)時間所需資源1—(42,50,61)821(30,40,48)1731(35,50,59)1241(39,40,69)352(18,36,41)1363,4(16,25,35)1775,6(52,58,69)16

表2 α=0, 0.1, 0.2, 0.3, 0.4時，F(xiàn)RCPSP最終調度結果

表3 α=0.5, 0.6, 0.7, 0.8時，F(xiàn)RCPSP最終調度結果

表4 α=0.9, 1時，F(xiàn)RCPSP最終調度結果

表5 α=0.5時本文所提出算法與CDEHPSO以及PSO的算法性能比較

根據(jù)表2、表3和表4可以看出，工期模糊情況下，當α=0,0.1,0.2,0.3,0.4時，項目關鍵路徑為1-4-6-7，各活動的模糊調度時間如表2所示，此時項目最短工期為(175，223，272)；當α=0.5,0.6,0.7,0.8時，項目關鍵路徑由原來的1-4-6-7變成了1-3-6-7，F(xiàn)RCPSP的調度結果也相應地發(fā)生了改變，各活動的模糊調度時間由原來表2的調度結果變成了表3所示結果，項目最短工期也變?yōu)?179，213，282)；而當α=0.9,1時，項目關鍵路徑由1-3-6-7變?yōu)榱?-2-5-7，此時FRCPSP的調度結果與表3相同。而文獻[5]求解出的項目模糊最短工期為一個固定的模糊數(shù)，并沒有如上述結果所示考慮工期模糊情況下，項目模糊最短工期以及各活動的模糊調度時間可能會發(fā)生改變的問題。

為了驗證所提出的混沌差分進化粒子群算法的尋優(yōu)性能，利用上述算例求解過程中粒子的適應度值來評價比較所提出算法與文獻[15]提出的CDEHPSO算法和標準PSO的優(yōu)化水平。分別用這三種算法對上述算例進行20次測試，這里僅給出α=0.5時的比較結果，如表5所示。從表5可以看出，相比其它兩種算法，所提出的混沌差分進化粒子群算法具有較優(yōu)的搜索性能。

6 結論

本文研究了以項目模糊工期最小為目標的FRCPSP，采用一種改進的基于區(qū)間數(shù)距離測度的模糊取最大運算來比較模糊工期的大小。針對該問題提出的混沌差分進化粒子群算法，能有效維持種群多樣性、避免粒子早熟，能快速求解出不同α-cut值下可能會發(fā)生改變的項目模糊最短工期以及各活動的模糊開始和模糊完成時間，解決了以往研究中忽略的工期模糊情況下，項目模糊最短工期及各活動的模糊調度時間可能會發(fā)生改變的問題。

[1]VANPETEGHEMV,VANHOUCKEM.Anexperimentalinvestigationofmetaheuristicsforthemulti-moderesource-constrainedprojectschedulingproblemonnewdatasetinstances[J].EuropeanJournalofOperationalResearch, 2014, 235(1): 62-72.

[2]吳亞麗, 張立香. 資源受限項目調度的多智能體文化演化算法[J]. 系統(tǒng)工程, 2010, 28(2): 9-16.

WUYali,ZHANGLixiang.Multi-agentculturalevolutionaryalgorithmforresource-constrainedprojectscheduling[J].SystemsEngineering, 2010, 28(2): 9-16.

[3]ATLIO,KAHRAMANC.Resource-constrainedprojectschedulingproblemwithmultipleexecutionmodesandfuzzy/crispactivitydurations[J].JournalofIntelligentandFuzzySystems, 2014, 26(4): 2001-2020.

[4]ZHANGH,XINGF.Fuzzy-multi-objectiveparticleswarmoptimizationfortime-cost-qualitytradeoffinconstruction[J].AutomationinConstruction, 2010, 19(8): 1067-1075.

[5]王宏, 林丹, 李敏強. 求解模糊資源受限項目調度問題的遺傳算法[J]. 系統(tǒng)工程學報, 2006, 21(3): 323-327.

WANGHong,LINDan,LIMinqiang.Applicationofgeneticalgorithminsolvingfuzzyresource-constrainedprojectschedulingproblem[J].JournalofSystemsEngineering, 2006, 21(3): 323-327.

[6]TAPKANP, ?ZBAKlRL,BAYKASOLUA.Solvingfuzzymultipleobjectivegeneralizedassignmentproblemsdirectlyviabeesalgorithmandfuzzyranking[J].ExpertSystemswithApplications, 2013, 40(3): 892-898.

[7]WANGJ.Afuzzyprojectschedulingapproachtominimizescheduleriskforproductdevelopment[J].FuzzySetsandSystems, 2002, 127(2): 99-116.

[8]CHENSP,TSAIMJ.Time-costtrade-offanalysisofprojectnetworksinfuzzyenvironments[J].EuropeanJournalofOperationalResearch, 2011, 212(2): 386-397.

[9]BHASKART,PALMN,PALAK.Aheuristicmethodforrcpspwithfuzzyactivitytimes[J].EuropeanJournalofOperationalResearch, 2011, 208(1): 57-66.

[10]ZHANGH,LIH,TAMCM.Particleswarmoptimizationforresource-constrainedprojectscheduling[J].InternationalJournalofProjectManagement, 2006, 24(1): 83-92.

[11]謝陽, 葉春明, 陳君蘭等. 基于混沌粒子群的資源受限項目調度問題[J]. 工業(yè)工程, 2012, 15(3): 57-61+91.

XIEYang,YEChunming,CHENJunlan,etal.Resource-constrainedprojectschedulingbasedonchaosparticleswamoptimization[J].IndustrialEngineeringJournal, 2012, 15(3): 57-61+91.

[12]彭武良, 郝永平. 求解資源受限項目調度問題的改進粒子群算法[J]. 系統(tǒng)工程, 2010, 28(4): 84-88.

PENGWuliang,HAOYongping.AnimprovedPSOforsolvingresource-constrainedprojectschedulingproblem[J].SystemsEngineering, 2010, 28(4): 84-88.

[13]FAHMYA,HASSANTM,BASSIONIH.ImprovingRCPSPsolutionsqualitywithstackingjustification-applicationwithparticleswarmoptimization[J].ExpertSystemswithApplications, 2014, 41(13): 5870-5881.

[14]何立華，張連營. 改進的模糊網絡關鍵路徑法[J]. 系統(tǒng)工程理論與實踐, 2014, 34(1): 190-196.

HELihua,ZHANGLianying.Animprovedfuzzynetworkcriticalpathmethod[J].SystemsEngineering-Theory&Practice, 2014, 34(1): 190-196.

[15]劉建平. 基于混沌和差分進化的混合粒子群優(yōu)化算法[J]. 計算機仿真, 2012, 29(2): 208-212.

LIUJianping.Hybridparticleswarmoptimizationalgorithmbasedonchaosanddifferentialevolution[J].ComputerSimulation, 2012, 29(2): 208-212.

[16]王凌, 鄭環(huán)宇, 鄭曉龍. 不確定資源受限項目調度研究綜述[J]. 控制與決策, 2014, 29(4): 577-584.

WANGLing,ZHENGHuanyu,ZHENGXiaolong.Surveyonresource-constrainedprojectschedulingunderuncertainty[J].ControlandDecision, 2014, 29(4): 577-584.

[17]TRANL,DUCKSTEINL.Comparisonoffuzzynumbersusingafuzzydistancemeasure[J].FuzzySetsandSystems. 2002, 130(3): 331-341.

[18]KOULINASG,KOTSIKASL,ANAGNOSTOPOULOSK.Aparticleswarmoptimizationbasedhyper-heuristicalgorithmfortheclassicresourceconstrainedprojectschedulingproblem[J].InformationSciences, 2014, 277: 680-693.

[19]倪霖, 段超, 賈春蘭. 差分進化混合粒子群算法求解項目調度問題[J]. 計算機應用研究, 2011, 28(4): 1286-1289.

NILin,DUANChao,JIAChunlan.Hybridparticleswarmoptimizationalgorithmbasedondifferentialevolutionforprojectschedulingproblems[J].ApplicationResearchofComputers, 2011, 28(4): 1286-1289.

A Fuzzy Resource-constrained Project Scheduling Problem Based on the Chaotic Differential Evolution Particle Swarm Optimization Algorithm

A resource-constrained project scheduling problem with fuzzy activity times is studied. By using a fuzzy maximum operator based on measuring interval number distance to compare fuzzy activity times of a project, the proposed method overcomes the shortage of existing works which did not consider the facts that the critical path may change in case of fuzzy activity times. Accordingly, the fuzzy scheduling time of each activity and the shortest fuzzy completion time of the project may also change owing to the changed critical path. Meanwhile, a hybrid particle swarm optimization algorithm based on chaos and differential evolution is introduced to deal with this problem. Furthermore, the inertia weight of the introduced hybrid particle swarm optimization algorithm is improved to solve the above problem. Finally, an example is illustrated to prove the effectiveness of the established model and proposed method.

fuzzy resource constrained project scheduling problem; fuzzy number ranking; particle swarm optimization; chaos; differential evolution

2015- 07- 01

國家自然科學基金資助項目 (71501188)；山東省自然科學基金資助項目(ZR2015GM009)；中央高校基本科研業(yè)務費專項資金資助項目(15CX05007B、15CX04102B)

何立華(1971-)，男，漢族，安徽省人，副教授，博士，主要研究方向為工程項目管理、多目標優(yōu)化.

10.3969/j.issn.1007- 7375.2016.05.006

F224

A

1007-7375(2016)05- 0039- 06