Die Ablaufplanung für Werkstattproduktion befasst sich mit der Zuordnung von Aufträgen zu Arbeitssystemen bzw. Maschinen und umgekehrt unter Beachtung des Rüstzustands
der Maschinen und der Verfügbarkeit von Werkzeugen, Transportmitteln usw.
Es wird in die Feinplanung des hierarchischem Planungskonzepts eingeordnet.
Bei Job Shop Scheduling Problem(JSSP) handelt es sich um die verallgemeinerte Ablaufplanung für Werkstattproduktion ohne Berücksichtigung der reihenfolgeabhängigen
Rüstzustände der Maschinen und Kapazitätsrestriktionen von Werkzeugen, Transportmitteln usw. Viele JSSP sind sowohl NP-Vollständig als auch eins die schlechsten in dieser
Problemklasse. Die meisten untersuchten Lösungsansätze eignen sich nur für deterministische
Bearbeitungszeiten. Ihre praktischen Einsatzmöglichkeiten sind daher relativ begrenzt. Genetische Algorithmen(GA) zählen zu den populären Lösungsverfahren, die
auf verschiede Arten Optimierungsprobleme angewandt sind.
Gegenstand der Seminararbeit ist die Darstellung eines genetischen Algorithmus(GAUCE), der das JSSP unter stochastischen Bearbeitungszeiten lösen kann. Nach einer Einführung
in der Problematik der Ablaufplanung wird GAUCE detailliert dargestellt. In der Folge werden numerische Experimente und deren Ergebnisse analysiert und diskutiert. Abschließend werden Kritiken und weitere Aspekte beschrieben.
Inhaltsverzeichnis
1 Einfuhrung zur stochastischen Ablaufplanung
2 Modelle zur Ablaufplanung
2.1 Statisches Job Shop Scheduling Problem (JSSP)
2.2 Stochastisches JSSP (SJSSP)
3 Genetische Algorithmen (GA) als Lösungsverfahren zum SJSSP
3.1 Klassische GA
3.2 Monte Carlo Simulation (MC)
3.3 GAUCE Verfahren
3.3.1 Repräsentation
3.3.2 Initialisierung der ersten Population
3.3.3 Evaluationsfunktion und Selektionsverfahren
3.3.4 Genetische Operatoren
4 Numerische Experimente und Analyse
4.1 Experimentsrahmen
4.2 Ergebnisse und Analyse
5 Kritik
6 Fazit und Ausblick
A Programm GEAL
Zielsetzung & Themen
Die vorliegende Arbeit zielt darauf ab, ein Verfahren zur Lösung des Job Shop Scheduling Problems (JSSP) unter stochastischen Bedingungen zu präsentieren, wobei ein genetischer Algorithmus namens GAUCE eingesetzt wird, um ein approximatives Optimum für die Zykluszeit zu finden.
- Grundlagen der stochastischen Ablaufplanung
- Modellierung des JSSP und SJSSP
- Einsatz genetischer Algorithmen als Lösungsansatz
- Anwendung des GAUCE-Verfahrens
- Durchführung und Analyse numerischer Experimente
Auszug aus dem Buch
3.3 GAUCE Verfahren
Stochastische Programmierung ist eine Art mathematischer Programmierung unter Berücksichtigung der Unsicherheit, die i. d. R. durch eine Verteilung mit passenden Parametern charakterisiert werden kann. Dabei kann sich eine Verteilung hinsichtlich des Zielfunktionswertes für jede Lösungsmöglichkeit ergeben.
Um eine stochastische Programmierung anhand GA zu lösen, wird es angenommen, dass die stochastischen Einflusse auf die Zielfunktion und/oder die Restriktionen in der stochastischer Programmierung als die stochastischen Einflusse auf die Evaluationsfunktion in GA betrachtet werden. Solche GA werden auch als GAUCE genannt.
Die zugrundlegende Hypothese von GAUCE lautet, dass der Genotyp mit der höchsten Häufigkeit über alle Generationen die optimale Lösung ist. In klassischen GA betrachtet man dagegen das Optimum als den Genotyp mit der höchsten Fitness z. B. in der letzten Generation. Allerdings die Validität der Hypothese muss noch durch numerische Experimente untersucht werden. Aufgrund dieser Hypothese wird GAUCE auch zur Lösung SJSSP eingesetzt.
Zusammenfassung der Kapitel
1 Einfuhrung zur stochastischen Ablaufplanung: Dieses Kapitel motiviert die Problemstellung der Ablaufplanung unter Unsicherheit und führt in die Thematik der genetischen Algorithmen als Lösungsansatz ein.
2 Modelle zur Ablaufplanung: Hier werden das deterministische JSSP sowie die Erweiterung zum stochastischen JSSP definiert und die grundlegenden Annahmen für die Arbeit festgelegt.
3 Genetische Algorithmen (GA) als Lösungsverfahren zum SJSSP: Dieses Kapitel erläutert die Funktionsweise klassischer genetischer Algorithmen, die Monte Carlo Simulation und das spezifische GAUCE-Verfahren sowie dessen Komponenten.
4 Numerische Experimente und Analyse: Der Rahmen für die durchgeführten Experimente wird gesteckt und die erzielten Ergebnisse werden detailliert analysiert und diskutiert.
5 Kritik: Hier werden kritische Aspekte des GAUCE-Verfahrens, wie die fehlende Berücksichtigung bestimmter Restriktionen und die Anfälligkeit für Overfitting, diskutiert.
6 Fazit und Ausblick: Das Fazit fasst die Ergebnisse zusammen und zeigt potenzielle zukünftige Forschungsfelder auf.
A Programm GEAL: In diesem Anhang wird kurz das im Rahmen der Arbeit entwickelte Computerprogramm zur Implementierung des GAUCE-Verfahrens beschrieben.
Schlüsselwörter
Ablaufplanung, Job Shop Scheduling Problem, JSSP, SJSSP, Stochastik, Genetische Algorithmen, GAUCE, Optimierung, Zykluszeit, Monte Carlo Simulation, Population, Fitness, Mutation, Crossover, Phänotyp
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit beschäftigt sich mit der Optimierung der Ablaufplanung in der Produktion, insbesondere unter Einbeziehung von Unsicherheiten bei den Bearbeitungszeiten.
Was sind die zentralen Themenfelder?
Die Themenfelder umfassen die stochastische Ablaufplanung, das Job Shop Scheduling Problem (JSSP) und die Anwendung genetischer Algorithmen als Lösungsmethode.
Was ist das primäre Ziel der Forschungsarbeit?
Das primäre Ziel ist es, ein stochastisches JSSP-Modell mittels des GAUCE-Algorithmus zu lösen und die Eignung dieses Verfahrens zur Findung approximativer Optima zu untersuchen.
Welche wissenschaftliche Methode wird verwendet?
Die Arbeit nutzt genetische Algorithmen, kombiniert mit einer Monte Carlo Simulation zur Bewertung der Lösungsgüte unter stochastischen Bedingungen.
Was wird im Hauptteil behandelt?
Der Hauptteil behandelt die theoretischen Modelle zur Ablaufplanung, die detaillierte Beschreibung der Komponenten des GAUCE-Verfahrens sowie eine numerische Experimentreihe zur Validierung.
Welche Schlüsselwörter charakterisieren die Arbeit?
Die zentralen Begriffe sind unter anderem JSSP, SJSSP, Genetische Algorithmen, GAUCE, stochastische Programmierung und Zykluszeitoptimierung.
Was unterscheidet GAUCE von klassischen genetischen Algorithmen?
Im Gegensatz zu klassischen GAs, die oft den besten Genotyp der letzten Generation betrachten, setzt GAUCE auf die Hypothese, dass der Genotyp mit der höchsten Häufigkeit über alle Generationen hinweg das Optimum darstellt.
Welche Rolle spielt die Monte Carlo Simulation in diesem Verfahren?
Die Monte Carlo Simulation wird verwendet, um den Erwartungswert der Zykluszeit für die gefundenen Lösungen unter Berücksichtigung stochastischer Bearbeitungszeiten zu berechnen und damit deren Qualität zu bewerten.
Welche Schwächen des GAUCE-Verfahrens werden genannt?
Kritisiert werden insbesondere die eingeschränkte Praxisrelevanz durch fehlende Berücksichtigung von Rüstzeiten oder Kapazitätsrestriktionen sowie die Anfälligkeit für Overfitting.
- Quote paper
- Diplom-Wirtschaftsinformatiker Junjie Tang (Author), 2004, Robuste Ablaufplanung mit stochastischen genetischen Algorithmen, Munich, GRIN Verlag, https://www.grin.com/document/54958
