Search algorithms for resource constrained project scheduling problem

Abstract

We consider a project scheduling problem with multiple resource constraints as well as precedence constraints. For this problem, we apply and compare three popular search methods - Genetic Algorithm (GA), Simulated annealing (SA) and Tabu Search (TS), which have been used for various combinatorial optimization problems. We develop an encoding scheme in which a solution is represented with a string of numbers. Each number of the string denotes priority of each activity. The priority is used to select an activity among competing ones for resource allocation. This encoding method is very flexible, in the sense that problems with objective functions of a general functional form (such as a nonlinear function) and complex constraints from real world can be considered with much difficulty since it does not depend on the network topology. Furthermore, our procedure can be used in project scheduling problems with multiple projects. To evaluate the performance of our procedure, a series of computational test was done on randomly generated problems. The test shows that our procedure outperforms other existing heuristic methods - the minimum slack method, the iterative technique, the SEARCH heuristic.