- II -

Inhaltsverzeichnis

Inhaltsverzeichnis   II

Abbildungsverzeichnis.   III

Tabellenverzeichnis   IV

Abk  ürzungsverzeichnis.  V

1  Einleitung  1

1.1  Problemstellung und Zielsetzung  2

1.2  Vorgehensweise  2

1.3  Notenverrechnung  3

2  Evolutionäre Algorithmen  4

3  Supply Chain Management  7

4  Theoretische Abhandlung der Genetischen Algorithmen  11

4.1  Selektion.  11

4.2  Rekombination  13

4.3  Mutation  15

5  Umsetzung des Genetischen Algorithmus  18

5.1  Selektion.  20

5.2  Rekombination  21

5.3  Mutation  23

5.4  Grafische Benutzeroberfläche  24

6  Evaluation Optimierung der Genetischen Operationen  26

6.1  Selektion.  26

6.2  Rekombination  33

6.3  Mutation  38

6.4  Optimierungs-Szenario für den Grundalgorithmus.  43

7  Dezentraler Ansatz  46

7.1  Varianten eines Dezentralen Ansatzes  46

7.2  Struktogramme der umgesetzten Ansätze  47

7.3  Evaluation des Dezentralen Ansatzes  50

8  Fazit.  53

Anhang   VI

Anhang 1:  Aufgabenverteilung  VI

Anhang 2:  Ergebnisse der ersten Phase.  VII

Anhang 2:  Ergebnisse der zweiten Phase.  IX

Quellenverzeichnis   X

- III -

Abbildungsverzeichnis   

Abb.  1: Prinzipieller Ablauf Evolutionärer Suchverfahren.  

Abb.  2: Aufbau einer Supply Chain  

Abb.  3: Grafische Darstellung der Rekombination  

Abb.  4: Rekombination - Einpunktkreuzung  

Abb.  5: Rekombination - Mehrpunktkreuzung  

Abb.  6: Rekombination - Gleichmäßige Kreuzung.  

Abb.  7: Bit-Flipping  

Abb.  8: Struktogramm Bit-Flipping’  

Abb.  9: Swap-Mutation  

Abb.  10: Struktogramm ,Swap-Mutation’  

Abb.  11: Struktogramm Ablauf des Evolutionären Algorithmus’  

Abb.  12: Quelltext Erzeugung der Binärmatrix’  

Abb.  13: Zusammenspiel der genetischen Operationen.  

Abb.  14: Roulette-Rad mit Sektorenzuweisung je Individuum entsprechend der Fitness.  

Abb.  15: Struktogramm Ablauf der Selektion’  

Abb.  16: Übertragung int in String  

Abb.  17: Erzeugung der Kindgeneration durch zufällige Trennung der Elternindividuen  

Abb.  18: Struktogramm Ablauf der Rekombination’  

Abb.  19: Struktogramm Ablauf der Mutation’  

Abb.  20: Screenshot der grafischen Benutzeroberfläche  

Abb.  21: Bestenselektion.  

Abb.  22: Struktogramm Bestenselektion’  

Abb.  23: Werteverlauf Bestenselektion (Instanz 1 Phase 1, 100 Generationen)  

Abb.  24: Wettkampfselektion  

Abb.  25: Struktogramm Wettkampfselektion’  

Abb.  26: Werteverlauf Wettkampfselektion (Instanz 1 Phase 1, 100 Generationen)  

Abb.  27: Einfache Rekombination mit fester Trennstelle in der Mitte.  

Abb.  28: Struktogramm Einfache Rekombination mit fester Trennstelle in der Mitte’  

Abb.  29: Werteverlauf Rekombination - Feste Trennstelle Mitte  

  (Instanz 1 Phase 1, 1000 Generationen)  

Abb.  30: Gleichmäßige Rekombination.  

Abb.  31: Struktogramm Gleichmäßige Rekombination’  

Abb.  32: Rekombination mit zwei zufälligen Trennstellen - Ablauf  

Abb.  33: Struktogramm Rekombination mit zwei zufälligen Trennstellen’  

Abb.  34: Werteverlauf Rekombination - Zwei Trennstellen  

  (Instanz 1 Phase 1, 1000 Generationen)  

Abb.  35: Flip-Mutation an einer Stelle.  

Abb.  36: Struktogramm Flip-Mutation an einer Stelle’  

Abb.  37: Werteverlauf Flip-Mutation an einer Stelle (Instanz 1 Phase 1, 100 Generationen)  

Abb.  38: Flip-Mutation an zwei Stellen  

Abb.  39: Struktogramm Flip-Mutation an zwei Stellen’  

Abb.  40: Werteverlauf Flip-Mutation an zwei Stellen (Instanz 1 Phase 1, 100  

Abb.  41: Swap-Mutation  

Abb.  42: Struktogramm Swap - Mutation’  

Abb.  43: Werteverlauf Swap-Mutation (Instanz 1 Phase 1, 100 Generationen)  

Abb.  44: Struktogramm ,Bewerten() - Border 1’  

Abb.  45: Struktogramm ,Selektion - Border 1’  

Abb.  46: Struktogramm ,Bewerten() - Border 2'  

Abb  47: Werteverlauf Border 1 (Instanz 1 Phase 1, 100 Generationen)  

- IV -Abb. 48: Werteverlauf Border 1 (Instanz 1 Phase 1, 100 Generationen)................................. 51 Abb. 49: Abweichungsanalyse Optimierungs-/ Grundalgorithmus und X-Men

(Instanzen Phase 1).................................................................................................... 53

Tabellenverzeichnis

Tab. 1: Vor- und Nachteile eines Evolutionären Algorithmus................................................... 6 Tab. 2: Gegenüberstellung Roulette- und Bestenselektion (Instanz 1 Phase 1)....................... 27 Tab. 3: Gegenüberstellung Roulette- und Bestenselektion (Instanz 1 Phase 2)....................... 28 Tab. 4: Gegenüberstellung Roulette- und Wettkampfselektion (Instanz 1 Phase 1) ............... 30 Tab. 5: Gegenüberstellung Roulette- und Wettkampfselektion (Instanz 1 Phase 2) ............... 31 Tab. 6: Gegenüberstellung Besten- und Wettkampfselektion.................................................. 32 Tab. 7: Gegenüberstellung Besten- und Wettkampfselektion (Instanz 1 Phase 2) .................. 32 Tab. 8: Gegenüberstellung Rekombination mit variabler/ fester Trennstelle .......................... 34 Tab. 9: Gegenüberstellung Rekombination mit variabler Trennstelle/

gleichmäßige Rekombination....................................................................................... 35 Tab. 10: Gegenüberstellung Einfache/ Zweifache Rekombination mit einer/

zwei variablen Trennstellen ....................................................................................... 37 Tab. 11: Gegenüberstellung Flip-Mutation mit Mutationswahrsch./

Flip-Mutation an einer Stelle...................................................................................... 39 Tab. 12: Gegenüberstellung Flip-Mutation mit Mutationswahrsch./

Flip-Mutation an zwei Stellen .................................................................................... 40 Tab. 13: Gegenüberstellung Flip-Mutation mit Mutationswahrsch./ Swap-Mutation ............. 42 Tab. 14: Kombinationsmöglichkeiten für Szenarien................................................................ 43 Tab. 15: Übersicht über ausgewählte Szenarien ...................................................................... 44 Tab. 16: Ergebnisse der ersten zehn Instanzen mit verschiedenen Szenarien ......................... 45 Tab. 17: Vergleich dezentrale Ansätze (Phase 1, Instanz 1).................................................... 52 Tab. 18: Abweichungsanalyse für Phase 1............................................................................... 53 Tab. 19: Leistungsvergleich ..................................................................................................... 54 Tab. 20: Abweichungsanalyse für Phase 2............................................................................... 54

- V - Abkürzungsverzeichnis

Abb. Abbildung d.h. das heißt EA Evolutionäre Algorithmen GPRS General Packet Radio Service GUI Graphical User Interface Lsg Lösung SCC Supply-Chain-Council SCM Supply Chain Management SCOR Supply Chain Operations Reference Model Tab. Tabelle z.B. zum Beispiel

- 1 - 1Einleitung

In einer Zeit, in der modernste Technologie allgegenwärtig und alltäglich geworden ist, verändern sich Märkte in rasanter Geschwindigkeit. Das Internet ermöglicht schnellsten Informationsaustausch und schnellste Reaktionsfähigkeit. Damit werden Märkte dynamischer und Wettbewerbsvorteile können von Konkurrenten rasant aufgeholt werden. Vor kurzer Zeit waren nur Branchen betroffen, die hochtechnisiert waren. Heute stehen alle Branchen und Märkte im Einfluss des Internets. Damit nicht genug, das Internet ist mobil geworden, Blackberry ¹ , IPhone ² oder GPRS-Karte ³ gehören zur Grundausstattung eines modernen Geschäftsmannes. Damit wächst für Unternehmen der Druck, Wettbewerbsvorteile auszubauen und zu halten. In Unternehmen mit eigener Produktion aber auch im Dienstleistungsbereich werden Schnittstellen zur Kommunikation zwischen Unternehmen immer wichtiger.

Innerhalb von Unternehmen wurde in den letzen Jahren kräftig „aufgeräumt“. Effizienzsteigerung, Prozessoptimierung, oder „Lean Production“ ⁴ sind nur einige Schlagwörter, die zu einer Verschlankung der Unternehmen geführt haben. Prozesse oder ganze Teile des Unternehmens wurden outgesourced, viel Potential für Verbesserungen ist nicht geblieben, außer an den Schnittstellen zwischen Unternehmen. Dort ist noch einiges an Verbesserungspotential vorhanden. Eine unternehmensübergreifende Kommunikation kann zahlreiche Vorteile mit sich bringen. Dabei können Unternehmen sowohl im Rahmen der Kooperation, der Coopetition ⁵ oder einfach als Lieferant und Kunde miteinander zusammenarbeiten und ihre Prozesse optimieren. Die Kommunikation läuft nicht nur in eine Richtung, sondern auch gegenläufig und erstreckt sich über viele Unternehmen entlang einer Lieferkette hinweg. Eine solche Lieferkette ist meist eine Wertschöpfungskette, da jedes beteiligte Unternehmen einen Mehrwert in seiner Stufe der Kette generiert. Die Koordination und Kommunikation in einer solchen Kette umfasst ein ganzes Fachgebiet in der Betriebswirtschaftslehre. Dieses Fachgebiet hat sich zu einem Managementkonzept, genannt „Supply Chain Management“, entwickelt. Es hat als Aufgabe die Koordination der einzelnen Unternehmen, um die Wertschöpfungskette zu optimieren. Dies ist auch das Thema dieser Fallstudie.

¹ Vgl. http://www.blackberry.com/de/.

² Vgl. http://www.apple.com/de/iphone/.

³ GPRS ermöglicht mobilen Internetzugang in Verbindung mit einem GPRS-fähigen Endgerät.

⁴ Schlanke Produktion, Produktionsorganisation.

⁵ Wertschöpfung aus „Cooperation“ und „Competition“, meint die Kooperation von Konkurrenten.

- 2 - 1.1Problemstellung und Zielsetzung

Optimierungsprobleme im Bereich des Supply Chain Managements sind aufgrund ihrer unzähligen Variablen oft hoch komplex. Ob Tourenplanungen oder Kostenoptimierung: mathematische Verfahren, die sich in vielen Problemstellungen bewährt haben, stoßen hierbei an ihre Grenzen. An der Theorie hapert es dabei nicht, die meisten Problemstellungen lassen sich lösen, der kritische Faktor ist jedoch die Zeit. Trotz hoch modernen Rechenzentren mit Prozessoren, die sich jährlich übertreffen und einer „Top - 100 - Liste“ von Supercomputern, die ständig aktualisiert werden muss, ist Rechenzeit bei der Lösung vieler Optimierungen der Faktor, an der die Anwendung von herkömmlichen Verfahren scheitert. Viele Problemstellungen würden über einhundert Jahre Rechenzeit benötigen, damit ist die Anwendung herkömmlicher Verfahren unmöglich. Eine Lösungsmöglichkeit für diese Probleme sind Heuristiken, die mit verschiedenen Verfahren versuchen, eine gute Lösung zu finden. Verblüffend ist dabei, dass sich ab und zu nicht nachvollziehen lässt, wie die Lösung entstanden ist. Es ist aber beweisbar, wie gut eine solche Lösung im Vergleich zu anderen bekannten Lösungen ist. In diesem Bereich lassen sich Evolutionäre Algorithmen einsetzen, die im nachfolgenden Kapitel näher beschrieben werden.

Diese Fallstudie verfolgt das Ziel, die Möglichkeiten Evolutionärer Algorithmen aufzuzeigen, um ein betriebswirtschaftliches Optimierungsproblem aus dem Bereich Supply Chain Management zu lösen.

1.2 Vorgehensweise

Nach einer Einführung in die Welt der evolutionären Algorithmen wird das Supply Chain Management näher dargestellt. Die wesentlichen Bestandteile von Evolutionären Algorithmen, also Mutation, Rekombination und Selektion, werden im darauf folgenden Kapitel detailliert erklärt. Anschließend wird die praktische Umsetzung eines betriebswirtschaftlichen Optimierungsproblems aus dem Bereich Supply Chain Management mit Hilfe evolutionärer Algorithmen aufgezeigt. Dabei werden die zuvor theoretisch erklärten Bestandteile evolutionärer Algorithmen angewendet. Eine solche Anwendung macht eine nachfolgende Optimierung notwendig, um die erzielten Ergebnisse zu verbessern. Es wird die Anwendung verschiedener Optimierungsvarianten und deren Ergebnisse präsentiert. Im letzten Kapitel wird ein dezentraler Ansatz vorgestellt, mit dem sich ein solches

- 3 -Optimierungsproblem ebenfalls lösen lässt, allerdings ohne zentrale Koordination, d.h. ohne die Berücksichtigung der Gesamtkosten.

1.3 Notenverrechnung

Bezüglich der Notenverrechnung möchten wir Einzelnoten ausgewiesen bekommen. Bitte beachten Sie hierzu die Anlage ⁶ , in der die Einzelleistungen dargestellt werden.

⁶ siehe Anhang 1: Aufgabenverteilung.

- 4 - 2Evolutionäre Algorithmen

Das Verfahren:

Der Evolutionäre Algorithmus ist ein Optimierungsverfahren ⁷ , das bereits zu Beginn der sechziger Jahre von verschiedenen Forschergruppen entwickelt wurde. ⁸ Beim EA werden die Abläufe einer biologischen Evolution als Vorbild gesehen und in einem Algorithmus benutzt. Das Ziel eines EA ist es, eine möglichst gute Lösung zu einem bestimmten Problem, also unter bestimmten Bedingungen, zu finden. In der Natur entsprechen diese Bedingungen bzw. Probleme den Lebensbedingungen an die sich ein Individuum anpassen muss. Die optimale Lösung stellt in der Natur ein Individuum dar, welches sich sehr gut an die Bedingungen angepasst hat und somit überlebensfähig ist.

Die Natur greift hierbei auf drei biologische Prinzipien zurück, um aus einer Startpopulation Individuen zu entwickeln, die bestmöglich an die Bedingungen angepasst sind. Dieser Vorgang lässt sich so auch auf einen EA übertragen: 9

- Mutation/Nachkomme(n): 10 11

- Rekombination/Nachkomme(n): 12 13

- Selektion/Partnerwahl: 14

⁷ Vgl. http://www.tu-chemnitz.de/informatik/ModSim/Software/leo.html.

⁸ Vgl. http://ls2-www.cs.uni-dortmund.de/~storch/documents/DiplomArbeit.pdf.

⁹ Vgl. http://www.fh-meschede.de/public/willms/ea/simu.html.

^{10 Vgl. http://www.guidobauersachs.de/genetik/muta.html. 11} Vgl. http://www.informatikdidaktik.de/HyFISCH/Spitzenforschung/Wegener.htm.

¹² Vgl. http://www.biosicherheit.de/de/lexikon/#R.

¹³ Vgl. http://www-ti.informatik.uni-tuebingen.de/~heim/lehre/proseminar_ss99/ausarbeitung /andreas_korsten/node10.html.

¹⁴ Vgl. http://fbim.fh-regensburg.de/~saj39122/vhb/NN-Script/script/gen/k040401.html.

- 5 -Der Ablauf eines EA lässt sich somit in folgendem Schema darstellen: 15

Abb. 1: Prinzipieller Ablauf Evolutionärer Suchverfahren 16

Anwendungsgebiete

EA dienen der Lösung von Optimierungsproblemen bei denen traditionelle Optimierungsverfahren auf Grund von Nichtlinearitäten ¹⁷ und Diskontinuitäten ¹⁸ zur Findung einer optimalen Lösung nicht mehr benutzt werden können. 19

¹⁵ Vgl. http://www.iai.fzk.de/www-extern/index.php?id=237.

¹⁶ http://www.iai.fzk.de/www-extern/uploads/pics/Evo-Ablauf.gif.

¹⁷ Jedes System, welches nicht in jedem Bereich proportional auf das Eingangssignal (Systemreiz) antwortet.

¹⁸ Diskontinuität bezeichnet eine Funktion, die nicht stetig ist.

¹⁹ Vgl. http://ls2-www.cs.uni-dortmund.de/~jansen/EvoAlg2004/.

- 6 - Vor-und Nachteile

Tab. 1: Vor- und Nachteile eines Evolutionären Algorithmus

Teilbereiche

Zu dem Themengebiet der EA zählen auch die Themengebiete der genetischen Programmierung, genetische Algorithmen, Evolutionsstrategien und der Evolutionären Programmierung. Diese Verfahren haben alle das Prinzip der biologischen Evolution zum Vorbild und dienen alle der Findung von Lösungen von Optimierungsproblemen.

- 7 - 3Supply Chain Management

Die aktuelle Situation für Unternehmen auf gesättigten Märkten zwingt sie zur Konzentration auf ihre Kernkompetenzen. Dafür ist vor allem bei Produktionsunternehmen eine enge Verflechtung und Vernetzung mit und zwischen Zulieferbetrieben und Betrieben, die Waren abnehmen, erforderlich. Diese Koordinationsaufgabe nennt sich Supply Chain Management und bedeutet konkret die Planung, Koordination und Steuerung der Material- und Informationsströme in Unternehmensnetzwerken. 20

Supply Chain

Der Ausdruck „Supply Chain“ kann mit den Begriffen „logistische Kette, Lieferkette, Versorgungskette oder Leistungswirtschaft“ übersetzt werden. In der Literatur ist häufig die Bezeichnung „Wertschöpfungskette“ zu finden. Die Supply Chain beschreibt den Weg eines Produktes oder einer Dienstleistungen innerhalb mehrerer Unternehmen von der Herstellung des Produktes mit den einzelnen Zwischenschritten entlang einer Kette von Produktionsstufen bis zum Endverbraucher.

Abb. 2: Aufbau einer Supply Chain 21

²⁰ Vgl. Böhnlein, Claus-Burkard (2005), S. 92.

²¹ Vgl. Schinzer, Heiko (1999), S. 857.

- 8 -Wesentlich ist dabei, dass während der Produktion des Produktes oder der Ausführung der Dienstleistung ein Mehrwert gegenüber dem vorhergegangenen Produktionsschritt entsteht. Daher der Name Wertschöpfungskette.

Die Idee und das Konzept einer solchen Kette wurde als erstes von dem Wirtschaftswissenschaftler Michael E. Porter im Jahr 1985 vorgestellt. ²² Warenströme fließen in einer Supply Chain vom Hersteller zu den Endverbrauchern, Geldströme fließen in die Gegenrichtung. Dabei ist zu beachten, dass es zusätzliche Informationsströme gibt, die die Waren - und Geldströme begleiten wie z.B. Lieferscheine. Eine Supply Chain muss nach Auffassung von Porter von einer „Value Chain“ abgegrenzt werden. Bei einer „Value Chain“ handelt es sich um eine Kette der Organisation innerhalb eines Unternehmens, eine „Supply Chain“ erstreckt sich über mehrere Unternehmen hinweg. Eine Supply Chain ist also ein virtuelles Organisationsgebilde über Unternehmen hinweg. Der Extremfall einer Supply Chain geht von der Rohstoffgewinnung bis zum Recycling eines Produktes.

Supply Chain Management

Der Ausdruck des Supply Chain Management, meist abgekürzt mit „SCM“, wird analog zur Supply Chain mit „Versorgungskettenmanagement“ oder „Lieferkettenmanagement“ übersetzt.

Ziel des SCM ist die nahtlose Integration der einzelnen Partner einer Lieferkette untereinander mit dem Hauptziel der Steigerung der Effektivität und Effizienz in der gesamten Lieferkette. SCM bedeutet weiter die Unterstützung und Optimierung von Informations- und Kommunikationsflüssen unter den beteiligten Unternehmen zur Abstimmung von Warenbewegungen. SCM ist ein Managementkonzept, das sich mit logistischen Fragestellungen beschäftigt. 23

Abgrenzung zur Logistik

Die Begriffe SCM und Logistik werden oft synonym verwendet, haben genau genommen aber unterschiedliche Bedeutung. Die Logistik befasst sich mit gleichen Themen wie das SCM, der Unterschied liegt darin, dass sich die Logistik primär mit den Warenflüssen etc. eines Unternehmens befasst, das SCM jedoch unternehmensübergreifend agiert.

²² Vgl. Werner, Hartmut (2007), S.5.

²³ Vgl. Melzer-Ridinger, Ruth (2007), S.9.