In dieser Arbeit wird versucht, für ein spezifisches Ablaufplanungsproblem eine lokale Suche anzuwenden, mit dem Ziel eine bessere Lösung zu finden.
Dabei wird zunächst das spezifische Problem im Abschnitt 2 erklärt und dann wird im Abschnitt 3 beschrieben, wie die Startlösung des Problems zur Verfügung gestellt wird. Im Abschnitt 4 wird nach einer kurzen Definition von lokaler Suche angedeutet, wie die lokale Suche bei diesem Problem angewendet werden kann. Die Idee zur Anwendung der lokalen Suche muss danach in C-Programm implementiert werden. Die genaue Beschreibung, wie die lokale Suche in C-Programm umgesetzt wird, wurde im Abschnitt 5 geschrieben. Das Ziel dieser Arbeit erfordert eine Anwendung der lokalen Suche an zahlreichen Beispielen, um zu untersuchen, wie gut die vorgeschlagene lokale Suche funktioniert. Aus diesem Grund wurde die vorgeschlagene lokale Suche mit Hilfe von C-Programm auf 200 verschiedene Instanzen, in denen alle benötigten Daten eines Problems stehen, angewendet und die Ergebnisse sowie die Analyse der Ergebnisse im Abschnitt 6 besprochen.
Inhaltsverzeichnis
1 Einleitung
2 Das untertägige Ablaufplanungsproblem
3 Erstellung einer Startlösung
4 Lokale Suche
4.1 Grundlage der lokalen Suche
4.2 Lokale Suche bei dem untertägigen Ablaufplanungsproblem
4.2.1 Darstellung der Startlösung
4.2.2 Bestimmung der benachbarten Lösung
4.2.3 Abbruchkriterium der lokalen Suche
5 Implementierung der lokalen Suche in C-Programm
6 Ergebnisse nach der Anwendung der lokalen Suche
7 Fazit
Zielsetzung & Themen
Die vorliegende Arbeit zielt darauf ab, ein spezifisches Ablaufplanungsproblem im Untertagebau durch die Anwendung einer lokalen Suche zu optimieren, um eine effizientere Fertigstellungszeit zu erreichen.
- Analyse und mathematische Modellierung des untertägigen Ablaufplanungsproblems.
- Entwicklung und Implementierung einer heuristischen Methode zur Erstellung einer validen Startlösung.
- Anwendung lokaler Suchverfahren zur iterativen Verbesserung der Lösungsgüte.
- Einsatz von C-Programmierung zur algorithmischen Umsetzung und Durchführung von Simulationen.
- Umfangreiche Evaluierung der Methode anhand von 200 verschiedenen Instanzen.
Auszug aus dem Buch
4.2.1 Darstellung der Startlösung
Um lokale Suche anwenden zu können, muss die Startlösung, die anhand der beschriebenen Heuristik im Abschnitt 3 zur Verfügung gestellt wurde, dargestellt werden. Die Darstellung erfolgt anhand eines Digraphen (basiert auf von Roy & Sussmann hergestelltem Disjunktivgraphen [1964]), dessen Knoten die Bearbeitung eines Jobs an einer Stufe repräsentiert. Zu diesen Knoten werden zwei anderen Knoten, nämlich Quelle und Senke, hinzugefügt. Also ist die Anzahl an Knoten in diesem Graphen maximal gleich dem Produkt aus Anzahl an Jobs und Anzahl an Stufen plus 2. Es kann auch vorkommen, dass weniger Knoten zur Darstellung der Startlösung gebraucht werden, wenn einige Jobs, die an der ersten Stelle ihrer Kette stehen, zum Zeitpunkt Null nicht vor der ersten Stufe stehen.
Ein Knoten mit der Beschriftung i,k repräsentiert also die Bearbeitung von Job i an Stufe k. Die Maschine, an der Job i an Stufe k bearbeitet wurde, wird separat gespeichert. In dieser Arbeit wurde zwischen den Maschinen mit verschiedenen Farben unterschieden.
Von Quelle zu den Knoten, die Bearbeitung der Jobs an ihrer ersten Stufe zum Zeitpunkt Null repräsentieren, gibt es einen Pfeil mit der Bewertung Null. Für k≤7 gibt es von dem Knoten i,k zu dem Knoten i,k+1 einen Pfeil mit der Bewertung P_{i,k,n_{i,k}}, wobei n_{i,k} die Maschine ist, an der Job i an Stufe k bearbeitet wurde. Von den Knoten i,8 geht ein Pfeil mit der Bewertung P_{i,8,n_{i,8}} zu der Senke, falls Job i der letzte Job seiner Kette ist, aber wenn Job i noch Nachfolger in seiner Kette hat, geht ein Pfeil mit der Bewertung P_{i,8,n_{i,8}} zum Knoten i+1,1.
Zusammenfassung der Kapitel
1 Einleitung: Die Einleitung umreißt die Zielsetzung der Arbeit, ein lokales Suchverfahren zur Verbesserung eines spezifischen Ablaufplanungsproblems einzusetzen und dessen Effektivität zu untersuchen.
2 Das untertägige Ablaufplanungsproblem: Dieses Kapitel definiert die technologischen Ketten und Arbeitsstufen im untertägigen Abbau, die als Grundlage für das zu optimierende Hybrid-Flow-Shop-Problem dienen.
3 Erstellung einer Startlösung: Es wird eine Heuristik basierend auf der MWR-Prioritätsregel ("Most Work Remaining") vorgestellt, um eine zulässige Ausgangsbasis für die weitere Optimierung zu generieren.
4 Lokale Suche: Der theoretische Rahmen für die lokale Suche wird gelegt, inklusive der Darstellung der Lösung als Digraph, des Austauschs von Nachbarschaften zur Lösungsverbesserung und der Definition von Abbruchkriterien.
5 Implementierung der lokalen Suche in C-Programm: Das Kapitel beschreibt die technische Umsetzung der Algorithmen (einschließlich des Tripel-Verfahrens) in der Programmiersprache C.
6 Ergebnisse nach der Anwendung der lokalen Suche: Eine empirische Auswertung anhand von 200 Instanzen verdeutlicht die Performance der entwickelten Methode und analysiert die Einflüsse unterschiedlicher Parameter auf die Lösungsqualität.
7 Fazit: Die Arbeit fasst zusammen, dass die Kombination aus lokaler Suche und Verbesserungsverfahren bei spezifischen Konfigurationen im Untertagebau effektiv anwendbar ist.
Schlüsselwörter
Ablaufplanungsproblem, lokaler Suche, Startlösung, Heuristik, MWR-Prioritätsregel, Hybrid-Flow-Shop, Digraph, Disjunktivgraph, Fertigstellungszeit, C-Programmierung, Optimierung, untertägiger Abbau, technologische Ketten, Nachbarschaftsoperator, Tripel-Algorithmus.
Häufig gestellte Fragen
Worum geht es in dieser Bachelorarbeit grundsätzlich?
Die Arbeit beschäftigt sich mit der Optimierung eines Ablaufplanungsproblems im Untertagebau, bei dem verschiedene Arbeitsstufen und technologische Ketten von Jobs effizient aufeinander abgestimmt werden müssen.
Was sind die zentralen Themenfelder der Arbeit?
Die Arbeit verknüpft Themen der Betriebswirtschaftslehre und Unternehmensforschung, insbesondere Produktionsplanung, Ablaufplanung im Hybrid-Flow-Shop sowie die Anwendung von Suchheuristiken.
Was ist das primäre Ziel oder die Forschungsfrage?
Das Hauptziel ist es, ein lokales Suchverfahren zu implementieren, um die maximale Fertigstellungszeit (Makespan) bei einem untertägigen Planungsproblem gegenüber einer heuristischen Startlösung zu verbessern.
Welche wissenschaftliche Methode wird verwendet?
Es werden heuristische Verfahren zur Erstellung einer Startlösung, lokale Suchoperatoren zur iterativen Verbesserung sowie graphbasierte Repräsentationen (Digraphen) verwendet, die rechnerisch mittels des Tripel-Algorithmus ausgewertet werden.
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil gliedert sich in die Problemdefinition, die mathematische Modellierung mittels Disjunktivgraphen, die Implementierung des Optimierungsalgorithmus in C und eine umfangreiche Simulation an 200 Testinstanzen.
Welche Schlüsselwörter charakterisieren die Arbeit?
Die Arbeit lässt sich primär über die Begriffe Ablaufplanung, lokale Suche, Hybrid-Flow-Shop und MWR-Heuristik definieren.
Wie unterscheidet sich die "gleiche Kettenlänge" von der "unterschiedlichen Kettenlänge" in den Ergebnissen?
Die Ergebnisse zeigen, dass bei unterschiedlichen Kettenlängen durch die Anpassung der Reihenfolge oft deutlichere Verbesserungen erzielt werden können, da die MWR-Werte der Jobs dort stärker voneinander abweichen.
Warum wird für die Implementierung die Programmiersprache C gewählt?
Die Sprache C bietet die notwendige Performanz für die rechenintensiven Algorithmen der lokalen Suche, insbesondere bei der wiederholten Anwendung auf eine große Anzahl von Instanzen und bei der Manipulation der Digraphen-Datenstrukturen.
Welche Rolle spielt die MWR-Regel bei der Startlösung?
Die MWR-Regel ("Most Work Remaining") priorisiert Jobs mit einer höheren verbleibenden Gesamtarbeit, um sicherzustellen, dass kritische Pfade im Prozess frühzeitig berücksichtigt und Engpässe vermieden werden.
- Quote paper
- Cinna Seifi (Author), 2014, Lokales Suchverfahren für ein untertägiges Ablaufplanungsproblem, Munich, GRIN Verlag, https://www.grin.com/document/452531
