Case‐based reasoning and improved adaptive search for project scheduling

Most scheduling problems are notoriously intractable, so the majority of algorithmsfor them are heuristic in nature. Priority rule‐based methods still constitute the most importantclass of these heuristics. Of these, in turn, parametrized biased random sampling methods haveattracted particular interest, due to the fact that they outperform all other priority rule‐based methodsknown. Yet, even the “best” such algorithms are unable to relate to the full range of instances of aproblem: Usually there will exist instances on which other algorithms do better. We maintain thatasking for the one best algorithm for a problem may be asking too much. The recently proposedconcept of control schemes , which refers to algorithmic schemes allowing to steer parametrizedalgorithms, opens up ways to refine existing algorithms in this regard and improve theireffectiveness considerably. We extend this approach by integrating heuristics and case‐based reasoning(CBR), an approach that has been successfully used in artificial intelligence applications. Usingthe resource‐constrained project scheduling problem as a vehicle, we describe how to devise sucha CBR system, systematically analyzing the effect of several criteria on algorithmic performance.Extensive computational results validate the efficacy of our approach and reveal a performancesimilar or close to state‐of‐the‐art heuristics. In addition, the analysis undertaken provides newinsight into the behaviour of a wide class of scheduling heuristics. © 2000 John Wiley & Sons, Inc.Naval Research Logistics 47: 201–222, 2000