Local search techniques for the generalized resource constrained project scheduling problem

✍ Scribed by Scott E. Sampson; Elliott N. Weiss

• Publisher: John Wiley and Sons
• Year: 1993
• Tongue: English
• Weight: 665 KB
• Volume: 40
• Category: Article
• ISSN: 0894-069X
• DOI: 10.1002/1520-6750(199308)40:5<665::aid-nav3220400509>3.0.co;2-j

✦ Synopsis

In this article 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 110-problem data set of Patterson to test our procedure. Our results indicate a significant improvement over the best heuristic results reported to date for these problems (Bell and Han [l]). 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 noncontinuous components, which are easily considered by the procedure. The results of our algorithm are significantly better than random solutions to the problem.