不确定环境下项目调度算法研究

论文摘要

经济和科技的高速发展引起了生产规模的不断扩大,导致了项目调度在整个项目管理过程中的作用也越来越大。一个好的调度方案可以使整个项目管理变得更加高效。一般情况下,影响项目调度的因素主要有每个活动的周期、可用资源量等,而且这些因素在现实生活中往往都是不确定的。因此,不确定环境下项目调度问题就随之而产生了。针对上面提到的问题,本论文主要针对项目调度中存在的不确定因素如不确定的活动周期和可用资源量等,提出了两种在单目标下的解决方案和一种在多目标下的解决方案。首先,本论文采用模糊理论对上述问题进行了研究。模糊理论可以很好的对项目调度问题中的不确定因素进行描述。本论文利用三角隶属函数对不确定的活动周期进行了描述,利用梯形隶属函数对不确定的可用资源量进行了描述及可用性判定,然后给出相应的数学模型和约束条件。其次,本论文先利用启发式算法对不确定环境下项目调度问题进行了求解。在启发式算法中,本论文采用的是串行进度生成机制和最早结束时间的优先规则的方法来生成可执行序列。再次,为了避免启发式算法经常会出现局部最优解的情况,本论文又提出了以遗传算法为基础,通过与模拟退火算法的结合的混合遗传算法的方法对问题模型进行了求解。这种混合遗传算法也很好的克服了遗传算法自身的缺陷,并取得了良好效果,同时在实践中得到了较好的应用。最后,本论文对不确定环境下多目标的调度问题也进行了研究。利用了改进后的NSGA-II算法对问题进行了求解,在传统的算法基础上引入自适应交叉算子和自适应变异算子,并将求得的结果利用模拟退火算法进行进一步提炼。该算法通过在实际中的应用,取得了比较好的效果。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题研究的背景及意义
• 1.2 项目调度问题研究现状
• 1.2.1 传统项目调度问题研究现状
• 1.2.2 多目标优化问题的研究现状
• 1.2.3 模糊项目调度问题的研究现状
• 1.2.4 当前项目调度问题研究中存在的问题
• 1.3 本文的主要研究内容
• 第2章 不确定因素的表示及其相关运算
• 2.1 项目中的不确定因素
• 2.2 项目中不确定因素的表示方法
• 2.2.1 不确定周期的表示方法
• 2.2.2 资源不确定性的表示方法
• 2.3 不确定因素之间的基本运算定义
• 2.3.1 三角模糊数和梯形模糊数的加减法定义
• 2.3.2 模糊数比较的定义
• 2.4 模糊理论的应用
• 2.5 本章小结
• 第3章 基于启发式算法的项目调度问题
• 3.1 问题描述
• 3.2 不确定因素的描述及其可用性判定
• 3.2.1 活动的模糊周期的表示
• 3.2.2 资源不确定性描述及其可用性判定
• 3.3 问题模型
• 3.4 启发式算法
• 3.4.1 优先规则及进度生成机制
• 3.4.2 算法设计
• 3.5 数据实验结果分析
• 3.6 本章小结
• 第4章 不确定环境下的项目调度算法
• 4.1 问题描述
• 4.2 遗传模拟退火算法的设计与应用
• 4.2.1 问题的数学模型
• 4.2.2 遗传模拟退火算法
• 4.2.3 染色体编码和适应度函数
• 4.2.4 交叉
• 4.2.5 变异
• 4.2.6 进化
• 4.2.7 对结果进行模拟退火算法
• 4.3 数据试验
• 4.4 算法分析
• 4.5 本章小结
• 第5章 不确定环境下多目标项目调度算法
• 5.1 问题描述
• 5.2 多目标项目调度问题的混合遗传算法
• 5.3 算法设计
• 5.3.1 编码方案
• 5.3.2 适应度计算
• 5.3.3 遗传算子
• 5.3.4 改进后NSGA-II 和模拟退火算法的实现
• 5.4 数据实验及实验分析
• 5.4.1 数据实验
• 5.4.2 实验分析
• 5.5 本章小结
• 结论
• 参考文献
• 攻读硕士期间发表论文和参加科研情况
• 致谢