Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/147577 
Year of Publication: 
1998
Series/Report no.: 
Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel No. 471
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 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.
Subjects: 
PROJECT SCHEDULING
PARAMETERIZED SAMPLING HEURISTICS
PRIORITY RULES
CONTROL SCHEMES
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.