An evolutionary algorithm with active plans for the RCPSP

Abstract

This paper presents a genetic algorithm for the Resource Constrained Project Scheduling Planning (RCPSP). The Evolutionary Algorithm is based on a random keys chromosome that is very easy to implement and allows using conventional transformation operators for combinatorial optimization problems. A project is formed by a set of activities that has to be performed using a set of resources. Each activity uses a specific set of resources, and it is also necessary to guarantee that there is no overlap in the time it takes to process activities in the same resource. The objective of the RCPSP is to minimize the makespan. The use of exact algorithms for the RCPSP is still limited to instances of small size. The alternative in solving the Real-Large Resource Constrained Project Scheduling Planning is the use of heuristic procedures. This evolutionary algorithm includes specific knowledge of the problem to improve its efficiency. A constructive algorithm based on Giffler-Thompson's algorithm is used to generate active plans. The constructive algorithm reads the chromosome and decides which activity is scheduled next. The Evolutionary Algorithm will be tested by using some benchmark problems.