Result: Local search techniques for the generalized resource constrained project scheduling problem

Summary: We address the problem of scheduling a single project network with both precedence and resource constraints through the use of a local search technique. We choose a solution definition which guarantees precedence feasibility, allowing the procedure to focus on overcoming resource infeasibility. We use the classic 110-problem data set of J. H. Patterson to test our procedure. Our results indicate a significant improvement over the best heuristic results reported to date for these problems by \textit{C. E. Bell} and \textit{J. Han} [Nav. Res. Logist. 38, No. 3, 315-331 (1991; Zbl 0725.90044)]. 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. We present a problem example with an objective function and resource constraints which include nonlinear and non-continuous components, which are easily considered by the procedure. The results of our algorithm are significantly better than random solutions to the problem.