Flowhop Scheduling mit parallelen Genetischen Algorithmen - Bierwirth, Christian

. .

Biographie:
.

Sommaire:
1 Motivation.- 2 Flowshop Scheduling.- 2.1 Das deterministische Job Scheduling Modell.- 2.1.1 Planvorgaben und implizite Annahmen.- 2.1.2 Durchlaufzeitbezogene Optimierungsziele.- 2.1.3 Problemklassifikation.- 2.2 Optimierung von Flowshop Problemen.- 2.2.1 Die Komplexit?t des Flowshop.- 2.2.2 Evaluierung und Absch?tzung der Zykluszeit.- 2.2.3 Standardheuristiken f?r Flowshop Probleme.- 3 Genetische Algorithmen.- 3.1 Einf?hrung.- 3.1.1 Das programmierte Paradigma.- 3.1.2 Theoretische Vorbetrachtung.- 3.2 Ein Exkurs in Genetik oder das biologische Vorbild.- 3.2.1 Chromosomale Repr?sentation des Erbguts.- 3.2.2 Keimspaltung und Crossing-Over.- 3.2.3 Mutation und Selektion.- 3.3 Modellierung evolution?rer Strategien.- 3.3.1 Konkurrenz: Formalisierung ph?notypischer Selektion.- 3.3.2 Kooperation: Einbeziehung genotypischer Vererbung.- 3.3.3 Stochastische Kontrolle und das Fundamentaltheorem.- 3.4 Parallelisierung Genetischer Algorithmen.- 3.4.1 Populationsstrukturen.- 3.4.2 Verteilte Selektion und nat?rliche Asynchronit?t.- 4 PGA ? ein verteilt-asynchrones Optimierungsverfahren.- 4.1 Die PGA Komponenten ? eine Funktionsbeschreibung.- 4.2 Terminierungskriterien.- 4.3 PGA Netzwerkimplementation.- 5 Genetische Problemrepr?sentation.- 5.1 Bin?re Kodierung des TSP.- 5.2 Kanonische L?sungs-Kodierung.- 5.2.1 Repr?sentation durch Wege in Graphen.- 5.2.2 Beispiele.- 5.3 Das kanonische Schema.- 5.3.1 Problemabh?ngige syntaktische Regeln.- 5.3.2 Semantische Strukturmerkmale.- 6 Problemabh?ngige PGA Komponenten.- 6.1 Das Crossing-Over.- 6.1.1 F?nf Operatoren.- 6.1.2 Implizite Mutationen.- 6.1.3 Problemsensitivit?t.- 6.2 Explizite Mutationen.- 6.3 Lokale Optimierung.- 6.3.1 ?-Optimalit?t.- 6.3.2 Lins 2-0PT.- 6.3.3 Pairwise Exchange.- 6.3.4 Leistungsvergleich lokaler Optimierer.- 7 Problemunspezifische PGA Komponenten.- 7.1 ?berlappende Populationen.- 7.1.1 Nachbarschaften und elit?re Populationen.- 7.1.2 Populations- und Nachbarschaftsgr??en.- 7.2 Verteilte Selektion.- 7.2.1 Partnerwahl mit abgestuften Wahrscheinlichkeiten.- 7.2.2 Akzeptanz ?ber lokale Abstimmung.- 7.3 Balancierung der Selektion in ?berlappenden Populationen.- 8 Konfigurationsraum-Analysen.- 8.1 Travelling Salesman Problem.- 8.2 Flowshop Probleme.- 8.3 Interpretation konfigurierender Merkmale.- 9 Ergebnisse.- 9.1 Experimentelle Flowshop Plattform.- 9.2 Leistungsverhalten der PGA Heuristik.- 9.3 PGA Leistungsvergleich mit Standardheuristiken.- 10 Zusammenfassung und Ausblick.- A Anhang.- A.1 Dokumentation der Testprobleme und besten L?sungen.- A.2 Konfigurationsdiagramme aller Testprobleme.- A.3 Funktionale Beschreibung der Optimierungsziele.- A.3.3 ?bersicht von Optimierungszielen der Ablaufplanung.- Literatur.