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-Optimization(ACO)-Metaheuristik zu entwickeln.
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.
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!
Häufig gestellte Fragen
Worum geht es in der Diplomarbeit "Ablaufplanungsheuristiken für parallele Maschinen mit reihenfolgeabhängigen Umrüstzeiten"?
Die Diplomarbeit beschäftigt sich mit der Verteilung und Festlegung der Reihenfolge von Jobs mit reihenfolgeabhängigen Umrüstzeiten auf parallele, identische Maschinen. Das Ziel ist die Minimierung der totalen gewichteten Verspätung. Ein Verfahren auf Basis der Ant-Colony-Optimization(ACO)-Metaheuristik soll für dieses Ablaufplanungsproblem entwickelt werden.
Welche Themen werden in der Arbeit behandelt?
Die Arbeit behandelt unter anderem die folgenden Themen:
- Ablaufplanungsprobleme für parallele Maschinen mit reihenfolgeabhängigen Umrüstzeiten (Motivation, Problembeschreibung, formale Beschreibung des Problems, Diskussion von Vorarbeiten)
- Konzept zur Lösung des Problems (Prioritätsbasierte Heuristiken, Anwendung der ATCS-Regel, ACO-Metaheuristik, Anwendung der ACO-Metaheuristik auf das Pm|sij | wjTj-Problem)
- Implementierung des Verfahrens
- Leistungsbewertung des Verfahrens
Was ist das Ziel der Arbeit?
Das Ziel der Arbeit ist die Entwicklung eines Verfahrens auf Basis der ACO-Metaheuristik zur Lösung des Problems der Ablaufplanung auf parallelen Maschinen mit reihenfolgeabhängigen Umrüstzeiten, wobei die totale gewichtete Verspätung minimiert werden soll.
Welche Heuristiken werden in der Arbeit untersucht?
Die Arbeit untersucht die Apparent-Tardiness-Cost-with-Setups (ATCS)-Heuristik als prioritätsbasierte Heuristik und die ACO-Metaheuristik. Die ATCS-Heuristik dient als Referenzheuristik.
Was ist die ACO-Metaheuristik?
Die ACO-Metaheuristik (Ant-Colony-Optimization) ist ein Verfahren, das von der Futtersuche von Ameisen inspiriert ist. Es wird zur Lösung von Optimierungsproblemen eingesetzt.
Welche Kapitel enthält die Arbeit?
Die Arbeit ist in folgende Kapitel gegliedert:
- Einleitung
- Ablaufplanungsprobleme für parallele Maschinen mit reihenfolgeabhängigen Umrüstzeiten
- Konzept zur Lösung des Problems
- Implementierung
- Leistungsbewertung
- Zusammenfassung
- Literaturverzeichnis
- Dateiformate der Testdaten
- Benchmarktest - Verbesserungen
Wo finde ich weiterführende Informationen zu dem Thema?
Weiterführende Informationen sind im Literaturverzeichnis der Arbeit aufgeführt. Zudem wird auf die Arbeit von [Lia07] verwiesen, die ein Verfahren auf Basis der ACO-Metaheuristik für das analoge Einzelmaschinenproblem vorstellt.
Wer ist der Bearbeiter der Diplomarbeit?
Der Bearbeiter der Diplomarbeit ist Mark Blume.
Wann war der Abgabetermin für die Diplomarbeit?
Der Abgabetermin war der 27. Oktober 2009.
- Citar trabajo
- Mark Blume (Autor), 2009, Ablaufplanungsheuristiken für parallele Maschinen mit reihenfolgeabhängigen Umrüstzeiten , Múnich, GRIN Verlag, https://www.grin.com/document/149578
