资源受限项目调度问题的时间窗分解算法研究

摘要

资源受限项目调度问题是项目管理领域的一类长期受人关注的研究课题，此类问题是各类新的高性能优化方法的实验床。在此类问题的求解中，人们一般会直接利用活动的整体时间窗属性，通过可行解空间的搜索来获取最优调度方案，而在搜索中却忽略了活动的时间窗的可分解特性。通过活动时间窗的分解，可以有效缩小可行解空间，减少搜索过程中的计算量和时间花费，这对求解大规模的资源受限项目调度问题具有重大意义，因此本文对时间窗分解算法进行了创新性的尝试。
　　本研究结合活动时间窗分解的基本思想，首先设计并分析了合适的时间窗分解活动的选择策略与可行解空间分解策略，将原问题可行解空间分解成多个子可行解空间，然后根据重定义方法更新子可行解空间的时间窗，随后基于不同采样策略设置每个子可行解空间的采样规模，最后分别在不同的子可行解空间中进行调度方案的搜索。经过实验对不同策略的检验，本文选取了五种时间窗分解活动的选择策略、三种可行解空间分解策略和两种采样策略进行详细介绍，并对上述策略进行有效组合，通过基于标准案例库PSPLIB的计算实验，分别在J30、J60与J120三组测试集上做了实验分析和对比，广泛地验证了本算法的有效性。
　　实验结果表明，RCPSP的时间窗分解算法在具体案例上能将可行解空间有效降低，并在不同可行解空间分解策略和采样策略下，均相对于未分解的算法在求解时间效率上有显著提高，充分表明了算法的合理性和有效性。此外，本算法具有良好的可拓展性，可嵌套多种启发式算法进一步提高求解效率，这对于未来的研究方向也指出了可行的道路。

目录

封面

声明

中文摘要

英文摘要

目录

1. 绪论

1 .1 引言

1.2 课题背景及研究意义

1.3 国内外相关研究情况概述

1.4 课题研究内容

1.5 论文结构安排

2. 资源受限项目调度问题与时间窗分解算法

2.1 引言

2.2 资源受限项目调度问题模型

2.3 时间窗分解

2.4 基于时间窗分解的搜索算法

2.5 本章小结

3. 时间窗分解算法的关键策略

3.1 引言

3.2 时间窗分解活动选择策略

3.3 基于时间窗分解的子可行解空间重定义策略

3.4 子可行解空间采样策略

3.5 本章小结

4. 计算实验与结果分析

4.1 引言

4.2 算法实验设计

4.3 固定采样规模实验组结果分析

4.4 固定采样时间实验组结果分析

4.5 本章小结

5. 总结与展望

5.1 全文总结

5.2 研究展望

致谢

参考文献

附录1 实验组一结果

附录2 不同项目特征参数下J120进行50000次调度结果

附录3 不同分区算法的平均求解时间比较

附录4 攻读硕士学位期间发表论文目录

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