Class-based control schemes for parameterized project scheduling heuristics

Most scheduling problems are notoriously intractable, so the majority of algorithms for them are heuristic in nature. Priority rule-based methods still constitute the most important class of these heuristics. Of these, in turn, parameterized biased random sampling methods have attracted particular interest, due to the fact that they outperform all other priority rule-based methods known. Yet, even the 'best' such algorithms are unable to relate to the particularities of all possible instances of the problem at hand: usually there will exist instances on which other, e.g. the second- or third-best, algorithms perform better. We maintain that asking for the one best algorithm for a given problem may in fact be asking too much. The recently proposed concept of control schemes, which refers to algorithmic schemes allowing to guide the proceeding of parameterized algorithms, opens up ways to refine existing algorithms in this regard. By partitioning the set of all instances of a problem into equivalence classes and identifying algorithmic components that are suited for the respective classes, class-based control schemes constitute one way to achieve this goal. Using the resource-constrained project scheduling problem as a vehicle, we describe how to devise such control schemes, making systematic use of different scheduling schemes as well as random sampling schemes and priority rules. Results from extensive computational experimentation validate effectiveness and efficiency of our approach.