Adaptive control schemes for parameterized heuristic scheduling

For most computationally intractable problems there exists no heuristic which performs best on all instances. Usually, a heuristic characterized as best will perform good on the majority of instances but leave a minority on which other heuristics do better. In priority rule-based scheduling, attempts to remedy this have been made by combining simple priority rules in a fixed and predetermined way. We investigate another way, viz. the design of adaptive control schemes which dynamically combine algorithms as appropriate, taking into account instance-specific knowledge. We scrutinize recently proposed algorithmic approaches from the open literature. Although these have been used in various settings (e.g. lotsizing and scheduling, course scheduling), a thorough experimental investigation, comparing their performance on standard benchmark instances to that of other contemporary methods, has been lacking. Our research aims to close this gap by validating these approaches on one of the best-researched scheduling problems, viz. the resource-constrained project scheduling problem (RCPSP). We provide the results of a comprehensive computational study. We then show how to improve algorithmic effectiveness by adding a sampling stage; the arising algorithm is almost as effective as the most effective construction methods currently known, and it enjoys several additional advantages over these which facilitate the researcher's task of designing good algorithms.