资源受限的项目调度问题及其应用研究

论文摘要

资源受限的项目调度问题（Resource-Constrained Project Scheduling Problem,RCPSP）是运筹学领域的一个重要分支,它要求在满足项目时序约束和资源约束的条件下,安排所有任务的开始时间和结束时间,以达到工期最短、资源均衡、代价最小等目标。本文针对RCPSP的三个分支（经典的项目调度问题、任务可拆分项目调度问题以及多项目调度问题）进行了研究,取得了较好的结果。针对经典的资源受限的项目调度问题,本文提出了一种根据粒子适应值的变化动态调整惯性权重的粒子群算法,对标准粒子群算法（Particle Swarm Optimization,PSO）的惯性权重的调整策略进行改进。在此基础上给出了基于优先数编码的粒子群算法（PrirorityValue Based Particle Swarm Optimization,PVPSO）与基于优先规则编码的粒子群算法（Prirority Rule Based Particle Swarm Optimization,PRPSO）。其中PVPSO算法采用了一种启发式信息与随机信息相结合的初始化方法,比全部采用随机信息的初始化方法所选取的初始种群效果更好。PRPSO以粒子群算法为基础,搜索求解RCPSP问题最优优先规则组合。本文还提出了一种基于任务列表的混合粒子群算法（Permuation Based ParticleSwarm Optimization,PEPSO）,该算法将遗传算法中的单点交叉引入到粒子的更新过程中,通过增加粒子的局部搜索技术帮助粒子跳出局部最优解。在PSPLIB测试集上的实验表明,与其他启发式算法相比,本文给出的算法PVPSO、PRPSO与PEPSO与本问题国内外其它同类算法相比,最短工期的平均偏差率均较低。针对允许通过任务拆分以缩短工期的资源受限的项目调度问题,本文采用PEPSO算法对Patterson问题集进行了测试,结果表明PEPSO算法能有效地缩短项目的偏差率。为进一步解决经典的任务不可拆分的项目调度问题,本文提出了一种基于虚拟任务拆分预测的PWiest方法,与优先规则、粒子群算法和蚁群算法等智能优化方法相结合,有效改进了算法的性能,PSPLIB集上的测试结果表明新算法能够进一步降低算法的偏差率。针对无耦合任务的多项目调度问题,本文提出了基于迭代的拓扑优化方法,根据项目网络结构的特点进行任务调度,在任务的调度过程中综合考虑任务的各种信息,如项目资源的影响,后续任务影响、关键路径任务优先以及最小空闲时间等优先规则。通过实例测试结果表明,该方法与其它启发式方法相比能得到更短的工期。对含有耦合任务的多项目调度问题,本文采用设计结构矩阵（Design Structure Matrix,DSM）表示含有耦合信息的任务之间的关系,给出了基于信息量对DSM中的耦合集进行解耦的方法。针对实际设计任务调度的特点,结合耦合信息的割裂方法和迭代拓扑优化方法,提出了求解含有耦合关系的多项目调度问题的拓扑优化方法。并将该方法应用到船舶设计任务调度系统中。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 选题意义
• 1.2 问题提出和分类
• 1.3 经典项目调度问题研究概况
• 1.3.1 精确求解方法
• 1.3.2 启发式方法
• 1.4 任务可拆分项目调度问题研究概况
• 1.5 多项目调度问题研究概况
• 1.6 船舶设计任务调度研究概况
• 1.7 论文的研究内容
• 2 粒子群算法求解RCPSP
• 2.1 资源受限的项目调度问题
• 2.1.1 数学模型
• 2.1.2 测试集
• 2.1.3 调度生成方案比较
• 2.1.4 RCPSP算法评价标准
• 2.2 粒子群算法
• 2.2.1 粒子群算法的基本定义
• 2.2.2 算法模型
• 2.2.3 粒子群算法当前研究重点
• 2.2.4 RCPSP中粒子表示方法研究
• 2.3 PVPSO
• 2.3.1 粒子优先数表示方法
• 2.3.2 动态惯性权重
• 2.3.3 实验结果
• 2.4 PRPSO
• 2.4.1 粒子优先规则表示方法
• 2.4.2 调度生成方案
• 2.4.3 粒子更新方式与参数设置
• 2.4.4 实验结果
• 2.5 PEPSO
• 2.5.1 粒子任务列表表示方法
• 2.5.2 粒子更新方式
• 2.5.3 局部搜索技术
• 2.5.4 PEPSO算法框架
• 2.5.5 实验结果
• 2.6 算法性能分析
• 2.7 本章小结
• 3 粒子群算法求解任务可拆分的RCPSP
• 3.1 数学模型
• 3.2 调度拆分
• 3.2.1 项目工期下界计算方法
• 3.2.2 调度的关键路径
• 3.3 任务的可拆分调度
• 3.3.1 拆分任务选择
• 3.3.2 任务的拆分方式
• 3.4 PEPSO求解任务可拆分的项目调度问题
• 3.4.1 粒子表示
• 3.4.2 调度生成方案
• 3.5 实验结果
• 3.6 本章小结
• 4 改进的Wiest调整法
• 4.1 Wiest调整法
• 4.2 带有预测的Wiest调整法
• 4.3 实验设计
• 4.3.1 优先规则
• 4.3.2 粒子群算法
• 4.3.3 蚁群算法
• 4.3.4 人工免疫算法
• 4.4 实验结果及讨论
• 4.4.1 优先规则结果
• 4.4.2 粒子群算法结果
• 4.4.3 蚁群算法结果
• 4.4.4 人工免疫算法结果
• 4.4.5 Pwiest调整法性能分析
• 4.5 本章小结
• 5 迭代的拓扑优化算法求解RCMPSP
• 5.1 数学模型
• 5.2 基于迭代的拓扑优化算法
• 5.3 问题实例
• 5.4 本章小结
• 6 船舶设计任务调度
• 6.1 船舶设计过程概述
• 6.1.1 船舶设计阶段
• 6.1.2 船舶设计任务特点
• 6.2 设计结构矩阵
• 6.2.1 任务关系
• 6.2.2 划分
• 6.2.3 割裂
• 6.2.4 DSM在船舶流程优化中的应用实例
• 6.3 船舶设计任务初步调度
• 6.3.1 带有耦合关系的拓扑优化算法
• 6.3.2 问题实例
• 6.4 船舶设计任务动态调度
• 6.4.1 船舶设计任务调度特点
• 6.4.2 船舶设计任务动态调度
• 6.4.3 船舶设计任务与管理系统原型
• 6.5 本章小结
• 7 总结与展望
• 7.1 总结
• 7.2 展望
• 创新点摘要
• 参考文献
• 附录A 调度生成方案
• A.1 串行调度生成方案
• A.2 并行调度生成方案
• 附录B 若干优先规则计算方法
• 攻读博士学位期间发表学术论文情况
• 攻读博士学位期间参加的科研项目
• 致谢