An Exchange Heuristic Algorithm for Project Scheduling with Limited Resources

Abstract

In this paper an effective search-type heuristic algorithm for the problems of scheduling activities under resource and precedence constraints is presented. Such problems are typically massive in size and combinatorially explosive. The algorithm to solve these problems consists of two phases (both of which are heuristic). Phase I develops a “good” initial solution. Phase II then employs the solution derived in Phase I as a starting point; attempting to manipulate this schedule so as to reduce the project completion time via suitable reshuffles, or rearrangements of the activities while maintaining feasibility. A random problem generator and a random active schedule generator were prepared and utilized to evaluate the performance of the algorithm.