Adaptive control schemes for parameterized heuristic scheduling

Armin Schirmer

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

Abstract: For most computationally intractable problems there exists no heuristic which performs best on all instances. Usually, a heuristic characterized as best will perform good on the majority of instances but leave a minority on which other heuristics do better. In priority rule-based scheduling, attempts to remedy this have been made by combining simple priority rules in a fixed and predetermined way. We investigate another way, viz. the design of adaptive control schemes which dynamically combine algorithms as appropriate, taking into account instance-specific knowledge. We scrutinize recently proposed algorithmic approaches from the open literature. Although these have been used in various settings (e.g. lotsizing and scheduling, course scheduling), a thorough experimental investigation, comparing their performance on standard benchmark instances to that of other contemporary methods, has been lacking. Our research aims to close this gap by validating these approaches on one of the best-researched scheduling problems, viz. the resource-constrained project scheduling problem (RCPSP). We provide the results of a comprehensive computational study. We then show how to improve algorithmic effectiveness by adding a sampling stage; the arising algorithm is almost as effective as the most effective construction methods currently known, and it enjoys several additional advantages over these which facilitate the researcher's task of designing good algorithms.

Keywords: PROJECT SCHEDULING; HEURISTICS; ADAPTIVE 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 (2)

Downloads: (external link)
https://www.econstor.eu/bitstream/10419/147585/1/manuskript_488.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:488

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 ().