Robuste Ablaufplanung mit stochastischen genetischen Algorithmen

Inhaltsverzeichnis

Abbildungsverzeichnis

Tabellenverzeichnis

Abkürzungsverzeichnis

Symbolsverzeichnis

Gliederung

1 Einführung zur stochastischen Ablaufplanung

2 Modelle zur Ablaufplanung
2.1 Statisches Job Shop Scheduling Problem (JSSP)
2.2 Stochastisches JSSP (SJSSP)

3 Genetische Algorithmen (GA) als Lösungsverfahren zum SJSSP
3.1 Klassische GA
3.2 Monte Carlo Simulation (MC)
3.3 GAUCE Verfahren
3.3.1 Repräsentation
3.3.2 Initialisierung der ersten Population
3.3.3 Evaluationsfunktion und Selektionsverfahren .
3.3.4 Genetische Operatoren

4 Numerische Experimente und Analyse
4.1 Experimentsrahmen
4.2 Ergebnisse und Analyse

5 Kritik

6 Fazit und Ausblick

Anhang

A Programm GEAL

Literaturverzeichnis

Abbildungsverzeichnis

1 Gannt-Diagramm von einem Schedule

2 klassische GA-Ablauf

3 GAUCE-Ablauf

4 Codierung eines Phänotyps

5 One-point Crossover

6 One-point Mutation

Tabellenverzeichnis

1 6 × 6 JSSP (Muth und Thompson (1963))

2 Lösungen unter deterministischer Bedingung

3 Lösungen bei einer Standardabweichung 0 . 1 × E (t)

4 Lösungen bei einer Standardabweichung 0 . 2 × E (t)

5 Lösungen bei einer Standardabweichung 0 . 3 × E (t)

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

Symbolsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

1 Einführung zur stochastischen Ablaufplanung

Die Ablaufplanung für Werkstattproduktion befasst sich mit der Zuordnung von Aufträgen zu Arbeitssystemen bzw. Maschinen und umgekehrt unter Beachtung des Rüstzustands der Maschinen und der Verfügbarkeit von Werkzeugen, Transportmitteln usw.¹. Es wird in die Feinplanung des hierarchischem Planungskonzepts eingeordnet.

Bei Job Shop Scheduling Problem(JSSP) handelt es sich um die verallgemeinerte Ablaufplanung für Werkstattproduktion ohne Berücksichtigung der reihenfolgeabhängigen Rüstzustände der Maschinen und Kapazitätsrestriktionen von Werkzeugen, Transportmitteln usw. Viele JSSP sind sowohl NP-Vollständig als auch eins die schlechsten in dieser Problemklasse.² Die meisten untersuchten Lösungsansätze eignen sich nur für deterministische Bearbeitungszeiten. Ihre praktischen Einsatzmöglichkeiten sind daher relativ begrenzt. Genetische Algorithmen(GA) zählen zu den populären Lösungsverfahren, die auf verschiede Arten Optimierungsprobleme angewandt sind.

Gegenstand der Seminararbeit ist die Darstellung eines genetischen Algorithmus(GAUCE), der das JSSP unter stochastischen Bearbeitungszeiten lösen kann. Nach einer Einführung in der Problematik der Ablaufplanung wird GAUCE detailliert dargestellt. In der Folge werden numerische Experimente und deren Ergebnisse analysiert und diskutiert. Abschließend werden Kritiken und weitere Aspekte beschrieben.

2 Modelle zur Ablaufplanung

2.1 Statisches Job Shop Scheduling Problem (JSSP)

Bei einem JSSP sind n Aufträge oder Jobs auf M Maschinen zu bearbeiten. Ein Auftrag lässt sich in verschiedene Arbeitsgänge oder Operationen unterteilen. Die Reihenfolge der Maschinen, mit denen die Arbeitsgänge innerhalb eines Auftrags nacheinander bearbeitet sind, bezeichnet man als Maschinenfolge³. Die zeitliche Reihenfolge, in der die einzelnen Aufträge auf einer Maschine k zu bearbeiten sind, heißt Auftragsfolge. Eine zulässige Menge aller Auftragsfolgen heißt Schedule.

Es wird eine weitgehend einheitliches Klassifikationsschema in der Literatur durchgesetzt. Die Probleme unterscheiden sich hinsichtlich ihrer:⁴

-Maschinencharakteristik,
-Auftragscharakteristik und
-Zielsetzung.

Maschinencharakteristik beschreibt die Anordnung und die Anzahl der zur Verfügung stehenden Maschinen. Dabei kann ein Auftrag auf jeder Maschine mehrmals bearbeitet werden oder aber einzelne Maschinen auslassen. Weitere Merkmale sind Kapazitäten, Rüstzeiten, Ausfallrate und Reparaturdauern.

Wesentliche Merkmale der Auftragscharakteristik sind Ankunftszeitpunkt, Bearbeitungszeit und Unterbrechbarkeit. Wenn alle Aufträge zum Zeitpunkt 0 vorliegen, dann spricht man von einem statischen Modell. Die Ankunftszeitpunkte können auch dynamisch(mit bekannten zukünftigen Terminen) oder stochastisch sein. Die Bearbeitungszeit eines Arbeitsgangs kann ebenfalls statisch oder stochastisch sein. Unterbrechbarkeit bedeutet, dass die Bearbeitung jedes Arbeitsgangs auf einer Maschine beliebig unterbrochen und zu einem späteren Zeitpunkt fortgesetzt werden kann.

In der Literatur werden neben der Minimierung der Zykluszeit eine Reihe weiterer Ziel- setzungen behandelt.⁵ Unter Zykluszeit versteht man die Zeitspanne vom Beginn der Bearbeitung des ersten Auftrags bis zum Fertigstellungszeitpunkt des letzten Auftrags.

Wir betrachten das JSSP hinsichtlich ihrer Charakteristiken für diese Seminararbeit mit folgenden Grundannahmen:⁶

-Eine Maschine kann zu jeder Zeit maximal einen Auftrag bearbeiten.
-Jeder Auftrag enthält maximal M Arbeitsgänge.
-Maschinenfolgen sind vorgegeben.
-Kapazitäten, Ausfallrate, Rüstzeiten, Reparaturdauern aller Maschinen werden nicht berücksichtigt.
-Ankunftszeitpunkte aller Aufträge sind 0.
-Die Bearbeitungszeit für jeden Arbeitsgang ist vorgegeben.
-Jeder Arbeitsgang ist nicht unterbrechbar.
-Gesucht sind Auftragsfolgen für jede Maschine.
-Zielsetzung ist die Minimierung der Zykluszeit.

Damit kann das Problem durch das folgende Modell beschrieben werden:⁷

Abbildung in dieser Leseprobe nicht enthalten

Dabei bedeuten:

Abbildung in dieser Leseprobe nicht enthalten

Die Zielfunktion (1) minimiert die Zykluszeit. Die Bedingungen(2) garantieren, dass jeder Auftrag seine Maschinenfolge einhält. Die Bedingungen (3) fordern, dass für jedes um eine Maschine konkurrierende Arbeitsgangspaar (i, j) eine Reihenfolge i vor j oder j vor i festgelegt wird. Die Bearbeitung beginnt gemäß (4) zum Zeitpunkt 0.

Muth und Thompson (1963) stellen die Daten eines speziellen Job Shop Scheduling Problems Problems mit zehn Maschinen und zehn Aufträgen vom Beginn der sechziger Jahre dar. Eine optimale Lösung hat man jedoch erst Ende der achtziger Jahre gefunden und als solche bewiesen.

Um das JSSP hinsichtlich dieser Daten zu lösen, wird eine Reihe von GA im letzten Jahrzehnt entwickelt.⁸

2.2 Stochastisches JSSP (SJSSP)

Das JSSP unter stochastischen Bedingungen wird als stochastisches JSSP (SJSSP) bezeichnet. Im Vergleich zu JSSP ist SJSSP viel praxisrelevanter, weil z. B. die Bearbeitungszeit eines Arbeitsgangs sich in der Realität meistens stochastisch verhält. SJSSP wird aber auch auf besonders schwierige Lösbarkeit verwiesen.⁹

In dieser Seminararbeit werden die stochastischen Bedingungen auf stochastische Bear- beitungszeit beschränkt. Als Zielsetzung wird ein Schedule mit minimalem Erwartungs- wert der Zykluszeit gesucht. Die anderen Restriktionen im Vergleich zu JSSP bleiben unverändert. Zusätzlich in SJSSP werden vier Bedingungen ergänzt, um die Zykluszeit richtig zu kalkulieren und die Erzeugung unzulässiger Schedule zu vermeiden:¹⁰

-Die Startzeit eines Arbeitsgangs innerhalb eines Auftrags soll so früh wie möglich sein.
-Eine zulässige Reihenfolge der Aufträge auf einem Gannt-Diagramm heißt ein Sche- dule.
-Ein Schedule wird durch die Reihenfolge der Aufträge auf einem Gannt-Diagramm in Form einer Liste von entsprechenden Auftragsnummern repräsentiert.
-Auf einem Gannt-Diagramm werden die Positionen der Arbeitsgänge eines Auftrags schrittweise festgestellt.

Als Beispiel repräsentiert ein Schedule (1-2-5-4-3-6) aus den in Tabelle 1¹¹ beschriebenen Daten unter deterministischen Bearbeitungszeiten das in Abbildung 1 dargestellte Gannt- Diagramm.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Gannt-Diagramm von einem Schedule (1-2-5-4-3-6)

3 Genetische Algorithmen (GA) als Lösungsverfahren zum SJSSP

3.1 Klassische GA

GA werden von dem Darwin’schen Prinzip der natürlichen Selektion inspiriert.¹² In GA wird jede potenziale Lösung als Phänotyp genannt. Jeder Phänotyp wird durch einen Genotyp repräsentiert. Die klassische Form der Genotypen ist Bitsequenzen fester Länge. Eine Menge von Genotypen heißt dann eine Population. Abhängig von der Güte der Lösungsmöglichkeit enthält jeder Genotyp eine reelle Zahl als sogenannte Fitness.

Der Ablauf von GA wird in Abbildung 2 beschrieben.¹³ Nach Initialisierung wird die Fitness jedes Genotyps berechnet. Je höher die Fitness eines Genotyps ist, desto höher ist die Wahrscheinlichkeit, dass er nun an der nächsten Generation teilnehmen darf. Mit Hilfe von genetischen Operatoren werden neue Genotypen konstruiert. Zwei typische Operatoren sind Mutation und Crossover. Mutation ermöglicht zufällig auftretende kleine Veränderungen in Genotypen. Eine größere Vielfalt an Nachkommen ermöglicht das Crossover. Das Verfahren wird iteriert, bis die vorgegebne Anzahl der Generation erreicht wird, oder bis ein sonstiges Abbruchkriterium erfüllt ist.

Für eine konkrete Anwendung wird meist ein speziell angepasster Algorithmus entworfen. Die fünf anzupassenden Komponenten sind:¹⁴

-Repräsentation der Genotypen
-Initialisierung der ersten Generation
-Evaluationsfunktion zur Berechung der Fitness eines Genotyps und Selektionsver- fahren

[...]

¹ vgl. Günter und Tempelmeier(1999), Kap.9.1.5, S. 229-231

² vgl. Nakano and Yamada (1991), S. 474 zitiert nach Garey and Johnson (1979); Domschke et al.(1997) Kap. 5.6, S. 396-397

³ vgl. Yoshitomi (2002), S. 484-485

⁴ vgl. Domschke et al.(1997) Kap. 5.1.3, S. 283-299

⁵ vgl. Domschke et al.(1997) Kap. 5.1.3.3, S. 291-299

⁶ vgl. Yoshitomi (2002), S. 484-485

⁷ vgl. Adams et al.(1988), S. 391-392

⁸ vgl. R. Nakano und T. Yamada (1991); Yamada, T. und Nakano (1992); Yamada, T. und Nakano (1997)

⁹ vgl. Kise und Ibaraki (1983), S. 384-388

¹⁰ vgl. Yoshitomi(2002), S. 485

¹¹ vgl. S. 13

¹² Das korrekte Verhalten von GA wird durch das sogenannte Schema-Theorem gesichert. Nach Schema-Theorem erhalten Genotypen überdurch- schnittlicher Fitneß, kurzer definierender Länge und niedriger Ordnung in den Folgegenerationen steigende Chancen, sich zu reproduzieren. vgl. Michalewicz(1996) Kap. 3; vgl. Mitchell(1996), Kap. 4.1 S. 87-94

¹³ vgl. Mitchell (1996) Kap. 1.6, S. 8-10; Michalewicz(1996), S. 1-5

¹⁴ vgl. Michalewicz(1996), Kap.1, S. 17-18