Title

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

Authors

Authors

G. W. DePuy;G. E. Whitehouse

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

Abbreviated Journal Title

Int. J. Prod. Res.

Keywords

MULTIPLE RESOURCE; ALGORITHM; BRANCH; Engineering, Industrial; Engineering, Manufacturing; Operations Research; & Management Science

Abstract

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.

Journal Title

International Journal of Production Research

Volume

39

Issue/Number

14

Publication Date

1-1-2001

Document Type

Article

Language

English

First Page

3275

Last Page

3287

WOS Identifier

WOS:000170775400014

ISSN

0020-7543

Share

COinS