采用优先规则的粒子群算法求解RCPSP  

Priority rule-based particle swarm optimization for RCPSP

作　　者：邓林义[1,2] 林焰[2] 金朝光[2] 

机构地区：[1]大连理工大学电信学院,辽宁大连116024 [2]大连理工大学船舶CAD工程中心,辽宁大连116024

出　　处：《计算机工程与应用》2009年第10期40-44,共5页Computer Engineering and Applications

摘　　要：优先规则是解决大规模资源受限的项目调度问题(Resource-Constrained Project Scheduling Problem,RCPSP)强有力的方法,但是单一的优先规则的往往仅在某些特定的问题上表现出良好的性能。以粒子群算法为基础,提出了基于优先规则编码的粒子群算法(Priority Rule based Particle Swarm Optimization,PRPSO),求解资源受限的项目调度问题。该方法能够通过粒子群算法搜索优先规则和调度生成方案的组合。分别对PRPSO采用串行调度方案、并行调度方案和混合调度方案时,不同任务数和资源强度的问题实例进行了分析。通过对PSPLIB进行测试,结果表明该方法与其它基于优先规则的启发式方法相比有较低的偏差率,因而有较好的性能。In this paper,the Resource-Constrained Project Scheduling Problem（RCPSP） and makespan minimization are considered as objective.A new Particle Swarm Optimization（PSO） approach is presented to solve this problem.The particle representation is based on priority rules.The potential solution to the RCPSP is a sequence of priority rules deciding the order of scheduling the non-dummy activities,and is represented by the multidimensional particle position.Hence PSO is applied to search the optimal schedule for the RCPSP,in which three schedule generate schemes are adopted to transform the particle-represented priority rule to a schedule.Computational analyses are represented to verify the effective of the proposed methodology.

关 键 词：项目调度 资源受限 粒子群 优先规则 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]