Ziel dieser Arbeit ist es, für ein konkretes Beispiel aus der Produktionspraxis einen speziellen genetischen Algorithmus zu entwickeln, welcher die Maschinenbelegung
bestmöglich plant.
Markt- und Kundenorientierung stehen im Mittelpunkt moderner Unternehmensstrategien.
Um die Wünsche nach Sachgütern und Dienstleistungen mit niedrigen Preisen, hoher Qualitäat und kurzen Lieferzeiten erfüllen zu können und dennoch trotz ständig sinkender Gewinnspannen profitabel zu arbeiten, sind die Unternehmen dazu angehalten, Möglichkeiten der Kostensenkung zu finden.
Insbesondere im Produktionsbereich lassen sich durch einen verbesserten Ressourcenverbrauch sowie eine Verringerung der Durchlaufzeiten erhebliche Kosten einsparen, ohne dabei Abstriche bei der Qualität zu machen. Dazu ist eine rationelle
Produktionsplanung und -steuerung notwendig.
Die Maschinenbelegungsplanung ist dabei eines der zentralen Probleme. Die Aufgabe besteht darin, eine Zuordnung von Aufträgen zu Maschinen in einer gewissen Reihenfolge zu finden, so dass ein bestimmtes Ziel bestmöglich erfüllt wird.
Seit den fünfziger Jahren werden die unterschiedlichsten Verfahren zur Lösung von Maschinenbelegungsproblemen vorgeschlagen. Zu den bekanntesten zählen Branch & Bound Verfahren sowie prioritätsregelbasierte Verfahren.
Während Ersteres zwar eine Optimallösung garantiert, dessen Einsatz jedoch aufgrund immenser Rechenzeit bei größeren Problemen unmöglich ist, liefert das zweite Verfahren meist nur unbefriedigende Ergebnisse. Neuere Verfahren, wie Simulated Annealing, Tabu Search oder genetische Algorithmen liefern hingegen bei moderater Rechenzeit gute Lösungsqualitäten.
Insbesondere genetische Algorithmen scheinen für die Lösung komplexer Optimierungsprobleme besonders gut geeignet zu sein.
Zunächst wird die Maschinenbelegungsplanung aus theoretischer Sicht innerhalb der Produktionsplanung eingeordnet. Aufgrund der Vielfältigkeit der Maschinenbelegungsprobleme werden diese danach klassifizert. Im Anschluss wird der genetische Algorithmus aus aus mathematischer Sicht erläutert, um dann diese theoretischen Erkenntnisse auf das Praxisbeispiel in einem C Programm anzuwenden. Um einen Performancevergleich zu erhalten, wird ebenfalls kurz das Simulated Annealing theoretisch behandelt und anschließend ebenfals in einem C Programm umgesetzt.
Die erzielten Ergebnisse werden grafisch aufbereitet dargestellt.
Inhaltsverzeichnis
1 Einleitung
1.1 Motivation
1.2 Zielsetzung
2 Das Maschinenbelegungsproblem
2.1 Einordnung des Maschinenbelegungsproblems
2.2 Beschreibung des Maschinenbelegungsproblems
2.3 Das Job Shop Problem
3 Genetischer Algorithmus
3.1 Überblick über Evolutionäre Algorithmen
3.2 Grundlagen genetischer Algorithmen
3.2.1 Die Wahl der Kodierung
3.2.2 Populationskonzepte
3.2.3 Die Fitnessfunktion
3.2.4 Selektionsmechanismen
3.2.5 Rekombinationsoperatoren
3.2.6 Parameter und Leistungssteigerung
4 Konvergenzbetrachtungen des genetischen Algorithmus
4.1 Eine allgemeine Formulierung genetischer Algorithmen
4.2 Die Evolution als Markov-Prozess
4.2.1 Definitionen und grundlegende Eigenschaften
4.2.2 Die Übergangsmatrix des genetischen Algorithmus
4.2.3 Konvergenz homogener Markov-Ketten
4.3 Eine obere Schranke für die Konvergenzgeschwindigkeit
5 Ein Produktionsplanungsmodell bei Florena als Beispiel eines Maschinenbelegungsproblems
5.1 Produktionsbeschreibung
6 Umsetzung des Florena-Modells
6.1 Verwendete Komponenten des genetischen Algorithmus
6.2 Allgemeine Bezeichnungen
6.3 Besonderheiten des Florena-Beispiels und eine erste Modellierung
6.3.1 Erreichbarkeit des globalen Optimums
6.3.2 Nachteile des Modells
6.4 Das 2-Operationen-Modell
6.4.1 Verbesserungen des 2-Operationen-Modells
7 Programmbeschreibung
7.1 Programminput
7.2 Programmaufbau
7.3 Programmablauf
7.3.1 „ProzessMethoden.h“
7.3.2 „EvolutionsMethoden.c“
7.4 Programmoutput
7.5 Simulated Annealing
7.5.1 Programmaufbau des Simulated Annealing
7.6 Beurteilung der Güte des genetischen Algorithmus am Florena-Beispiel
7.6.1 Ergebnisvergleich
8 Zusammenfassung
A Flussdiagramme
A.1 Flussdiagramm Hauptprogramm
A.2 Flussdiagramm zur Bestimmung der Zykluszeiten
A.3 Flussdiagramm genetischer Algorithmus
A.4 Flussdiagramm Simulated Annealing
B Diagramme der Iterationen
B.1 Genetischer Algorithmus - beste Lösung pro Generation
B.2 Genetischer Algorithmus - beste Lösung gesamt
B.3 Simulated Annealing - beste Lösung pro Iteration
B.4 Simulated Annealing - beste Lösung gesamt
C Programmausgabe in Textdateien
C.1 Genetischer Algorithmus
C.1.1 Parameter.txt
C.1.2 Kompakt.txt
C.1.3 Jobs.txt
C.1.4 Maschinen.txt
C.2 Simulated Annealing
C.2.1 Parameter.txt
C.2.2 Kompakt.txt
C.2.3 Jobs.txt
C.2.4 Maschinen.txt
Zielsetzung & Themen
Diese Arbeit zielt darauf ab, einen speziellen genetischen Algorithmus zu entwickeln, um das komplexe Maschinenbelegungsproblem in der Produktionspraxis, konkret am Beispiel des Unternehmens Florena Cosmetics GmbH, bestmöglich zu lösen und die Konvergenzeigenschaften dieses Verfahrens mathematisch zu analysieren.
- Optimierung von Maschinenbelegungsplänen mittels genetischer Algorithmen
- Modellierung des Produktionsprozesses der Florena Cosmetics GmbH als Job Shop Problem
- Mathematische Konvergenzbetrachtungen von genetischen Algorithmen als Markov-Prozess
- Entwicklung und Implementierung eines C-Programms zur praktischen Umsetzung des Modells
- Vergleich der Leistungsfähigkeit des entwickelten Verfahrens mit einer Variante des Simulated Annealing
Auszug aus dem Buch
Die Wahl der Kodierung
Die Leistungsfähigkeit des genetischen Algorithmus hängt in hohem Maße von der geeigneten Wahl der Kodierung der Lösungen ab. Eine gute Kodierung sollte vor allem folgende Anforderungen erfüllen:
• Ausschluss der Entstehung ungültiger Lösungen
• Minimalität des Suchraumes, wobei keine (guten) Lösungen ausgeschlossen sein dürfen
• Möglichst effiziente Methoden der Kodierung und Dekodierung
Ist es aus bestimmten Gründen nicht möglich alle unzulässigen Lösungen auszuschließen, so erreicht man den ersten Punkt, indem man unzulässigen Lösungen aufgrund der Wahl der Fitnessfunktion eine möglichst schlechte Fitness zuweist, so dass diese Lösungen nicht als Optimallösung in Frage kommen. Hierzu können beispielsweise Strafwerte vergeben werden. Unzulässige Lösungen müssen jedoch nicht unbedingt durch Nichterfüllung einer Nebenbedingung unzulässig sein, sondern können dies, insbesondere bei Maschinenbelegungsplänen, auch durch Zyklen in der Auftragsreihenfolge auf verschiedenen Maschinen sein. Da die Erkennung und Eliminierung solcher Zyklen vor allem bei großen Problemen erheblichen Aufwand verursacht, ist es sinnvoll, Zyklen von vornherein auszuschließen. Aufgrund der Komplexität von Maschinenbelegungsproblemen, versteht sich die zweite und dritte Forderung von selbst.
Zusammenfassung der Kapitel
Einleitung: Stellt die Motivation zur Effizienzsteigerung in der Produktionsplanung dar und definiert das Ziel der Arbeit, einen genetischen Algorithmus für das Unternehmen Florena zu entwickeln.
Das Maschinenbelegungsproblem: Führt theoretische Grundlagen und Klassifikationen von Maschinenbelegungsproblemen ein, mit Fokus auf das Job Shop Problem.
Genetischer Algorithmus: Vermittelt die theoretischen Grundlagen evolutionärer Algorithmen, deren Komponenten, sowie spezifische Kodierungen und Operatoren.
Konvergenzbetrachtungen des genetischen Algorithmus: Analysiert den Algorithmus mathematisch als Markov-Kette und leitet Konvergenzbedingungen sowie Konvergenzraten ab.
Ein Produktionsplanungsmodell bei Florena als Beispiel eines Maschinenbelegungsproblems: Detaillierte Beschreibung der Produktionsprozesse bei Florena und deren spezifische Modellierungsparameter.
Umsetzung des Florena-Modells: Beschreibt die konkrete Anwendung des genetischen Algorithmus auf das Florena-Beispiel, inklusive notwendiger Anpassungen und der Entwicklung eines alternativen 2-Operationen-Modells.
Programmbeschreibung: Dokumentiert die technische Umsetzung in C, die Struktur des Programms und das Verfahren der Simulated Annealing Variante.
Zusammenfassung: Fasst die Ergebnisse der Diplomarbeit zusammen und diskutiert den praktischen Nutzen sowie Ansätze für weiterführende Verbesserungen.
Schlüsselwörter
Maschinenbelegungsplanung, Genetische Algorithmen, Job Shop Problem, Produktionsplanung, Simulated Annealing, Fitnessfunktion, Konvergenzanalyse, Markov-Prozess, Florena Cosmetics, Heuristische Verfahren, Optimierung, C-Programmierung, Schedule, Reihenfolgeproblem, Produktionstechnik
Häufig gestellte Fragen
Worum geht es in der Arbeit grundsätzlich?
Die Arbeit beschäftigt sich mit der Optimierung des Maschinenbelegungsproblems in der Produktion durch den Einsatz moderner heuristischer Verfahren, speziell genetischer Algorithmen.
Was sind die zentralen Themenfelder?
Zentrale Themen sind die mathematische Modellierung von Fertigungsabläufen, die Theorie genetischer Algorithmen, deren Konvergenzanalyse mittels Markov-Ketten sowie die praktische Umsetzung für ein reales Industrieunternehmen.
Was ist das primäre Ziel der Arbeit?
Das Ziel ist die Entwicklung eines spezialisierten genetischen Algorithmus, der für das Produktionsbeispiel der Florena Cosmetics GmbH eine möglichst effiziente Maschinenbelegung plant.
Welche wissenschaftliche Methode wird verwendet?
Es werden genetische Algorithmen als heuristisches Optimierungsverfahren eingesetzt und deren Konvergenzverhalten theoretisch durch die Modellierung als homogene Markov-Kette untermauert.
Was wird im Hauptteil behandelt?
Der Hauptteil befasst sich mit der theoretischen Klassifizierung des Maschinenbelegungsproblems, der detaillierten Beschreibung der Funktionsweise genetischer Algorithmen, der mathematischen Konvergenzbeweise sowie der konkreten Modellierung und Implementierung der Lösung für den Anwendungsfall Florena.
Welche Schlüsselwörter charakterisieren die Arbeit?
Maschinenbelegungsplanung, Genetische Algorithmen, Job Shop Problem, Produktionsplanung und Konvergenzanalyse.
Warum wurde das "2-Operationen-Modell" eingeführt?
Das ursprüngliche Modell führte bei der Florena-Instanz zu sehr vielen unzulässigen Zyklen, wodurch die Suche nach gültigen Lösungen extrem erschwert wurde; das neue Modell vereinfacht die Operationen, um die Suchraumeffizienz zu erhöhen.
Wie schneidet der genetische Algorithmus im Vergleich ab?
Die Ergebnisse zeigen, dass der genetische Algorithmus eine gute Brauchbarkeit aufweist und im Vergleich mit Simulated Annealing wettbewerbsfähige Lösungen liefert, wobei je nach Modellgröße unterschiedliche Vorteile bestehen.
- Quote paper
- Rainer Haensel (Author), 2004, Produktionspraxis. Maschinenbelegung optimieren mittels genetischem Algorithmus, Munich, GRIN Verlag, https://www.grin.com/document/27465
