Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem

We consider heuristic algorithms for the resource-constrained project scheduling problem, Starting with a literature survey, we summarize the basic components of heuristic approaches, We briefly describe so-called X-pass methods which are based on priority rules as well as metaheuristic algorithms. Subsequently, we present the results of our in-depth computational study. Here, we evaluate the performance of several state-of-the-art heuristics from the literature on the basis of a standard set of test instances and point out to the most promising procedures. Moreover, we analyze the behavior of the heuristics with respect to their components such as priority rules and metaheuristic strategy. Finally, we examine the impact of problem characteristics such as project size and resource scarceness on the performance. (C) 2000 Elsevier Science B.V. All rights reserved.