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
Zielsetzung und Themenschwerpunkte
Diese Diplomarbeit befasst sich mit der Optimierung eines Maschinenbelegungsproblems mittels genetischer Algorithmen. Das Hauptziel ist die Entwicklung und Implementierung eines genetischen Algorithmus zur Lösung eines konkreten Produktionsplanungsproblems bei Florena Cosmetics. Die Arbeit untersucht sowohl die theoretischen Grundlagen genetischer Algorithmen als auch deren praktische Anwendung. Die Konvergenzeigenschaften des Algorithmus werden mathematisch analysiert.
- Optimierung der Maschinenbelegung mittels genetischer Algorithmen
- Entwicklung eines spezifischen Algorithmus für ein reales Produktionsproblem
- Mathematische Analyse der Konvergenzeigenschaften des Algorithmus
- Vergleich mit anderen heuristischen Verfahren (Simulated Annealing)
- Praktische Implementierung und Evaluierung des Algorithmus
Zusammenfassung der Kapitel
1 Einleitung: Die Einleitung motiviert die Arbeit durch die Notwendigkeit effizienter Produktionsplanung in modernen Unternehmen. Sie hebt die Bedeutung der Maschinenbelegungsplanung hervor und skizziert die Herausforderungen, die mit der Lösung dieses kombinatorischen Optimierungsproblems verbunden sind. Die Arbeit stellt sich zum Ziel, einen genetischen Algorithmus für ein konkretes Praxisbeispiel (Florena Cosmetics) zu entwickeln.
2 Das Maschinenbelegungsproblem: Dieses Kapitel ordnet das Maschinenbelegungsproblem in den Kontext der Produktionsplanung ein, beschreibt das Problem detailliert und klassifiziert verschiedene Arten von Maschinenbelegungsproblemen. Es liefert einen Überblick über bekannte Lösungsmethoden, unterstreicht die Grenzen herkömmlicher Verfahren und begründet die Wahl des genetischen Algorithmus als Lösungsansatz.
3 Genetischer Algorithmus: Kapitel 3 bietet eine umfassende Einführung in genetische Algorithmen. Es beschreibt die grundlegenden Komponenten wie Kodierung, Populationskonzepte, Fitnessfunktion, Selektions- und Rekombinationsmechanismen sowie die Parameteroptimierung. Das Kapitel legt den theoretischen Grundstein für das Verständnis des in dieser Arbeit verwendeten Algorithmus.
4 Konvergenzbetrachtungen des genetischen Algorithmus: Dieses Kapitel widmet sich der mathematischen Analyse der Konvergenzeigenschaften des genetischen Algorithmus. Durch die Formulierung als Markov-Prozess wird die Konvergenz im Unendlichen gezeigt und die Abhängigkeit der Konvergenzgeschwindigkeit von Algorithmusparametern untersucht. Dieses Kapitel liefert wichtige Erkenntnisse zur theoretischen Fundiertheit des gewählten Lösungsansatzes.
5 Ein Produktionsplanungsmodell bei Florena als Beispiel eines Maschinenbelegungsproblems: In diesem Kapitel wird das konkrete Produktionsplanungsproblem bei Florena Cosmetics GmbH detailliert vorgestellt. Es beschreibt den Produktionsprozess und legt die Grundlage für die Modellierung des Problems im darauffolgenden Kapitel.
6 Umsetzung des Florena-Modells: Der Kern der Arbeit liegt in diesem Kapitel. Hier wird ein spezifischer genetischer Algorithmus entwickelt, der auf das Florena-Problem angewendet werden kann. Es werden notwendige Annahmen und Vereinfachungen diskutiert, um eine gute Modellierung zu gewährleisten. Das Kapitel beinhaltet die Beschreibung verschiedener Modellierungsansätze und deren jeweilige Vor- und Nachteile.
7 Programmbeschreibung: Kapitel 7 beschreibt die Implementierung des entwickelten genetischen Algorithmus in einem C-Programm. Es wird der Programmaufbau, der Ablauf und der Input/Output detailliert erläutert. Zusätzlich wird ein Simulated Annealing Algorithmus implementiert und zum Vergleich herangezogen.
Schlüsselwörter
Maschinenbelegungsproblem, genetischer Algorithmus, Produktionsplanung, Optimierung, Florena Cosmetics, Markov-Prozess, Konvergenz, Simulated Annealing, heuristische Verfahren, kombinatorische Optimierung.
Häufig gestellte Fragen zur Diplomarbeit: Optimierung eines Maschinenbelegungsproblems mittels genetischer Algorithmen
Was ist das Thema der Diplomarbeit?
Die Diplomarbeit befasst sich mit der Optimierung eines Maschinenbelegungsproblems mittels genetischer Algorithmen. Der Fokus liegt auf der Entwicklung und Implementierung eines solchen Algorithmus zur Lösung eines konkreten Produktionsplanungsproblems bei Florena Cosmetics. Die Arbeit umfasst sowohl theoretische Grundlagen als auch praktische Anwendung und mathematische Analyse der Konvergenzeigenschaften.
Welche Ziele werden in der Arbeit verfolgt?
Die Hauptziele sind die Entwicklung und Implementierung eines genetischen Algorithmus für ein reales Produktionsproblem bei Florena Cosmetics, die mathematische Analyse der Konvergenzeigenschaften des Algorithmus und ein Vergleich mit anderen heuristischen Verfahren (Simulated Annealing).
Welche Themen werden in der Arbeit behandelt?
Die Arbeit behandelt das Maschinenbelegungsproblem, die Grundlagen genetischer Algorithmen (Kodierung, Populationskonzepte, Fitnessfunktion, Selektion, Rekombination), die mathematische Analyse der Konvergenz (Markov-Prozesse), die Modellierung eines konkreten Produktionsplanungsproblems bei Florena Cosmetics, die Implementierung des Algorithmus in C und einen Vergleich mit Simulated Annealing.
Wie ist die Arbeit strukturiert?
Die Arbeit ist in acht Kapitel gegliedert: Einleitung, Das Maschinenbelegungsproblem, Genetischer Algorithmus, Konvergenzbetrachtungen des genetischen Algorithmus, Ein Produktionsplanungsmodell bei Florena, Umsetzung des Florena-Modells, Programmbeschreibung und Zusammenfassung. Jedes Kapitel behandelt einen spezifischen Aspekt des Themas.
Welche Methoden werden verwendet?
Die zentrale Methode ist der genetische Algorithmus. Die Konvergenz wird mittels der Theorie der Markov-Prozesse analysiert. Zum Vergleich wird ein Simulated Annealing Algorithmus implementiert. Die Implementierung erfolgt in C.
Welche konkreten Ergebnisse werden präsentiert?
Die Arbeit präsentiert einen entwickelten und implementierten genetischen Algorithmus zur Lösung des Maschinenbelegungsproblems bei Florena Cosmetics. Es werden verschiedene Modellierungsansätze verglichen und die Ergebnisse des genetischen Algorithmus mit denen von Simulated Annealing verglichen. Die mathematische Analyse liefert Erkenntnisse zur Konvergenzgeschwindigkeit.
Welche Schlüsselwörter beschreiben die Arbeit?
Schlüsselwörter sind: Maschinenbelegungsproblem, genetischer Algorithmus, Produktionsplanung, Optimierung, Florena Cosmetics, Markov-Prozess, Konvergenz, Simulated Annealing, heuristische Verfahren, kombinatorische Optimierung.
Wo finde ich den vollständigen Inhalt der Diplomarbeit?
Der vollständige Inhalt der Diplomarbeit ist nicht in diesem FAQ enthalten. Dieser Text bietet eine Zusammenfassung und Übersicht über die zentralen Aspekte der Arbeit.
- Quote paper
- Rainer Haensel (Author), 2004, Produktionspraxis. Maschinenbelegung optimieren mittels genetischem Algorithmus, Munich, GRIN Verlag, https://www.grin.com/document/27465
