Research On Algorithms For Solving Resource-Constrained Project Scheduling Problems

The resource-constrained project scheduling problem (RCPSP) is to schedule the activities such that precedence and resource constraints are satisfied while optimizing some managerial objective. Applications can be found in diverse industries, especially in make-to-order and small batch production such as construction engineering, software development, ships and planes etc. The models in this field are rich, many well-known optimization problems are special cases, for instance job shop scheduling and flow shop scheduling. So, researches in this area have important values in theory and practical applications. The main contents of this thesis are as follows:1. Genetic Algorithm (GA) is an effective method for solving the classical RCPSP. In this paper we propose a new GA approach to solve this problem. Our approach employs a new representation for solutions that is an activity list with two additional genes. The first determines which of the two decoding procedures is used to computer a schedule for the activity list. The second indicates the direction in which the activity list is scheduled. The two genes determine the decoding procedure and decoding direction for the related activity list simultaneously. The performance evaluation done on the 156 benchmark instances shows that our GA yields better results than the other two GAs which make use of the activity list representation and the activity list with decoding procedure representation respectively.2. This thesis studies the RCPSP with fuzzy processing time and fuzzy due date in which the objective is to maximize the scheduling robustness. Fuzzy processing time and fuzzy due date are denoted by six-point fuzzy numbers. We introduce two weak comparison rules (WCR) for fuzzy numbers, i.e. integral value method and centroid distance method. A Genetic Algorithm with activity list representation is proposed for solving this problem. The computational experiment shows that the performance of the proposed algorithm is better than the best heuristics appearing in the literature, there is no difference between the two WCR on the performance of the algorithm.3. This thesis proposes a multi-objective evolutionary algorithm called the Fast Elitist Non-Dominated Sorting Genetic Algorithm (NSGA-â…¡) to solve the RCPSP with multiple activity performance modes and two objectives to minimize project makespan and resource utilization smoothness. The solution is represented by a precedence feasible activity list and a mode assignment. An agricultural example with two objectives is used to test the performance of algorithm proposed. The results show that NSGA-â…¡is efficient for solving the multi-objective RCPSP.In this thesis, we develop the GA for solving three different models of RCPSP and the procedures are designed using information related to some characteristics of RCPSP. The three procedures we proposed yield better results. This study shows that GA is a promising approach for RCPSP.