资源约束下的多项目调度问题研究

论文摘要

资源约束下的多项目调度问题（Resource-Constrained Multi-Project Scheduling Problem,RCMPSP）是一类应用广泛的组合优化问题,RCMPSP是指多项目任务在内部任务逻辑约束和外部有限资源约束的条件下,合理安排两个或以上项目任务的开始和完成时间,从而实现目标函数的优化。这一问题不仅具有丰富的理论研究价值,而且对企业提高资源利用率、缩短项目工期、降低项目管理成本也起着积极的意义,具有巨大的工程价值。现有研究经典资源约束多项目调度问题文献仅利用单一进度计划生成机制生成调度方案,即要么串行调度生成机制,要么并行调度生成机制。然而针对具体的问题实例,无法事先得知两种中哪种进度计划生成机制效果更好,因此,本文提出一种基于自适应编码的改进遗传算法。在染色体的任务列表后加入一个选择进度计划生成机制的基因值。通过遗传操作,效果较好的进度计划生成机制得以存活,另一种则遭到淘汰,使算法能够针对具体问题实例自适应的选择进度计划生成机制,保证调度结果的较优性,使得改进的遗传算法具有自适应性,并设计了与之匹配的遗传操作。经典资源约束下多项目调度问题假定资源在两个任务之间传递不需要额外时间,这与企业实际情况不符。因此,本文明确资源传递时间的定义,提出一个考虑资源传递时间,并以多项目总工期及各个项目工期的加权和最短为目标的考虑资源传递时间的多项目调度数学模型。与基本的资源约束多项目调度问题只考虑资源约束不同,该模型同时考虑资源传递时间约束和资源传递数量约束,并针对模型特点,提出一种基于三级启发式规则解码的改进遗传算法。为了验证两种算法的有效性和资源传递时间的重要性,本文采用一个含有5个子项目的多项目问题实例,针对经典多项目调度问题和考虑资源传递时间的多项目调度问题分别运用本文所提算法进行求解,并将本文算法与其他算法进行比较。通过结果对比说明了资源传递时间的重要性,同时算法结果也证明了本文提出的基于自适应编码的改进遗传算法和基于三级启发式规则解码的改进遗传算法的有效性。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 课题来源
• 1.2 课题研究背景
• 1.3 课题研究目的和意义
• 1.4 资源约束项目调度问题的类型
• 1.5 求解资源约束项目调度问题的算法
• 1.6 资源约束多项目调度问题的研究现状
• 1.7 本文主要工作与结构
• 2 基于改进遗传算法的多项目调度问题
• 2.1 引言
• 2.2 经典资源约束下的多项目调度模型
• 2.3 基于自适应编码的改进遗传算法
• 2.4 本章小结
• 3 考虑资源传递时间的多项目调度问题
• 3.1 引言
• 3.2 考虑资源传递时间的多项目调度模型
• 3.3 基于三级启发式规则解码的遗传算法
• 3.4 本章小结
• 4 算例论证及结果分析
• 4.1 引言
• 4.2 算例介绍
• 4.3 算例结果分析
• 4.4 本章小结
• 5 结果与展望
• 5.1 本文总结
• 5.2 研究展望
• 致谢
• 参考文献
• 附录 攻读学位期间发表学术论文目录