The Research On Some Problems For Resource-Constrained Project Scheduling

Resource-Constrained Project Problem (RCPSP) widely exists in all walks of life, which is not only the key part of the project management field but also one of the important branches of the Operation Research. Efficient scheduling scheme could save resource, shorten makespan and obtain huge economic benefits. Most of problems involved in RCPSP are NP-hard, which makes the solving process complicated. Therefore, researches in this area have important values in theory and practical applications. Regarding this problem, this dissertation consists of two parts:1)a new extension of RCPSP constrained by hard time limitation named RCPSP with Forbidden Time Windows (RCPSP-FTW), which is motivated by water conservancy project;2)introduction of DEA into RCPSP for solving the scheduling scheme selection dilemma. The main contents of this paper are as follows:1. The characteristics of RCPSP-FTW are described in detail and the corresponding mathematic model is formulated. The classical scheduling schema and heuristics based on multi-priority rules are adjusted to make them suitable for solving the RCPSP-FTW. The simulation datasets with forbidden time windows constraint are generated based on the PSPLIB. The computational experiments show that the multi-priority rule approach is efficient for solving the RCPSP-FTW.2. Two meta-heuristic algorithms are developed for solving RCPSP-FTW. One is genetic algorithm, using a forbidden time windows crossover operator derived in specific problem characteristics and double justification and elitism selection techniques for improving the quality of solutions. The other is Electromagnetism-like Mechanism, which combines topological-order with random key as encoding method and modifies the local search, particle charge, total force and the movement of particle. A simplified water conservancy project and a large number of simulation data are used to test the performance of the two algorithms respectively. The experiments show that these two algorithms can greatly improve the quality of the solutions and also illustrate the forbidden time windows and distribution of activities affected by forbidden time windows are the main cause of the fluctuations of RCPSP-FTW makespan.3. Three conflicting objectives exist in project scheduling problem, which are duration, cost and quality. In practice, managers’preferences for these three goals are different, which makes the choice from many candidate scheduling schemes difficult. Therefore, the Data Envelopment Analysis model is introduced into RCPSP. A multi-mode resource constrained project scheduling problem is taken as an example to explain how to combine the two fields. This provides a new perspective for the actual project decision-making and the extension for RCPSP applications.