Resource-constrained project scheduling: An evaluation of adaptive control schemes for parameterized sampling heuristics

For most computationally intractable problems there exists no simple heuristic that consistently outperforms all other heuristics. One remedy is to bundle simple heuristics into composite ones in a fixed and predetermined way. Adaptive control schemes take this approach one step further by dynamically combining algorithms. Several such algorithms have been proposed recently in various settings, yet an experimental investigation comparing them with other contemporary methods has been lacking. The aim here is to close this gap by a comprehensive computational study on the field of resource-constrained project scheduling. Also shown is how to improve effectiveness of the best algorithm by means of randomized sampling. Finally, revealed are several advantages of adaptive control schemes over other algorithms which facilitate the OR practitioner's task of designing good algorithms for newly arising problems.