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!
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen.