Für die Planung von Produktionsabläufen bei der Waferbearbeitung werden verschiedene konventionelle Algorithmen eingesetzt. Diese sind, bedingt durch die Komplexität des Problems und die bei der Produktion entstehenden Kosten, zu optimieren. Ziel dieser Arbeit ist es ausgewählte evolutionäre Heuristiken von der Natur auf das Optimierungsproblem für ein Cluster Tool zu übertragen.
Nach einer Beschreibung der Grundlagen, erfolgt die schrittweise Adaption des Ameisenalgorithmus und des Partikel Schwarm Algorithmus in ein mathematisches Modell. Anschließend finden eine Analyse der einzelnen Strategien, sowie ein Vergleich mit herkömmlichen Lösungsverfahren statt. Die Untersuchung zeigt, dass der Ameisenalgorithmus in den getesteten Formen für das gegebene kombinatorische sequenzabhängige Schedulingproblem nicht effizient nutzbar ist. Der Partikel Schwarm Algorithmus stellt im Gegensatz eine vorteilhafte Alternative zu bisherigen Verfahren dar.
Inhaltsverzeichnis
1 Einleitung
2 Grundlagen
2.1 Einordnung des Themengebietes
2.2 Vorbild Natur
2.3 Problemstellung
2.4 Basis der Optimierung
2.5 Aufbau und Funktionsweise eines Cluster Tools
2.6 Matrix Prediciton Method
2.7 Struktur des Suchraumes und Lösungsansätze
3 Algorithmen
3.1 Random Down Swing
3.1.1 Implementierung
3.1.2 Optimierung
3.1.3 Modifikationen
3.2 Ameisenalgorithmus
3.2.1 Das Vorbild in der Natur
3.2.2 Anwendung auf Scheduling
3.2.3 Implementierung
3.2.4 Monte Carlo Auswahl
3.3 Partikel Schwarm Algorithmus
3.3.1 Das Vorbild der Natur
3.3.2 Anwendung auf Scheduling
3.3.3 Implementierung
3.3.4 Richtungsableitung
3.4 Vergleichsalgorithmen
3.4.1 Monte Carlo Methode
3.4.2 Random Walk
3.4.3 Simulated Annealing
3.4.4 Genetischer Algorithmus
3.4.5 Brute Force
3.4.6 Strong Derivative
4 Simulation
4.1 Framework
4.2 Simulationsumgebung
4.3 Random Down Swing
4.3.1 Shift oder Swap
4.3.2 Modifikation
4.4 Ameisenalgorithmus
4.4.1 Pheromonablagerung
4.4.2 Gruppenmarkierung
4.4.3 Verwitterung
4.4.4 Auswertung der Ameisenalgorithmus Ergebnisse
4.5 Partikel Schwarm Algorithmus
4.5.1 Modifikation
4.5.2 Richtungsableitung
4.6 Vergleich der Algorithmen
4.6.1 Berechnungsaufwand
4.6.2 Leistung in Abhängigkeit der Wiederholungsanzahl und Loadportanzahl
4.6.3 Unterschiedliche Maschinen
4.6.4 Vergleich mit dem Optimum in ausgewählten Aufgaben
5 Zusammenfassung und Ausblick
A Werkzeuge und Hilfsmittel
B Simulation
B.1 Simulationsumgebung
B.1.1 Betriebsumgebungen
B.1.2 Testfälle
B.2 Random Down Swing
B.2.1 Shift oder Swap
B.2.2 Swap Modifikationen
B.2.3 Swap Modifikationen vier Loadports
B.3 Ameisenalgorithmus
B.4 Partikel Schwarm Algorithmus
B.5 Vergleich der Algorithmen bei unterschiedlichen Loadportanzahlen
B.6 Vergleich mit Optimum
Zielsetzung & Themen
Die vorliegende Arbeit zielt darauf ab, evolutionäre Heuristiken zur Optimierung von komplexen, sequenzabhängigen Schedulingproblemen bei Cluster Tools in der Halbleiterindustrie zu implementieren und zu evaluieren, um die Produktionszeit zu verkürzen und Kosten zu senken.
- Adaption von Ameisenalgorithmen und Partikel Schwarm Algorithmen auf Scheduling-Modelle.
- Entwicklung eines Frameworks zur Simulation und mathematischen Modellierung von Produktionsabläufen.
- Vergleich der neuartigen Metaheuristiken mit konventionellen Lösungsverfahren und dem globalen Optimum.
- Untersuchung der Einflussfaktoren wie Loadport-Anzahl und Iterationsanzahl auf die Leistung der Algorithmen.
Auszug aus dem Buch
2.2 Vorbild Natur
Im Tierreich lassen sich Möglichkeiten zur Lösung von Optimierungsproblemen finden. Tiere leben in Kolonien, bilden Schwärme und interagieren mit ihrer Umwelt und miteinander. Durch das Zusammenwirken der einzelnen Lebewesen über das soziale Verhalten gelingt es ihnen komplexe Aufgaben zu bewältigen. Die Koordination erfolgt dabei meist ohne zentrale Steuerung. Diese Dezentralisierung ist oft auch ein Designkriterium beim Entwurf moderner verteilter Informationssysteme. Dies setzt ein hohes Maß an Selbstorganisation voraus. Solche Systeme sind sehr flexibel, robust und fehlertolerant gegenüber dem Versagen einzelner Teile. Die aus dem sozialen Verhalten resultierende Gruppendynamik ist kaum vorhersagbar. In den hier betrachteten Algorithmen besitzen die einzelnen Lebewesen nur sehr eingeschränkte kognitive Fähigkeiten. Anspruchsvolle Aufgaben werden durch das gemeinschaftliche Verhalten erfüllt und nicht durch die Leistung eines Individuums. Diese Organisationsform wird Superorganismus genannt. Das emergente Verhalten auf der Mikroebene spiegelt seine Auswirkung erst auf der Makroebene wieder. Das ist der Grundgedanke der kollektiven Intelligenz, welche auch als Schwarmintelligenz bezeichnet wird. Das Zusammenwirken der spezialisierten Handlungsweisen übertrifft die Möglichkeit der einzelnen Mitglieder. Der klassische Superorganismus dieser Kategorie ist der Ameisenstaat. Eine einfache Form von Superorganismen stellen Schwärme dar. Zum Beispiel bewegen sich Fische im Schwarm, um Feinde zu irritieren.
Zusammenfassung der Kapitel
1 Einleitung: Diese Einleitung führt in die Bionik ein und erläutert die Motivation, biologisch inspirierte Schwarmintelligenz auf komplexe Schedulingprobleme in der Wafer-Produktion zu übertragen.
2 Grundlagen: Hier werden das Themengebiet der Evolutionary Computation, biologische Vorbilder und das spezifische Scheduling-Problem an Cluster Tools mathematisch beschrieben.
3 Algorithmen: Dieses Kapitel detailliert die verschiedenen verwendeten Optimierungsstrategien, darunter Random Down Swing, Ameisenalgorithmus und Partikel Schwarm Algorithmus, sowie deren mathematische Adaption.
4 Simulation: In diesem Teil erfolgt die praktische Evaluierung der Algorithmen mittels eines Java-basierten Frameworks anhand verschiedener Testfälle und Parameterkombinationen.
5 Zusammenfassung und Ausblick: Das Fazit bewertet die Eignung der untersuchten Metaheuristiken für Schedulingprobleme und gibt einen Ausblick auf potenzielle Erweiterungen der Arbeit.
Schlüsselwörter
Scheduling, Cluster Tools, Evolutionary Computation, Ameisenalgorithmus, Partikel Schwarm Algorithmus, Schwarmintelligenz, Optimierung, Simulation, Metaheuristiken, Wafer-Produktion, Durchsatz, Gesamtbearbeitungszeit, Bionik, Sequenzabhängigkeit, Komplexe Systeme.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit befasst sich mit der Anwendung und Evaluierung von evolutionären Optimierungsalgorithmen zur effizienten Planung von Produktionsabläufen bei Cluster Tools in der Halbleiterfertigung.
Was sind die zentralen Themenfelder der Arbeit?
Die zentralen Felder sind Scheduling-Probleme, Schwarmintelligenz, die mathematische Modellierung komplexer Produktionsprozesse und die computergestützte Simulation von Optimierungsverfahren.
Was ist das primäre Ziel der Untersuchung?
Ziel ist es, durch den Einsatz von aus der Natur inspirierten Heuristiken die Produktionszeiten bei der Waferbearbeitung zu minimieren und den Durchsatz zu maximieren.
Welche wissenschaftlichen Methoden werden verwendet?
Es werden Metaheuristiken (insbesondere Ant Colony Optimization und Particle Swarm Optimization) implementiert und mittels Java-Simulationen unter variierenden Parametern und Testreihen mit konventionellen Algorithmen verglichen.
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil gliedert sich in die algorithmische Beschreibung und Anpassung an das Scheduling-Problem (Kapitel 3) sowie die umfangreiche Analyse und Simulation des Verhaltens dieser Algorithmen in verschiedenen Szenarien (Kapitel 4).
Welche Begriffe charakterisieren die Arbeit?
Wichtige Begriffe sind Scheduling, Cluster Tools, Partikel Schwarm Algorithmus, Ameisenalgorithmus, Durchsatz, Gesamtbearbeitungszeit und Metaheuristiken.
Warum ist die Wahl des Ameisenalgorithmus problematisch?
Die Analyse ergab, dass der Ameisenalgorithmus aufgrund des hochdimensionalen und multimodalen Suchraums bei den getesteten Problemstellungen keine effizienten Lösungen liefern kann, da er in der beschriebenen Form keine konsistente Konvergenz erreicht.
Inwiefern beeinflusst die Anzahl der Loadports das Scheduling?
Die Anzahl der Loadports limitiert die Parallelverarbeitung der Wafer und erhöht die Komplexität des Scheduling-Problems, da sie die Konkurrenz der Jobs um Ressourcen maßgeblich beeinflusst.
- Citar trabajo
- Peter Hillmann (Autor), 2010, Implementierung und Evaluation von Heuristiken aus dem Gebiet "Evolutionary Computation" zur Lösung komplexer Schedulingprobleme, Múnich, GRIN Verlag, https://www.grin.com/document/353388
