Case-based reasoning and improved adaptive search for project scheduling

Case-based reasoning and improved adaptive search for project scheduling

0.00 Avg rating0 Votes
Article ID: iaor2001183
Country: United States
Volume: 47
Issue: 3
Start Page Number: 201
End Page Number: 222
Publication Date: Apr 2000
Journal: Naval Research Logistics
Authors:
Keywords: scheduling, artificial intelligence
Abstract:

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, parametrized 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 full range of instances of a problem: usually there will exist instances on which other algorithms do better. We maintain that asking for the one best algorithm for a problem may be asking too much. The recently proposed concept of control schemes, which refers to algorithmic schemes allowing to steer parametrized algorithms, opens up ways to refine existing algorithms in this regard and improve their effectiveness considerably. We extend this approach by integrating heuristics and case-based reasoning (CBR), an approach that has been successfully used in artificial intelligence applications. Using the resource-constrained project scheduling problem as a vehicle, we describe how to devise such a CBR system, systematically analyzing the effect of several criteria on algorithmic performance. Extensive computational results validate the efficacy of our approach and reveal a performance similar or close to state-of-the-art heuristics. In addition, the analysis undertaken provides new insight into the behaviour of a wide class of scheduling heuristics.

Reviews

Required fields are marked *. Your email address will not be published.