Skip to main content
main-content

Inhaltsverzeichnis

Frontmatter

1. Motivation

Zusammenfassung
Die betriebliche Produktionsablaufplanung, auch Maschinenbelegungsplanung genannt, bildet innerhalb der Produktionsplanung zusammen mit der Losgrößenplanung das Teilgebiet der Produktionsprozeßplanung. Zur Produktionsplanung gehören neben der Produktionsprozeßplanung die Programm- und die Bereitstellungsplanung. Für alle Teilgebiete der Produktionsplanung wurden befriedigende Lösungsverfahren entwickelt, mit Ausnahme der Ablaufplanung.
Christian Bierwirth

2. Flowshop Scheduling

Zusammenfassung
Das Flowshop Scheduling Problem zählt zu den allgemeinen Produktionsablaufproblemen (production scheduling problems). Die zentrale Fragestellung der Produktionsablaufplanung ist einfach zu formulieren: Gegeben sei eine Menge von n Aufträgen (Jobs) und m Maschinen. Die Ausführung jedes Auftrags ist an die Bearbeitung durch bestimmte Maschinen gekoppelt. In welcher Abfolge sollen die einzelnen Aufträge von den Maschinen behandelt werden, so daß
1.
eine Menge A von produktionstechnischen Anforderungen der Fertigung (technological constraints) berücksichtigt und
 
2.
eine Funktion B als numerisch meßbares Zielkriterium (objective measure) optimal erfüllt wird?
 
Christian Bierwirth

3. Genetische Algorithmen

Zusammenfassung
In diesem Abschnitt werden die grundlegenden Forschungsergebnisse über Genetische Algorithmen zusammenhängend dargestellt. Aus der theoretischen Behandlung des Gegenstands ergibt sich zweierlei. Der GA-Ansatz wird in die historische Entwicklung der Optimierung mit Evolutionsstrategien systematisch eingeordnet. Die theoretische Begründung für eine erfolgreiche GA-Anwendung a posteriori läßt sich hingegen nicht a priori aus dem Verfahren selbst ableiten. In einem späteren Abschnitt müssen folglich der GA und seine Anwendungen zusammenhängend analysiert werden.
Christian Bierwirth

4. PGA — ein verteilt-asynchrones Optimierungsverfahren

Zusammenfassung
Die Funktionsweise des PGA läßt sich informal so beschreiben: N Individuen leben in einer strukturierten Population, also etwa einer zweidimensionalen Ringwelt. Jedes Individuum repräsentiert durch seinen Genoty-pus eine kodifizierte zulässige Lösung eines Optimierungsproblems. Nach außen stellt es sich in einer lokalen Nachbarschaft durch seinen Phänotypus — d. h. durch den Wert einer Zielfunktion — dar.
Christian Bierwirth

5. Genetische Problemrepräsentation

Zusammenfassung
In diesem Abschnitt wird das zentrale Problem behandelt, wie die Lösungen einer kombinatorischen Optimierungsaufgabe genetisch repräsentiert werden sollten, um Genetischen Algorithmen eine möglichst effiziente Kodierungsstruktur zur genotypischen Kooperation zu geben. Sofern die Nebenbedingungen eines kombinatorischen Problems komplexerer Art sind als z. B. die der Aufgabe (11), treten unerwartete Schwierigkeiten in der Behandlung des Problems durch den GA auf. So führt im allgemeinen die binäre Problemrepräsentation während der Reproduktionsphase (siehe Abbildung 5 in Abschnitt 3.1.1) zu neuen Lösungen, die bzgl. der Nebenbedingungen unzulässig sind. Für diesen Effekt zeichnet insbesondere die Crossover Operation verantwortlich; im nächsten Abschnitt wird dies am Beispiel des TSP verdeutlicht.
Christian Bierwirth

6. Problemabhängige PGA Komponenten

Zusammenfassung
Das Zauberwort der Genetischen Algorithmen heißt Crossing-Over. Hinter dem der Genetik entlehnten Begriff verbirgt sich eine Technik zum Austausch von Informationen zwischen unterschiedlichen Lösungen. Mittels dieser Technik modelliert ein GA die sexuelle Reproduktion von Nachkommen, also von neuen Lösungen. Folgende Darstellung illustriert, wie ein Crossing-Over von zwei binär kodierten Eltern-Genotyen aussehen kann.
Christian Bierwirth

7. Problemunspezifische PGA Komponenten

Zusammenfassung
In der Literatur finden sich unterschiedliche Modelle überlappender Populationen. Mühlenbein und Gorges-Schleuter ordnen die Individuen einer Lösungspopulation auf zwei übereinanderliegenden Ringen an. Kommunikationswege innerhalb der Population bilden die Ringsegmente und weitere Kanten, die je zwei auf den Ringen gegenüberliegende Individuen miteinander verbinden. Sie nennen diese zirkuläre und in sich abgeschlossene Struktur eine Leiterpopulation [Gorg89]. Im Hinblick auf Transputerimplementationen erscheinen auch Topologien interessant, die jedem Individuum vier unmittelbare Nachbarn zuordnen, welche unter Ausnutzung der vier physikalischen Ein/Ausgänge des Transputers direkt erreicht werden können. Größere Nachbarschaften können jedoch nur durch Überspringen (routing) einzelner Transputer angesprochen werden. Tanese berichtet über Parallel-Implementationen des GA in Hyperwürfen der Ordnung Vier [Tane87].
Christian Bierwirth

8. Konfigurationsraum-Analysen

Zusammenfassung
Unsere Vorstellung der natürlichen Evolution beruht auf der Annahme, daß der vom genetischen Code induzierte Genotypenraum auf eine Weise angeordnet ist, in der die darüber projezierte Mannigfaltigkeit der natürlichen Fitness annähernd stetig verläuft. Rechenberg bezeichnet dies als Glätte der Tauglichkeitsfunktion über dem Nukleotidraum [Rech73, S. 54-63]. Nun erscheint ein quantitatives Modell der natürlichen Fitness bereits theoretisch unmöglich und folglich besitzt unser Grundverständnis der Evolution in weiten Teilen deskriptiven Charakter. In diesem Flausibilitätsmodell formuliert das Glättepostulat ein fundamentales Prinzip zwischen den genotypischen Spezifikationen von Organismen und ihrer Fitness. In [StBi91] haben wir es als Contiguence-Hypothese bezeichnet, was sich frei durch Angrenzungsannahme übersetzen läßt:
Contiguence-Hypothese: Kleine Störungen im genetischen Code von Organismen bewirken geringe Änderungen ihrer phänotypischen Merkmale.
Christian Bierwirth

9. Ergebnisse

Zusammenfassung
Im Gegensatz zum Travelling Salesman Problem existieren im Scheduling Bereich keine standardisierten Testinstantiierungen. Die vereinzelt in der Literatur publizierten Probleme sind von kleinem Umfang (n, m ≤ 5) und dienen in der Regel nur zur Illustration eines neuen Lösungsverfahrens. Verantwortlich hierfür zeichnet die vergleichsweise große Anzahl von zu instantiierenden Variablen. Während ein euklidisches n-Städte TSP durch die Angabe von 2 n Koordinaten vollständig beschrieben ist, erfordert ein vollständiges n-Aufträge, m-Maschinen Ablaufproblem bereits die Über-tragung von 2 m (n+1) reellen Zahlwerten, um die Operationszeitmatrix, die technischen Reihenfolgerestriktionen sowie Verfügbarkeits- und Liefertermine zu spezifizieren.
Christian Bierwirth

10. Zusammenfassung und Ausblick

Zusammenfassung
In der Vergangenheit wurde verschiedentlich versucht, das Paradigma der genetischen Optimierung durch eine stochastische Analyse seiner Operatoren zu rechtfertigen. Diese Ansätze müssen als gescheitert betrachtet werden.
Christian Bierwirth

Backmatter

Weitere Informationen