Permutation-Based Elitist Genetic Algorithm for Optimization of Large-Sized Resource-Constrained Project Scheduling

Abstract

The resource-constrained project scheduling problem (RCPSP) has received the attention of many researchers because its general model can be used in a wide variety of construction planning and scheduling applications. The exact procedures and priority-rule-based heuristics fail to search for the optimum solution to the RCPSP of large-sized project networks in a reasonable amount of time for successful application in practice. This paper presents a permutation-based elitist genetic algorithm for solving the problem in order to fulfill the lack of an efficient optimal solution algorithm for project networks with 60 activities or more as well as to overcome the drawback of the exact solution approaches for large-sized project networks. The proposed algorithm employs the elitist strategy to preserve the best individual solution for the next generation so the improved solution can be obtained. A random number generator that provides and examines precedence feasible individuals is developed. A serial schedule generation scheme for the permutation-based decoding is applied to generate a feasible solution to the problem. Computational experiments using a set of standard test problems are presented to demonstrate the performance and accuracy of the proposed algorithm.