Research On The Simulation Optimization Method For The Resource-constrained Project Scheduling Problem And Its Application

Resource-constrained project scheduling problem (RCPSP) is an NP-hard problem and concerned with production, construction and science projects, where scarce resources have to be allocated to dependent activities over time. The aim of RCPSP is to minimize the project duration with the precedence constraints and resource constraints. It is very important for the prediction of project duration and the arrangement of project activities. In this dissertation, the research content is as follows:(1) The uncertainty characteristic of the project lends itself very well to simulation applications, therefore a method of discrete-event simulation (DES) for resource-constrained project scheduling is proposed. The simulation model of RCPSP is composed of resource management model and project scheduling model, where the resource management model is used to manage and model diverse kinds of resources in the project, and the project scheduling model is built using an extended-directed-graph (EDG) which is an extension of activity-on-node (AON) network by adding the definition of resource so as to describe the precedence constraints and resource constraints of project. An improved simulation strategy based on the three-phase scanning is applied on the simulation model to generate scheduling alternatives which are satisfied with the precedence constraints and resource constraints.(2) The goal of simulation for project scheduling model is to choose the best alternative from among a set of competing alternatives. When stochastic behaviors such as random activity durations are considered in the simulation model, the corresponding output performances contain random variances. So, special statistical method is required to evaluate and compare the output performances of different scheduling alternatives. A multiple-comparison procedure called Procedure CY based on common random numbers is exploited to compare the random output performances obtained from the stochastic simulation model so as to select the scheduling alternative with minimal average project duration.(3) Simulation is a technique of experimental analysis and cannot generate optimal solutions automatically. Therefore, simulation-based optimization method integrated optimization algorithms with simulation is rapidly becoming an effective tool for many real-world problems. Gene expression programming (GEP) is proposed to automatically construct effective scheduling rule for RCPSP, which is the algebraic combination of project status and attributes of activity and is also a new representation form of solution compared with other optimal algorithms for RCPSP. In the simulation optimation method, GEP is used to search the optimal scheduling rules which can lead to the minimal project duration, and simulation is adopted to transform the scheduling rules into explicit scheduling alternatives for the evaluation of chromosomes.(4) In practice, some activities may be performed in one of several execution modes, and each mode is characterized by a known duration and given resource requirements. This type RCPSP with multiple activity modes is categorized as multi-mode resource-constrained project scheduling problem (MMRCPSP). A new hybrid meta-heuristic algorithm is proposed to solve the MMRCPSP in view of minimizing the project duration. The new algorithm splits the problem into a mode assignment step and a single mode project scheduling step. The mode assignment step is solved by particle swarm optimization (PSO) and returns a feasible mode combination to the project scheduling step, then the project scheduling step is solved using GEP to discover effective scheduling rules which are transformed into explicit scheduling alternatives using simulation, and the mode combination and scheduling rule that leads to the minimal project duration is the optimal solution.Aiming at several kinds of RCPSP, the assembly process and experiment process of a lager laser device are used as the applications. According to the modeling, simulation and optimization, the project scheduling model can be described intuitively, and the multiple scheduling alternatives can be evaluated and compared so as to provide the best alternative. The proposed method guides and optimizes the assembly process and experiment process of the laser system, and improves the efficiency and quality of project management.