论文摘要
资源受限项目调度问题（RCPSP）是一类重要的调度问题,它要求在满足项目时序约束和资源约束的条件下,安排所有工作的开工期和完工期,以达到某一最优的目标。该问题理论上属于NP-hard问题,许多组合优化问题是RCPSP的特殊情形。因此研究RCPSP具有重要的理论和现实意义。本文主要研究求解资源受限项目调度问题的改进遗传算法。首先,结合文化算法的双层结构和多智能体进化算法的演化优势以及遗传算法的灵活编码方式,提出一种求解资源受限项目调度问题的混合遗传算法—多智能体文化遗传算法。算法设置了上层信仰空间和下层群体空间,各空间内智能体通过与其邻域进行竞争、合作操作及自学习操作来增加自身的能量,空间之间的交互是定期通过接受操作和影响操作采用同步传输方式来完成,同时为测试算法的通用性,选择了多个标准测试函数进行了仿真。结果表明：多智能体文化遗传算法（MACGA）不仅能够有效地跳出局部最优,而且具有较高的的收敛速度。其次,将各算法应用到经典资源受限项目调度问题中,算法采用十进制编码方式,结合工作的存储邻接矩阵随机生成调度序列,有效地解决了工作调度违例现象。运用优先抢占模式的资源分配方式,来安排工作资源,从而避免了资源分配中的冲突问题。本文以准数据库PSPLIB中的经典资源受限项目调度问题为例进行仿真,验证各算法的稳定性和有效性。最后,考虑到实际项目中各工作执行时往往有多种执行模式可供选择,因此将各算法应用到多模式资源受限项目调度问题中。由于一种模式代表一组资源需求量及相应执行时间的组合,不同的执行时间对应不同的资源投入量,本文采用二维编码方式,并定义了算法中的各操作。通过对标准数据库PSPLIB中的多模式资源受限项目调度问题的仿真,结果表明：此算法不仅具有很好的收敛特性,而且运行速度快,是一种求解大规模调度问题的有效算法。
论文目录
摘要Abstract1 绪论1.1 研究背景及意义1.2 资源受限项目调度问题研究现状1.2.1 经典资源受限项目调度问题的研究现状1.2.2 多模式资源受限项目调度问题的研究现状1.3 论文研究的内容1.3.1 论文的研究内容1.3.2 论文的组织结构2 资源受限项目调度问题基本理论2.1 资源受限项目调度问题概述2.2 资源受限项目调度问题分类2.2.1 按资源类型分类2.2.2 按项目调度目标分类2.2.3 按模型分类2.3 资源受限项目调度问题模型及参数介绍2.3.1 经典资源受限项目调度问题2.3.2 多模式资源受限项目调度问题2.3.3 资源受限项目调度问题的基本定义和定理2.4 求解资源受限项目调度问题的方法2.4.1 精确最优调度方法2.4.2 基于优先规则的方法2.4.3 智能优化方法2.5 本章小结3 基于文化遗传算法的经典资源受限项目调度问题研究3.1 遗传算法原理3.1.1 遗传算法基本思想3.1.2 遗传算法的结构3.2 改进遗传算法—文化遗传算法3.2.1 文化算法3.2.2 基于文化算法的改进—文化遗传算法3.3 求解经典资源受限项目调度问题的文化遗传算法3.3.1 CGA求解经典RCPSP的编码设计3.3.2 工作调度序列的生成3.3.3 适应度函数设计3.3.4 CGA求解经典RCPSP的进化策略3.3.5 CGA求解经典RCPSP的解码设计3.3.6 求解经典RCPSP的文化遗传算法3.4 实例仿真及结果分析3.5 本章小结4 基于多智能体文化遗传算法的经典资源受限项目调度问题研究4.1 多智能体进化算法的原理及结构4.2 混合遗传算法—多智能体文化遗传算法4.2.1 多智能体文化遗传算法框架4.2.2 算法性能测试4.3 求解经典资源受限项目调度问题的多智能体文化遗传算法4.3.1 求解经典RCPSP的编码设计4.3.2 求解经典RCPSP的进化策略4.3.3 求解经典RCPSP的解码设计4.3.4 求解经典RCPSP的多智能体文化遗传算法4.4 实例仿真及结果分析4.5 本章小结5 基于改进遗传算法的多模式资源受限项目调度问题研究5.1 基于文化遗传算法的MRCPSP5.1.1 求解MRCPSP的编码设计5.1.2 求解MRCPSP的适应值函数设计5.1.3 CGA求解MRCPSP的进化策略5.1.4 CGA求解MRCPSP的解码设计5.2 基于多智能体文化遗传算法的MRCPSP5.2.1 MACGA求解MRCPSP的进化策略5.2.2 MACGA求解MRCPSP5.3 实例仿真及结果分析5.4 本章小结6 总结与展望6.1 总结6.2 未来研究方向参考文献致谢硕士期间发表的学术论文
相关论文文献
标签：项目调度论文; 资源受限论文; 遗传算法论文; 多智能体进化算法论文; 文化算法论文;
