Class-based control schemes for parameterized project scheduling heuristics

Andreas Schirmer and Sven Riesenberg

No 471, Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel from Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre

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.

Keywords: PROJECT SCHEDULING; PARAMETERIZED SAMPLING HEURISTICS; PRIORITY RULES; CONTROL SCHEMES (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
https://www.econstor.eu/bitstream/10419/147577/1/manuskript_471.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:zbw:cauman:471

Access Statistics for this paper

More papers in Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel from Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre Contact information at EDIRC.
Bibliographic data for series maintained by ZBW - Leibniz Information Centre for Economics (econstor@zbw-workspace.eu).