Local search techniques for the generalized resource constrained project scheduling problem

In this article the authors address the problem of scheduling a single project network with both precedence and resource constraints through the use of a local search technique. They choose a solution definition which guarantees precedence feasibility, allowing the procedure to focus on overcoming resource infeasibility. The authors use the 110-problem data set of Patterson to test the present procedure. The results indicate a significant improvement over the best heuristic results reported to date for these problems (Bell and Han). Two major advantages of the local search algorithm are its ability to handle arbitrary objective functions and constraints and its effectiveness over a wide range of problem sizes. The authors present a problem example with an objective function and resource constraints which include nonlinear and noncontinuous components, which are easily considered by the procedure. The results of the present algorithm are significantly better than random solutions to the problem.