Some efficient multi-heuristic procedures for resource-constrained project scheduling

Various heuristic procedures have been proposed to solve the well known NP-hard, resource-constrained project scheduling problem. Most of these procedures are parallel heuristics. In this paper, some multi-heuristic procedures employing parallel rules as well a serial rules are suggested. These multi-heuristics were compared to 13 single heuristic procedures. This comparison is based on a set of 36 small problems (5 to 20 activities) and 30 large scale projects (38 to 111 activities). The main performance measure used to assess the efficiency of each heuristic was the project completion time expressed as a percentage of either the optimal duration (for small problms) or the critical path length (for large projects). As an example, a three-heuristic procedure yielded the optimum schedule in 27 of the 36 small problems (75%) and produced the shortest duration schedule for 56 of the 66 test problems (85%).