资源时间窗约束下任务可拆分项目调度的Rollout算法研究

摘要

目前资源受限项目调度问题主要对任务不可拆分、资源单技能且全程可得的问题进行研究。随着社会的日益发展，项目工程和资源特性逐渐发生变化，一些关键性资源具有时间窗特性，且具有多技能特征，同时任务的执行允许不连续，可以对任务进行适当拆分。
　　本文分别对单技能和多技能资源时间窗约束下任务可拆分项目调度问题进行研究。首先建立整数规划模型，然后根据模型设计基于优先规则的Rollout算法对问题进行求解，其中在单技能情形下，直接汇总技能提供量和需求量，来判断是否满足资源约束，在多技能情形下，提出贪心策略来判断任务是否满足资源约束，最后使用算例来检验算法的性能，通过设计资源技能矩阵和资源时间窗，将Patterson测试集中110个算例改进为多技能资源时间窗约束下任务可拆分问题，对多组不同的资源技能比例、含时间窗的资源比例和可用时间占比参数下进行实验，来检验参数的灵敏度。
　　实验结果表明在小规模问题上，该算法求取最优解的概率较大，拆分次数比CPLEX软件求解的最优解要少；在中大规模问题上，CPLEX软件无法求解，该算法能在较短时间内得到较优解。同时任务的可拆分性，资源的多技能性均能缩短项目工期。当单技能资源比例较多情形下，参数的灵敏度较大，当单技能资源比例适中或较少时，参数的灵敏度较小。

目录

封面

声明

中文摘要

英文摘要

目录

1绪论

1.1课题来源

1.2研究目的及意义

1.3国内外研究现状

1.4论文的研究内容与组织结构

2.单技能资源时间窗约束下任务可拆分项目调度

2.1引言

2.2问题描述

2.3模型建立

2.4基于优选规则的Rollout算法

2.5算例的测试与结果分析

2.6本章小结

3.多技能资源时间窗约束下任务可拆分项目调度

3.1引言

3.2问题描述

3.3模型建立

3.4 PPSP-CTWMSR的求解

3.5算例的测试与结果分析

3.6本章小结

4.基于Patterson测试集的计算实验

4.1算例设计

4.2结果对比分析

4.3灵敏度分析

4.4本章小结

5.总结与展望

5.1全文总结

5.2研究展望

参考文献

附录1单技能情形下Rollout算法求解结果

附录2灵敏度分析结果

附录3攻读硕士学位期间发表的论文

附录4 攻读硕士学位期间参加的科研项目