Ablaufplanungsheuristiken für parallele Maschinen mit reihenfolgeabhängigen Umrüstzeiten

FernUniversität in Hagen
Fakultät für Mathematik und Informatik
Lehrgebiet Unternehmensweite Softwaresysteme

Ablaufplanungsheuristiken für parallele Maschinen mit
reihenfolgeabhängigen Umrüstzeiten

Diplomarbeit

an der Fakultät für Mathematik und Informatik
der FernUniversität in Hagen

Bearbeiter : Mark Blume
Bearbeitungszeit: 6 Monate
Abgabetermin : 27. Oktober 2009

Inhaltsverzeichnis
1 Einleitung 1
2 Ablaufplanungsprobleme für parallele Maschinen mit reihenfolgeabhängigen Umrüstzeiten 3
2.1 Motivation 3
2.2 Problembeschreibung  4
2.2.1 Problembeschreibung anhand eines Beispiels 4
2.2.2 Formale Beschreibung des Problems 7
2.3 Diskussion von Vorarbeiten 11
3 Konzept zur Lösung des Problems 15
3.1 Prioritätsbasierte Heuristiken  15
3.2 Anwendung der ATCS-Regel auf das Pm|sij | wjTj-Problem 18
3.3 ACO-Metaheuristik 19
3.3.1 Futtersuche von Ameisen  20
3.3.2 AS 21
3.3.3 ACS 23
3.3.4 ASRank  25
3.3.5 MMAS  25
3.3.6 ACO 26
3.4 Anwendung der ACO-Metaheuristik auf das Pm|sij | wjTj-Problem 28
3.4.1 Anwendung der ACO-Metaheuristik auf Ablaufplanungsprobleme 28
3.4.2 Konstruktion des Graphen für die ACO-Metaheuristik 30
3.4.3 Anwendung der ACO-Metaheuristik auf das Pm|sij |wjTj-Problem 38
4 Implementierung 45
4.1 Repräsentation von Probleminstanz und Problemlösung 45
4.2 Implementierung der ATCS-Regel 47
4.3 Implementierung der ACO-Metaheuristik 49
5 Leistungsbewertung 51
5.1 Vergleich der Kostenfunktionen für die ATCS-Heuristik 52
5.2 Leistungsbewertung der ACO-Heuristik 53
5.2.1 Testreihe 1: SMaxMin = false, SPos = false 53
5.2.2 Testreihe 2: SMaxMin = true, SPos = false 59
5.2.3 Testreihe 3: SMaxMin = false, SPos = true  62
5.2.4 Testreihe 4: Benchmarktest  65
6 Zusammenfassung 69
Literaturverzeichnis 71
B Dateiformate der Testdaten 83
B.1 ATCS - Vergleich der Kostenfunktionen  83
B.2 ACO - Parametertest 84
C Benchmarktest - Verbesserungen 85

1 Einleitung
Diese Arbeit beschäftigt sich mit dem Problem der Verteilung und Festlegung der Reihenfolge von Jobs mit reihenfolgeabhängigen Umrüstzeiten auf parallele, identische Maschinen. Als Leistungsmaß soll die totale gewichtete Verspätung minimiert werden. Das Ziel dieser Arbeit besteht darin, für dieses Ablaufplanungsproblem ein Verfahren auf Basis der Ant-Colony-Optimazation(ACO)-Metaheuristik zu entwickeln. Die ACO-Metaheuristik ist in [Dor99] beschrieben. Ein Verfahren auf Basis der ACO-Metaheuristik für das analoge Einzelmaschinenproblem ist in [Lia07] vorgestellt worden. Das dort vorgestellte Verfahren dient als Ausgangspunkt der vorliegenden Arbeit.

In Kapitel 2 wird zunächst das Problem erläutert. Es werden Beispiele genannt und das Problem formal beschrieben. Weiterhin erfolgt eine Vorstellung von Arbeiten, in denen sich mit der Anwendung der ACO-Metaheuristik auf Ablaufplanungsprobleme bereits beschäftigt wurde.

In Kapitel 3 wird das Konzept zur Anwendung der ACO-Metaheuristik auf das Problem erarbeitet. Zunächst wird die Apparent-Tardiness-Cost-with-Setups(ATCS)-Heuristik als prioritätsbasierte Heuristik vorgestellt. Die ATCS-Heuristik soll als Referenzheuristik dienen. Anschließend wird die ACO-Metaheuristik beschrieben und das Konzept für die Anwendung der ACO-Metaheuristik auf das gegebene Ablaufplanungsproblem vorgestellt.

Nachdem in Kapitel 4 auf die Implementierung des Verfahrens eingegangen wurde, erfolgt in Kapitel 5 eine Leistungsbewertung des Verfahrens.

[...]

Für eine erweiterte Vorschau bitte auf das Buch-Cover neben dem Buchtitel oben klicken!