TU Darmstadt / ULB / TUprints

Simple Metaheuristics for Scheduling

Besten, Matthijs Leendert den (2005)
Simple Metaheuristics for Scheduling.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
PDF
PhD.pdf
Copyright Information: In Copyright.

Download (1MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Simple Metaheuristics for Scheduling
Language: English
Referees: Bibel, Prof.Dr. Wolfgang ; Stützle, Dr. Thomas
Advisors: Bibel, Prof.Dr. Wolfgang ; Stützle, Dr. Thomas
Date: 13 January 2005
Place of Publication: Darmstadt
Date of oral examination: 6 October 2004
Abstract:

This dissertation is concerned with configuring stochastic local search for combinatorial optimization problems by means of new automatic experimental procedures. The configuration and selection of stochastic local search is determined by an univocally specified computer-based evaluation of various variants of stochastic local search by means of racing. Depending on the amount of effort that is needed to generate a solution, the quality of the solution and the run time that is required to obtain the solution are taken into account in a specific way: If the effort required to generate the solutions is more or less equal for all candidates, then the solution quality is the main criterion for selection among the candidates; if there are big differences, then the run time is explicitly taken account of as well; and in cases where the search algorithms can generate a series of solutions with increasing quality, the quality of every new solution is taken into account together with the associated run time in order to select among the candidates. The application of these selection procedures is illustrated in this dissertation with the application of construction heuristics, the application of iterative improvement and the application of iterated local search to twelve distinct scheduling problems. Each time, the final result is a search algorithm whose performance is on a par with the state-of-the-art for the problem domain. In addition, new insights could be obtained on the influence of search algorithm components on algorithm performance in relation to the structure of the optimization problems that were investigated.

Alternative Abstract:
Alternative AbstractLanguage

Diese Dissertation behandelt die Konfiguration stochastisch lokaler Suchverfahren für kombinatorische Optimierungsprobleme mittels neuer, automatischer experimentellen Prozeduren. Die Konfiguration and Selektion des Suchverfahrens wird aufgrund einer genau spezifizierten, vom Rechner durchgeführten Evaluation der Performanz von verschiedenen Varianten des Suchverfahrens mittels Racingverfahren bestimmt. In Abhängigkeit des Aufwands der Erzeugung von Lösungen, werden die Lösungsgüte und der Berechnungsaufwand, d.h. die Rechenzeit zur Erzeugung der Lösungen, unterschiedlich berücksichtigt. Können Lösungen mit ungefähr gleichem Aufwand generiert werden, ist die Güte der Lösungen das Hauptkriterium für die Auswahl. Gibt es erhebliche Unterschiede im Aufwand der Erzeugung von Lösungen, wird die Rechenzeit explizit in der Auswahl berücksichtigt. Falls die Suchverfahren eine Serie von Lösungen steigender Güte generieren können, wird die Güte jeder neuen solchen Lösung zusammen mit der entsprechenden Rechenzeit im Auswahlverfahren berücksichtigt. Die Anwendung dieser Auswahlverfahren wird in dieser Dissertation anhand von Konstruktionsheuristiken, Varianten von iterierten Verbesserungsverfahren und der iterierten lokalen Suche für deren jeweilige Anwendung auf zwölf unterschiedliche Schedulingprobleme dargestellt. Das Endergebnis ist jeweils ein Suchverfahren, dessen Performanz oft dem ``State-of-the-Art'' im Problembereich entspricht. Zusätzlich konnten durch eine eingehende, statistische Analyse der Versuchsdaten neue Einsichten in den Einfluss der Komponenten von Suchverfahren auf die Performanz in Abhängigkeit der Struktur der untersuchten Optimierungsprobleme gewonnen werden.

German
Uncontrolled Keywords: Stochastische lokale Suche, Metaheuristiken, experimentelle Analyse, Algorithmenkonfiguration
Alternative keywords:
Alternative keywordsLanguage
Stochastische lokale Suche, Metaheuristiken, experimentelle Analyse, AlgorithmenkonfigurationGerman
stochastic local search, metaheuristics, experimental analysis, algorithm configuration, model selectionEnglish
URN: urn:nbn:de:tuda-tuprints-5164
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science
Date Deposited: 17 Oct 2008 09:21
Last Modified: 07 Dec 2012 11:50
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/516
PPN:
Export:
Actions (login required)
View Item View Item