基于分散缓冲的鲁棒项目调度问题研究

摘要

大多数传统的项目调度研究都是在一个确定性环境下进行的，即活动持续时间和资源需求等参数都是唯一的。然而，实际的项目环境充满了不确定性、干扰和风险，基于确定参数制定的进度计划在执行时，可能会与预期产生较大偏差，甚至变得不可行。鲁棒项目调度作为解决不确定环境下项目调度问题的有效方法，其目标是产生一个具有较高的稳定性、并具有一定抵抗不确定因素能力的调度计划。
　　本文首先对已有的鲁棒性项目调度问题进行总结和归纳。然后建立基于分散缓冲的鲁棒性项目调度基本模型，采用鲁棒偏差性成本衡量计划的鲁棒性。为了描述不确定参数，简要介绍不确定理论后，使用不确定变量表示不确定工期，并采用一种不确定模拟的方法计算鲁棒性计划求解过程中涉及到的多种不确定变量，如活动实际开始时间、活动实际与计划的偏差成本。分散缓冲是基于工期最短的基准调度计划，在各个活动开始时间之前插入。为了解决分散缓冲插入过程中出现的资源冲突问题，提出一种改进的资源流网络构建启发式算法，然后设计改进的模拟退火算法优化分散缓冲大小。实验选取PSPLIB标准数据库中的算例，通过控制不同的不确定水平、项目截止日期与边际成本获得实际项目数据，测试改进的资源流网络算法与改进的模拟退火算法能否有效制定出基于分散缓冲的鲁棒性计划。实验表明，改进的资源流网络与模拟退火分散缓冲算法可以制定较稳健的鲁棒性计划。
　　实际的项目管理更多情况下是多目标决策问题，本文建立工期最小化与鲁棒性成本最小化的双目标鲁棒性调度模型，并使用改进的多目标进化算法NSGA-Ⅱ求解。根据支配关系和拥挤距离对可行解排序，改进种群更新策略，并提出一种局部搜索算子提高算法的优化能力。实验采用Hypervolume指标测试改进的算法能否提高帕累托最优解的质量，并设计其他指标测试多目标进化算法求得最优解的质量。实验表明，所设计算法可以求得较好的帕累托最优解。

目录

声明

摘要

1．1．1 选题背景

1．1．2 研究意义

1．2 国内外研究现状

1．3 研究内容和文章结构

第2章 鲁棒性项目调度理论基础

2．1 基于分散缓冲的鲁棒性调度问题

2．1．1 问题描述

2．1．2 鲁棒性目标

2．1．3 求解方法

2．2 基于不确定理论处理活动工期

2．2．1 不确定测度

2．2．2 不确定变量的期望值

2．2．3 不确定变量的熵

2．2．4 不确定活动工期

2．3 基于不确定理论的鲁棒性调度

2．3．1 基准计划生成与资源流网络构建

2．3．3 鲁棒性目标函数替换公式

2．3．4 采用不确定模拟计算鲁棒性目标

2．4 本章小结

第3章 资源流网络与分散缓冲优化算法

3．1 基于鲁棒性成本最小化的鲁棒性调度模型

3．2 现有文献的资源流网络算法

3．2．1 Artigues算法

3．2．2 MEPC算法

3．3 基于MEPC改进的资源流网络启发式算法

3．3．1 改进思路

3．3．2 算法步骤

3．4 仿真实验

3．4．1 仿真算例生成设计

3．4．2 结果分析

3．5 现有文献的分散缓冲算法

3．5．1 STC指标分散缓冲法

3．5．2 禁忌搜索算法

3．6 改进的模拟退火分散缓冲算法

3．6．1 算法思路

3．6．2 算法步骤

3．7 仿真实验

3．7．1 实验设计

3．7．2 结果分析

3．8 本章小结

第4章 基于分散缓冲的双目标鲁棒性调度

4．1 基于工期和鲁棒性的双目标鲁棒性调度模型

4．2 传统的NSGA-Ⅱ多目标进化算法

4．2．1 个体表示与初始种群

4．2．2 非支配排序

4．2．3 拥挤距离计算

4．2．4 遗传操作

4．2．5 种群更新策略

4．3．2 局部搜索算子

4．3．3 算例分析

4．4 仿真实验

4．4．1 Hypervolume指标测试

4．4．2 帕累托最优解测试

4．5 本章小结

第5章 研究成果和结论

参考文献

致谢