Research On The Flexible Resource-Constrained Multi-Mode Project Scheduling Problem

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.