Angesichts des wachsenden Konkurrenzdruckes, der durch die Globalisierung zunehmend gefördert wird, müssen sich Unternehmen der Herausforderung stellen, den Produktionsablauf flexibel an die Marktbedingungen anzupassen.
Insbesondere das Maschinenbelegungsproblem birgt noch ein hohes Verbesserungspotential. Algorithmen werden ständig verbessert, angepasst oder auch neu entwickelt. Unter der Vielzahl von Lösungen die entwickelt wurden, lassen sich exakte, spezielle heuristische und metaheuristische Methoden unterscheiden. Die erste Gruppe der Verfahren, in die beispielsweise die ganzzahlige lineare Optimierung oder die Vollständige Enumeration eingeordnet werden können, sind lediglich für einige Spezialfälle (wie z.B. den Zwei-Maschinen flow shop unter der Zielsetzung der Minimierung der Zykluszeit) effizient lösbar. Heuristische Verfahren, wie beispielsweise unvollständig durchgeführte Branch-and-Bound-Verfahren, liefern keine befriedigende Lösung des Problems, da ihre Anwendung an Modellannahmen geknüpft sind, die das reale Problem nur unzureichend abbilden.
Ebenso wie die heuristischen Verfahren ermitteln metaheuristische Verfahren, wie das Simulated Annealing, Genetische Algorithmen oder Tabu Search keine optimalen, sondern Kompromisslösungen. Der Vorteil der Methoden der letzten Gruppe ist aber, dass sie flexibel, robust und einfach in der Anwendung sind. Gegenstand dieser Arbeit ist daher eine kritische Auseinandersetzung mit metaheuristischen Verfahren insbesondere dem Ameisenalgorithmus und dem Tabu Search Verfahren und deren Einordnung in ein modernes PPS-System.
Inhaltsverzeichnis
1 Einführung
1.1 Problemstellung
1.2 Gang der Untersuchung
1.3 Definition und Einordnung der Fließfertigung im PPS – System
2 Tabu – Search Verfahren
2.1 Historische Entwicklung
2.2 Mathematische Grundlagen
2.3 Allgemeiner Ansatz des Tabu Search Verfahrens
2.3.1 Erläuterung grundlegender Begriffe
2.3.1.1 Zug
2.3.1.2 Tabuliste
2.3.1.3 Tabudauer
2.3.2 Das Tabu Search Verfahren als Algorithmus
2.4 Verwendung des Tabu Search Verfahrens zur Lösung eines Maschinenbelegungsproblems
3 Ameisenalgorithmus
3.1 Anwendungsbereiche
3.2 Das Brückenexperiment
3.3 Modellierung von künstlichen Ameisen
3.4 Allgemeiner Ansatz des Ameisenalgorithmus
3.5 Verwendung des Ameisenalgorithmus zur Lösung des Traveling Salesman Problems (TSP)
3.6 Beispielhafte Belegung des Algorithmus anhand eines Ein-Maschinen- Planungsproblems
3.7 Verwendung des Ameisenalgorithmus zur Lösung eines Ein- Maschinen- Planungsproblems
4 Schlussbetrachtung
Zielsetzung & Themen
Die Arbeit befasst sich mit der kritischen Auseinandersetzung und Einordnung metaheuristischer Verfahren zur Produktionssteuerung in moderne PPS-Systeme, um bei steigendem Konkurrenzdruck und komplexen Maschinenbelegungsproblemen effiziente Lösungen zu erzielen.
- Grundlagen der Fließfertigung im PPS-System
- Methodische Analyse des Tabu Search Verfahrens
- Untersuchung des Ameisenalgorithmus und seiner biologischen Inspiration
- Praktische Anwendung der Algorithmen auf Maschinenbelegungsprobleme
- Gegenüberstellung und Bewertung der metaheuristischen Ansätze
Auszug aus dem Buch
2.3.1.2 Tabuliste
Die Tabuliste speichert den Suchverlauf des Algorithmus. Sie beinhaltet entgegengesetzte Aktionen von früheren Zügen. Die Leistung von TS wird hauptsächlich durch die Länge der Tabuliste und die Operatoren, die die Liste verändern, bestimmt. Operatoren legen das Hinzufügen bzw. das Entfernen von Tabuzügen fest. Bei komplexeren Aufgaben besteht das Problem, dass der Umfang der bereits besuchten Lösungen mit der Anzahl der durchgeführten Iterationen steigt.24 Da ein Speichern aller Lösungen hohe Speicherkapazitäten erfordert, setzt man Züge „tabu“, d.h., man beachtet sie für eine bestimmte Zeit (Tabudauer) nicht. Die Zahl der Iterationen, in denen man Züge „tabu“ setzt, ist dabei selbst festzulegen.
Nach Ablauf der definierten Tabudauer wird dieser Zug wieder aus der Tabuliste gelöscht bzw. überschrieben. Hierbei gilt in der Regel das FIFO-Prinzip, dass heißt, dass der erste Zug, der tabu gesetzt wurde, auch als erstes wieder raus geht.25 Wesentlich bedeutender als der Startwert ist ein intelligentes Handhaben der Tabuliste, wozu auch die Länge der Tabuliste t gehört. Eine zu kurz gewählte Länge kann ein lokales Optima nicht verhindern, eine zu lange Tabuliste wird dagegen viele möglicherweise sehr gute Züge von vornherein ausschließen oder gar für den Abbruch des Verfahrens sorgen, falls alle Züge zu einer Lösung in der Nachbarschaft bereits auf der Tabuliste stehen. Grundsätzlich scheint t im Intervall von 7 bis 10 sehr gute Lösungen zu liefern.26
Zusammenfassung der Kapitel
1 Einführung: Diese Einleitung beleuchtet die steigende Bedeutung flexibler Produktionsabläufe unter Wettbewerbsdruck und führt in die Thematik metaheuristischer Optimierungsverfahren ein.
2 Tabu – Search Verfahren: Dieses Kapitel erläutert die Funktionsweise von Tabu Search, inklusive der mathematischen Grundlagen, der Mechanismen zur Vermeidung lokaler Optima und der praktischen Anwendung auf Maschinenbelegungsprobleme.
3 Ameisenalgorithmus: Hier werden die biologischen Grundlagen, die Modellierung künstlicher Ameisen und die Anwendung des Algorithmus auf kombinatorische Problemstellungen wie das TSP und Ein-Maschinen-Planungsprobleme detailliert beschrieben.
4 Schlussbetrachtung: Das Fazit fasst die Eignung der untersuchten Metaheuristiken zusammen und reflektiert deren Vor- und Nachteile sowie die zukünftige Bedeutung für die industrielle Praxis.
Schlüsselwörter
Produktionssteuerung, Maschinenbelegungsproblem, Tabu Search, Ameisenalgorithmus, PPS-System, Metaheuristik, Fließfertigung, Optimierung, Schwarmintelligenz, Pheromon, Traveling Salesman Problem, Rüstzeitminimierung, lokale Optima, Nachbarschaftssuche.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit untersucht den Einsatz moderner metaheuristischer Algorithmen, speziell Tabu Search und Ameisenalgorithmen, zur Optimierung komplexer Produktionsabläufe.
Was sind die zentralen Themenfelder?
Die Arbeit fokussiert auf Maschinenbelegungsprobleme, die Fließfertigung sowie die theoretische und methodische Fundierung von Optimierungsheuristiken.
Was ist das primäre Ziel der Forschungsarbeit?
Das Ziel ist eine kritische Auseinandersetzung mit diesen Verfahren und deren erfolgreiche Einordnung in moderne Produktionsplanungs- und Steuerungssysteme (PPS).
Welche wissenschaftlichen Methoden werden verwendet?
Es erfolgt eine literaturbasierte Analyse mathematischer Optimierungsgrundlagen, ergänzt durch beispielhafte Berechnungen für spezifische Planungsszenarien.
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil gliedert sich in die detaillierte theoretische Herleitung der Tabu-Search-Logik und die Erklärung des Ameisenalgorithmus, jeweils untermauert durch praxisnahe Anwendungsbeispiele.
Welche Schlüsselwörter charakterisieren die Arbeit am besten?
Die Arbeit ist maßgeblich durch Begriffe wie Metaheuristik, Produktionssteuerung, Tabu Search, Ameisenalgorithmus und Optimierung gekennzeichnet.
Warum spielt die Tabuliste eine so entscheidende Rolle beim Tabu Search?
Die Tabuliste dient als Kurzzeitgedächtnis, das verhindert, dass der Algorithmus in bereits besuchte Zustände zurückfällt, und ermöglicht so das Überwinden lokaler Optima.
Welche Bedeutung haben Pheromone im Kontext des Ameisenalgorithmus?
Pheromone fungieren als Informationsmedium, das die Qualität gefundener Lösungen markiert und den nachfolgenden künstlichen Ameisen hilft, den Weg zur optimalen Lösung zu finden.
- Quote paper
- Jan Frenzel (Author), Hermine Tschek (Author), 2004, Neuere Algorithmen in der Produktionssteuerung, Munich, GRIN Verlag, https://www.grin.com/document/47876
