A genetic algorithm for the project scheduling with the resource constraints

Abstract

The resource-constrained project scheduling problem (RCPSP) has received the attention of many researchers because it can be applied in a wide variety of real production and construction projects. This paper presents a genetic algorithm (GA) solving the RCPSP with the objective function of minimizing makespan. Standard genetic algorithm has to be adapted for project scheduling with precedence constraints. Therefore, an initial population was generated by a random procedure which produces feasible solutions (permutation of jobs fulfilling precedence constraints). Besides, all implemented genetic operators have taken sequential relationships in a project into consideration. Finally, we have demonstrated the performance and accuracy of the proposed algorithm. Computational experiments were performed using a set of 960 standard problem instances from Project Scheduling Problem LIBrary (PSPLIB) presented by Kolisch and Sprecher [1]. We used 480 problems consisting of 30 jobs and 480 90-activity instances. We have tested effectiveness of various combinations of parameters, genetic operators to find the best configuration of GA. The computational results validate the good effectiveness of our genetic algorithm.