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

doi:10.3778/j.issn.1002-8331.2009.10.013

计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (10): 40-44.DOI: 10.3778/j.issn.1002-8331.2009.10.013

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

邓林义^1,2,林焰²,金朝光²

1.大连理工大学电信学院，辽宁大连 116024
2.大连理工大学船舶CAD工程中心，辽宁大连 116024

收稿日期:2008-01-15 修回日期:2008-04-18 出版日期:2009-04-01 发布日期:2009-04-01
通讯作者: 邓林义

Priority rule-based particle swarm optimization for RCPSP

DENG Lin-yi^1,2,LIN Yan²,JIN Chao-guang²

1.School of Electronic and Information Engineering，Dalian University of Technology，Dalian，Liaoning 116024，China
2.Ship CAD Engineering Center，Dalian University of Technology，Dalian，Liaoning 116024，China

Received:2008-01-15 Revised:2008-04-18 Online:2009-04-01 Published:2009-04-01
Contact: DENG Lin-yi

摘要/Abstract

摘要： 优先规则是解决大规模资源受限的项目调度问题（Resource-Constrained Project Scheduling Problem，RCPSP）强有力的方法，但是单一的优先规则的往往仅在某些特定的问题上表现出良好的性能。以粒子群算法为基础，提出了基于优先规则编码的粒子群算法（Priority Rule based Particle Swarm Optimization，PRPSO），求解资源受限的项目调度问题。该方法能够通过粒子群算法搜索优先规则和调度生成方案的组合。分别对PRPSO采用串行调度方案、并行调度方案和混合调度方案时，不同任务数和资源强度的问题实例进行了分析。通过对PSPLIB进行测试，结果表明该方法与其它基于优先规则的启发式方法相比有较低的偏差率，因而有较好的性能。

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

Abstract: 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.

Key words: project scheduling, resource-constrained, particle swarm optimization, priority rule

邓林义^1,2,林焰²,金朝光². 采用优先规则的粒子群算法求解RCPSP[J]. 计算机工程与应用, 2009, 45(10): 40-44.

DENG Lin-yi^1,2,LIN Yan²,JIN Chao-guang². Priority rule-based particle swarm optimization for RCPSP[J]. Computer Engineering and Applications, 2009, 45(10): 40-44.

[1]	孙泽宇，徐琛，苏艳超，李传锋，聂雅琳. 雾计算中跨层感知分簇路由协议[J]. 计算机工程与应用, 2021, 57(9): 109-117.
[2]	史春天，曾艳阳，侯守明. 群体智能算法在图像分割中的应用综述[J]. 计算机工程与应用, 2021, 57(8): 36-47.
[3]	朱佳莹，高茂庭. 融合粒子群与改进蚁群算法的AUV路径规划算法[J]. 计算机工程与应用, 2021, 57(6): 267-273.
[4]	李静星，杨有龙. 针对高维数据的马尔科夫毯特征选择[J]. 计算机工程与应用, 2021, 57(6): 58-66.
[5]	胡晓敏，王明丰，张首荣，李敏. 用于文本聚类的新型差分进化粒子群算法[J]. 计算机工程与应用, 2021, 57(4): 61-67.
[6]	王嘉月，史立. 考虑电池损耗的电动冷藏车路径及充电策略[J]. 计算机工程与应用, 2021, 57(24): 283-289.
[7]	陈万芬，王宇嘉，林炜星. 异构集成代理辅助多目标粒子群优化算法[J]. 计算机工程与应用, 2021, 57(23): 71-80.
[8]	杜守信，毋涛. 双种群混合遗传算法的裁剪分床应用研究[J]. 计算机工程与应用, 2021, 57(22): 182-189.
[9]	林炜星，王宇嘉，陈万芬，梁海娜. 基于多因子粒子群的高维数据特征选择算法[J]. 计算机工程与应用, 2021, 57(22): 199-207.
[10]	武哲纬，周世杰，刘启和. 运算资源受限环境下的目标跟踪算法综述[J]. 计算机工程与应用, 2021, 57(21): 24-40.
[11]	梁田，曹德欣. 基于莱维飞行的改进简化粒子群算法[J]. 计算机工程与应用, 2021, 57(20): 188-196.
[12]	李雷孝，邓丹，李杰，王永生. 基于粒子群优化的全比较计算数据分发策略[J]. 计算机工程与应用, 2021, 57(15): 109-117.
[13]	于国龙，赵勇，吴恋，崔忠伟. QPSO算法的改进及其在DBN参数优化中应用[J]. 计算机工程与应用, 2021, 57(10): 154-162.
[14]	廖玮霖，程杉，尚冬冬，魏昭彬. 多策略融合的粒子群优化算法[J]. 计算机工程与应用, 2021, 57(1): 69-76.
[15]	潘成胜，张斌，吕亚娜，杜秀丽，邱少明. 改进灰狼优化算法的K-Means文本聚类[J]. 计算机工程与应用, 2021, 57(1): 188-193.

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

Priority rule-based particle swarm optimization for RCPSP

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics