An evolution programme for the resource-constrained project scheduling problem

This paper describes an implementation of an evolution programme for the resource-constrained project scheduling problem. In essentials, the problem consists of two issues; (a) to determine the order of activities without violating precedence constraints and (b) subsequently to determine earliest start time for each activity according to available resources. How to determine the order of activation is critical to the problem, because if the order is determined, a schedule can be easily constructed with some determining procedures. The basic ideas of the proposed approach are; (a) using an evolution programme to evolve an appropriate order of activities and (b) using a fit-in-best procedure to calculate the earliest start times of activities. A new approach is addressed to guide how to design genetic operators; one operator is designed to perform a widespread search to try to explore the area beyond local optima, whereas the other is designed to perform an intensive search to try to find an improved solution. These two kinds of search abilities, the intensive search and the widespread search, form the mutual complementary components of genetic search. With this approach, crossover operator and mutation operator play the same important role in genetic search. The suggested approach can significantly improve the performance of the evolution programme both in terms of speed and accuracy. The proposed method has been tested on several benchmark problems and the results are very encouraging. The proposed method can be readily applied to other types of resource constrained project scheduling problems.