基于依赖结构矩阵的资源受限项目调度优化

《基于依赖结构矩阵的资源受限项目调度优化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、浙江大学硕士学位论文基于依赖结构矩阵的资源受限项目调度优化姓名：李菲申请学位级别：硕士专业：管理科学与工程指导教师：寿涌毅2013-01-21浙江大学硕士学位论文摘要摘要本文的研究对象是资源受限项目调度问题(RCPSP)的一个扩展问题，“存在任务交叠和迭代的资源受限项目调度问题”。在现实的项目运作中，任务在执行过程中往往存在一定的交叠性，任务并非需要完全结束才能输出信息流，同时，任务也并非在执行初始就需要其他任务输入的信息流。另外在项目执行过程中，所有的任务均一次执行达标的情况颇为少见，大部分项目都会有或多或少的返工情况存在。对于这一类广泛存

2、在的项目，若仍然忽略其交叠性和返工情况，而采用经典的资源受限项目调度问题的调度方法，得到的调度安排并不准确，且资源的利用率也不能达到理想的状况，对于现实项目运作的指导意义也较为有限。因此，探索适合于这类问题的调度模型和求解方法，对于拓展项目调度思想在项目实际运作中的应用有重要意义。本文在已有的研究基础上，构建了完整的存在任务交叠和返工的RCPSP问题的调度模型，并设计了适用于这一问题的工期计算方法，最终设计遗传算法求解。首先，本文从信息流的角度描述任务之间的关系，以依赖结构矩阵(DSM)为基础来构建调度模型。使用信息流矩阵、输入时间因子矩阵、

3、信息流持续矩阵、输出时间因子矩阵以及返工概率矩阵这五个矩阵来描述问题并构建模型。信息流矩阵描述任务之间的信息流关系；输入时间因子矩阵和输出时间因子矩阵描述任务的交叠性；信息流持续矩阵描述任务之间的信息流传递所需时间；返工概率矩阵描述任务之间的返工信息流以及返工发生的概率。随后，本文设计了两种不同的工期计算方法：放弃返工部分的工期计算和不放弃返工部分的工期计算。放弃返工部分的工期计算是认为在某项任务收到信息流确定需要返工时，该返工信息流涉及到所有任务的尚未执行部分将被放弃，直接安排这些任务重新执行，即开始返工的时刻为信息流被接收到的时刻；不放弃

4、返工部分的工期计算是在某项任务确认造成其他返工后，继续执行该任务直至该任务执行完成，再重新安排需返工的任务重新执行，即开始返工的时刻为输出信息，流的任务完全结束后的时刻。进行这两种设计的考虑是，在不考虑任务交叠的项目调度中，信息流完成传递的时间即是任务完成的时间，返工的时刻则为信息1II浙江大学硕士学位论文流输出任务完全结束时的时刻，而在本文的研究问题下，两个时刻是不相同的。我们可以想象，一般的存在任务交叠的项目操作中，在某项任务确认需要返工后，其后序为执行部分一般不会再继续进行，而是直接开始需要返工的任务。我们设置两种工期计算方法，希望能够

5、测试放弃返工部分是否能够节省时间，缩短工期，提高资源利用率。本文在一个示例上的测试和大规模试验都表明此项假设成立。最后我们设计了遗传算法，来求解存在任务交叠和返工的资源受限项目调度问题。由于返工的存在，项目工期无法确定为一个数值，故本文的遗传算法目标函数设定为项目平均总工期最小化。项目平均总工期由多次蒙特卡洛模拟求出。我们设计了八种不同配置的遗传算法，实验部分使用这八种算法求解自行设计的算例，算法均表现除了较好的收敛性，并求得了较好的结果。采用非参数检验对比八种遗传算法的求解效果，结果显示八种算法的求解效果相差不大。本文的成果具有理论和实践意

6、义，将依赖结构矩阵引入到资源受限项目调度问题的调度优化中，构建了存在任务交叠与返工的资源受限项目调度模型，丰富了资源受限项目调度问题的研究内容，并拓展了依赖结构矩阵的应用领域；本文所构建的存在任务交叠与返工的资源受限项目调度模型能够用于许多实际项目的进度管理决策中，扩展了项目调度思想的应用范围。关键词：项目调度；依赖结构矩阵；任务交叠；任务返工；蒙特卡罗模拟；遗传算法AbstractTheresearchsubjectofthispaperisrelatedtOoneoftheextensionissuesofclassicresource。

7、constrainedprojectschedulingproblem，namelyresource．constrainedprojectschedulingproblemwithactivityoverlappinganditeration．Inmostrealprojectsjactivitiesareoverlappedtocompressdurationandreworkoriterationisalsoquitecommon．Scheduleswithoutconsideringoverlappingandreworkbetween

8、activitiesarenotaccuratethatcouldnotmakemeaningfulcontributetoprojectoperationinmo