Title

A Simple And Effective Heuristic For The Resource Constrained Project Scheduling Problem

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.

Publication Date

9-20-2001

Publication Title

International Journal of Production Research

Volume

39

Issue

14

Number of Pages

3275-3287

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1080/00207540110060608

Socpus ID

0035922493 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0035922493

This document is currently not available here.

Share

COinS