【作者】 吴兵；

【导师】 罗荣桂；

【作者基本信息】 武汉理工大学 ， 管理科学与工程， 2008， 博士

【摘要】 本研究将资源受限的多模式项目调度问题中的可更新资源拓展为柔性资源,建立了柔性资源受限的多模式项目调度问题(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】 Along with the renewable resource in the resource-constrained multi-mode project scheduling problem(RCMPSP) is extended to flexible resource,the mathematic model of the flexible resource-constrained multi-mode project scheduling problem (FRCMPSP) is put forward in this dissertation.FRCMPSP is a strong NP-hard problem in which the jobs of the project are constrained with precedence and flexible resources,every job has several different execution modes and each execution mode has various capability demands and durations,the resource flexibility means resource has various capabilities.FRCMPSP considers the variety of job execution modes and resources’ assignment together.To begin with,the mechanism of PROGEN,which is a benchmark instance generator for the resource-constrained project scheduling problem(RCPSP),is analyzed in detail.Some improvements were made on PROGEN to transfer the benchmark instance for RCPSP to that for FRCMPSP.In addition,to overcome the imperfection of PROGEN,a new benchmark instance generator for FRCMPSP is constructed and named as FGEN.FGEN can generate FRCMPSP benchmark instances with more features.In the next place,the solving methods for FRCMPSP are explored.Enumeration and implicit enumeration algorithms for FRCMPSP are developed in which implicit enumeration algorithm enumerate the identical flexible resource only once.Through the analysis of enumeration and implicit enumeration algorithms,it is found that the bottleneck of solving the FRCMPSP exists in three aspects which are the combinations of jobs’ topological queue,jobs’ execution modes,and unit capabilities’ resource assignment.Then,2500 benchmark instances with 10 non-dummy jobs every project are generated with PROGEN.They are solved with Xpress-MP exactly and the influences of benchmark instances’ parameters on the benchmark instances’ solving difficulty and project makespan are analyzed.Based on the research above, 45 priority-based rules are constructed by the combination of three mode selection rules,five job priority rules and three resource assignment rules.It has been showed that the rule combined with mode with shortest job duration first,job with minimum latest start time first,and resource with minimum capability number first outperforms other ones.Finally,38880 benchmark instances for FRCMPSP are generated with FGEN.A heuristic algorithm is put forward to solve these benchmark instances with the priority rule combined with mode with shortest job duration first,job with minimum latest start time first,and resource with minimum capability number first.The influences of benchmark instances’ parameters on benchmark instances’ solving difficulty and project makespan are discussed,the value of resource flexibility is analyzed and it is pointed out that the value of resource flexibility relies not only on the value of resource flexibility but also the construction of the resource’s capabilities.This research will provide theory basis for the optimum assignment of flexible resource in project management and foundation for the development of relative scheduling software,which will make the capability-based project management come into realization.更多还原