Produktionspraxis. Maschinenbelegung optimieren mittels genetischem Algorithmus


Diplomarbeit, 2004

103 Seiten, Note: 1,0


Leseprobe

Universität Leipzig
Fakultät für Mathematik und Informatik
Mathematisches Institut

Diplomarbeit

Optimierung eines praktischen
Maschinenbelegungsproblems mittels
genetischem Algorithmus

vorgelegt von

Rainer Hänsel

Mai 2004 

Studiengang
Wirtschaftsmathematik

 

Inhaltsverzeichnis

1 Einleitung ... 1
1.1 Motivation  ...  1
1.2 Zielsetzung  ... 1

2 Das Maschinenbelegungsproblem  ... 3
2.1 Einordnung des Maschinenbelegungsproblems ... 3
2.2 Beschreibung des Maschinenbelegungsproblems  ...  4
2.3 Das Job Shop Problem  ...  7

3 Genetischer Algorithmus  ... 13
3.1 Überblick über Evolutionäre Algorithmen  ...  13
3.2 Grundlagen genetischer Algorithmen ...  14
3.2.1 Die Wahl der Kodierung ... 15
3.2.2 Populationskonzepte  ...  21
3.2.3 Die Fitnessfunktion ...  22
3.2.4 Selektionsmechanismen  ... 23
3.2.5 Rekombinationsoperatoren  ...  24
3.2.6 Parameter und Leistungssteigerung  ... 27

4 Konvergenzbetrachtungen des genetischen Algorithmus  ... 29
4.1 Eine allgemeine Formulierung genetischer Algorithmen ...  29
4.2 Die Evolution als Markov-Prozess  ... 32
4.2.1 Definitionen und grundlegende Eigenschaften  ...  32
4.2.2 Die Übergangsmatrix des genetischen Algorithmus  ... 34
4.2.3 Konvergenz homogener Markov-Ketten  ... 36
4.3 Eine obere Schranke für die Konvergenzgeschwindigkeit ... 42

5 Ein Produktionsplanungsmodell bei Florena als Beispiel eines Maschinenbelegungsproblems  ... 49
5.1 Produktionsbeschreibung  ...  49

6 Umsetzung des Florena-Modells  ... 54
6.1 Verwendete Komponenten des genetischen Algorithmus  ... 54
6.2 Allgemeine Bezeichnungen ...  55
6.3 Besonderheiten des Florena-Beispiels und eine erste Modellierung  ... 56
6.3.1 Erreichbarkeit des globalen Optimums  ... 59
6.3.2 Nachteile des Modells  ... 64
6.4 Das 2-Operationen-Modell ...  65
6.4.1 Verbesserungen des 2-Operationen-Modells  ...  66

7 Programmbeschreibung  ... 68
7.1 Programminput  ...  69
7.2 Programmaufbau ...  69
7.3 Programmablauf ...  73
7.3.1 ”ProzessMethoden.h“  ...  73
7.3.2 ”EvolutionsMethoden.c“  ... 74
7.4 Programmoutput  ...  75
7.5 Simulated Annealing  ... 76
7.5.1 Programmaufbau des Simulated Annealing  ... 77
7.6 Beurteilung der Güte des genetischen Algorithmus am Florena-Beispiel  ...  79
7.6.1 Ergebnisvergleich  ...  80

8 Zusammenfassung  ... 81

Anhang ... 83

A Flussdiagramme  ... 83
A.1 Flussdiagramm Hauptprogramm  ... 83
A.2 Flussdiagramm zur Bestimmung der Zykluszeiten  ... 84
A.3 Flussdiagramm genetischer Algorithmus  ...  85
A.4 Flussdiagramm Simulated Annealing  ...  87

B Diagramme der Iterationen ... 88
B.1 Genetischer Algorithmus - beste Lösung pro Generation ...  88
B.2 Genetischer Algorithmus - beste Lösung gesamt  ... 88
B.3 Simulated Annealing - beste Lösung pro Iteration  ... 89
B.4 Simulated Annealing - beste Lösung gesamt  ... 89

C Programmausgabe in Textdateien  ... 90
C.1 Genetischer Algorithmus  ...  90
C.1.1 Parameter.txt  ...  90
C.1.2 Kompakt.txt  ...  90
C.1.3 Jobs.txt ... 91
C.1.4 Maschinen.txt ...  93
C.2 Simulated Annealing ... 94
C.2.1 Parameter.txt  ...  94
C.2.2 Kompakt.txt  ... 94
C.2.3 Jobs.txt  ...  95
C.2.4 Maschinen.txt  ...  97

Symbolverzeichnis  ... 98

Literaturverzeichnis  ... 99

 

1 Einleitung

1.1 Motivation

Markt- und Kundenorientierung stehen im Mittelpunkt moderner Unternehmensstrategien. Um die Wünsche nach Sachgütern und Dienstleistungen mit niedrigen Preisen, hoher Qualität 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. Dieses kombinatorische Optimierungsproblem ist als schwer lösbar bekannt. Seit den fünfziger Jahren werden daher in der Literatur 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.

1.2 Zielsetzung

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.

Bei dem Praxisbeispiel handelt es sich um das Unternehmen Florena Cosmetics GmbH mit Sitz in Waldheim/Sachsen. Florena ist ein Hersteller kosmetischer Produkte. Wir betrachten in dieser Arbeit den Unternehmensbereich ” Hautcreme & Lotion“ . Hier können in mehreren Arbeitsschritten ca. 185 verschiedene Fertigprodukte hergestellt werden.

Im zweiten Kapitel wird die Maschinenbelegungsplanung aus theoretischer Sicht innerhalb der Produktionsplanung eingeordnet.

Aufgrund der Vielfältigkeit der Maschinenbelegungsprobleme werden diese danach klassifiziert. Der letzte Abschnitt des Kapitels gibt einen überblick über bekannte Lösungsmethoden der Maschinenbelegungsplanung.

Zur Lösung des Maschinenbelegungsproblems wollen wir als Vertreter der heuristischen Verfahren den genetischen Algorithmus genauer untersuchen. Kapitel 3 diskutiert die Klasse der genetischen Algorithmen. Nach einer allgemeinen Beschreibung werden die einzelnen Komponenten des Algorithmus’ näher erläutert und spezielle Instanzen beschrieben.

Kapitel 4 beschäftigt sich mit dem mathematischen Hintergrund des genetischen Algorithmus. Da heuristische Verfahren bekanntlich das Erreichen eines globalen Optimums nicht garantieren können, ist es wichtig zu zeigen, dass genetische Algorithmen dennoch ein bestimmtes Verhalten aufweisen. Insbesondere soll gezeigt werden, dass eine Konvergenz im Unendlichen stattfindet und die Konvergenzgeschwindigkeit direkt von gewissen Parametern des Algorithmus abhängt.
Dazu wird eine abstrakte Instanz des Algorithmus als Markov-Prozess formuliert und dessen Verhalten untersucht.

Nachdem nun der genetische Algorithmus und sein Verhalten näher beleuchtet worden sind, wird in Kapitel 5 das Praxisbeispiel der Florena Cosmetics GmbH genauer beschrieben und eine erste Modellierung vorgenommen. Den eigentlichen Kern der Arbeit bildet Kapitel 6. Ausgehend von Kapitel 3 und 5 wird hier ein spezieller Algorithmus entwickelt, der das Florena Beispiel lösen soll. Wir werden sehen, dass es notwendig ist, spezielle Annahmen zu machen, um tatsächlich eine gute Modellierung zu erhalten.

Kapitel 7 beschreibt die Umsetzung des in Kapitel 6 entwickelten genetischen Algorithmus’ in einem C- Programm. Zu Vergleichszwecken wird außerdem eine vereinfachte Variante des Simulated Annealing implementiert und ausführlich getestet.

Schließlich fasst Kapitel 8 die in dieser Arbeit erzielten Ergebnisse zusammen und gibt einen Ausblick auf weiterführende Untersuchungen bezüglich der Thematik. Für die sehr gute Betreuung meiner Diplomarbeit möchte ich mich bei Herrn Prof. Stefan Luckhaus bedanken. Sein fachlicher Rat sowie die kritische Betrachtungsweise haben erheblich zum Verständnis des Themas und den sich ergebenden Problemen beigetragen.

2 Das Maschinenbelegungsproblem

In diesem Kapitel soll die Maschinenbelegungsplanung als Hauptschritt der operativen Produktionsplanung eingeordnet und allgemein umrissen werden. Aufgrund der Fülle verschiedener Maschinenbelegungsprobleme bietet sich eine Klassifikation an. Da sich später zeigen wird, dass unser spezielles Maschinenbelegungsproblem bei der Florena Cosmetics GmbH zur Klasse der Job Shop Probleme zu zählen ist, wird auf diese Problemklasse als spezielles Maschinenbelegungsproblem näher eingegangen und es werden Lösungsmethoden dafür genannt. Die Ausführungen dieses Kapitels orientieren sich insbesondere an [Rix97] und [Tei98].

2.1 Einordnung des Maschinenbelegungsproblems

Die Maschinenbelegungsplanung ist ein Schritt der operativen Produktionsplanung. Ausgehend von strategischen Entscheidungen über Art der Produkte, Betriebsmittelausstattung u.ä., legt die operative Planung die Menge der herzustellenden Produkte und die dafür benötigten Rohstoff e für einen bestimmten Zeitraum fest. Das Hauptziel ist dabei zumeist die Maximierung der Deckungsbeiträge. Es werden aber auch markt- und kundenorientierte Ziele verfolgt.

Da die einzelnen Stufen der operativen Produktionsplanung voneinander abhängig sind, müsste eine simultane Planung durchgeführt werden. Dies scheitert jedoch an der Komplexität der einzelnen Planungsschritte sowie an unvorhergesehenen äußeren Einflüssen. Daher führt man eine hierarchische Planung durch, wobei die untergeordneten Stufen auf den Ergebnissen der übergeordneten Stufen aufbauen. 
Abbildung 1 zeigt eine solche Hierarchie der operativen Produktionsplanung. Dabei sind die einzelnen Hierarchiestufen sowie in Klammern der jeweilige Planungshorizont angegeben.

Ganz allgemein wird innerhalb der hierarchischen Planung zunächst eine Mengenplanung und dann eine Zeitplanung vorgenommen. Die Mengenplanung legt den Primärbedarf der zu produzierenden Güter fest. Ausgehend davon wird der Materialbedarf festgestellt und geprüft, ob dieser durch Eigen- oder Fremdfertigung beschat wird. Dabei sind jeweils Lagerbestände sowie evtl. Reservierungen aus Vorperioden zu berücksichtigen.

Die Planung der eigentlichen Produktion und somit der uns interessierende Teil beginnt mit der Durchlaufplanung. Hier werden, ohne Kapazitäten zu beachten, grobe Start- und Endzeiten festgelegt. Anschließend werden die Kapazitäten mit dem vorhandenen Terminplan in Einklang gebracht. Danach werden die Aufträge für die Produktion freigegeben. Nach der Auftragsfreigabe wird eine konkrete Einplanung auf den Maschinen durchgeführt. Dies ist Gegenstand der Maschinenbelegungsplanung.

[....]

Ende der Leseprobe aus 103 Seiten

Details

Titel
Produktionspraxis. Maschinenbelegung optimieren mittels genetischem Algorithmus
Hochschule
Universität Leipzig  (Institut für Mathematik)
Note
1,0
Autor
Jahr
2004
Seiten
103
Katalognummer
V27465
ISBN (eBook)
9783638295086
ISBN (Buch)
9783638721189
Dateigröße
1109 KB
Sprache
Deutsch
Schlagworte
Optimierung, Maschinenbelegungsproblems, Algorithmus
Arbeit zitieren
Rainer Haensel (Autor), 2004, Produktionspraxis. Maschinenbelegung optimieren mittels genetischem Algorithmus, München, GRIN Verlag, https://www.grin.com/document/27465

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Produktionspraxis. Maschinenbelegung optimieren mittels genetischem Algorithmus



Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden