A simple and effective heuristic for the resource constrained project scheduling problem

• Published in: International journal of production research 2001-01, Vol.39 (14), p.3275-3287
• Main Authors: Depuy, Gail W., Whitehouse, Gary E.
• Format: Article
• Language: English
• ISSN: 0020-7543; 1366-588X
• DOI: 10.1080/00207540110060608

This paper investigates the development and application of a simple heuristic to the resource constrained project scheduling problem (RCPSP). This computer heuristic, which is based on the COMSOAL heuristic, constructs a feasible solution at each iteration and chooses the best solution of several iterations. Although COMSOAL was originally a solution approach for the assembly-line balancing problem, it can be extended to provide solutions to the resource allocation problem. The Modified COMSOAL technique presented in this paper uses priority schemes intermittently with a random selection technique. This hybrid of randomness and priority scheme allows a good solution to be found quickly while not being forced into the same solution at each iteration. Several different priority schemes are examined within this research. The COMSOAL heuristic modified with the priority schemes heuristic was tested on several established test sets and the solution values are compared with both known optimal values and the results of several other resource allocation heuristics. In the vast majority of cases, the Modified COMSOAL heuristic outperformed the other heuristics in terms of both average and maximum percentage difference from optimal. The Modified COMSOAL heuristic seems to have several advantages over other RCPSP heuristics in that it is easy to understand, easy to implement, and achieves good results.