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

    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