Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/147578 
Year of Publication: 
1998
Series/Report no.: 
Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel No. 472
Publisher: 
Universität Kiel, Institut für Betriebswirtschaftslehre, Kiel
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, 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 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 parameterized 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.
Subjects: 
PROJECT SCHEDULING
HEURISTICS
RANDOM SAMPLING
CASED-BASED REASONING
Document Type: 
Working Paper
Document Version: 
Digitized Version

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.