In einer von Vernetzung und Globalisierung geprägten Umwelt wächst der Wettbewerbsdruck auf die Unternehmen am Markt stetig. Die effektive Nutzung der Ressourcen einerseits und die enge Zusammenarbeit mit Lieferanten und Kunden andererseits führen für nicht wenige Unternehmen des industriellen Sektors zu entscheidenden Wettbewerbsvorteilen, die das Fortbestehen jener Unternehmen am Markt sichern. Viele Unternehmen verstehen sich aus diesem Grund als Bestandteil so genannter Supply Chains. Die unternehmensübergreifende Steuerung und Optimierung des Wertschöpfungsprozesses stellt ein charakteristisches Problem des Supply Chain Managements dar und besitzt zur Erzielung von Wettbewerbsvorteilen hohes Potential.
Produktionsnetzwerke sind ein wesentlicher Forschungsschwerpunkt der Professur für Produktionswirtschaft und Industriebetriebslehre an der TU Chemnitz. Das Extended Value Chain Management (EVCM) stellt ein kompetenzorientiertes Konzept für die Bildung und zum Betrieb hierarchieloser temporärer regionaler Produktionsnetzwerke im Sinne virtueller Unternehmen dar.
Gegenstand dieser Arbeit ist ein diskretes Optimierungsproblem, dass einen mehrstufigen Entscheidungsprozesses unter Berücksichtigung mehrerer Ziele abbildet, der sich bei der Auswahl möglicher Partner in einem Produktionsnetzwerk nach dem Betreiberkonzept des EVCM ergibt.
Da mehrere Zielstellungen bestehen, werden grundlegende Methoden der mehrkriteriellen Optimierung und Entscheidung erörtert. Neben der Vorstellung des Problems sollen mehrzielorientierte Ansätze im Sinne einer Pareto-Optimierung auf Basis des Dynamic Programmings als Verfahren zur Bestimmung von Optimallösungen sowie Ant Colony Optimization zur näherungsweisen Lösung vorgestellt werden. Darauf aufbauend werden verschiedene Möglichkeiten der Hybridisierung beider Methoden diskutiert. Die entwickelten Ansätze werden auf ihre Eignung im Rahmen der informationstechnischen Umsetzung des EVCM-Konzepts untersucht und einer Evaluierung unterzogen. Hierzu werden verschiedene Kennzahlen zur Beurteilung der Verfahren entwickelt.
Die modellierten Algorithmen und entwickelten Konzepte beschränken sich nicht ausschließlich auf das betrachtete Problem, sondern können leicht auf Probleme mit ähnlichen Eigenschaften übertragen werden. Insbesondere das NP-vollständige mehrkriterielle Kürzeste-Wege-Problem stellt einen Spezialfall des behandelten Optimierungsproblems dar.
Inhaltsverzeichnis
1 Einführung
1.1 Gegenstand der Arbeit
1.2 Dokumentstruktur
2 Theoretische Grundlagen
2.1 Grundlagen der Graphentheorie
2.1.1 Gerichtete Graphen
2.1.2 Wichtige Eigenschaften von Graphen
2.2 Grundlagen der Komplexitätstheorie
2.2.1 Komplexitätsmaße
2.2.2 Komplexitätsklassen P und NP
2.2.3 Problemrelationen und polynomielle Reduktion
2.3 Diskrete und kombinatorische Optimierung
2.3.1 Problemdefinition und Eigenschaften
2.3.2 Ausgewählte Optimierungsprobleme
3 Optimierung bei Mehrfachzielsetzung
3.1 Mehrkriterielle Probleme
3.1.1 Problemstellung
3.1.2 Zielbeziehungen
3.2 Optimalität bei mehrfacher Zielsetzung
3.2.1 Paretooptimalität
3.2.2 Eigenschaften der paretooptimalen Lösungsmenge
3.2.3 Idealpunkte und Nadir-Punkt der Front
3.3 Multikriterielle kombinatorische Optimierung
3.3.1 Klassifizierung entscheidungstheoretischer Ansätze
3.3.2 A-priori-Methoden als reduktive Verfahren
3.3.3 A-posteriori-Methoden als nicht-reduktive Verfahren
3.4 Reduktive Entscheidungsmodelle
3.4.1 Lexikographische Ordnung
3.4.2 Haupt- und Nebenziele
3.4.3 Methode der gewichteten Summen und Produkte
3.4.4 AHP
3.4.5 Fuzzy Decision Making
3.4.6 Goal Programming und Compromise Programming
3.5 Fazit
3.5.1 Beurteilung der A-priori-Methoden
3.5.2 Beurteilung der A-posteriori-Methoden
4 Optimierung von Angebotsnetzen im EVCM
4.1 Extended Value Chain Management
4.1.1 Phasenmodell
4.1.2 Prozessvariantenplan und Prozessplan
4.1.3 Angebotsnetze
4.1.4 Problemstellung bei der Kompetenzzellenauswahl
4.2 Formalisierung des Problems
4.2.1 Problemgraph
4.2.2 Restriktionssystem
4.2.3 Lösungskonstruktion und Problemstellung
4.3 Zielsetzungen der Optimierung
4.3.1 Preis
4.3.2 Lieferwahrscheinlichkeit
4.3.3 Liefertermin
4.4 Angebote mit unvollständigen Mengen
4.4.1 Ansatz mit impliziter Behandlung von Teilmengen
4.4.2 Ansatz mit Behandlung expliziter Fehlmengen
4.5 Problemkomplexität
5 Dynamic Programming
5.1 Theoretische Grundlagen
5.1.1 Einführung
5.1.2 Problemstellung und Lösungsprinzip
5.1.3 Verfahren
5.2 Problemspezifische Modellierung
5.2.1 Problemspezifischer Basisalgorithmus
5.2.2 Umgang mit Divergenzen
5.3 Komplexitätsbetrachtungen
5.3.1 Komplexität bei einkriteriellen Problemen mit rein konvergierenden Prozessplänen
5.3.2 Komplexität bei einkriteriellen Problemen mit allgemeinen Prozessplänen
6 Ant Colony Optimization
6.1 Einführung
6.1.1 Einordnung des Verfahrens
6.1.2 Naturanalogie
6.1.3 ACO-Metaheuristik
6.2 Verschiedene Ansätze
6.2.1 Ant System
6.2.2 Ant Colony System
6.3 Mehrkriterielle Ameisenalgorithmen
6.3.1 Überblick
6.3.2 Paretooptimierung mit ACO
6.3.3 Gewichtung bei beliebiger Zielanzahl
6.4 Problemspezifische Modellierung
6.4.1 Ant Family Heuristic
6.4.2 Lösungskonstruktion
6.4.3 Heuristikwerte für das Angebotsnetz
6.4.4 Konvergenzverhalten und Pheromoninitialisierung
7 Hybride Methoden und Erweiterungen
7.1 Pheromonaktualisierung bei Paretooptimierung
7.1.1 Eigenschaften der bisherigen Strategie
7.1.2 Nadir-Punkt-Strategie
7.2 Paretooptimierung mit Auswahl nach Fuzzy Decision Making
7.2.1 Ausgangssituation
7.2.2 Auswahlwahrscheinlichkeiten über Fuzzy Decision Making
7.3 Problemreduktion
7.3.1 Dominanz von Teilgraphen
7.3.2 Algorithmisches Konzept
7.4 Die Look-Ahead-Heuristic
7.4.1 Ausgangssituation
7.4.2 Konzept der Look-Ahead-Heuristic
8 Evaluierung
8.1 Evaluierung des Parallel Path Problems und des dynamischen Programms
8.1.1 Verwendete Evaluierungsmaße
8.1.2 Abhängigkeiten zwischen Komplexität und Zielkriterien
8.1.3 Abhängigkeiten zwischen Paretofront und Zielfunktionen
8.1.4 Komplexität von Angebotsnetzen
8.1.5 Probleme mit divergenten Prozessplänen
8.2 Evaluierung ACO und hybride Ansätze
8.2.1 Verwendete Evaluierungsmaße
8.2.2 Problemlösungsverhalten der Ameisenalgorithmen
8.2.3 Verwendung von Routingtabellen und Tabulisten
8.2.4 Aktualisierungsstrategien
8.2.5 Analyse verschiedener Aggregationsmethoden
8.2.6 Standard-Heuristik und Look-Ahead-Heuristic
8.2.7 Problemreduktion
Fazit und Ausblick
A Ergänzungen und Detailinformationen zur Evaluierung
A.1 Evaluierte Problemgraphen und Prozesspläne
A.1.1 Technologiegraphen
A.1.2 Problemgraphen
A.2 Verwendete Konfigurationen und Parameter von ACO
A.2.1 Verwendete Konfiguration
A.2.2 Verwendete Parameter
B Beispielrechnung
B.1 Dynamisches Programm
B.2 Lösungskonstruktion ACO
Literaturverzeichnis
Register
Zielsetzung & Themen
Die Arbeit untersucht das Optimierungsproblem von Angebotsnetzen innerhalb des "Extended Value Chain Management" (EVCM). Ziel ist die Entwicklung und Evaluierung von Lösungsansätzen zur Auswahl von Kompetenzzellen in einem unternehmensübergreifenden Produktionsnetzwerk, wobei die Komplexität des Problems in uni- und multikriterieller Hinsicht analysiert wird.
- Optimierung von Angebotsnetzen mittels dynamischer Programmierung
- Einsatz von Ant Colony Optimization zur näherungsweisen Problemlösung
- Hybridisierung und Erweiterung von Lösungsalgorithmen
- Umgang mit Divergenzen in Prozessplänen und deren Komplexitätsauswirkungen
- Evaluierung der Leistungsfähigkeit der entwickelten Methoden
Auszug aus dem Buch
2.1.1 Gerichtete Graphen
Ein Graph G kann über das Tupel G = (V, E) definiert werden. In diesem Zusammenhang beschreibt V eine endliche oder unendliche, nichtleere Menge, deren Elemente v ∈ V als Knoten, Ecken oder Punkte bezeichnet werden. Die Elemente e = {a, b} mit a, b ∈ V der Menge E ⊆ V^2 beschreiben zweielementige Teilmengen aus V und werden als Kanten des Graphen zwischen den Endpunkten a und b bezeichnet, wenn a = b ist. Im Falle, dass a = b gilt, wird ein Element e Schlinge genannt. In der graphischen Darstellung von Graphen werden Knoten als Punkte oder Kreise und Kanten als verbindende Linien zwischen diesen Punkten dargestellt. In gerichteten Graphen, auch Digraphen genannt, setzt sich die Menge E aus geordneten Paaren (a, b) zusammen, wobei a Startpunkt oder tail und b Endpunkt oder head heißt. Aus Gründen der Unterscheidung zu ungerichteten Graphen wird für eine gerichtete Kante auch die Bezeichnung Bogen verwendet. Gerichtete Kanten werden in der graphischen Darstellung mit einer Pfeilspitze in Richtung des Endpunktes gekennzeichnet. Für Elemente dieser Menge werden die Notationen e = ab oder e = a → b verwendet. Zwei Knoten a und b besitzen in einem Graphen Mehrfachkanten, falls mindestens zwei oder mehr verschiedene Elemente ei ∈ E mit i = {1 . . . n} und i ∈ N existieren, welche zwei Knoten a und b miteinander verbinden. Im ungerichteten Fall werden zwei Kanten e1 = (a, b) und e2 = (b, a) als parallel bezeichnet. Im gerichteten Fall hingegen heißen die Bögen beziehungsweise gerichteten Kanten e1 = a → b und e2 = b → a antiparallel, da sie zwar die gleichen Knoten verbinden, sich ihre Richtung aber unterscheidet.
Zusammenfassung der Kapitel
1 Einführung: Einleitung in die Problematik der Angebotsnetze im EVCM und Vorstellung der Forschungsfrage sowie Dokumentstruktur.
2 Theoretische Grundlagen: Erläuterung graphentheoretischer, komplexitätstheoretischer und diskreter Optimierungsgrundlagen.
3 Optimierung bei Mehrfachzielsetzung: Detaillierte Betrachtung multikriterieller Probleme, paretooptimaler Lösungen und verschiedener Entscheidungsansätze.
4 Optimierung von Angebotsnetzen im EVCM: Vorstellung des EVCM-Konzepts und Formalisierung des Optimierungsproblems.
5 Dynamic Programming: Theoretische Einführung in die dynamische Programmierung und deren Anwendung zur exakten Lösung des Parallel Path Problems.
6 Ant Colony Optimization: Vorstellung der ACO-Metaheuristik und deren Anpassung an die Anforderungen von Angebotsnetzen.
7 Hybride Methoden und Erweiterungen: Entwicklung und Analyse hybrider Algorithmen zur Verbesserung der Lösungsgüte bei komplexen Problemstellungen.
8 Evaluierung: Umfassende Untersuchung und Evaluierung der vorgestellten Methoden anhand verschiedener Problemgraphen und Leistungskennzahlen.
Schlüsselwörter
EVCM, Angebotsnetze, kombinatorische Optimierung, Parallel Path Problem, Dynamische Programmierung, Ant Colony Optimization, Paretooptimalität, Multikriterielle Optimierung, heuristische Verfahren, Look-Ahead-Heuristic, Problemkomplexität, NP-Vollständigkeit, Lieferwahrscheinlichkeit, Preis, Liefertermin.
Häufig gestellte Fragen
Worum geht es in dieser Diplomarbeit?
Die Arbeit befasst sich mit der Optimierung unternehmensübergreifender Angebotsnetze im Rahmen des sogenannten Extended Value Chain Managements (EVCM).
Welche zentralen Themenfelder werden behandelt?
Zentrale Themen sind die mathematische Modellierung von Angebotsnetzen, die Anwendung exakter Lösungsverfahren wie der dynamischen Programmierung und metaheuristischer Verfahren wie Ant Colony Optimization.
Was ist das primäre Ziel der Arbeit?
Das Hauptziel ist die Entwicklung und Evaluierung von Methoden zur Auswahl der optimalen Kombination von Kompetenzzellen, die den Kundenanforderungen an Preis, Lieferwahrscheinlichkeit und Liefertermin entsprechen.
Welche wissenschaftliche Methode kommt zum Einsatz?
Die Arbeit nutzt Methoden der Graphentheorie zur Modellierung, Techniken der diskreten und multikriteriellen kombinatorischen Optimierung sowie algorithmische Ansätze der dynamischen Programmierung und Ameisenalgorithmen (ACO).
Was wird im Hauptteil behandelt?
Der Hauptteil gliedert sich in die theoretische Fundierung, die spezifische Modellierung der Angebotsnetze als "Parallel Path Problem" und die Erarbeitung von Lösungsverfahren, inklusive einer detaillierten Evaluierung.
Welche Schlüsselbegriffe charakterisieren die Arbeit?
Charakterisierende Begriffe sind EVCM, Angebotsnetze, Parallel Path Problem, Paretooptimalität, Multikriterielle Optimierung und Ant Colony Optimization.
Warum ist die "Look-Ahead-Heuristic" wichtig?
Diese Heuristik wurde entwickelt, um die Schwächen der Standard-Greedy-Heuristik in ACO-Algorithmen bei unterschiedlichen Pfadlängen zu beheben und somit eine realistischere Bewertung von Alternativen zu ermöglichen.
Welche Rolle spielt die Problemreduktion?
Die Problemreduktion nutzt Konzepte der dynamischen Programmierung, um den Lösungsraum vorab zu vereinfachen und die Effizienz des Ameisenalgorithmus durch Fokus auf relevante Entscheidungsbereiche zu erhöhen.
Was zeigt die Evaluierung hinsichtlich der Lösbarkeit?
Die Evaluierung demonstriert, dass exakte Lösungen mittels dynamischer Programmierung nur für kleinere und mittlere Instanzen praktikabel sind, während für größere Probleme oder Probleme mit hoher Divergenz auf ACO-basierte Näherungsverfahren zurückgegriffen werden muss.
- Citar trabajo
- Dipl.-Wirt.-Inf. Sascha Häckel (Autor), 2006, Hybride Ansätze zur Optimierung Kürzester-Wege-Probleme in gerichteten Graphen, Múnich, GRIN Verlag, https://www.grin.com/document/90934
