A Competitive Genetic Algorithm for Resource-Constrained Project Scheduling

In this paper we consider the resource-constrained project scheduling problem (RCPSP) with makespan minimization as objective. We propose a new genetic algorithm approach to solve this problem. Subsequently, we compare it to two genetic algorithm concepts from the literature. While our approach makes use of a permutation based genetic encoding that contains problem-specific knowledge, the other two procedures employ a priority value based and a priority rule based representation, respectively. Then we present the results of our thorough computational study for which a standard set of project instances has been used. The outcome reveals that our procedure is the most promising genetic algorithm to solve the RCPSP. Finally, a priority rule based random sampling procedure known from the literature serves as a further benchmark. We show that our genetic algorithm yields better results than this sampling approach