基于混沌差分进化粒子群算法的模糊资源受限项目调度问题

何立华， 马芳丽



基于混沌差分进化粒子群算法的模糊资源受限项目调度问题

何立华， 马芳丽

(中国石油大学(华东) 经济管理学院，山东 青岛 266580)

本文研究了工期模糊情况下的资源受限项目调度问题，采用一种基于区间数距离的模糊取最大运算比较模糊工期的大小，解决了以往研究中忽略的工期模糊情况下，项目关键路径可能会发生改变，相应地各活动的模糊调度时间以及项目的模糊最短工期也可能随之发生改变的问题。引入一种基于混沌和差分进化的混合粒子群优化算法，并对算法的惯性权重进行改进来求解上述问题。通过一个算例验证了所建立模型及提出方法的有效性。

模糊资源受限项目调度问题； 模糊数排序； 粒子群算法； 混沌； 差分进化

HE Lihua, MA Fangli

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

资源受限项目调度问题(resource constrained project scheduling problem, RCPSP)研究在满足一定的时序约束和资源约束条件下，安排各项任务的开始和完成时间，以实现项目的特定目标[1]。在任务工期确定的情况下，对RCPSP的研究已经取得了大量的成果[2]。然而实际环境中，项目往往受一些不确定因素的影响，使得项目工期具有模糊性，从而引出了对模糊资源受限项目调度问题(fuzzy resource constrained project scheduling problem, FRCPSP)的研究[3]。

在FRCPSP的调度过程中，考虑到任务的时序约束，需要对任务的模糊工期进行比较，因此，许多模糊数弱比较方法被应用于FRCPSP的求解中。文献[4]采用PERT技术，文献[5]采用重心距离法和积分值法将模糊工期转化为精确值。文献[6]提出用积分值法、符号距离法以及基于面积的排序方法进行模糊数之间的排序比较运算。文献[7]利用可能性测度和必然性测度衡量任务模糊工期，并通过比较二者的权重和来确定两个模糊工期的大小。文献[8]计算出不同置信水平下模糊工期的下限和上限值，将其分别代入精确模型来求解问题。文献[9]基于一种区间数距离的排序方法比较模糊工期。上述文献采取了不同的方法来比较项目模糊工期的大小，对FRCPSP的求解均做出了贡献。但是这些方法都未考虑到任务工期模糊的环境下，项目关键路径有可能发生改变，各活动的模糊调度时间以及项目的模糊最短工期也可能随之相应地发生改变的问题。

另一方面，在算法求解过程中，由于粒子群优化方法(particle swarm optimization, PSO)易于实施，能快速得到问题的解，是有效解决FRCPSP的一种群智能算法[10]。但是传统PSO由于算法自身的局限性，容易出现粒子早熟现象，使算法陷入局部最优。针对传统PSO的诸多不足，文献[11]将混沌算法嵌入PSO中，通过对比粒子群和混沌算法返回的全局极值大小，不断更新算法的全局极值，避免算法陷入局部极小值。文献[12]引入向量相似度法建立粒子速度的更新模型。文献[13]将重叠对齐技术引入到粒子调度生成机制中，改进了搜索过程中解的质量。上述方法分别从避免算法陷入局部极值以及提高迭代过程中解的质量方面对PSO进行改进，有效改善了算法的全局搜索能力。但是这些方法的优化结果与理想结果之间仍存在一定的差距。

为了解决上述问题，本文采用文献[14]提出的一种改进的模糊取最大运算来比较模糊工期的大小。同时，为了进一步提高求解这一问题的PSO的全局搜索能力，本文针对文献[15]提出的基于混沌和差分进化的混合粒子群优化算法，通过对算法惯性权重进行动态调整改进，将其引入到FRCPSP的求解中。

1 模糊资源受限项目调度问题

FRCPSP的数学模型如下所示[16]：

(1)

(2)

(3)

其中，式(1)为目标函数，表示项目的模糊工期取最小；式(2)为活动间的时序约束；式(3)为活动的资源约束。

2 模糊数排序

由于上述模型中式(1)目标函数表示的项目工期为模糊数，式(2)所示时序约束中要确定任意活动的模糊开始时间也要比较其所有紧前活动的模糊完成时间，这都需要比较两个模糊数之间的大小。针对这一问题，本文引入一种改进的基于区间数距离测度的模糊取最大运算[14]来比较模糊数间的大小，解决了以往研究中忽略的工期模糊情况下，项目关键路径有可能发生改变，相应地FRCPSP最终调度结果中项目的模糊最短工期以及各活动的模糊调度时间也可能随之发生改变的问题。

(4)

(5)

(6)

(7)

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

本文将文献[15]提出的基于混沌和差分进化的混合粒子群优化算法(chaos and differential evolution particle SWARM optimization algorithm, CDEHPSO)引入到FRCPSP的求解中，该算法利用混沌技术初始化种群，基于一种早熟判断机制识别出早熟粒子，并对其进行差分变异、交叉和选择以维持种群多样性。为了进一步提高算法的优化性能，本文对算法惯性权重进行动态调整改进，提出了混沌差分进化粒子群算法。

3.1 标准粒子群算法

PSO的数学描述如下：设种群规模为M，搜索空间维数为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]之间的随机数，t为迭代数，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映射的初始值，根据式(10)得到混沌序列hn+1,j(μ为控制参数)：

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

(10)

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

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

(11)

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

2)惯性权重更新策略

在迭代初期，算法惯性权重w取值应该较大，使算法进行全局搜索，迭代后期w取值应该较小，使算法快速收敛。针对这一问题，本文在文献[15]所提出算法的基础上引入一种非线性动态自适应惯性权重更新策略[19]，其计算过程如下所示：

(12)

其中，t为当前迭代数，tmax为最大的迭代次数，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为变异规模因子，Cr为交叉概率，zi,j(t+1)代表变异向量，ui,j(t+1)代表试验向量，randj是0到1之间均匀分布的一个数，rnb(i)是从1到N之间随机选择的数。

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

本文采用基于活动优先值的粒子表示方式，同时，FRCPSP的调度生成机制有并行和串行两种方法，串行方法生成的是积极计划，并行方法生成的是非延迟计划，但其有可能会错过最优解[12]，因此为了保证解的质量，本文采用串行调度生成机制，将由活动优先值表示的粒子转化为可行调度。

4.1 粒子表示方式

将每一个N维粒子与项目的N个活动相对应，用粒子位置向量Xi(t)=(xi1(t),xi2(t),…,xiN(t))的N个参数值分别表示项目N个活动调度的优先值。

4.2 串行调度生成机制

1)设CS是已排列的活动集合，DS是没有参加排列的活动集合。初始条件下，CS=Ø，DS=(1,2,…,N)。对各活动优先值进行降序排列，选择优先值最大的活动进行时序约束判断，若满足则进行下一步；不满足，则按优先值大小选择下一个活动判断，直到找出一个满足时序约束的活动为止；

2)对所选活动进行资源约束判断，判断所选活动能否与已安排活动并行调度，可以则转下一步；不行，则将该活动安排到CS中，计算该活动的模糊开始时间，更新CS和DS，并返回第1)步；

3)对上一步所选活动进行并行调度安排，根据式(7)比较各活动模糊工期大小，确定该活动的模糊开始时间，并将其安排到CS中，更新CS和DS，返回第 1)步，直到安排完所有活动。

4.3 算法参数调整

在迭代过程中，为了避免不可行的粒子位置以及粒子由于速度过大运动到可行搜索空间的外部，对粒子的位置向量和速度向量进行调整，如下所示。

(18)

(19)

4.4 FRCPSP的求解步骤

步骤2 令t=t+1，根据 式(12)计算当前迭代次数下的惯性权重w(t)值，再根据 式(8)和(9)更新粒子的速度和位置，并根据 式(18)和(19)对其进行调整；

步骤4 根据公式(15)、(16)和(17)，对早熟粒子进行差分变异、交叉和选择操作；

步骤5 将由优先值表示的粒子转化为可行调度，得出项目模糊工期大小。根据式(7)计算出各粒子适应度值，更新此代粒子lbesti(t)和gbest(t)；

步骤6 检查算法是否满足终止条件，若满足则停止迭代，输出此时的最优解，否则，转到步骤2继续搜索最优解。算法整体流程如图1所示。

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

5 算例分析

图2 某项目网络图

活动紧前工作模糊持续时间所需资源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时，FRCPSP最终调度结果

表3 α=0.5, 0.6, 0.7, 0.8时，FRCPSP最终调度结果

表4 α=0.9, 1时，FRCPSP最终调度结果

表5 α=0.5时本文所提出算法与CDEHPSO以及PSO的算法性能比较

根据表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，FRCPSP的调度结果也相应地发生了改变，各活动的模糊调度时间由原来表2的调度结果变成了表3所示结果，项目最短工期也变为(179，213，282)；而当α=0.9,1时，项目关键路径由1-3-6-7变为了1-2-5-7，此时FRCPSP的调度结果与表3相同。而文献[5]求解出的项目模糊最短工期为一个固定的模糊数，并没有如上述结果所示考虑工期模糊情况下，项目模糊最短工期以及各活动的模糊调度时间可能会发生改变的问题。

为了验证所提出的混沌差分进化粒子群算法的寻优性能，利用上述算例求解过程中粒子的适应度值来评价比较所提出算法与文献[15]提出的CDEHPSO算法和标准PSO的优化水平。分别用这三种算法对上述算例进行20次测试，这里仅给出α=0.5时的比较结果，如表5所示。从表5可以看出，相比其它两种算法，所提出的混沌差分进化粒子群算法具有较优的搜索性能。

6 结论

本文研究了以项目模糊工期最小为目标的FRCPSP，采用一种改进的基于区间数距离测度的模糊取最大运算来比较模糊工期的大小。针对该问题提出的混沌差分进化粒子群算法，能有效维持种群多样性、避免粒子早熟，能快速求解出不同α-cut值下可能会发生改变的项目模糊最短工期以及各活动的模糊开始和模糊完成时间，解决了以往研究中忽略的工期模糊情况下，项目模糊最短工期及各活动的模糊调度时间可能会发生改变的问题。

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

[2]吴亚丽, 张立香. 资源受限项目调度的多智能体文化演化算法[J]. 系统工程, 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]. 系统工程学报, 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]. 工业工程, 2012, 15(3): 57-61+91.

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

[12]彭武良, 郝永平. 求解资源受限项目调度问题的改进粒子群算法[J]. 系统工程, 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]. 系统工程理论与实践, 2014, 34(1): 190-196.

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

[15]刘建平. 基于混沌和差分进化的混合粒子群优化算法[J]. 计算机仿真, 2012, 29(2): 208-212.

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

[16]王凌, 郑环宇, 郑晓龙. 不确定资源受限项目调度研究综述[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)；中央高校基本科研业务费专项资金资助项目(15CX05007B、15CX04102B)

何立华(1971-)，男，汉族，安徽省人，副教授，博士，主要研究方向为工程项目管理、多目标优化.

10.3969/j.issn.1007- 7375.2016.05.006

F224

A

1007-7375(2016)05- 0039- 06