A competitive genetic algorithm for resource-constrained project scheduling

TLDR

The study addresses the RCPSP with a makespan minimization objective. A permutation‑based genetic algorithm incorporating problem‑specific knowledge is proposed and benchmarked against two existing GA variants on standard RCPSP instances. The proposed GA outperforms existing GA variants and several heuristics, proving to be the most promising approach for RCPSP. © 1998 John Wiley & Sons, Inc., Naval Research Logistics 45:733–750.

Abstract

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 standard sets of project instances have been used. The outcome reveals that our procedure is the most promising genetic algorithm to solve the RCPSP. Finally, we show that our genetic algorithm yields better results than several heuristic procedures presented in the literature. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 733–750, 1998