An Efficient Solution of the Resource Constrained Project Scheduling Problem Based on an Adaptation of the Developmental Genetic Programming

摘要

An adaptation of the Developmental Genetic Programming (DGP) for solving an extension of the Resource-Constrained Project Scheduling Problem (RCPSP) is investigated in the paper. In DGP genotypes (the search space) and phe-notypes (the solution space) are distinguished and a genotype-to-phenotype mapping (GPM) is used. Thus, genotypes are evolved without any restrictions and the whole search space is explored. RCPSP is a well-known NP-hard problem but in its original formulation it does not take into consideration initial resource workload and it minimises the makespan. We consider a variant of the problem when resources are only partially available and a deadline is given but it is the cost of the project that should be minimized. The goal of the evolution is to find a procedure constructing the best solution of the problem for which the cost of the project is minimal. The paper presents new evolution process for the DGP as well as a comparison with other genetic approaches. Experimental results showed that our approach gives significantly better results compared with other methods.