Die vorliegende Studienarbeit befasst sich im theoretischen Teil mit dem Einsatz von genetischen und evolutionären Algorithmen im Fachbereich Operations Research. Praktische Anwendung findet die mathematische Herangehensweise an betriebswirtschaftliche Problemstellungen in einer ausführlichen Fallstudie die mit Microsoft Excel gelöst wurde.
Inhaltsverzeichnis
Abkürzungsverzeichnis
Abbildungsverzeichnis
Tabellenverzeichnis
Formelverzeichnis
1 Einleitung
1.1 Problemstellung
1.2 Ziele der Studienarbeit
1.3 Aufbau der Studienarbeit
2 Operations Research
2.1 Begriffsdefinition: „Operations Research“
2.2 Theoretischer Ansatz
2.2.1 Modelle im OR
2.2.2 Vorgehensweise bei der Problemlösung
2.3 Problemtypen
2.3.1 Kombinatorische Probleme
2.3.2 Lagerhaltungsprobleme
2.3.3 Ersatzprobleme
2.3.4 Wartezeitprobleme
2.3.5 Konkurrenzprobleme
2.4 Anwendungsverfahren
2.4.1 Statische Optimierung
2.4.2 Dynamische Optimierung
2.4.3 Netzplantechnik
2.4.4 Simulation
2.4.5 Heuristiken
2.4.6 Spieltheorie
2.4.7 Warteschlangentheorie
2.4.8 Entscheidungsbaumverfahren
3 Algorithmen – Grundlage für Optimierungsprozesse
3.1 Grundlegende Definition
3.2 Evolutionäre Algorithmen
3.3 Genetische Algorithmen
4 Fallstudie: Optimierung der Losgrößen und Auftragsreihenfolge
4.1 Aufgabenstellung
4.2 Zielsetzung der Optimierung
4.3 Werkzeug zur Problemlösung: Der Excel-Solver
4.4 Ermittlung der optimalen Losgröße in der Fertigung
4.4.1 Gesamtkosten
4.4.2 Gebundenes Kapital
4.4.3 Aufbereitung des Excel-Modells für den Einsatz des Solvers
4.4.4 Ermittlung der optimalen Losgröße
4.5 Optimierung der Auftragsreihenfolge
4.5.1 Ermittlung der Bearbeitungszeiten
4.5.2 Ermittlung der Rüstzeiten
4.5.3 Ermittlung der Belegzeiten
4.5.4 Vorbereitung im Excel-Modells mit dem „SVERWEIS“ 23
4.5.5 Ermittlung der Durchlaufzeit
4.5.6 Ermittlung der optimalen Auftragsreihenfolge zur Minimierung der Durchlaufzeit
4.5.7 Zusammenfassung der Ergebnisse
Literaturverzeichnis
III. Abkürzungsverzeichnis
Abbildung in dieser Leseprobe nicht enthalten
IV. Abbildungsverzeichnis
Abbildung 1: Vorgehensmodell bei OR-Verfahren
Abbildung 2: Evolution in der Biologie (vereinfachte Darstellung)
Abbildung 3: Solver-Konfiguration zur Bestimmung der optimalen Losgröße
Abbildung 4: Exemplarisches Beispiel SVERWEIS
Abbildung 5: Darstellung Berechnung der Durchlaufzeit
Abbildung 6: Solver Konfiguration zur Bestimmung der optimalen Durchlaufzeit
V. Tabellenverzeichnis
Tabelle 1: Produktgrunddaten aus Aufgabenstellung
Tabelle 2: Produktionszeiten pro Produkte und Maschine
Tabelle 3: Excel-Modell vor Solver-Einsatz zur Ermittlung der optimalen Losgröße
Tabelle 4: Ergebnisse für die optimale Losgröße
Tabelle 5: Bearbeitungszeiten der Produkte auf den Maschinen
Tabelle 6: Rüstzeiten der einzelnen Produkte
Tabelle 7: Belegzeiten Produkt auf Maschine
Tabelle 8: Ausprägung der Produktkombination mit SVERWEIS
Tabelle 9: Berechnungsmatrix für die Durchlaufzeit
Tabelle 10: Ergebnis für die optimale Durchlaufzeit
Tabelle 11: Alternative Produktvariation
Tabelle 12: Ergebnisse Ziel 1
VI. Formelverzeichnis
Formel 1: Gesamtkosten nach Andler
Formel 2: Berechnung des gebundenen Kapitals
Formel 3: Beispiel Gesamtkosten Produkt 1
Formel 4: Beispiel gebundenes Kapital Produkt 1
Formel 5: Beispielhafte Berechnung der Bearbeitungszeit
Formel 6: Berechnung der Rüstzeit in Minuten
Formel 7: Beispielhafte Berechnung der Rüstzeit
Formel 8: Berechnung der Belegzeiten
Formel 9: Beispiel zur Berechnung der Belegzeiten
Formel 10: SVERWEIS in Excel
1 Einleitung
1.1 Problemstellung
Problemstellungen und Herausforderungen im Unternehmensalltag können meist auf einen Fokus konzentriert werden: Optimieren. Lagerbestände, Durchlaufzeiten, Standzeiten, Time-to-market, Entwicklungsdauer, Füllmengen und andere quantifizierbare Werte gilt es mit den zur Verfügung stehenden Ressourcen zu optimieren. „Operations Research“ ist ein Teilbereich der angewandten Mathematik, der sich genau mit dieser Thematik beschäftigt. Grundlage sind hierbei vor allem mathematische Modelle, die beim zu Grunde legen von Rahmenbedingungen zur Optimierung von Zielgrößen dienen können.
1.2 Ziele der Studienarbeit
Die vorliegende Studienarbeit verfolgt zwei grundlegende Ziele:
1) Der Leser soll einen umfassenden Einblick in das Themengebiet Operations Research erhalten. Dabei ist der Fokus der Theorie auf die Möglichkeiten gelegt, die angewandte Mathematik als Werkzeug für Problemlösungen zu nutzen.
2) Anhand der Fallstudie soll die Vorgehensweise zur Problemlösung praktisch dargestellt werden. Vor allem die Möglichkeiten, die dabei mit Microsoft Excel ausgeschöpft werden können, stehen im Vordergrund.
1.3 Aufbau der Studienarbeit
In Kapitel 2 wird der Bereich Operations Research theoretisch betrachtet. Nach der thematischen Einordnung und der Beleuchtung des theoretischen Ansatzes wird auf die verschiedenen Problemtypen und Anwendungsverfahren im Operations Research eingegangen.
Kapitel 3 befasst sich mit der Grundlage von mathematischen Optimierungsprozessen, den genetischen und evolutionären Algorithmen.
Um die theoretischen Ansätze in Kapitel 2 und 3 mit einem Praxisbeispiel zu untermalen, beschäftigt sich der Hauptteil der Arbeit mit der in Kapitel 4 bearbeiteten Fallstudie zur Optimierung von Losgrößen und der Auftragsreihenfolge bei einem Automobilzulieferer. Bei der Lösung der Fallstudie wird hauptsächlich auf Microsoft Excel als Lösungswerkzeug zurückgegriffen.
2 Operations Research
2.1 Begriffsdefinition: „Operations Research“
Operations Research befasst sich mit der Analyse betrieblicher und wirtschaftlicher Prozesse sowie mit der Anwendung mathematischer Methoden zur Entscheidungsfindung.[1] Eine einheitliche Definition des Begriffes „Operations Research“ existiert in der Literatur nicht. Alle Definitionsversuche beinhalten jedoch drei charakteristische Kernpunkte:[2]
- Entscheidungsvorbereitung
- Anstreben einer optimalen Entscheidung und
- Einsatz mathematischer Methoden
Ins Deutsche übersetzt bedeutet Operations Research die Erforschung von Operationen.[3] Dieser oder ein anderer deutscher Begriff hat sich jedoch bisher nicht durchsetzten können. Die gängige Abkürzung für Operations Research, welche im Folgenden auch verwendet wird, lautet OR.
2.2 Theoretischer Ansatz
2.2.1 Modelle im OR
Charakteristisch für das OR ist, neben der Quantifizierung des Problems und dem Streben nach der optimalen Lösung, die Abstraktion der relevanten Situation in Modellen.[4] Modelle sind Abbilder der Realität, welche sich auf wesentliche Beziehungszusammenhänge beschränken.[5]
Wichtig bei der Bildung von Modellen ist die Vereinfachung der realen Situation ohne relevante Aspekte zu vernachlässigen. Die Struktur der Realität, d.h. die relevanten Aspekte und deren Beziehungen untereinander, muss bewahrt und im Modell abgebildet werden.
Ein reales Problem kann mit Hilfe von Modellen vereinfacht dargestellt werden. Aus dem realen Problem wird durch die Modellbildung ein formelles Problem. Dieses kann nun mit Hilfe von OR- Methoden gelöst werden. Die so ermittelte Modelllösung wird anschließend auf die Realität übertragen, um das reale Problem zu lösen.
2.2.2 Vorgehensweise bei der Problemlösung
Die typische Vorgehensweise des OR lässt sich in sechs Schritten beschreiben:[6]
1. Erkennen und Analysieren eines Problems: Für ein gegebenes Problem muss zu Beginn der Handlungsspielraum abgesteckt werden. Unter einem Problem wird hierbei die Möglichkeit oder Notwendigkeit einer Entscheidung oder Handlung verstanden.
2. Bestimmen von Zielen und Handlungsmöglichkeiten: Ist das Problem erkannt und der Handlungsspielraum abgesteckt, müssen die Ziele für die Problemlösung definiert werden. Anschließend werden die Entscheidungskriterien und –alternativen sowie die möglichen Umweltzustände analysiert und in einem deskriptiven Modell, d.h. einem vereinfachten Abbild der konkreten Situation, dargestellt.
3. Mathematisches Modell: Das mathematische Modell, auch Symbolmodell genannt, ist eine Näherung der konkreten Situation. Es beschreibt Zusammenhänge zwischen einzelnen die Situation beeinflussende Faktoren.
4. Datenbeschaffung: Dies geschieht meist mit Hilfe von Prognosen und ist daher oft unsicher. Ziel ist es, die Entwicklung der Umweltparameter abzuschätzen.
5. Lösungsfindung: Mit Hilfe von Algorithmen[7] wird das mathematische Modell gelöst und somit
die vorteilhafteste Handlungsalternative ermittelt.
6. Bewertung der Lösung: Zusätzlich zu den im mathematischen Modell abgebildeten quantitativen Parametern müssen auch qualitative Einflüsse berücksichtigt werden. Außerdem müssen die Handlungsalternativen, Umweltzustände und Handlungskriterien auf Richtigkeit und Vollständigkeit überprüft werden, um die Qualität der Lösung beurteilen zu können.
Grafisch kann dieser Prozess folgendermaßen dargestellt werden:
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 1: Vorgehensmodell bei OR-Verfahren[8]
2.3 Problemtypen
Die wichtigsten Problemtypen werden im Folgenden kurz dargestellt und erläutert. Anzumerken ist dabei, dass die einzelnen Problemtypen auch gleichzeitig auftreten können.
2.3.1 Kombinatorische Probleme
Kombinatorische Probleme können weiter unterteilt werden in Reihenfolge- sowie Zuordnungs- und Zuteilungsprobleme. Ein klassisches Reihenfolgeproblem ist das Travelling-Salesman-Problem.
Dabei geht es um die optimale Routenplanung, um eine möglichst kurze Wegstrecke zu erreichen.[9]
Kombinatorische Probleme findet man oft im Bereich Produktionsplanung und Logistik wieder. Dabei sollen durch eine möglichst optimale Transport- oder Produktionsplanung die Kosten minimiert und der Gewinn maximiert werden.
2.3.2 Lagerhaltungsprobleme
Durch die Bestimmung optimaler Lagermengen sollen die Lagerhaltungskosten minimiert werden. Dazu gehört auch die Bestimmung von optimalen Bestellmengen und –terminen.
2.3.3 Ersatzprobleme
Ein wesentlicher Kostenpunkt bei der Produktion von Gütern sind Wartungs- und Instandhaltungskosten. Die Minimierung dieser Kosten ist daher ein wichtiges Ziel für produzierende Unternehmen. Dabei wird versucht, optimale Wartungsintervalle und Ersatzzeitpunkte zu ermitteln.
2.3.4 Wartezeitprobleme
Durch unterschiedliche Kapazitäten kann es in einer Abfolge von Tätigkeiten je nach Auslastung der Einzelelemente zu Engpässen kommen. Dieses Problem ist vor allem aus der Produktion bekannt, wo Maschinen mit kleinerer Kapazität Engpässe bilden, an denen Wartezeiten für die Weiterbearbeitung entstehen. Ziel ist es daher, die Engpässe so auszulegen, dass die Wartezeit dort unterhalb bestimmter Grenzwerte bleibt.
2.3.5 Konkurrenzprobleme
Bei Konkurrenzproblemen ist die Wirksamkeit der zu treffenden Maßnahmen abhängig von Maßnahmen konkurrierender Subjekte.[10] Dies ist z.B. beim Absatz von Gütern der Fall.
2.4 Anwendungsverfahren
Um die eben beschriebenen Probleme lösen zu können, wurde eine Vielzahl von Anwendungsverfahren entwickelt. Zur Lösung der Probleme soll für gewöhnlich eine Zielfunktion maximiert oder minimiert werden. Dies geschieht durch Einsetzen bestimmter Werte, welche durch Nebenbedingungen beschränkt werden.[11] Im Folgenden werden die wichtigsten Verfahren kurz vorgestellt.
2.4.1 Statische Optimierung
Bei der statischen Optimierung werden mehrere Verfahren unterschieden. Allen gemein ist, dass die von ihnen gelösten Modelle über den gesamten Betrachtungszeitraum hinweg unverändert bleiben. Dies gilt sowohl für die verwendeten Daten als auch für die Beziehungen der im Modell abgebildeten Aspekte der Realität.
Zu den statischen Optimierungsverfahren gehören:
– die lineare Optimierung, bei welcher sowohl die Zielfunktion als auch die Nebenbedingungen linear sind,
– die nichtlineare Optimierung, bei welcher die Zielfunktion und die Nebenbedingungen nichtlinear sind, und
– die ganzzahlige Optimierung, welche sowohl linear als auch nichtlinear sein kann und bei der alle oder mehrere Variablen ganzzahlige Werte annehmen müssen.
2.4.2 Dynamische Optimierung
Voraussetzung der dynamischen Optimierung ist die Aufteilung des Problems in mehrere Stufen. Die Optimierung wird dann stufenweise durch Rekursion durchgeführt. Das Verfahren wird unter anderem bei der Bestellmengen- und Losgrößenplanung angewandt.[12]
2.4.3 Netzplantechnik
Die Netzplantechnik (NPT) wird in der Praxis sehr häufig bei der Planung eingesetzt und dient der Beschreibung, Planung, Steuerung und Kontrolle von Projekten. Dabei werden die einzelnen Tätigkeiten eines Projektes grafisch in einem Netzplan dargestellt, welcher die gegenseitigen Abhängigkeiten und die Zeitvorgaben für die Realisation enthält.[13] Die grafische Darstellung macht das Projekt sehr transparent. Damit kann die NPT zur Planung von Terminen, Kosten, Kapazitäten und Finanzen eingesetzt werden.
2.4.4 Simulation
Simulationen finden immer dann Anwendung, wenn das betrachtete System komplex und somit das Problem mathematisch nicht mehr lösbar ist.[14] Bei einer Simulation muss sowohl die Struktur der Realität als auch deren Verhalten gewahrt werden.[15] Ziel von Simulationen ist es, die vereinfachte Realität nachzuspielen und durch zielgerichtetes Experimentieren zu einer optimalen Lösung zu kommen.
2.4.5 Heuristiken
Heuristische Verfahren werden bei der Lösung sehr komplexer Probleme angewandt. Ziel ist es, mit wenig Aufwand eine gute Lösung zu finden. Dabei wird nicht die mathematisch optimale Lösung ermittelt, sondern lediglich eine Näherung davon.[16] Diese kann durch Iteration, d.h. durch mehrmaliges Anwenden der Heuristik, präzisiert werden.
2.4.6 Spieltheorie
Die Spieltheorie befasst sich mit Systemen mit mehreren Akteuren, also vor allem mit Konkurrenz- und Konfliktsituationen. Dabei werden sowohl die Entscheidungen der Konkurrenz, empirische Daten und psychologische Momente als auch deren Abhängigkeiten voneinander berücksichtigt. Bekannte Beispiele sind unter anderem das Gefangenendilemma, „quid pro quo“ bzw. „tit for tat“ sowie das Braess-Paradoxon[17].
2.4.7 Warteschlangentheorie
Die Warteschlangentheorie beschäftigt sich mit der Abfertigung von Aufträgen und Serviceleistungen und ermittelt Engpässe oder Durchlaufzeiten. Analysiert werden beispielsweise Maschinenengpässe, Bankschalter oder Kassen im Supermarkt.
2.4.8 Entscheidungsbaumverfahren
Mit Hilfe eines Entscheidungsbaumes können sämtliche Lösungswege aufgezeigt und berechnet werden. Die Ergebnisse werden schließlich miteinander verglichen, um die optimale Lösung zu finden. Dabei können Teillösungen, welche offensichtlich nicht zur optimalen Lösung führen (können), ohne eine vollständige Berechnung ausscheiden.
3 Algorithmen – Grundlage für Optimierungsprozesse
Der Begriff des Algorithmus gehört zu den Grundbegriffen der Informatik. Jedem Programm, das auf einem Computer installiert ist, liegt eine, unabhängig von der verwendeten Programmiersprache, formulierbare Verarbeitungsvorschrift — ein Algorithmus — zugrunde. Die Informationstechnologie, wie wir sie heute kennen, würde somit ohne Algorithmen nicht existieren. Doch nicht nur der technologische Fortschritt profitiert von Algorithmen. In der Mathematik wurden Algorithmen schon viele Jahrhunderte vor der Erfindung des Computers als systematische Berechnungsvorschriften eingesetzt. Das Wort „Algorithmus“ geht auf den Gelehrten Muhammed Al-Chwarizmi zurück. Die lateinische Übersetzung eines seiner im 9. Jahrhundert verfassten mathematischen Werke beginnt mit den Worten „Dixit Algorismi“ („Algorismi hat gesagt“) und beschäftigt sich mit Rechenverfahren durch Ergänzen und Ausgleichen. Im Laufe der Zeit verband man die daraus entstandene Verballhornung „Algorithmus“ ganz allgemein mit mechanisch ausführbaren Rechenverfahren.[18]
Der wohl bekannteste Algorithmus ist der nach dem griechischen Mathematiker Euklid benannte euklidische Algorithmus. Er beschreibt ein Verfahren zur Ermittlung des größten gemeinsamen Teilers zweier natürlicher Zahlen.
3.1 Grundlegende Definition
Unter einem Algorithmus versteht man eine genau definierte Handlungsvorschrift zur Lösung eines Problems oder einer bestimmten Art von Problemen.[19] Algorithmen sind permanente Begleiter des täglichen Lebens und beeinflussen Handlungen auf verschiedenste Art und Weise. Die praktische Verwendung von Algorithmen reicht von einfachen Anwendungen wie Kochrezepten und der Tonfolge beim Spielen einer Melodie über Bedienungsanleitungen und Schaltpläne bis hin zur Lösung komplexer mathematischer Probleme.
Im Allgemeinen löst ein Algorithmus eine Klasse von Problemen. Die Auswahl eines einzelnen Problems erfolgt über Parameter. Aus der Präzision der sprachlichen Darstellung des Algorithmus muss die Abfolge der einzelnen Verarbeitungsschritte eindeutig hervorgehen. Hierbei sind Wahlmöglichkeiten zugelassen. Jedoch muss genau festgelegt sein, wie die Auswahl einer Möglichkeit erfolgen soll.[20]
Algorithmen besitzen folgende charakteristische Eigenschaften:
1. Finitheit
Die Beschreibung eines Algorithmus besitzt eine endliche Länge (statische Finitheit). Ferner darf zu jedem Zeitpunkt seiner Ausführung nur endlich viel Platz belegt werden (dynamische Finitheit).
[...]
[1] Gohout, Operations Research, S.1
[2] Corsten, Corsten, Sartor, Operations Research, S.3
[3] Heinrich, Operations Research, S.1
[4] Gohout, Operations Research, S.3
[5] Corsten, Corsten, Sartor, Operations Research, S.5
[6] Domschke, Drexl, Einführung in Operations Research, S.1f.
[7] Siehe Kapitel 3
[8] Heinrich, Operations Research, S.9
[9] Ellinger, Beuermann, Leisten, Operations Research, S.8
[10] Ellinger, Beuermann, Leisten, Operations Research, S.11
[11] Ellinger, Beuermann, Leisten, Operations Research, S.11
[12] Domschke, Drexl, Einführung in Operations Research, S.8
[13] Ellinger, Beuermann, Leisten, Operations Research, S.13
[14] Heinrich, Operations Research, S.153
[15] Runzheimer, Operations Research, S.246
[16] Ellinger, Beuermann, Leisten, Operations Research, S.14
[17] Das Braess-Paradoxon besagt, dass das Schaffen einer weiteren alternativen Handlungsmöglichkeit aufgrund von rationaler Einzelentscheidungen aller Individuen zu einer Verschlechterung der Gesamtsituation für alle Individuen führen kann.
[18] Vgl. Internetquelle Nr.1, S. 27
[19] Vgl. Internetquelle Nr.2, S. 27
[20] Vgl. Claus, V. /Schwill, A.: Duden Informatik
-
-
-
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen.