柔性资源受限的多模式项目调度问题研究

论文摘要

本研究将资源受限的多模式项目调度问题中的可更新资源拓展为柔性资源,建立了柔性资源受限的多模式项目调度问题（flexible resource-constrainedmulti-mode proiect scheduling problem,简称FRCMPSP）的数学模型,并证明了该问题是强NP-hard问题。FRCMPSP的主要特点是项目活动具有时序关系约束和柔性资源约束、每个活动具有多种执行模式且每种执行模式对应着不同种类的能力需求和活动工期、资源柔性体现在资源具有多种不同的能力。首先,探讨了已有资源受限的项目调度问题的算例生成器PROGEN的实现机制,对其进行改造以能生成FRCMPSP算例,并针对PROGEN的不足构造了专用于生成FRCMPSP的算例生成器FGEN。FGEN能够根据更多的算例特征参数系统地构造算例。其次,探讨了FRCMPSP的求解方法。设计了该问题的全枚举和隐枚举算法。通过对枚举算法的分析发现FRCMPSP的求解瓶颈存在于3个方面,分别是活动拓扑排序组合、活动执行模式组合以及单位能力柔性资源配置组合。利用PROGEN系统地生成了项目非虚活动数目为10的2500个算例,使用Xpress-MP软件包进行了精确求解,并分析了算例特征参数与算例求解难度和算例项目完工时间之间的关系。在此基础之上,设计了求解FRCMPSP的基于优先规则的三阶段启发式算法,将3种模式选择规则、5种活动优先规则和3种资源配置规则所组合而成的45种启发式规则的求解结果与精确解进行了比较。结果表明活动工期最短模式优先—最小最迟开始时间活动优先—最少能力数资源优先规则是最好规则。再次,使用FGEN系统地构造了38880个FRCMPSP算例,并选取最好规则即活动工期最短模式优先—最小最迟开始时间活动优先—最少能力数资源优先构建了启发式方法对算例进行了求解,进一步探讨了算例特征参数与算例求解难度和算例项目完工时间之间的关系,对资源柔性的价值进行了分析。指出资源柔性的价值大小并不仅仅取决于资源柔性值的大小,更取决于资源能力的结构。本论文的研究能够为项目管理中柔性资源的优化配置提供理论依据,为相关调度软件的开发提供研究基础,进而使得基于能力的项目管理得以实现。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究的背景和意义
• 1.2 研究的理论基础
• 1.2.1 资源受限的项目调度问题研究
• 1.2.2 柔性资源受限的调度问题研究
• 1.3 研究目标、内容、方法及主要创新点
• 1.3.1 研究目标
• 1.3.2 研究内容
• 1.3.3 研究方法
• 1.3.4 主要创新点
• 1.4 本章小结
• 第2章 相关研究述评
• 2.1 引言
• 2.2 国内外相关研究综述
• 2.2.1 Vairaktarakis（2003）的资源受限活动配置问题研究
• 2.2.2 Bellenguez（2006）的多技能员工受限项目调度问题研究
• 2.2.3 Kadrou and Najid（2006）的多技能员工受限多模式项目调度问题研究
• 2.2.4 黄敏镁（2007）的柔性资源受限项目调度问题研究
• 2.2.5 Cordeau等（2008）的技术员和任务调度问题研究
• 2.3 国内外相关研究比较
• 2.4 本章小结
• 第3章 柔性资源受限的多模式项目调度问题建模
• 3.1 引例
• 3.2 柔性资源和资源柔性
• 3.3 问题描述
• 3.4 FRCMPSP的混合整数规划模型
• 3.4.1 离散型FRCMPSP模型
• 3.4.2 连续型FRCMPSP模型
• 3.4.3 FRCMPSP的复杂性
• 3.4.4 模型的扩展
• 3.5 本章小结
• 第4章 算例构造
• 4.1 引言
• 4.2 PROGEN的实现机制
• 4.2.1 PROGEN的结构
• 4.2.2 基本特征参数生成
• 4.2.3 项目网络生成
• 4.2.4 资源需求生成
• 4.2.5 资源可用性生成
• 4.2.6 PROGEN的改造
• 4.3 FGEN的实现机制
• 4.3.1 FGEN的结构
• 4.3.2 FGEN的模块说明
• 4.4 本章小结
• 第5章 FRCMPSP的求解方法
• 5.1 引言
• 5.2 枚举算法
• 5.2.1 程序框架
• 5.2.2 模块说明
• 5.2.3 枚举算法绩效比较
• 5.3 XPress-MP软件精确求解
• 5.3.1 Xpress-MP软件包介绍
• 5.3.2 程序框架
• 5.3.3 模块说明
• 5.3.4 算例参数设置
• 5.3.5 结果分析
• 5.3.6 局限与不足
• 5.4 启发式算法
• 5.4.1 基于优先规则的三阶段启发式算法
• 5.4.2 程序框架
• 5.4.3 模块说明
• 5.4.4 结果分析
• 5.5 本章小结
• 第6章 资源柔性的价值分析
• 6.1 引言
• 6.2 实验设计
• 6.2.1 程序框架
• 6.2.2 模块说明
• 6.2.3 算例特征参数
• 6.3 结果分析
• 6.3.1 算例特征参数与问题求解难度
• 6.3.2 算例特征参数与算例项目完工时间
• 6.3.3 资源能力结构与算例项目完工时间
• 6.4 本章小结
• 第7章 全文总结与研究展望
• 7.1 全文总结
• 7.2 研究展望
• 参考文献
• 致谢
• 附录1:FGEN程序组
• 附录2:枚举算法程序组
• 附录3:Xpress-MP精确求解程序组
• 附录4:启发式算法程序组
• 附录5:资源柔性的价值分析实验程序组
• 附录6:攻读博士学位期间发表的学术论文
• 附录7:攻读博士学位期间参与的科研课题与获奖