Hybride Ansätze zur Optimierung Kürzester-Wege-Probleme in gerichteten Graphen

Inhaltsverzeichnis

Abbildungsverzeichnis

Tabellenverzeichnis

Algorithmenverzeichnis

Abkürzungsverzeichnis

Verwendete Notationen

Symbolverzeichnis

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

Abbildungsverzeichnis

1.1 Strukturelle Abhängigkeit der Kapitel

2.1 Beispielhaftes Kürzeste-Wege-Problem

3.1 Vergleich von MODM und MADM sowie der kombinatorischen Optimierung

3.2 Indifferenzkurven bei Verfahren mit und ohne Kompensation

3.3 Grafische Darstellung von Zielfunktionen der Methode der gewichteten Summe

4.1 Phasenmodell des EVCM

4.2 Beispielhafter Graph eines Prozessplans für die Herstellung eines Produktes

4.3 Beispielhaftes Angebotsnetz für ein Produkt

4.4 Konvergenzreihen bei der Multiplikation vieler kleiner Werte für C#-Datentypen

4.5 Schematische Darstellung eines Fließkommadatentyps

4.6 Rucksackproblem als bikriterielles Shortest Path Problem

5.1 Einordnung von Dynamic Programming als Verfahren

5.2 Schematisches Modell eines dynamischen Optimierungsproblems

5.3 Paretooptimierung bei dynamischen Programmen

5.4 Beispielhafte Segmentierung des Angebotsnetzes in Stufen

5.5 Minimalbeispiel für die Nichteignung von Mittelwertfunktionen bei dynamischen Pro- grammen

5.6 Beispiel für die Verletzung der MARKOV-Eigenschaft bei divergenten Prozessen

5.7 Teilproblembildung bei divergierenden Prozessen

5.8 Komplexer Prozessplan mit exponentiellen Aufwand

6.1 Einordnung von Ant Colony Optimization als heuristisches Verbesserungsverfahren

6.2 Doppelbrückenexperiment mit argentinischen Ameisen

6.3 Kriteriengewichtung auf Basis des Durchmusterungsparameters χ

6.4 Suchdurchmusterung bei drei Kriterien

7.1 Vergleich der mehrkriteriellen Aktualisierungsstrategien

7.2 Problemreduktion mit dynamischer Programmierung am Beispiel

8.1 Komplexität und Anzahl der Zielkriterien

8.2 Konvexe Paretofront des Problems T010

8.3 Konkave Paretofront des Problems T011

8.4 Paretofront des Problems G036 mit typischem Verlauf für Angebotsnetze

8.5 Vergleich der Approximation der verschiedenen Algorithmenvarianten für G030

8.6 Vergleich des Diversitätsmaßes der verschiedenen Algorithmenvarianten für G030

8.7 Branching-Faktor bei der Anwendung der verschiedenen Algorithmen auf G030

8.8 Paretofront und nichtdominierte Fronten verschiedener ACO-Läufe für G040

8.9 Approximation als Distanzmaß im Vergleich von Standard-Heuristik und LAH für G040

8.10 Diversität als Distanzmaß im Vergleich von Standard-Heuristik und LAH für G040

8.11 Vergleich der nichtdominierten Fronten von LAH und Standard-Heuristik

A.1 Prozesspläne der Technologiegraphen TG01 und TG01a-c

B.1 Darstellung des Problemgraphen von B001

B.2 Zugrunde liegender Prozessplan des Problems B001

Tabellenverzeichnis

3.1 (1-9)-Bewertungsskala des Analytical Hierarchy Process

8.1 Zielfunktionen der Probleme T010, T011 und G036

8.2 Übersicht über die exakte Lösbarkeit beziehungsweise Nichtlösbarkeit von Problemen

8.3 Übersicht über die exakte Lösbarkeit beziehungsweise Unlösbarkeit von Problemen mit Divergenzen

8.4 Eingesetzte Parameterkonfigurationen von verschiedenen ACO-Algorithmen

8.5 Ergebnisse der Evaluierungsläufe mit mehrkriteriellen Ameisenalgorithmen

8.6 Ergebnisse der Evaluierungsläufe mit und ohne Verwendung von Routing

8.7 Testergebnisse bei Verwendung verschiedener Update-Strategien

8.8 Testergebnisse bei Verwendung verschiedener Aggregationsmethoden

8.9 Approximation, Diversität und Größe der ermittelten Front im Vergleich bei Verwendung der Standard-Heuristik und der Look-Ahead-Heuristic

8.10 Evaluierung der Schwellwertübertretungen der Diversität bei Verwendung der Standard- Heuristik und der Look-Ahead-Heuristic

8.11 Testergebnisse für den Vergleich von LAH in der Best- und Worst-Case-Variante hinsicht- lich Distanz, Diversität und Frontgröße

8.12 Testergebnisse für den Vergleich von LAH in der Best- und Worst-Case-Variante hinsicht- lich der Diversität

8.13 Auswirkungen der Problemreduktion auf die Eingabelänge und Lösungsraumgröße . . .

8.14 Testergebnisse mit den Auswirkungen der Problemreduktion auf ACS

A.1 Übersicht über alle verwendeten Prozesspläne (Technologiegraphen)

A.2 Übersicht über alle verwendeten Problemgraphen

A.3 Parameter der verwendeten Konfigurationen (1)

A.4 Parameter der verwendeten Konfigurationen (2)

A.5 Parameter der verwendeten Konfigurationen (3)

B.1 Zielfunktionsbeiträge der Angebote des bikriteriellen Problems B001

Algorithmenverzeichnis

1 Automatisierte Generierung des Restriktionssystems eines Angebotsnetzes

2 Testalgorithmus zur Analyse der Präzision des Datentyps double

3 Dynamisches Programm zur Lösung rein konvergierender Parallel Path Probleme

4 Hilfsfunktionen für das dynamische Programm für rein konvergierende Probleme

5 Auflösung von Restriktion und restriktionsbehaftete Pfadkonstruktion

6 Dominanzvergleiche bei Divergenzen

7 Generierung von Lösungskombinationen bei Problemen mit Divergenzen

8 Algorithmenskelett der ACO-Metaheuristik

9 Generierung von Routingtabellen für das Forwarding von Ameisenagenten

10 Lösungskonstruktion der Ameisen unter Nutzung von Routing und Restriktionen

11 Generierung von Tabulisten für Knoten als Agentenrestriktionen

12 Erstellen von zulässigen Auswahlmengen auf Basis von Tabulisten

13 Dynamisches Programm zur Problemreduktion

14 Hilfsfunktionen zur Problemreduktion

15 Berechnung von Look-Ahead-Heuristic-Werten für das Parallel Path Problem

16 Bestimmung der Lösungsraumgröße

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

Verwendete Notationen

Abbildung in dieser Leseprobe nicht enthalten

Symbolverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

Einführung

In einer Umwelt, die von Vernetzung und Globalisierung geprägt ist, 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 einer so genannten Lieferkette (Supply Chain).¹

Die unternehmensübergreifende Steuerung und Optimierung des Wertschöpfungsprozesses stellt ein wesentliches Problem des Supply Chain Managements dar und besitzt zur Erzielung von Wettbewerbsvorteilen einer Lieferkette gegenüber Konkurrenten ein sehr hohes Potential.

Ein Forschungsschwerpunkt der Professur Produktionswirtschaft und Industriebetriebslehre sowie des Arbeitskreises Logistische Informationssysteme (LogIs) an der Technischen Universität Chemnitz sind hierarchielose, regionale Produktionsnetzwerke.² Das im Rahmen dieser Forschungsarbeit entstandene kompetenzzellenbasierte Extended Value Chain Management (EVCM)³ generiert - vereinfacht beschrieben - unternehmensübergreifende Angebotsnetze mit dem Ziel, eine den Präferenzen des Kunden des Unternehmensnetzwerkes entsprechende Kombination von Kompetenzzellen auszuwählen, die die Durchführung bestimmter Prozesselemente entlang der Wertschöpfung des für den Kunden herzustellenden Produktes übernehmen. Diese Auswahl bedarf einer übergreifenden Optimierung.⁴

1.1 Gegenstand der Arbeit

Gegenstand dieser Arbeit ist das im Extended Value Chain Management bestehende Problem der Op- timierung von Angebotsnetzen. Im Rahmen dieser Arbeit soll das bestehende Problem ausführlich be- schrieben und analysiert werden. Eine wesentliche Kernfrage stellt die Komplexität des Problems dar, welche sowohl in der uni- als auch in der multikriteriellen Variante betrachtet werden soll. Neben der Vorstellung des Problems sollen Ansätze auf Basis der dynamischen Programmierung und von Ant Colony Optimization erörtert werden, die das Problem exakt beziehungsweise näherungsweise lösen. Darauf aufbauend soll eine Hybridisierung der beiden Lösungsansätze angestrebt werden.

Neben der problemspezifischen Modellierung sollen die entwickelten Ansätze außerdem in Hinblick auf ihre Eignung im Rahmen der informationstechnischen Umsetzung des EVCM-Konzeptes untersucht werden. Hierzu sollen die entwickelten Algorithmen einer Evaluierung unterzogen werden, die sowohl die Lösungsgüte als auch den notwendigen Berechnungsaufwand einbezieht.

1.2 Dokumentstruktur

Das in dieser Arbeit untersuchte Optimierungsproblem von Angebotsnetzen im EVCM stellt ein kom- plexes graphentheoretisches Problem der kombinatorischen Optimierung dar. Zudem unterliegt das Problem einer Mehrfachzielsetzung. Aus diesem Grund soll nach der Erläuterung einiger theoretischer Grundlagen aus den Bereichen der Graphentheorie, der Komplexitätstheorie und der diskreten Op- timierung in Kapitel 2 die Thematik der mehrkriteriellen Optimierung in Kapitel 3 näher untersucht werden.

In Kapitel 4 findet anschließend eine Einführung in die Begriffswelt des Extended Value Chain Ma- nagements, gefolgt von der detaillierten Beschreibung des Optimierungsproblems in Angebotsnetzen statt. Anschließend wird das Problem formalisiert und bezüglich seiner Komplexität näher untersucht.

In den beiden darauf folgenden Kapiteln 5 und 6 werden mit der dynamischen Programmierung und Ant Colony Optimization ein exaktes Verfahren und ein heuristischer Lösungsansatz einerseits theoretisch erläutert und andererseits problemspezifisch modelliert.

Diese Lösungskonzepte werden in Kapitel 7 aufgegriffen und zu hybriden Ansätzen zur Optimierung von Angebotsnetzen weiterentwickelt.

Die vorgestellten Methoden sollen in Kapitel 8 abschließend evaluiert werden. Abbildung 1.1 zeigt die strukturellen Abhängigkeiten zwischen den einzelnen Kapiteln.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1.1: Strukturelle Abhängigkeit der Kapitel

Kapitel 2 Theoretische Grundlagen

Bevor die eigentliche Thematik dieser Arbeit erörtert werden kann, ist die Vorstellung einiger theoretischer Grundlagen aus den Fachbereichen der Graphentheorie, der diskreten Optimierung sowie der Komplexitätstheorie unabdingbar. Aufgrund dessen sollen die notwendigen Grundlagen in gebotener Kürze vorgestellt werden.

2.1 Grundlagen der Graphentheorie

In diesem Abschnitt werden ausgewählte grundlegende Bausteine aus der Graphentheorie erläutert, um begriffliche Verwendungen in späteren Teilen der Arbeit klarzustellen und abzugrenzen. In diesem Zusammenhang soll zunächst der Graph als theoretisches Konstrukt und anschließend einige Eigenschaften dieses Konstruktes erläutert werden.

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² 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.⁴

2.1.2 Wichtige Eigenschaften von Graphen

Neben der Definition sollen nachfolgend einige wesentliche Eigenschaften betrachtet werden, über welche Graphen verfügen können.

Die Eigenschaft der Vollständigkeit besitzt ein Graph genau dann, wenn je zwei Knoten vi, vj ∈ V des Graphen G mit [Abbildung in dieser Leseprobe nicht enthalten]durch eine Kante verbunden sind. Ein Graph wird hingegen genau dann als leer bezeichnet, wenn[Abbildung in dieser Leseprobe nicht enthalten] ist.⁵

Eine Kantenfolge in einem gerichteten Graphen ist eine Folge aus Kanten und Knoten, wobei einem Knoten eine Kante und einer Kante ein Knoten folgt. Sie beginnt und endet mit einem Knoten. Demnach kann eine Kantenfolge in der Form mit[Abbildung in dieser Leseprobe nicht enthalten] 0 < k ∈ N und i = 1,...,k dargestellt werden, wobei die Kante ei−1→i die Verbindung des Knotens vi−1 und vi repräsentiere, wobei vi der Endpunkt der Kante ist. Als Weg oder Pfad wird eine Kantenfolge genau dann bezeichnet, wenn alle Knoten v0, ..., vk und folglich auch alle Kanten der Folge voneinander verschieden sind. Wenn die Teilkantenfolge v1...vk−1 einen Weg repräsentiert und die Kantenfolge aufgrund von v0 = vk geschlossen ist, heißt sie Kreis oder Zyklus. Graphen, die keine Kreise besitzen, werden als zyklenfreie Graphen bezeichnet.⁶

Die Eigenschaft des Zusammenhangs besitzt ein nichtleerer ungerichteter Graph genau dann, wenn für je zwei Knoten vi, vj ∈ V des Graphen G ein Weg zwischen vi und vj existiert.⁷ Ein Graph heißt gewichtet oder bewertet, wenn Kosten- oder Nutzenwerte für die einzelnen Kanten oder Knoten des Graphen existieren, die durch Gewichte auf diesen Kanten oder Knoten repräsentiert werden.⁸

2.2 Grundlagen der Komplexitätstheorie

Während in der Praxis hauptsächlich Optimierungsprobleme gelöst werden müssen, betrachtet die Komplexitätstheorie Entscheidungsprobleme, die aber in enger Beziehung zu den zugehörigen Optimierungsproblemen stehen. Die Transformation eines Optimierungsproblems, das auf die Bestimmung der bestmöglichen Lösung eines Problems zielt, erfolgt auf Basis einer gegebenen Lösung dieses Problems und fragt nach der Eigenschaft der Lösung, optimal zu sein. Die Antwort eines Entscheidungsproblems kann dabei immer über einen binären Wert, das heißt mit ja beziehungsweise wahr und nein beziehungsweise falsch, formuliert werden.⁹

Ziel der Komplexitätstheorie ist es, für mit Computern berechenbare Probleme einen Minimalauf- wand beziehungsweise -ressourcenbedarf für deren Lösung zu bestimmen. Bei der Ermittlung dieses Minimalaufwands müssen sämtliche Algorithmen betrachtet werden, welche für die Lösung eines Pro- blems infrage kommen. Dies stellt aufgrund der Vielzahl der möglichen Algorithmen die wesentliche Schwierigkeit der Komplexitätstheorie dar.¹⁰ Ein für die Praxis relevanter Untersuchungsgegenstand der Komplexitätstheorie ist dabei die Grenze zwischen der effizienten Lösbarkeit und dem prohibi- tiv großen und unvertretbaren Rechenaufwand für die Lösung von Problemen.¹¹ Aus diesem Grund werden die Probleme, welche von der Komplexitätstheorie betrachtet werden, so genannten Komple- xitätsklassen zugeordnet, die eine Aussage über die zu erwartende Schwierigkeit bei der Lösung des Problems ermöglichen.

Um die Komplexitätsklassen näher erläutern zu können, werden zunächst die gängigen Komplexitätsmaße vorgestellt.

2.2.1 Komplexitätsmaße

Der Zeitbedarf, den ein Algorithmus zur Berechnung der Lösung eines Problems benötigt, hängt von den Eingabeparametern (Problem), dem verwendeten Rechner, der Programmiersprache und der Im- plementierung des Algorithmus ab. Der Einfluss aller Größen mit Ausnahme der Problem-Eingabepara- meter ist jedoch entweder stark begrenzt oder statisch.¹² Um ein vergleichbares und allgemeines Kom- plexitätsmaß zu gestalten, wird dieses in ausschließlicher Abhängigkeit vom verwendeten Algorithmus und den Eingabeparametern definiert. Als Maß der Komplexität wird dabei die Anzahl der Operatio- nen oder die Anzahl der Takte beziehungsweise Schritte betrachtet, die ein Algorithmus benötigt, um das Entscheidungsproblem entweder mit positiver oder negativer Antwort zu lösen.¹³

Für ein Problem können in diesem Zusammenhang mehrere Komplexitätsmaße angegeben werden. Zunächst kann der maximale Aufwand bestimmt werden, welchen ein Algorithmus zur Lösung des Problems benötigt. Folglich können aus diesem Komplexitätsmaß Aussagen über Algorithmen und de- ren Effizienz abgeleitet werden. Dieses Maß wird anhand der O-Notation nach Gleichung 2.1 definiert.¹⁴

Abbildung in dieser Leseprobe nicht enthalten

Durch O wird laut Definition die Menge aller Funktionen t beschrieben, für welche ab einem Wert n0 kein Funktionswert von t (n) über einem Wert c·f (n) liegt, wobei c einen existierenden konstanten Wert darstellt. Der Parameter n beschreibt die Größe des Problems hinsichtlich der Eingabeparameter, wie beispielsweise die Anzahl von Knoten und Kanten in graphentheoretischen Problemen.¹⁵ Die Menge O beschränkt somit die Komplexität mit f (n) nach oben. Ein Algorithmus, welcher durch die Komplexität ( O n² ) beschränkt wird, benötigt somit maximal n² Schritte beziehungsweise Operationen, bis er das Problem der Eingabelänge n beantworten kann.

Entgegen dem maximalen Aufwand kann auch ein minimaler Aufwand betrachtet werden, den ein beliebiger Algorithmus, der das Problem löst, mindestens benötigt, um eine Entscheidung zu treffen. Dieses Komplexitätsmaß erlaubt demnach Aussagen über die Schwierigkeit des Problems, gestaltet sich jedoch als sehr schwierig hinsichtlich der Bestimmung, da sämtliche Algorithmen betrachtet werden müssen, die das Problem lösen. Somit kann im engeren Sinne ausschließlich eine Aussage über alle bekannten Algorithmen, die das Problem lösen, abgeleitet werden. Dieses Maß wird anhand der Ω- Notation nach Gleichung 2.2 definiert.¹⁶

Abbildung in dieser Leseprobe nicht enthalten

Dieses Maß beschreibt somit mit der Menge Ω auf Basis der Funktion f (n) den minimalen Aufwand beziehungsweise die minimale Anzahl von Schritten, die ein Algorithmus bei einer Eingabelänge von n zur Problemlösung benötigt. Bei einer Komplexität von Ω n² ) existiert kein bekannter Algorithmus, welcher bei deterministischer Vorgehensweise in weniger als n² Schritten mit Sicherheit ein Problem der Eingabelänge n entscheiden kann.

2.2.2 Komplexitätsklassen P und NP

Die Komplexitätstheorie hat Klassenkonstrukte entwickelt, welche Probleme mit ähnlichen Eigenschaf- ten bezüglich der Schwierigkeit der Problemlösung zusammenfassen. Relevant für die Praxis sind da- bei insbesondere die Komplexitätsklassen P und NP. Die Komplexitätsklasse P umfasst alle Probleme, für die ein bekannter deterministischer Algorithmus existiert, der nach endlich vielen Operationen beziehungsweise Schritten eine Lösung für das Problem liefert, wobei die Anzahl der Schritte durch ein Polynom[Abbildung in dieser Leseprobe nicht enthalten]der nachfolgenden Form begrenzt ist.¹⁷

Abbildung in dieser Leseprobe nicht enthalten

Da die Komplexität des Problems somit polynomiell in Abhängigkeit von der Problemgröße beschränkt werden kann, werden Probleme der Klasse P als effizient lösbar betrachtet.¹⁸

Die Klasse NP kann ähnlich definiert werden und umfasst alle Probleme, für welche ein nichtdeter- ministischer Algorithmus existiert, welcher eine polynomiell beschränkte Laufzeit besitzt. Je nach Sicht- weise ist ein nichtdeterministischer Algorithmus entweder im Besitz der Fähigkeit, die richtigen Berech- nungsschritte zu erraten oder sämtliche bis zu 2p(n) Rechenwege in maximal p(n) atomaren Schritten zu enumerieren. Aufgrund dessen ist der nichtdeterministische Algorithmus praktisch nicht realisierbar, sondern ausschließlich ein abstraktes Konstrukt der theoretischen Informatik.¹⁹ Für die Komplexitäts- klassen P und NP gilt folglich die Teilmengenbeziehung P ⊆ NP, wobei die Frage nach der Echtheit der Teilmengenbeziehung ein ungelöstes Problem der Mathematik darstellt.²⁰ Probleme, die in der Klasse NP liegen und für welche nicht bekannt ist, ob sie gleichzeitig in P liegen, werden als nicht effizient lösbar eingestuft, da bisher kein Algorithmus gefunden wurde, der das Problem sicher in polynomieller Zeit lösen kann. Für diese Probleme sind bisher nur Algorithmen bekannt, die eine exponentielle oder höhere Anzahl von Operationen ausführen müssen, um das Problem zu lösen.²¹

2.2.3 Problemrelationen und polynomielle Reduktion

Unter der Annahme, C sei eine Komplexitätsklasse, heißt ein Problem A genau dann C-schwierig, wenn A mindestens genauso schwierig zu lösen ist, wie jedes andere Problem B ∈ C. Die Komplexitätsklasse C wird dabei durch die schwierigsten Probleme in C repräsentiert. A heißt C-vollständig, wenn A einerseits C-schwierig ist und andererseits zur Komplexitätsklasse C gehört. Kann für ein Problem A nachgewiesen werden, dass es mindestens genauso schwierig wie ein C-vollständiges Problem ist, impliziert dies, dass A die Eigenschaft der C-Schwierigkeit besitzt. Wird zusätzlich nachgewiesen, dass A ∈ C gilt, folgt daraus, dass A die Eigenschaft der C-Vollständigkeit besitzt.²²

Der Nachweis, dass ein Problem A mindestens genauso schwierig wie ein Problem B ist, erfolgt im Allgemeinen über die polynomielle Reduktion. Ein Problem B wird auf ein Problem A reduziert, indem die Eingaben von B mit Hilfe einer Funktion δ in Eingaben von A transformiert werden. Alle Problem- instanzen von B können demnach durch diese Transformation als Probleminstanzen von A abgebildet werden. Stellt δ eine polynomiell berechenbare Funktion dar, ist B polynomiell auf A reduzierbar und folglich A mindestens genauso schwierig wie B.²³ Daraus folgt, dass ein Problem NP-vollständig ist, wenn es auf ein anderes NP-vollständiges Problem reduziert werden kann und Element der Klasse NP ist.

Den ersten Beweis zur NP-Vollständigkeit eines Problems erbrachte der Begründer der NP-Vollstän- digkeitstheorie STEPHEN COOK im Jahre 1971 für das Erfüllbarkeitsproblem (SAT).²⁴ Der Nachweis der NP-Vollständigkeit aller übrigen Probleme kann, vorausgesetzt das Problem gehört zur Klasse NP, über die polynomielle Reduktion auf SAT oder ein anderes NP-vollständiges Problem erbracht werden.²⁵

2.3 Diskrete und kombinatorische Optimierung

Gegenstand dieser Arbeit ist die Analyse und die exakte sowie näherungsweise Lösung eines Problems aus der Klasse der kombinatorischen Optimierung. Aus diesem Grund und zur Begriffsabgrenzung soll diese Problemklasse im Folgenden kurz vorgestellt werden.

2.3.1 Problemdefinition und Eigenschaften

Bei näherer Betrachtung der Strukturen von Entscheidungsmodellen stellt die diskrete Optimierung neben der stetigen Optimierung, in der sämtliche Entscheidungsvariablen durch reelle Zahlen repräsentiert werden, und der dynamischen Optimierung, in welcher Zeitfunktionen oder Folgen von Entscheidungen betrachtet werden, einen dritten wesentlichen Typ von Optimierungsmodellen dar.²⁶

Diskrete Optimierungsmodelle zeichnen sich durch die Eigenschaft aus, entweder über eine end- lich große oder zumindest abzählbar unendlich große Entscheidungsmenge zulässiger Alternativen zu verfügen.²⁷

Aufgrund dessen besteht die Möglichkeit, jeder Entscheidungsalternative eine natürliche Zahl zuzuordnen, wobei die resultierende Entscheidungsmenge U zumeist als Menge von binären Vektoren U ⊆ {0,1}n oder als Menge von Vektoren aus natürlichen Zahlen U ⊆ Nn gegeben ist. Daher werden diskrete Optimierungsmodelle in der Literatur auch oft als ganzzahlige Modelle bezeichnet. Ein weiteres Synonym stellt der Begriff der kombinatorischen Optimierung dar, welcher darauf zurückzuführen ist, dass die Ableitung der Größe der Lösungsmenge häufig durch einfache kombinatorische Überlegungen aus den Eingabeparametern des Problems möglich ist. Alternativ kann die Menge U jedoch auch durch ein graphentheoretisches Problem definiert werden.²⁸

Unter der Annahme, U sei eine endliche oder abzählbar unendlich große Menge, kann ein diskretes Optimierungsproblem durch eine Zielfunktion[Abbildung in dieser Leseprobe nicht enthalten]wie nach Gleichung 2.3 definiert werden.²⁹

Abbildung in dieser Leseprobe nicht enthalten

Da für viele ganzzahlige beziehungsweise diskrete Optimierungsprobleme exakte Methoden aufgrund der Komplexität des Problems einen zu hohen Rechenaufwand benötigen, werden oft Heuristiken zur Approximation der Lösung eingesetzt.³⁰

2.3.2 Ausgewählte Optimierungsprobleme

Nachfolgend werden einige ausgewählte und für diese Arbeit relevante kombinatorische Probleme vorgestellt. Insbesondere das Rucksackproblem und das Travelling Salesman Problem sowie das KürzesteWege-Problem sind bekannte Vertreter der diskreten Optimierung.

2.3.2.1 Das Rucksackproblem

Einem Reisenden stehe ein Rucksack zur Verfügung, welcher ein Maximalgewicht k aufnehmen kann. Des Weiteren existieren n verschiedene Gegenstände j ∈ {1 . . . n}, welchen jeweils ein Wert pj und ein Gewicht wj zugeordnet ist. Das daraus resultierende Optimierungsproblem ergibt sich aus der Frage, welche Gegenstände in den Rucksack eingepackt werden sollen, um den Wert des Inhaltes zu maximieren, ohne jedoch dabei die zulässige Gewichtsschranke k zu überschreiten.³¹ Formal kann dieses Problem wie folgt definiert werden.

Abbildung in dieser Leseprobe nicht enthalten

Hierbei gilt als Nebenbedingung die folgende Kapazitätsrestriktion

Abbildung in dieser Leseprobe nicht enthalten

mit[Abbildung in dieser Leseprobe nicht enthalten] Die Entscheidungsvariable uj nimmt den Wert 1 an, falls der Ge- genstand j eingepackt werden soll beziehungsweise 0, falls der Gegenstand j nicht eingepackt werden soll.

In [Kel04] wird durch die Reduktion des NP-vollständigen Subset Sum Problems auf das Rucksack- problem (auch knapsack problem) gezeigt, dass auch dieses zur Klasse der NP-vollständigen Probleme gehört.³²

Equality Knapsack ist eine Variante des Grundproblems, bei welchem anstatt der normalen Kapazitätsrestriktion, die forderte, dass das Gewicht nicht größer als die vorhandene Kapazität sein darf, die genaue Gleichheit zwischen Kapazität und des Gesamtgewichts aller eingepackten Gegenstände bedingt.³³ Formal kann diese Restriktion demnach in der Form

Abbildung in dieser Leseprobe nicht enthalten

definiert werden. Diese Variante ist aufgrund der NP-Vollständigkeit des Subset Sum Problems ebenso wie die Basisvariante NP-vollständig.³⁴

2.3.2.2 Travelling Salesman Problem

Das NP-vollständige Rundreiseproblem stellt einen Reisenden oder Verkäufer vor die Aufgabe, eine kürzeste Rundreise zwischen n Städten zu finden, ohne dabei eine Stadt mit Ausnahme jener, in welcher die Rundreise beginnt, mehr als ein Mal zu besuchen.³⁵ Formal kann das Problem durch einen ungerichteten, vollständigen und gewichteten Graphen beschrieben werden, in welchem ein so genannter Hamiltonkreis³⁶ kürzester Länge bezüglich der Kantengewichte gesucht wird.³⁷

Zur formalen Beschreibung des Problems wird die Entscheidungsmatrix U der Größe n × n mit den Elementen[Abbildung in dieser Leseprobe nicht enthalten] mit i, j = 1, ..., n definiert, wobei U eine Rundreise und somit eine Lösung des Problems repräsentiert. Die Elemente[Abbildung in dieser Leseprobe nicht enthalten]ergeben sich nach Gleichung 2.7.³⁸

Abbildung in dieser Leseprobe nicht enthalten

Um sicherzustellen, dass U einen Hamiltonkreis beschreibt, gelten die folgenden Gleichungen 2.8 und 2.9 als durch die Entscheidungsmatrix U zu erfüllende Restriktionen.

Abbildung in dieser Leseprobe nicht enthalten

Unter der Annahme, dass die Kantengewichte durch die Variable cij beschrieben werden, kann auf Basis der dargelegten Problemdefinition das Ziel der Optimierung wie folgt formuliert werden.

Abbildung in dieser Leseprobe nicht enthalten

Das Travelling Salesman Problem ist eines der schwierigsten algorithmischen Probleme. Die NPVollständigkeit dieses Problems kann durch die Technik der Reduktion auf andere NP-vollständige Probleme bewiesen werden.³⁹

2.3.2.3 Kürzeste Wege durch Graphen

Eng verwandt mit dem Rundreiseproblem ist das Kürzeste-Wege-Problem. Entgegen dem Rundreiseproblem wird jedoch nicht nach einer Rundreise durch alle Städte (Knoten) eines Graphen, sondern nach dem kürzesten Weg zwischen einem als Startpunkt und einem als Endpunkt definierten Knoten des Graphen gesucht.⁴⁰

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.1: Beispielhaftes Kürzeste-Wege-Problem

Die Abbildung zeigt einen unvollständigen, ungerichteten, gewichteten Graph, in welchem der kürzeste Weg zwischen den Knoten v1 und v2 bestimmt und markiert wurde.

Dieses Problem ist jedoch, anders als TSP, effizient lösbar. DIJKSTRA entwickelte einen Algorithmus, welcher das Problem mit einem Komplexitätsbedarf von O n² ) löst.⁴¹ Der Algorithmus von FLOYD und WARSHALL bestimmt sogar sämtliche kürzeste Wege zwischen allen Knoten mit einer Komplexität von O n³ ).⁴² Das Problem ist demnach Element der Komplexitätsklasse P.

Kapitel 3 Optimierung bei Mehrfachzielsetzung

Mehrkriterielle Probleme beschreiben die Realität meist deutlich besser als Probleme, welche das Optimierungsziel ausschließlich durch eine zu minimierende Kosten- oder zu maximierende Gewinnfunktion definieren. In so genannten real world problems müssen sehr oft Entscheidungen unter teilweise sehr vielen Gesichtspunkten, mit Hilfe so genannter Kriterienbündel, getroffen werden. Neben quantifizierbaren Größen wie Kosten, Gewinn oder Kapitalbindung sind häufig auch Ziele von Bedeutung, die nur qualitativ artikulierbar sind. So sind beispielsweise soziale oder ökologische Aspekte nicht zu vernachlässigen.¹ Zahlreiche Anwendungen zur Behandlung spezieller mehrkriterieller Probleme zeigen die Wichtigkeit dieser Thematik in der Praxis auf.²

Ein gutes Beispiel für mehrkriterielle Probleme (mit konfliktären Zielen) stellt die Reihenfolge- beziehungsweise Ablaufplanung in der betrieblichen Produktion dar, in welcher aufgrund von Bewertungsproblemen eine Reduktion der Kosten- auf Zeitziele stattfindet. Ziele in der Reihenfolgeplanung sind neben anderen die gleichzeitige Maximierung der Kapazitätsauslastung und die Minimierung der Durchlaufzeit.³ Weitere Ziele können beispielsweise die Vermeidung von Überstunden oder die Minimierung von Terminüberschreitungskosten sein.

Da auch das im Rahmen dieser Arbeit betrachtete Optimierungsproblem zur Auswahl von Kompetenzzellenangeboten aus einem Angebotsnetz einer Mehrfachzielsetzung unterliegt, soll nachfolgend eine Einführung in die multikriterielle Entscheidung und Optimierung stattfinden.⁴

3.1 Mehrkriterielle Probleme

Die Definition aus Abschnitt 2.3 auf Seite 7 betrachtete ausschließlich unikriterielle Probleme (SOP⁵ ). Nachfolgend soll zunächst eine formale Definition von Problemen mit mehrfacher Zielsetzung erfol- gen. Anschließend soll auf mögliche Abhängigkeiten und Beziehungen zwischen den Zielen näher ein- gegangen werden.

3.1.1 Problemstellung

Ein mehrkriterielles Optimierungsproblem (MOP⁶ ) kann als Erweiterung eines unikriteriellen Optimie- rungsproblems definiert werden. Während in einem einkriteriellen Optimierungsproblem stets genau eine zu minimierende oder zu maximierende Zielfunktion das Ziel des Problems beschreibt, existieren im multikriteriellen Fall mehrere solcher Funktionen, welche jeweils ein separates Ziel repräsentieren. Formal beschrieben sei M ein mehrkriterielles Optimierungsproblem mit Z verschiedenen Zielkri-terien z ∈ {1, ..., Z} und den zugehörigen Zielfunktionen fz . Der Lösungsraum eines Problems M sei durch das Symbol Π beschrieben. Die Zielfunktionen können formal wie folgt definiert werden.

Abbildung in dieser Leseprobe nicht enthalten

Für [Abbildung in dieser Leseprobe nicht enthalten]repräsentiere [Abbildung in dieser Leseprobe nicht enthalten] den Zielfunktionswert des z-ten Optimierungskriteriums der Lösung [Abbildung in dieser Leseprobe nicht enthalten]In diesem Zusammenhang sei darauf hingewiesen, dass viele Verfahren fordern, dass alle Zielkrite- rien entweder zu minimieren oder zu maximieren sind. Handelt es sich um ein Optimierungsproblem, welches sowohl zu minimierende Zielfunktionen von Zielkriterien als auch zu maximierende enthält, so müssen einige Zielfunktionen geeignet invertiert werden. Das Problem kann in der Form

Abbildung in dieser Leseprobe nicht enthalten

abgebildet werden. Dabei wird π ∈ Π als Entscheidungsvektor oder Lösung des Problems und Π als Entscheidungs- oder Lösungsraum bezeichnet. Der Vektor [Abbildung in dieser Leseprobe nicht enthalten]wird Zielvektor und Y Zielraum genannt. Die Nebenbedingungen ε bestimmen die Teilmenge des Lösungsraums, die zulässig respektive gültig ist.⁷ Diese Abbildung entspricht der Form eines Vektoroptimierungsproblems.⁸

3.1.2 Zielbeziehungen

Existieren für ein Optimierungsproblem mehrere Ziele, so können diese in unabhängiger (auch neutraler), komplementärer oder konkurrierender (auch konträrer) Beziehung zueinander stehen. Diese Zielbeziehungen sollen nachfolgend näher betrachtet werden.

Stehen zwei Ziele in komplementärer Beziehung, so bewirkt eine Verbesserung des Zielfunktionswertes einer zugehörigen Zielfunktion ebenso eine Verbesserung des Zielfunktionswertes der Zielfunktion des anderen Ziels. Analog würde eine Verschlechterung eines Zielfunktionswertes einer Funktion genauso zu einer Verschlechterung der anderen Zielfunktion führen. Ist die Beziehung zweier Ziele konkurrierend, stehen diese Ziele im Konflikt. Dies bedeutet, dass eine Verbesserung des Zielerreichungsgrades von einem der Ziele zu einer Verschlechterung der Zielerreichung des anderen Ziels führen würde. In einer neutralen, auch als indifferent bezeichneten Beziehung, kann keine Konkurrenz oder Komplementarität zwischen den Zielen nachgewiesen werden.⁹

Aufgrund dieser Zusammenhänge können Schlussfolgerungen über den Lösungsraum des zugrun- de liegenden Optimierungsproblems gezogen werden. Stehen alle Ziele eines Optimierungsproblems in komplementärer Beziehung, so existiert mindestens genau eine Lösung, welche für jedes Ziel den optimalen Zielfunktionswert besitzt. Eine Lösung, die diese Eigenschaft aufweist, wird als perfekte Lö- sung bezeichnet.¹⁰ Besteht zwischen allen Zielen eine symmetrische Komplementarität aller Ziele, kann ein multikriterielles Optimierungsproblem auf ein einkriterielles Optimierungsproblem reduziert wer- den.¹¹ Stehen hingegen mindestens zwei Ziele in Konflikt, enthält Π keine Lösung π, die für alle Ziele des Optimierungsproblems ein Optimum darstellt.¹² In diesem Falle kann, ebenso wie bei neutraler Zielbeziehung, eine Reduktion eines MOP auf ein SOP nicht ohne weiteres durchgeführt werden. Aus diesem Grund wird nachfolgend der Begriff der Optimalität bei mehrfacher Zielsetzung geklärt.

3.2 Optimalität bei mehrfacher Zielsetzung

Das Paretokriterium geht auf den Ökonomen VILFREDO PARETO (1848-1923) zurück und beschreibt ein volkswirtschaftliches Konzept, das die Effizienz einer Allokation von Gütern in einer Gesellschaft definiert. Eine Allokation gilt genau dann als effizient, wenn es durch eine Umverteilung von Gütern auf Konsumenten nicht möglich ist, ein beliebiges Wirtschaftssubjekt besser zu stellen, ohne gleichzei- tig mindestens ein anderes Wirtschaftssubjekt schlechter zu stellen. Ein solcher Zustand wird als effi- ziente beziehungsweise paretooptimale Allokation bezeichnet.¹³ Ausgehend von einer Gesamtmenge an Gütern können sehr viele paretooptimale Zustände existieren, welche durch eine unterschiedliche Verteilung der Güter auf einzelne Wirtschaftssubjekte erreichbar sind. Mit dem Paretokriterium kann demnach keine Aussage über Fairness oder Gerechtigkeit bei der Verteilung von Gütern abgeleitet wer- den. Welcher spezielle paretooptimale Zustand hinsichtlich einer Allokation anstrebenswert ist, obliegt den wirtschafts- und sozialpolitischen Intentionen der zugrunde liegenden Gesellschaft.¹⁴

Dieser volkswirtschaftliche Ansatz ist auf die Lösung multikriterieller Optimierungsprobleme übertragbar, wenn die Wirtschaftssubjekte den Zielkriterien und die zu verteilenden Güter den Zielerreichungsgraden dieser Zielkriterien entsprechen. In diesem Zusammenhang sollen zunächst die Begriffe der starken und schwachen Dominanz von Lösungen definiert werden, um das Konzept der Paretooptimalität in multikriteriellen Optimierungsproblemen zu konkretisieren.

3.2.1 Paretooptimalität

Um eine Beziehung zwischen Lösungen eines Optimierungsproblems darzustellen, werden die Begriffe der starken und schwachen Dominanz verwendet, welche im Folgenden definiert werden. Seien π1 und π2 gültige Lösungen des bereits in Abschnitt 3.1.1 definierten und zu minimierenden Optimierungsproblems M . Gilt der nachfolgende Zusammenhang zwischen den Zielfunktionswerten der Lösungen π1 und π2, so wird die Lösung π2 von der Lösung π1 stark dominiert.

Abbildung in dieser Leseprobe nicht enthalten

Dies bedeutet, dass die Kosten- beziehungsweise Zielfunktionswerte der Lösung π1 für jedes Zielkriterium kleiner (besser) sind als die der Lösung π2. Eine starke Dominanz der Lösung π1 gegenüber π2 sei durch die Schreibweise [Abbildung in dieser Leseprobe nicht enthalten]gekennzeichnet. Handelt es sich hingegen nur um eine schwache Dominanz der Lösung π1 gegenüber π2 müssen nur die Bedingungen

Abbildung in dieser Leseprobe nicht enthalten

(3.3)

Abbildung in dieser Leseprobe nicht enthalten

erfüllt sein, was bedeutet, dass sämtliche Zielfunktionswerte der Zielkriterien der Lösung π1 nicht kleiner (schlechter) als die der Lösung π2 sein dürfen, jedoch mindestens ein Zielfunktionswert im Vergleich zu π2 tatsächlich kleiner (besser) sein muss.¹⁵ Die schwache Dominanz einer Lösung π1 gegenüber π2 sei durch die Schreibweise [Abbildung in dieser Leseprobe nicht enthalten] dargestellt. Durch die strengere Restriktion der starken Dominanz ergibt es sich, dass jede starke Dominanz auch eine schwache Dominanz ist.

Formal kann die Paretooptimalität einer Lösung π∗ ∈ Π durch die Eigenschaft definiert werden, dass keine Lösung π ∈ Π mit [Abbildung in dieser Leseprobe nicht enthalten]und [Abbildung in dieser Leseprobe nicht enthalten]existiert. Wird demnach eine Lösung [Abbildung in dieser Leseprobe nicht enthalten]von keiner anderen Lösung des Optimierungsproblems schwach oder stark dominiert, heißt diese Lösung paretooptimal.¹⁶

Wird ein Algorithmus zur Lösung des Optimierungsproblems in der Form modelliert, dass durch ihn alle Lösungen ausgeschlossen werden, die durch eine andere Lösung in Π mindestens schwach dominiert werden, ermittelt dieser sämtliche paretooptimalen Lösungen. Die Menge aller paretooptimalen Lösungen [Abbildung in dieser Leseprobe nicht enthalten] konstruiert im Zielraum des Problems die so genannte Paretofront [Abbildung in dieser Leseprobe nicht enthalten].¹⁷

3.2.2 Eigenschaften der paretooptimalen Lösungsmenge

Aus den Definitionen der Dominanz und der Eigenschaft der Paretooptimalität kann abgeleitet werden, dass, falls die Menge aller paretooptimalen Lösungen eine Lösung enthält, welche über die Eigenschaft der schwachen oder starken Dominanz gegenüber allen übrigen Lösungen verfügt, diese die einzige Lösung in dieser Menge ist, da sie von keiner anderen Lösung dominiert werden kann. Gemäß der Definition ist diese Lösung perfekt. Perfekte Lösungen sind somit ein Spezialfall der Paretooptimalität.

Unabhängig von den Zielbeziehungen können folgende Aussagen über die paretooptimale Lösungs- menge eines multikriteriellen Optimierungsproblems getroffen werden. Einerseits kann die Menge der paretooptimalen Lösungen genau dann nicht leer sein, wenn der Lösungsraum des Optimierungspro- blems keine leere Menge bildet. Andererseits ergibt sich, dass die Menge der paretooptimalen Lösungen [Abbildung in dieser Leseprobe nicht enthalten] gleich der Menge aller Lösungen Π ist, falls keine Lösung im Lösungsraum existiert, welche eine an- dere Lösung zumindest schwach dominiert. Somit gilt die nachfolgende Teilmengenbeziehung.

Abbildung in dieser Leseprobe nicht enthalten

Die Anzahl der paretooptimalen Lösungen kann somit nicht stärker als durch den Lösungsraum Π begrenzt werden. Insbesondere bei Problemen, deren Lösungsraum exponentiell im Vergleich zur Eingabegröße einer Probleminstanz wächst, kann die Enumeration aller Lösungen der Front ein nicht zu vernachlässigendes Speicherproblem darstellen.

3.2.3 Idealpunkte und Nadir-Punkt der Front

Aufgrund der Relevanz in späteren Abschnitten und Kapiteln soll nachfolgend auf spezielle Punkte respektive Vektoren im Zielraum, welche diesen oder die Paretofront beschränken, näher eingegangen werden.¹⁸

Der positive Idealpunkt, auch ideal point oder utopia point genannt, stellt einen Vektor y+ im Z- dimensionalen Raum dar, dessen Elemente y+z denjeweiligenoptimalenZielerreichungsgradeinesZielkriteriums z beinhalten. Der Wert y+z stelltdenOptimalwertdar,welcherdurcheineeinkriterielleOptimierung für das Kriterium z ermittelt werden würde. Unter der Annahme, dass alle Zielfunktionen zu minimieren sind, kann dieser Punkt y+ wie folgt formal definiert werden.¹⁹

Abbildung in dieser Leseprobe nicht enthalten

Der positive Idealpunkt existiert als Zielfunktionsvektor nur dann als zulässige Lösung, wenn ein Pro- blem eine perfekte Lösung besitzt und ist bei allen übrigen Problemen nicht erreichbar.²⁰ Der negative Idealpunkt, auch negative ideal point oder anti-ideal point genannt, entspricht dem ge- nauen Gegenteil und beschreibt einen Vektor [Abbildung in dieser Leseprobe nicht enthalten], dessen Elemente [Abbildung in dieser Leseprobe nicht enthalten] denjeweiligenpessimalenZieler- reichungsgrad für das Kriterium [Abbildung in dieser Leseprobe nicht enthalten] beinhalten. Dieser Wert könnte durch eine einkriterielle Optimierung für das Kriterium z ermittelt werden, wenn das Ziel der Optimierung umgekehrt wird.²¹ Formal ist der Punkt y− wie folgt definiert.

Abbildung in dieser Leseprobe nicht enthalten

Der negative Idealpunkt beschreibt somit das inverse Konzept des positiven Idealpunktes und be- schränkt den Zielraum als untere Grenze. Es kann keine zulässige Lösung geben, welche von y− do- miniert wird.²²

Zusätzlich ergibt sich aus dem positiven Idealpunkt der so genannte nadir point (dt. Fußpunkt). Dieser Nadir-Punkt [Abbildung in dieser Leseprobe nicht enthalten]ergibt sich aufgrund des Dominanzkonzeptes nach dem Paretokriterium und stellt eine untere Beschränkung der Paretofront dar. Formal ergibt sich der Punkt nach folgender Gleichung, wobei [Abbildung in dieser Leseprobe nicht enthalten] die Menge der paretooptimalen Lösungen darstelle.

Abbildung in dieser Leseprobe nicht enthalten

Der Nadir-Punkt beschreibt als Fußpunkt der Paretofront deren untere Begrenzung, wobei definitionsgemäß keine paretooptimale Lösung π∗ ∈ Π existieren kann, für welche[Abbildung in dieser Leseprobe nicht enthalten] gilt.²³

3.3 Multikriterielle kombinatorische Optimierung

Da ausschließlich kombinatorische Optimierungsprobleme Gegenstand dieser Arbeit sind, soll die mul- tikriterielle Optimierung im Folgenden aus deren Perspektive näher betrachtet werden. In diesem Zu- sammenhang werden zunächst verschiedene Problemlösungsansätze und -klassen der Entscheidungs- theorie vorgestellt und eine mögliche Einordnung kombinatorischer Probleme vorgenommen. Anschlie- ßend werden grundsätzliche Vorgehensweisen für die mehrkriterielle kombinatorische Optimierung er- örtert.

3.3.1 Klassifizierung entscheidungstheoretischer Ansätze

Die Reihe der multikriteriellen Entscheidungsverfahren ist sehr groß, weshalb zunächst eine Klassifizierung der verfügbaren Methoden erfolgen soll. Da sich in der Literatur keine einheitliche Klassifizierung findet, sollen verschiedene Klassifizierungsmodelle nachvollzogen werden.

3.3.1.1 Multiattributive und multiobjektive Verfahren

Klassische multikriterielle Entscheidungsmodelle können unter dem Begriff Multi Criteria Decision Making zusammengefasst werden. Diese werden nach HWANG und YOON in Multi Objective Decision Making (MODM) und Multi Attribute Decision Making (MADM) unterschieden.²⁴ Wesentliche Unterschiede zwischen den Klassen finden sich einerseits in der Problemstruktur und andererseits in der Art der Problemlösung. WEBER beschreibt den Unterschied zwischen diesen Gruppen wie folgt.

»Multiobjektive Methoden dienen zur Erarbeitung von Lösungen für Probleme mit mehreren, teilweise konfliktären, jedenfalls aber quantifizierbaren Zielen, die unter Einhaltung vorgegebener Restriktionen bestmöglich zu erreichen sind. [...] Die multiattributiven Methoden (multiattributive methods) sind dagegen primär auf eine im voraus begrenzt festgelegte Zahl von Attributen und deren vergleichsweise Gewichtung im Hinblick auf eine - eventuell nur implizit erkennbare - Zielvorgabe ausgerichtet.«²⁵

Methoden der Gruppe MADM fordern demnach die explizite Vorgabe einer endlichen Alternativen- menge, welche in den meisten Fällen sehr klein ist. Eine Besonderheit dieser Methoden ergibt sich auf- grund der Eigenschaft, dass eine Ziel- beziehungsweise Attributerfüllung auf einem ordinalen Skalenni- veau zumeist ausreichend ist. Die Problemlösung durch eine MADM-Methode besteht folglich aus der Auswahl einer Alternative.²⁶ Hauptvertreter dieser Gruppe stellen Verfahren wie die Nutzwertanalyse, AHP und die Methode der gewichteten Summierung dar.²⁷ Für MODM-Methoden ist die implizite Vor- gabe der Alternativenmengen durch ein mathematisches Modell hinreichend. Die Alternativenmenge ist in der Regel unendlich groß, wobei die Zielerfüllungsgrade der Alternativen über quantifizierba- re Zielfunktionen beschrieben werden. Der Lösungsraum ist stetig und die Problemlösung durch ein zur Gruppe gehöriges Verfahren erfolgt über die Berechnung einer Alternative.²⁸ Hauptvertreter dieser Klasse sind abstandsorientierte Verfahren wie das Goal Programming und das Compromise Program- ming.²⁹

In Abbildung 3.1³⁰ wird ein Überblick über diese beiden Schulen von Entscheidungsmodellen anhand einer Gegenüberstellung wesentlicher Unterschiede dargestellt. In diesem Zusammenhang sei erwähnt, dass fast alle Verfahren der Gruppe MODM - insbesondere abstandsorientierte Verfahren - auch in Verbindung mit diskreten Lösungsräumen einsetzbar sind. Beispiele hierfür sind das Goal beziehungsweise Compromise Programming oder das TOPSIS-Verfahren.³¹ Es ist des Weiteren bei Verfahren der Klasse MADM möglich, diese mit quantifizierbaren Zielerfüllungen zu nutzen.

3.3.1.2 Einordnung der kombinatorischen Optimierung

Nachfolgend soll, soweit dies möglich ist, eine Zuordnung der kombinatorischen Optimierung zu den bereits im vorigen Abschnitt vorgestellten Modellklassen MODM und MADM erfolgen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.1: Vergleich von MODM und MADM sowie der kombinatorischen Optimierung

Die Abbildung zeigt eine vergleichende Gegenüberstellung der Eigenschaften von MODM und MADM als MCDM-Methoden. Des Weiteren wird eine Einordnung der mehrkriteriellen kombinatorischen Optimierung bezüglich dieser Eigenschaften vorgenommen.

Im Rahmen dieser Arbeit wird davon ausgegangen, dass die Zielerfüllung bei kombinatorischen Problemen auf einem hohen Skalenniveau quantifizierbar ist. Für jedes Ziel können demnach anhand von Vergleichen der Zielfunktionswerte die Verhältnisse zwischen den Zielerreichungsgraden mehrerer Lösungen dargestellt werden.

Die prinzipielle, praktisch allerdings kaum umsetzbare Möglichkeit, eine vollständige Enumeration für ein diskretes Problem durchzuführen, führt einerseits zu der Eigenschaft des Lösungsraums, dass nur eine endliche Anzahl von Alternativen existiert, verbietet jedoch andererseits hinsichtlich der Art der Alternativenvorgabe eine Einordnung in die Gruppe der multiattributiven Methoden, da prohibitiv viele Alternativen existieren können. Daher sollte eine Einordnung bei der nur impliziten Vorgabe der Alternativen erfolgen, welche aus der Definition des Problems und den konkreten Informationen der Probleminstanz folgt. Folglich ist nicht die Auswahl, sondern die Berechnung beziehungsweise Suche einer Alternative Ziel des Verfahrens. Da kein direkter Vergleich aller Alternativen mit dem Ziel, eine dieser Alternativen auszuwählen, vorgenommen werden kann, verbietet sich damit die Anwendung von MADM-Methoden. Folglich erscheint eine Zuordnung zu multiobjektiven Methoden durchaus gerechtfertigt. Verfahren der Klasse MADM können trotzdem verwendet werden, um eine Auswahlentscheidung für eine Alternative aus der paretooptimalen Lösungsmenge zu treffen oder um konkrete Alternativen im direkten Vergleich zu bewerten.

3.3.1.3 Klassifizierung nach der Kompensation der Zielerfüllungsgrade

Eine weitere Klassifizierungsmöglichkeit ergibt sich durch die Trennung in kompensatorische und nichtkompensatorische multikriterielle Entscheidungsmethoden. Kompensatorische Methoden besitzen dabei die Eigenschaft, dass ein schlechter Zielerfüllungsgrad eines Ziels durch einen sehr guten Zielerfüllungsgrad eines anderen Ziels ausgeglichen respektive kompensiert werden kann. Nichtkompensatorische Methoden besitzen diese Eigenschaft nicht.³²

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.2: Indifferenzkurven bei Verfahren mit und ohne Kompensation

Die Diagramme zeigen Indifferenzkurven für Verfahren mit und ohne Kompensationsmöglichkeiten der Zielerreichung hinsichtlich der Bewertung von Alternativen bei Anwendung auf ein bikriterielles Problem. Das linke Diagramm zeigt dabei ein Verfahren mit vollständiger Kompensation (Methode der gewichteten Summe), während das rechte Diagramm ein Verfahren ohne Kompensation zeigt (Fuzzy Decision Making).

Die Eigenschaft und der Grad der Kompensation kann durch Indifferenzkurven nachvollzogen und sichtbar gemacht werden. Dabei liegen genau die alternativen Lösungen eines Problems auf einer gemeinsamen Indifferenzkurve, welche durch das Verfahren hinsichtlich der Zielerreichung gleich bewertet werden.³³ Abbildung 3.2 zeigt unterschiedliche Indifferenzkurven für ein Verfahren mit und für ein Verfahren ohne die beschriebene Eigenschaft der Kompensation.³⁴

3.3.1.4 Klassifizierung nach der Integration des Entscheidungsträgers

Sowohl für klassische multiobjektive Methoden als auch für die nicht lineare multikriterielle Optimie- rung kann alternativ eine Klassifizierung der Verfahren aufgrund der Art und Weise der Integration des Entscheidungsträgers erfolgen. Dabei können die folgenden vier Klassen unterschieden werden.³⁵

1. A-priori-Methoden
2. A-posteriori-Methoden
3. Interaktive Verfahren
4. No-Preference-Verfahren

Methoden, bei denen bereits im Vorfeld des Optimierungsprozesses eine Artikulation der Präferenzen des Entscheidungsträgers gefordert wird, werden unter dem Begriff A-priori-Methoden zusammenge- fasst. Wird hingegen erst nach Durchführung des Such- beziehungsweise Berechnungsprozesses eine Präferenzangabe des Entscheidungsträgers gefordert, handelt es sich um A-posteriori-Methoden. No- Preference-Methoden verlangen keine Angabe der Präferenzen durch den Entscheidungsträger. Inter- aktive Verfahren treten über den gesamten Optimierungsprozess in Interaktion mit dem Entscheidungs- träger, wobei die Informationen über die Präferenzsituation progressiv artikuliert wird.³⁶

Nachfolgend sollen ausschließlich die beiden erstgenannten Methoden als alternative Modelle für die kombinatorische Optimierung tiefgehender untersucht werden. Für interaktive Methoden soll kei- ne weitere Betrachtung stattfinden, da diese Verfahren viel Zeit für die Kooperation mit dem Entschei- dungsträger erfordern. In Verbindung mit der ebenfalls von einem hohen Zeitbedarf geprägten kombi- natorischen Optimierung soll im Rahmen dieser Arbeit davon ausgegangen werden, dass sie kein sinn- volles Vorgehensmodell bereitstellen können, welches innerhalb eines angemessenen Zeitrahmens be- wältigt werden kann. Dem entgegen können mehrere Optimierungsläufe mit einem A-priori-Verfahren aufgrund wiederholter Präferenzänderungen ebenfalls als progressives Verfahren verstanden werden.³⁷

No-Preference-Methoden stellen ebenfalls keine sinnvolle Alternative dar, wenn nicht davon aus- gegangen werden kann, dass eine für den Entscheidungsträger passende Nutzenfunktion ableitbar ist, ohne dass Informationen über seine Präferenzen zur Verfügung gestellt werden müssen beziehungs- weise keine Situation vorliegt, in welcher der Entscheidungsträger über keine Präferenzen bezüglich der Zielkriterien verfügt.³⁸

3.3.2 A-priori-Methoden als reduktive Verfahren

Entsprechend der in Abschnitt 3.3.1.4 vorgestellten Klassifizierung besitzen A-priori-Methoden die Ei- genschaft, dass die Informationen über die Präferenzen des Entscheidungsträgers bereits vor Durchfüh- rung des Optimierungsprozesses vorliegen. Da diese Informationen bereits zu Beginn des Suchprozes- ses vorhanden sind, ist es Ziel des Verfahrens, genau eine paretooptimale Lösung zu generieren, welche den Präferenzen des Entscheidungsträgers am besten entspricht. Das gesamte Vorgehen kann demnach in die Phasen

1. Präferenzartikulation des Entscheidungsträgers
2. Detailgetreue Suche nach einer paretooptimalen Lösung
3. Ergebnispräsentation

gegliedert werden.³⁹ Unter Betrachtung der klassischen Entscheidungsmodelle, welche in Abschnitt 3.4 vorgestellt werden, ergeben sich verschiedene Vorgehensweisen für einen Optimierungsprozess.⁴⁰ Gemein ist allen Verfahren die Reduktion des mehrkriteriellen Problems auf ein oder mehrere unikriterielle Probleme. Aus diesem Grund werden A-priori-Methoden im Folgenden auch als reduktive Methoden beziehungsweise Verfahren bezeichnet.

3.3.2.1 Verfahren mit Ersatzzielfunktion

Die erste Gruppe dieser Verfahren bildet mit Hilfe der Präferenzangaben des Entscheidungsträgers ei- ne Ersatzzielfunktion, welche durch das Optimierungsverfahren zur Bewertung von Alternativen ge- nutzt wird. Diese Ersatzzielfunktion wird substituierend zu den »echten« Zielfunktionen des Problems verwendet, sodass ein unikriterielles Optimierungsproblem resultiert.⁴¹ Diese Vorgehensweise wird im Wesentlichen von multiobjektiven Verfahren, wie beispielsweise dem Compromise Programming oder dem TOPSIS-Verfahren verfolgt.⁴²

3.3.2.2 Verfahren mit echter Zielreduktion

Die zweite Gruppe der Verfahren reduziert die Ziele des Problems soweit, dass ein unikriterielles Op- timierungsproblem entsteht. Das verbleibende Ziel stellt dabei ein »echtes« Ziel (hinsichtlich der Ziel- funktion) des gegebenen Optimierungsproblems dar. Alle übrigen Ziele werden in anderer Form durch das Verfahren beachtet. Bei der lexikographischen Ordnung werden nach der Ermittlung der Lösungs- menge weitere Optimierungsläufe innerhalb dieser Lösungsmenge für alle übrigen Kriterien durchge- führt, während beim Verfahren der Haupt- und Nebenziele alle übrigen Ziele ausschließlich als Restrik- tion in das Problem einfließen.⁴³

3.3.3 A-posteriori-Methoden als nicht-reduktive Verfahren

Den reduktiven Verfahren gegenüber stehen die A-posteriori-Methoden, welche erst nach Abschluss des Optimierungs- respektive Suchprozesses die Angabe der Präferenzen durch den Entscheidungs- träger erfordern. Aus diesem Grund zielt der Suchprozess auf die Ermittlung der paretooptimalen Lö- sungsmenge, da während und vor dem Berechnungs- beziehungsweise Suchprozess keine Informatio- nen über die Präferenzen des Nutzers bekannt sind. Durch nachträgliche Angabe dieser Präferenzen kann im Anschluss an den Suchprozess die Lösung aus der Menge der paretooptimalen Lösungen aus- gewählt werden, welche am besten mit den Präferenzen des Nutzers übereinstimmt. Diese Auswahl kann beispielsweise mit Hilfe einer geeigneten MADM-Methode, der graphischen Darstellung der Pa- retofront oder einem progressiven Verfahren erfolgen. Das Vorgehen kann daher in die Phasen

1. Ermittlung der paretooptimalen Lösungsmenge
2. Präferenzartikulation des Entscheidungsträgers
3. Auswahl einer Lösung mit geeigneter Methode

gegliedert werden.⁴⁴ Nachfolgend werden Ansätze zur exakten Bestimmung und zur Approximation der Paretofront als mögliche Vorgehensweisen einer nicht-reduktiven Methode vorgestellt.

3.3.3.1 Dominanztechniken

Neben der Definition des Effizienzbegriffs und somit der Optimalität bei Problemen mit mehrfacher Zielsetzung stellt die Bestimmung der vollständigen Paretofront gleichzeitig eine Variante der multikriteriellen Optimierung dar. Eine mögliche Zielfunktion der Paretooptimierung kann aus dem Paretokriterium mit der Gleichung

Abbildung in dieser Leseprobe nicht enthalten

abgeleitet werden, wobei sämtliche Lösungen bestimmt werden müssen, welche den optimalen Zielfunktionswert F (π) = 1 besitzen.⁴⁵ Nach Ermittlung der paretooptimalen Lösungsmenge kann ein Nutzer eine seinen Präferenzen entsprechende Lösung aus dieser Menge auswählen, ohne im Vorfeld der Optimierung eine Angabe seiner Zielpräferenzen zu vollziehen.

Da jedoch in Gleichung 3.4 auf Seite 14 festgestellt wurde, dass prinzipiell die Möglichkeit besteht, dass[Abbildung in dieser Leseprobe nicht enthalten] gelten kann, folgt, dass die Bestimmung aller paretooptimalen Lösungen zu einer voll- ständigen Enumeration aller Lösungsmöglichkeiten führen kann. Wenn a priori keine Aussage über die Anzahl der paretooptimalen Lösungen getroffen werden kann, ergibt sich ein deutlicher Nachteil die- ses Verfahrens. Zusätzlich besteht, vor allem dann, wenn es sich um sehr große Paretofronten handelt, das Problem, dass die Anzahl der ermittelten Lösungen nach dem Optimierungslauf in vielen Anwen- dungsfällen reduziert werden muss, bevor sie einem Nutzer geeignet präsentiert werden kann. Da aus dem Paretokriterium analog zur Allokation von Gütern im volkswirtschaftlichen Sinne keine Aussa- ge über die Fairness beziehungsweise Gerechtigkeit bei der Verteilung abgleitet werden kann, ist es a posteriori zudem erforderlich, dass der Nutzer eine seinen Präferenzen entsprechende Lösung aus der ermittelten Lösungsmenge auswählt.⁴⁶

Da jedoch in Gleichung 3.4 auf Seite 14 festgestellt wurde, dass prinzipiell die Möglichkeit besteht, dass[Abbildung in dieser Leseprobe nicht enthalten] gelten kann, folgt, dass die Bestimmung aller paretooptimalen Lösungen zu einer voll- ständigen Enumeration aller Lösungsmöglichkeiten führen kann. Wenn a priori keine Aussage über die Anzahl der paretooptimalen Lösungen getroffen werden kann, ergibt sich ein deutlicher Nachteil die- ses Verfahrens. Zusätzlich besteht, vor allem dann, wenn es sich um sehr große Paretofronten handelt, das Problem, dass die Anzahl der ermittelten Lösungen nach dem Optimierungslauf in vielen Anwen- dungsfällen reduziert werden muss, bevor sie einem Nutzer geeignet präsentiert werden kann. Da aus dem Paretokriterium analog zur Allokation von Gütern im volkswirtschaftlichen Sinne keine Aussa- ge über die Fairness beziehungsweise Gerechtigkeit bei der Verteilung abgleitet werden kann, ist es a posteriori zudem erforderlich, dass der Nutzer eine seinen Präferenzen entsprechende Lösung aus der ermittelten Lösungsmenge auswählt.⁴⁶

3.3.3.2 Approximation der Paretofront

Der exakten Bestimmung der paretooptimalen Lösungsmenge gegenüber besteht jedoch des Weite- ren die Möglichkeit, mehrere parallele oder auch sequentielle Optimierungsläufe mit einem A-priori- Verfahren durchzuführen, um die Paretofront zu approximieren. Dazu wird eine systematische Durch- musterung von Präferenzsituationen generiert. Für alle Gewichtungsvektoren wird anschließend eine zielgerichtete Suche durchführt. Hierzu eignen sich allerdings nicht alle beschriebenen Verfahren, son- dern ausschließlich jene, welche eine freie Gewichtung der Zielkriterien zulassen.⁴⁷ Diese Vorausset- zung wird beispielsweise von den folgenden und - mit Ausnahme von TOPSIS - in dieser Arbeit be- trachteten Methoden erfüllt.⁴⁸

- Methode der gewichteten Summe / des gewichteten Produktes
- Analytical Hierarchy Process
- Gewichtetes Goal / Compromise Programming
- TOPSIS⁴⁹
- Fuzzy Decision Making

Die Methode der gewichteten Summe beziehungsweise des gewichteten Produkts wurde bereits erfolgreich in [Mer02] und [Gun04] in Kombination mit Ant Colony Optimization angewendet, um die Paretofront näherungsweise zu ermitteln.⁵⁰

Durch die Eigenschaft fast aller Verfahren, Kompensationen zwischen Zielfunktionswerten zu ermöglichen, ergeben sich hierbei jedoch Probleme, die dazu führen können, dass die Paretofront nicht gleichmäßig approximiert wird.⁵¹

Sowohl bei reduktiven als auch bei nicht-reduktiven Methoden können klassische Entscheidungsmo- delle als Bewertungs- oder Auswahlverfahren zum Einsatz kommen. Aufgrund dessen werden nach- folgend ausgewählte Verfahren vorgestellt, welche zu den Klassen der MADM- und MODM-Methoden gehören und sowohl als Bewertungs- als auch als Auswahlverfahren eingesetzt werden können.

Zunächst werden einige ausgewählte multiattributive Methoden vorgestellt und auf ihre Eignung für kombinatorische Probleme untersucht. Die Verwendung dieser Verfahren bleibt nicht auf die Auswahl einer Lösung aus der paretooptimalen Lösungsmenge beschränkt, sondern ist sogar in Form von Ersatzzielfunktionen denkbar. Um den Einsatz in letzterer Weise zu ermöglichen, benötigen einige dieser Verfahren geeignete Normierungstechniken, welche die konsistente Vergleichbarkeit von Zielfunktionswerten verschiedener Kriterien gewährleisten. Entsprechende Techniken werden in den jeweiligen Ausführungen ebenfalls diskutiert. Anschließend wird das Verfahren des Goal beziehungsweise Compromise Programmings als Vertreter der MODM-Methoden kurz erörtert.

3.4.1 Lexikographische Ordnung

Eine erste Möglichkeit zur Rückführung mehrerer Kriterien auf eine einkriterielle Optimierung stellt die lexikographische beziehungsweise hierarchische Anordnung der einzelnen Kriterien dar. Der Entscheidungsträger muss bei Verwendung der Methode eine eindeutige Präferenz hinsichtlich der subjektiven Bedeutung zwischen den Kriterien festlegen, sodass aus den Zielen Ψz mit z = 1, . . . , Z eine Ordnung mit einer eindeutigen Reihenfolge zwischen allen Zielen konsistent in der Form

Abbildung in dieser Leseprobe nicht enthalten

für die Optimierung als Parameter abgeleitet werden kann. Anhand einer solchen Reihenfolge führt ein Algorithmus einen Optimierungslauf durch, welcher das Problem zunächst ausschließlich für das Kriterium Ψ1 optimiert. Hierbei werden sämtliche Lösungen bestimmt, welche bezüglich dieses Ziels Optimalität besitzen. Die ermittelte Teilmenge des Lösungsraums dient als bereichsbeschränkende Ein- gabe für einen anschließenden Optimierungslauf, der nur dann sattfindet, falls mehr als eine Lösung bestimmt wurde.⁵² Innerhalb der zweiten Sequenz werden alle Lösungen bestimmt, welche innerhalb des beschränkten Bereichs bezüglich Ψ2 Optimalität besitzen.⁵³ Dieses Verfahren wird sequentiell für al- le folgenden Kriterien solange fortgeführt, bis entweder nur noch eine gültige Lösung im beschränkten Bereich liegt oder die Optimierung für alle Kriterien abgeschlossen wurde. Unter Anwendung dieser Verfahrensweise ergibt es sich, dass eine Optimierung des Ziels Ψz nur dann stattfindet, falls nach der Optimierung des Ziels Ψz−1 mehrere Lösungen im beschränkten Bereich liegen.⁵⁴ Daraus ergibt sich der wesentliche Nachteil dieses Verfahrens, da es auf diese Weise möglich ist, dass sämtliche Ziele, aus- genommen jenes mit der höchsten Präferenz, von dem Optimierungsalgorithmus unbeachtet bleiben. Verfahrensbedingt besteht keine Möglichkeit, die Gleichwertigkeit oder verhältnismäßige Präferenzen zwischen den Zielen anzugeben.⁵⁵ Das Verfahren scheint daher in der Praxis kaum anwendbar zu sein.

3.4.2 Haupt- und Nebenziele

Eine weitere Möglichkeit zur Rückführung auf ein unikriterielles Optimierungsproblem stellt die Un- terscheidung in ein Haupt- und mehrere Nebenziele dar. Hierbei muss eines der Ziele ausgewählt und als Hauptziel deklariert werden. Das Hauptziel wird als einziges tatsächliches Ziel im Optimierungsal- gorithmus betrachtet. Alle übrigen Ziele werden automatisch zu Nebenzielen degradiert, als Nebenbe- dingungen modelliert und gehen ausschließlich als diese in das Problem ein. Diese Nebenbedingungen haben die Funktion einer oberen Schranke beziehungsweise einer unteren Schranke, weshalb vom Ent- scheidungsträger für jedes Nebenziel die Vorgabe eines Grenzwertes erwartet wird. Die Nichterfüllung eines Nebenziels führt in diesem Zusammenhang zur Ungültigkeit einer Lösung.⁵⁶

Durch die zu extreme Wahl einer Schranke kann sich jedoch ergeben, dass der Zielfunktionswert des primären Ziels sehr schlecht wird oder die Nebenbedingungen zur Unlösbarkeit des Problems füh- ren.⁵⁷ Unter Betrachtung praxisrelevanter Ansichten, birgt dieser Ansatz jedoch einige Vorteile, da der Entscheidungsträger durchaus in der Lage sein könnte, Grenzwerte für die Zielerreichung anzugeben. Dies kann sich beispielsweise auf real vorhandene Restriktionen, welche beachtet werden müssen, be- gründen. Allerdings scheint es viel sinnvoller, nicht obligatorisch Schranken für Z − 1 Ziele zu fordern, sondern vielmehr eine optionale Angabe solcher Werte für alle Kriterien zu ermöglichen.

3.4.3 Methode der gewichteten Summen und Produkte

Eine sehr beliebte Variante, ein mehrkriterielles Problem auf nur ein einzelnes Ziel zu reduzieren, bildet die Aggregation aller Zielfunktionen zu einer gemeinsamen Zielfunktion über die Methode der gewichteten Summe. Formal beschrieben wird eine aggregierende Zielfunktion F definiert, die das Substitutionszielkriterium für ein Optimierungsproblem bildet. Das Problem kann daher in der Form

Abbildung in dieser Leseprobe nicht enthalten

abgebildet werden, wobei die folgenden Gleichungen als Nebenbedingungen gelten.⁵⁸ [Abbildung in dieser Leseprobe nicht enthalten]

Abbildung in dieser Leseprobe nicht enthalten

Die Wichtigkeit des einzelnen Kriteriums wird in diesem Zusammenhang durch die Variable λz re- präsentiert, wobei keine Notwendigkeit der hier angegeben Normierung der Gewichte besteht. Diese birgt allerdings den Vorteil, dass die relative Bedeutung jedes Ziels und somit der relative Einfluss auf die Gesamtoptimierung ablesbar ist. Zusätzlich wird durch die implizite Bedingung, dass λz ≥ 0 gel- ten muss, sichergestellt, dass jede nach Gleichung 3.10 optimale Lösung auch effizient im Sinne des Paretokriteriums ist.⁵⁹ Die Werte fz (π) berechnen sich aus einer Normierung des Zielfunktionswertes der Lösung π für das jeweilige Kriterium z. Die Normierung der Zielfunktionswerte ist erforderlich, da diese Werte der verschiedenen Kriterien auf eine gemeinsame Bewertungsskala [a, b] überführt werden müssen, um direkte Vergleiche zwischen ihnen konsistent zu ermöglichen. Üblicherweise wird hierfür die Norm der Werte als Anteilswerte zu einer Gesamtmasse von 1 analog der Gleichung

Abbildung in dieser Leseprobe nicht enthalten

verwendet.⁶⁰ Eine weitere Möglichkeit der Normierung stellt die Einordnung des Zielfunktionswertes im Intervall zwischen Minimum und Maximum der Zielfunktionswerte aller oder aller effizienten Lösungen eines Ziels dar. Die Berechnung erfolgt über Gleichung 3.13.⁶¹

Abbildung in dieser Leseprobe nicht enthalten

Analog zu den in Abschnitt 3.2.3 definierten Idealpunkten symbolisiert [Abbildung in dieser Leseprobe nicht enthalten] indiesemZusammenhang den Zielfunktionswert der Alternative mit dem schlechtestmöglichen und[Abbildung in dieser Leseprobe nicht enthalten]mitdembestmöglichen Wert fz .⁶² Es ergibt sich durch die Normierung daher das Intervall [0, 1], auf welchem alle Werte f˜ eingeordnet werden können.

Falls unter den einzelnen Zielkriterien sowohl zu minimierende Kriterien als auch zu maximierende Kriterien innerhalb des gleichen Problems zu unterscheiden sind, ergibt sich die Notwendigkeit, alle Kriterien mit zu maximierenden Zielen in Minimierungsziele zu invertieren, wenn die aggregierende Zielfunktion nach Gleichung 3.10 minimiert werden soll. Analog müssen alle Minimierungsziele als maximierende Zielfunktionen dargestellt werden, falls die aggregierende Zielfunktion maximiert wer- den soll. Diese Notwendigkeit der Invertierung ergibt sich aus der additiven Verknüpfung der Funkti- onswerte und ist bei der Normierung mit Gleichung 3.13 implizit durch die Fallunterscheidung beim Vergleich von [Abbildung in dieser Leseprobe nicht enthalten] und[Abbildung in dieser Leseprobe nicht enthalten]gegeben.Bei einer Normierung nach Gleichung 3.12 ist diese Invertierung ebenfalls im Rahmen der Überführung der Funktionswerte fz auf eine gemeinsame Skala zu den nor- mierten Funktionswerten[Abbildung in dieser Leseprobe nicht enthalten] möglich. O.B.d.A. wird davon ausgegangen, dass die Zielfunktion F (π) maximiert und alle vorhandenen zu minimierenden Kriterien invertiert werden sollen. Die normierten Funktionswerte können dann nach der Funktion

Abbildung in dieser Leseprobe nicht enthalten

ermittelt werden, um eine konsistente Vergleichssituation zu schaffen.⁶³

Die beschriebene Methode bildet im Vergleich zu den bisher vorgestellten Verfahren den Vorteil, dass die Zielpräferenzen des Entscheidungsträgers deutlich freier definiert werden können. Durch die Festlegung der Wichtigkeit einzelner Kriterien können sowohl die Gleichwertigkeit mehrerer Ziele als auch verhältnismäßige Präferenzen zwischen den Zielen abgebildet werden.

Die wesentlichen Nachteile des Verfahrens entspringen seiner Zugehörigkeit zu den kompensatori- schen Methoden, welche den Ausgleich sehr schlechter Zielfunktionswerte[Abbildung in dieser Leseprobe nicht enthalten] eines Zielkriteriums i durch einen oder mehrere andere Zielfunktionswerte [Abbildung in dieser Leseprobe nicht enthalten]zulassen. Diese Eigenschaft kann dazu führen, dass Lösungen, welche hinsichtlich einer Gewichtung der Zielkriterien sehr gut durch das Verfahren bewertet wurden, nicht tatsächlich den gewünschten Zielpräferenzen entsprechen.⁶⁴ DAS und DENNIS beschreiben in [Das97] die Nichteignung des Verfahrens bei Minimierungsproblemen mit nicht-konvexen Paretofronten, welche ebenfalls auf den kompensatorischen Effekt zurückführbar ist.⁶⁵

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.3: Grafische Darstellung von Zielfunktionen der Methode der gewichteten Summe Teilbild (a) zeigt die Paretofront eines bikriteriellen Optimierungsproblems mit den Lösungen π1, . . . , π10 in vereinfachter, direkt verbundener Darstellungsform. Teilbild (b) stellt die zugehörigen Zielfunktionen der Methode der gewichteten Summe bei unterschiedlichen Gewichten für die Kriteri- en mit den Zielfunktionswerten f (π1), . . . , f (π10) dar.

Das gleiche Problem ergibt sich bei nicht-konkaven Paretofronten von Maximierungsproblemen, wie das nachfolgende Beispiel anhand von Abbildung 3.3 zeigt. In Diagramm (a) wird die konvexe Paretofront eines bikriteriellen Optimierungsproblems dargestellt, die alle paretooptimalen Lösungen π1,...,π10 einer Probleminstanz enthält. In Diagramm (b) werden fünf zugehörige aggregierende Ziel- funktionen F der Methode der gewichteten Summe abgebildet, welche die Bewertungen aller Lösun- gen bei verschiedenen Gewichten λ1 für Ziel Ψ1 und λ2 für Ziel Ψ2 repräsentieren. Handelt es sich analog zu Gleichung 3.10 um ein Maximierungsproblem mit F (π) ⇒ max, können unabhängig von der verwendeten Gewichtung offensichtlich die Lösungen π2, ,π9 nicht als paretooptimale Lösungen gefunden werden, da es keine Gewichtskombination gibt, in welcher sich für diese Lösungen ein ma- ximaler Zielfunktionswert einstellen würde. Handelte es sich hingegen um ein Minimierungsproblem mit F (π) ⇒ min, kann jede Lösung π1, ..., π10 durch eine Bewertungsfunktion mit speziell gewählten Gewichten gefunden werden. Analog ergibt sich bei konkaven Paretofronten die gleiche Problematik für Minimierungsprobleme, während Maximierungsprobleme korrekt gelöst werden können.⁶⁶

GUNTSCH beschreibt in [Gun04] neben der Methode der gewichteten Summe des Weiteren die al- ternative Methode der gewichteten Produkte, in welcher die resultierende Zielfunktion nach Gleichung

3.15 gestaltet wird.⁶⁷

Abbildung in dieser Leseprobe nicht enthalten

Prinzipiell gelten hierbei die gleichen Aussagen, welche bereits bei der Methode der gewichteten Summe abgeleitet wurden. Der wesentliche Unterschied zur Methode der gewichteten Summe besteht darin, dass die Differenzen, welche zwischen den Zielerreichungsgraden der einzelnen Lösungen bestehen, aufgrund der Multiplikation der einzelnen Bestandteile stärker zur Geltung kommen.⁶⁸

3.4.4 AHP

Die von SAATY entwickelte AHP-Methode ist ein weiteres, sehr beliebtes Verfahren zur multikriteriel- len Optimierung.⁶⁹ Bei dieser Methode wird dem Nutzer ebenfalls abverlangt, a priori Entscheidungen über die Präferenzen zwischen den Zielen anzugeben. Anders als bei gewichteten Summen oder Pro- dukten, bei welchen globale Gewichte der Ziele des Problems angegeben werden müssen, findet hierbei ein paarweiser Vergleich zwischen den Zielen statt. Der Nutzer wird demnach angewiesen, für jeweils zwei Ziele im Vergleich eine Bewertung auf einer festen Skala anzugeben. Zusätzlich ist es möglich, die Kriterien im Vorfeld hierarchisch zu ordnen. Ein einziges oberstes Ziel aggregiert alle untergeordneten Ziele und dient als Zielkriterium der Optimierung beziehungsweise der Entscheidung über die Aus- wahl einer Alternative. Der paarweise Vergleich von Kriterien findet immer zwischen Elementen auf einer Hierarchiestufe hinsichtlich ihrer Bedeutung beziehungsweise ihres Einflusses auf das gemeinsa- me Oberziel statt. Durch den Entscheidungsträger müssen daher bei n Zielen auf einer Hierarchiestufe mit einem gemeinsamen Oberziel insgesamt[Abbildung in dieser Leseprobe nicht enthalten]Bewertungen vorgenommen werden.⁷⁰ Die Bewer- tungsskala der AHP-Methode wird in Tabelle 3.1⁷¹ vorgestellt.

Tabelle 3.1: (1-9)-Bewertungsskala des Analytical Hierarchy Process

Die Bewertungen werden anschließend in eine Evaluationsmatrix A übernommen, wobei nur die Elemente aij abgefragt werden müssen, bei welchen i < j gilt (obere Dreiecksmatrix).

Abbildung in dieser Leseprobe nicht enthalten

Die Elemente aij mit i > j ergeben sich durch [Abbildung in dieser Leseprobe nicht enthalten]die Elemente aij auf der Diagonale der Matrix mit i = j werden mit dem Wert 1 besetzt, da es sich um den Vergleich eines Ziels i mit sich selbst handelt. Aus der nun vollständigen Evaluationsmatrix A wird der Eigenvektor λ berechnet.

3.4 Reduktive Entscheidungsmodelle

Dieser Eigenvektor stellt die resultierenden Gewichte jedes Ziels z mit dem Eigenwert λz bereit.⁷²

Die Berechnung des Zielfunktionswertes erfolgt dann im Allgemeinen analog zur Methode der ge- wichteten Summe. Demnach ergibt sich der Zielfunktionswert F einer Lösung π über die Gleichung

Abbildung in dieser Leseprobe nicht enthalten

wobei der Wert λz das Gewicht und der Wert[Abbildung in dieser Leseprobe nicht enthalten] den normierten Zielfunktionswert des z-ten Ziels sym- bolisiert.⁷³

Da die Aggregation der Ziele hinsichtlich ihrer Zielfunktionswerte analog der Methode der gewich- teten Summe durchgeführt wird, gelten demnach die gleichen Aussagen über die Probleme des Verfah- rens wie bei dieser Methode.⁷⁴ Entgegen der Methode der gewichteten Summe wird mittels AHP auf- grund der paarweisen Vergleiche jedoch eine konsistente Präferenzsituation geschaffen, ohne dass der Nutzer seine Präferenzen mathematisch formulieren oder deren Auswirkung auf den Optimierungslauf genau kennen muss. Die Möglichkeit, hierarchische Zielstrukturen zu definieren, stellt einen weiteren Vorteil dar.⁷⁵

3.4.5 Fuzzy Decision Making

Ein weiteres reduktives Modell zur multikriteriellen Entscheidung beziehungsweise Bewertung von Lösungen stellt die Methode des Fuzzy Decision Making (FDM) dar, welche auf die 1965 von ZADEH entwickelte Fuzzy Logic zurückgeht.⁷⁶ Diese Methode soll im Folgenden vorgestellt werden, wobei auf detaillierte Ausführungen zu der Theorie der unscharfen Mengen verzichtet wird.⁷⁷

Hierbei stellen die einzelnen Zielkriterien, welche es zu optimieren gilt, unscharfe Mengen (sog. fuzzy sets) dar. Die Elemente dieser Mengen entsprechen den Ausprägungen der jeweiligen Zielfunk- tionswerte von Lösungen des Problems. Da die Zugehörigkeit eines Elements in unscharfen Mengen nicht eindeutig mittels einer booleschen Variable angegeben werden kann, wird diese durch so genann- te Zugehörigkeitsfunktionen µ beschrieben. Neben diesen Fuzzy-Zielen können Fuzzy-Restriktionen (Nebenbedingungen) und Fuzzy-Entscheidungen (reduzierte unikriterielle Zielwerte) ebenfalls als we- sentliche Bestandteile des Fuzzy Decision Making betrachtet werden, welche gleichwohl über Zugehö- rigkeitsfunktionen identifiziert werden.⁷⁸ Die Zugehörigkeitsfunktion µz eines Fuzzy-Ziels z wird auf einer Menge von möglichen Entscheidungsalternativen, des Lösungsraums Π, definiert.

Abbildung in dieser Leseprobe nicht enthalten

Dabei ist sowohl der Umgang mit einem stetigen Lösungsraum als auch mit einer endlichen Menge an Entscheidungen denkbar. Gleiches gilt für die Zugehörigkeitsfunktionen für Fuzzy-Restriktionen µC und Fuzzy-Entscheidungen µD .⁷⁹

Abbildung in dieser Leseprobe nicht enthalten

(3.19)

Abbildung in dieser Leseprobe nicht enthalten

Im Vergleich zu herkömmlichen Güte- beziehungsweise Kostenfunktionen beschränkt sich der Wer- tebereich von Zugehörigkeitsfunktionen von Fuzzy-Zielen auf das Intervall [0, 1], was eine Normierung der Zielfunktionswerte der klassischen Güte- beziehungsweise Kostenfunktion voraussetzt, um diese in eine Zugehörigkeitsfunktion zu überführen.⁸⁰ Für diese Normierung eignet sich beispielsweise die Methode nach Gleichung 3.13 auf Seite 24.

O. B. d. A. wird im Folgenden davon ausgegangen, dass die Zielfunktionen für die einzelnen Zielkri- terien in Form von Gütefunktionen vorliegen, sodass eine Fuzzy-Entscheidung für ein Kriterium z zwi- schen den Lösungen π1 und π2 genau dann zu Gunsten der Lösung π1 ausfällt, wenn µz (π1) > µz (π2) ist. Da das Problem jedoch über mehrere Kriterien verfügt, bleibt die Frage, auf welche Weise die Ziel- kriterien respektive deren Zugehörigkeitsfunktionen verknüpft werden, um eine mehrkriterielle Fuzzy- Entscheidung zu erhalten. BELLMAN und ZADEHschlugen hierfür die UND-Verknüpfung (Durchschnitt der Mengen) vor, sodass sich der Zielfunktionswert einer Lösung π der Zugehörigkeitsfunktion µD der Fuzzy-Entscheidungsmenge zu

Abbildung in dieser Leseprobe nicht enthalten

ergibt. Dabei werden alle Zugehörigkeitsfunktionen der insgesamt Z Zielkriterien z sowie alle m Restriktionen j mittels des UND-Operators verknüpft, wobei deutlich wird, dass keine Unterscheidung zwischen Restriktionen und Zielkriterien vorgenommen wird.⁸¹

Der Operator für den Durchschnitt unscharfer Mengen kann variieren und sollte von der zugrunde liegenden Problemstellung abhängig gemacht werden, wobei sowohl von BELLMAN und ZADEH als auch von anderen Autoren der MIN-Operator vorgeschlagen wird.⁸² Durch die Verwendung des MIN-Operators auf zu maximierende Zugehörigkeitsfunktionen führt dies zur Verwendung der MAXMIN-Entscheidungsregel (Wald-Regel), welche oft als sehr pessimistische Entscheidungsregel betrachtet wird, da sie keine Kompensation zwischen den Zielkriterien zulässt.⁸³

Bei der Überführung einer Gütefunktion in eine Zugehörigkeitsfunktion µz eines Fuzzy-Ziels z kann des Weiteren eine Gewichtung des Kriteriums z nach Gleichung 3.21 erfolgen.

Abbildung in dieser Leseprobe nicht enthalten

Dabei repräsentiert f˜z die normierte Gütefunktion des z-ten Kriteriums nach Gleichung 3.13 und λz der Faktor das Gewicht für das Kriterium z, wobei aus einer hohen Wahl des Parameters auch eine hohe Bedeutung des Kriteriums z resultiert.⁸⁴

Die Vorteilhaftigkeit des Einsatzes von Fuzzy Decision Making hängt eng damit zusammen, inwiefern eine Kompensation der Erreichungsgrade zwischen den Zielen erwünscht oder unerwünscht ist. Ist eine Kompensation nicht dienlich, erweist sich Fuzzy Decision Making gegenüber den übrigen kompensatorischen Verfahren als sinnvoll.

Abbildung in dieser Leseprobe nicht enthalten

3.4.6 Goal Programming und Compromise Programming

Im Goal Programming (GP) werden so genannte Anspruchsniveaus (auch »Goals«) separat für jedes Ziel a priori definiert. Das Anspruchsniveau eines Ziels entspricht einem Zielfunktionswert, welcher durch eine Lösung möglichst genau eingehalten werden soll. Im Rahmen der Optimierung wird die Zielfunktion insofern transformiert, dass nicht mehr nach dem optimalen Wert hinsichtlich eines Kri- teriums gesucht wird, sondern nach der geringsten Differenz zum definierten Anspruchsniveau.⁸⁵ Aus diesem Grund werden die Zielfunktionswerte in ein Abstandsmaß transformiert, das den Abstand ei- nes Zielfunktionswertes von dem zu erreichenden Anspruchsniveau repräsentiert. Im gewichteten Goal Programming ist es des Weiteren möglich, etwaige Präferenzen, welche zwischen den Zielen bestehen können, abzubilden. Die Aggregation der einzelnen Abstandswerte findet im Normalfall über die Me- thode der gewichteten Summe statt.⁸⁶ Bei dieser Methode ist zu beachten, dass sowohl Zielfunkti- onswerte, welche das definierte Anspruchsniveau unter- als auch solche, die jenes überschreiten, eine niedrigere Bewertung hinsichtlich der Zielerreichung erzeugen, als ein Zielfunktionswert, welcher dem Anspruchsniveau identisch ist und damit optimal bewertet wird.⁸⁷

Für Ziele, die nur schwer in Form eines Anspruchsniveaus definiert werden können, erweist sich der Einsatz des Goal Programmings jedoch als problematisch. Insbesondere bei Zielen, welche hinsichtlich der Zielerreichung unbeschränkt sind, wie zum Beispiel die Maximierung des Gewinns, kann eine Angabe eines Anspruchsniveaus durch den Nutzer nicht getätigt werden.⁸⁸

In diesem Zusammenhang besteht allerdings die Möglichkeit, das Optimierungsproblem für jedes Zielkriterium separat exakt zu lösen und den Zielfunktionswert der jeweiligen optimalen Lösung dem Anspruchsniveau gleichzusetzen. Es ergibt sich daraus der bereits in Abschnitt 3.2.3 definierte ideale Punkt y+, von welchem der gewichtete Abstand jeder Lösung ermittelt werden kann. Wird das Verfah- ren in Kombination mit der Ideallösung des Problems verwendet, wird häufig auch der Name Com- promise Programming (CP) verwendet.⁸⁹ Dabei findet zusätzlich eine skalenbasierte Normierung statt, bei welcher einerseits der positive Idealpunkt und andererseits entweder die negative Ideallösung oder der Nadir-Punkt als Skalenbegrenzung dient. Die Zielfunktion des Compromise Programmings kann formal wie folgt angegeben werden.⁹⁰

Abbildung in dieser Leseprobe nicht enthalten

(3.22)

Der Einsatz von CP ist allerdings nur dann sinnvoll, wenn die optimalen Lösungen der zugehörigen unikriteriellen Probleme effizient bestimmt werden können.

3.5 Fazit

In den letzten Abschnitten wurden verschiedene Vorgehensweisen, Ansätze und Verfahren der multi- kriteriellen Optimierung beziehungsweise Entscheidung vorgestellt. Nachfolgend sollen diese unter der Perspektive der Vor- und Nachteile und ihrer Eignung für den Einsatz bei kombinatorischen Problemen betrachtet werden.

3.5.1 Beurteilung der A-priori-Methoden

Die Menge der reduktiven Ansätze erfordert es zwingend, a priori Entscheidungen über die Präferen- zen des Entscheiders hinsichtlich der Zielkriterien zu treffen, welche als Parameter in die entsprechende Methode eingehen. In diesem Zusammenhang stellt sich zunächst die Frage, ob die Angabe solcher In- formationen von einem Entscheidungsträger erwartet werden können. Der Entscheidungsträger müsste einerseits über eine klare Vorstellung seiner Zielpräferenzen verfügen und andererseits im Stande sein, diese in geeigneter Form zu artikulieren. Hierzu ist es bei einigen Verfahren erforderlich, die Präfe- renzsituation mathematisch zu formulieren. Hierbei besteht zwar prinzipiell die Möglichkeit, Verfahren wie AHP einzusetzen, um qualitativ geprägte Informationen konsistent zu quantifizieren. Infolge der Unkenntnis des Entscheiders von der tatsächlichen Charakteristik beziehungsweise Ausprägung der Paretofront beziehungsweise des Ziel- und Lösungsraums des Problems können jedoch keine klare Vor- stellungen vorausgesetzt werden.⁹¹

Des Weiteren ergäbe sich bei Anwendung eines A-priori-Verfahrens nur eine Lösung oder sehr we- nige Lösungen, welche im besten Falle einerseits paretooptimal sind und andererseits den verwendeten Gewichtungsparametern sehr genau entsprechen. Da jedoch bereits festgestellt wurde, dass der Ent- scheidungsträger über sehr ungenaue Vorstellungen bezüglich seiner Präferenzen verfügt oder Proble- me bei der Artikulation letzterer entstehen können, resultiert daraus folglich ein hohes Risiko, dass sich die Präferenzen hinsichtlich der Gewichtungsparameter bei Präsentation des Ergebnisses ändern. In- dem das Verfahren derartige Präferenzänderungen zuließe, entstünde ein progressives Verfahren mit möglicherweise hohem Zeitbedarf, da bei jeder Präferenzänderung oder -anpassung ein weiterer Opti- mierungslauf mit neuen Parametern durchgeführt werden müsste. Diese Verfahren dürften sich dem- nach bei Anwendung in der Praxis als sehr inflexibel erweisen, wenn keine Möglichkeit gefunden wird, die Artikulation der Präferenzen durch zusätzliche Informationen über den Lösungs- beziehungswei- se Zielraum oder die Paretofront zur Verfügung zu stellen.⁹² Der wesentliche Vorzug der A-priori- Verfahren gegenüber anderen Methoden ergibt sich durch ein deutlich besseres Performanzverhalten, was sich hauptsächlich darauf begründet, dass mit Hilfe einer Ersatzzielfunktion eine Reduktion auf ein unikriterielles Problem vorgenommen und somit auch die Komplexität des Problems reduziert wird. Eine etwaige Wiederholung des Optimierungsprozesses aufgrund von Präferenzänderungen des Ent- scheiders wirkt diesem Vorzug jedoch entgegen.

Verfahren, welche keine freie Gewichtung der Präferenzen zwischen den Zielkriterien zulassen, soll- ten möglichst vermieden werden, da viele mögliche Präferenzsituationen nicht abgebildet werden kön- nen. Abschließend kann daher nur eine sehr bedingte Eignung der A-priori-Methoden abgeleitet wer- den.

3.5.2 Beurteilung der A-posteriori-Methoden

Den A-priori-Verfahren gegenüber stehen die deutlich weniger performanten nicht-reduktiven Verfah- ren, welche erst nach Durchführung des Suchprozesses auf eine Artikulation der Präferenzen vom Ent- scheidungsträger angewiesen sind. Ziel dieser Verfahren ist es, die vollständige Paretofront zu bestim- men.⁹³ Da bereits in Abschnitt 3.2.2 auf Seite 14 festgestellt wurde, dass prinzipiell die - wenn auch wenig wahrscheinliche - Möglichkeit besteht, dass sämtliche zulässige Lösungen nicht dominiert wer- den und demnach Π∗ = Π gilt, würde die Bestimmung der paretooptimalen Lösungsmenge auf eine vollständige Enumeration hinauslaufen. Insbesondere bei kombinatorischen Optimierungsproblemen wächst der Lösungsraum meist exponentiell im Vergleich zu den Input-Variablen des Problems. Die Ermittlung der vollständigen Paretofront mit Hilfe von Dominanztechniken sollte in diesem Zusam- menhang bei Unkenntnis der Größe der paretooptimalen Lösungsmenge nur eingeschränkt empfohlen werden. Hinzu kommt eine etwaige NP-Vollständigkeit des Problems, welche eine Lösung mit exak- ten Methoden bei großen Eingabelängen ohnehin verbietet. Wesentlicher Vorteil dieser Vorgehensweise ist, dass bei der Angabe der Präferenzen die ermittelte paretooptimale Lösungsmenge bereits zur Ver- fügung steht beziehungsweise bekannt ist. Der Entscheidungsträger wählt die Alternative aus dieser Menge, welche seinen Präferenzen am ehesten entspricht. Diese Auswahl kann mit Hilfe der reduktiven Techniken geschehen, wofür insbesondere die Methoden der Klasse MADM geeignet erscheinen.⁹⁴ Au- ßerdem besteht die Möglichkeit, Informationen über die Charakteristik der Paretofront bereitzustellen oder die Front in geeigneter Form zu visualisieren.⁹⁵ In diesem Zusammenhang sollte ebenfalls bemerkt werden, dass Präferenzänderungen des Entscheiders keinen neuen Optimierungslauf, sondern lediglich eine erneute Berechnung der Zielwerte über alle Alternativen der Paretofront erfordert.⁹⁶

Des Weiteren besteht die Möglichkeit, die Paretofront mit Hilfe der reduktiven Verfahren und einer systematischen Durchmusterung von Präferenzsituationen zu approximieren.⁹⁷ Auf diese Weise kann die Laufzeit auf ein angemessenes Maß reduziert werden, ohne die Ziellösungsmenge zu stark einzu- grenzen. Da der Detailgrad der Approximation steuerbar ist, folgt daraus implizit auch die Kontrolle über das Laufzeitverhalten. Auf diese Weise kann das Verhältnis von Güte und Performanz des Verfah- rens den Ansprüchen des Entscheiders beziehungsweise den Notwendigkeiten des Problems angepasst werden.⁹⁸ In diesem Rahmen ergibt sich auch die Möglichkeit, diese Technik in einem progressiven Modell einzusetzen. Dabei wird der Detailgrad der Optimierung in stärker präferierten Gebieten des Lösungsraums sukzessive erhöht. Die Approximation der Paretofront bildet daher aus den genannten Gründen eine angemessene Kompromisslösung zwischen den Vorteilen der A-posteriori- und A-priori- Verfahren.

Abschließend kann festgestellt werden, dass A-posteriori-Verfahren im Allgemeinen über eine Reihe von Vorzügen, bis auf die geringere Performanz jedoch über keine Nachteile gegenüber A-priori- Verfahren verfügen.

Kapitel 4 Optimierung von Angebotsnetzen im EVCM

Nachdem in den vergangenen Kapiteln allgemeine Grundlagen der kombinatorischen Optimierung so- wie der mehrkriteriellen Optimierung und Entscheidung behandelt wurden, soll im folgenden Kapitel ein konkreter Anwendungsfall eines mehrkriteriellen kombinatorischen Optimierungsproblems erläu- tert werden.

4.1 Extended Value Chain Management

TEICH definiert das Extended Value Chain Management wie folgt: »EVCM ist die ganzheitliche, kompetenzorientierte Betrachtung der Geschäftsprozesse ei- nes Produktionsnetzwerkes über alle Produktionsstufen beginnend beim Kunden und en- dend bei elementaren Zulieferern. Es umfasst dabei alle strategischen, taktischen und ope- rativen Maßnahmen zur effizienten Koordination aller inter- und intraorganisatorischen Ge- schäftsprozesse, die ihren Ursprung in der fachkompetenten Bildung von Prozessvarianten- plänen haben und sich bis zur sozialkompetenten, operationalisierten Auswahl von Netz- werkpartnern erstrecken.«¹

4.1.1 Phasenmodell

Kern des Extended Value Chain Management ist das die Ablauforganisation definierende Phasenmo- dell, welches sich aus neun aufeinander folgenden Phasen zusammensetzt und die Entstehung, den Betrieb und die Auflösung temporärer hierarchieloser Unternehmensnetzwerke beschreibt beziehungs- weise regelt. Die neun Phasen dieses Modells werden in Abbildung 4.1² dargestellt und sollen im Fol- genden kurz beschrieben werden. Eine ausführliche Darstellung des Modells findet sich in der Habili- tationsschrift von TEICH.³

Die Entstehung eines temporären Netzwerkes wird initiiert durch eine konkrete Kundenanfrage, welche im Wesentlichen Detailinformationen über das nachgefragte Produkt, die zu liefernde Men- ge und den durch den Kunden gewünschten Lieferzeitpunkt beinhaltet.⁴ Ausgehend von einer sol- chen Anfrage findet eine Dekomposition des Wertschöpfungsnetzes statt, welche die Zerlegung der Wertschöpfung in einzelne Prozessschritte zum Ziel hat. Dabei wird zunächst ein Prozessvariantenplan

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4.1: Phasenmodell des EVCM

Die 9 Phasen des EVCM-Phasenmodells. Dabei stellt Phase 6 den wesentlichen Bereich für die in dieser Arbeit betrachtete Optimierung dar.

(PVP) generiert, innerhalb dessen alle technologisch sinnvollen Herstellungsvarianten des nachgefrag- ten Produktes durch Prozessschritte und deren Reihenfolge beschrieben werden.⁵ Ergebnis der ersten Phase ist ein Nachfragevektor für die Anfrage, welcher sich aus Produkt-, Auftrags- und Prozessdaten zusammensetzt.⁶

In der anschließenden zweiten Phase des Modells wird nach Partnern gesucht, deren technologische Fähigkeiten mit denen des durch den Nachfragevektor aus der ersten Phase geforderten Kompetenzen korrespondierenden. Partner stellen dabei am Netzwerk beteiligte Unternehmen dar, die durch eine Kompetenzzelle repräsentiert werden und deren technologische Fähigkeiten mit Hilfe eines in einer zentralen Datenbank⁷ abgelegten und durch Selbstauskunft ermittelten Angebotsvektors beschrieben werden. Ergebnis dieser Suche sind potentielle Kandidaten für die Realisierung der in der ersten Phase identifizierten und zu bewältigenden Prozessschritte.⁸

Durch eine konkrete Anfrage dieser potentiellen Partner wird die dritte Phase des Modells initia- lisiert, in welcher die einzelnen Kompetenzzellen eine interne Ablaufplanung durchführen. Im Rah- men dieser Planung werden Verfügbarkeiten bei Lagerzugriffen (ATP-Prüfung) zu entsprechenden Zeit- punkten beziehungsweise der Ressourcen bei der Produktion (CTP-Prüfung) geprüft. Ziel und Ergebnis dieser Phase ist die Sammlung aller Informationen, um in der darauf folgenden vierten Phase entweder konkrete Angebote zu generieren, welche spezifische Lieferkonditionen wie beispielsweise Preis, Liefer- wahrscheinlichkeit und Liefertermin beinhalten, oder die Unfähigkeit der Lieferung zu den geforderten Konditionen herauszustellen. Dabei besteht die Möglichkeit, dass bei der Produktherstellung notwendi- ge Vorprodukte in die Produktion eingehen, welche nicht zum entsprechenden Bedarfszeitpunkt durch die Kompetenzzelle zur Verfügung gestellt werden können. In diesem Fall werden durch die rekur- sive Verwendung der ersten drei Phasen des Modells im Rahmen des so genannten Ausrollprozesses Angebote anderer Kompetenzzellen eingeholt, welche im Stande sind, die benötigten Vorprodukte zu liefern.⁹ Die Phase der Angebotsgenerierung stellt einen zugehörigen Einrollprozess dar, der die durch den Ausrollprozess erzeugte Rekursion, beginnend auf der untersten Stufe, sukzessive auflöst. Nach Abschluss des Aus- und Einrollprozesses ist demnach ein Netz aus abhängigen Angeboten entstanden, welches sich von dem in der ersten Phase erzeugten Prozessvariantenplan ableitet beziehungsweise eine konkrete Instanz dessen mit ausgeprägten Attributen repräsentiert. Ein Angebot für einen Prozessschritt wird bestimmt durch die Eigenschaften Preis, Menge, Liefertermin und Lieferwahrscheinlichkeit.¹⁰

Aus der Menge der möglichen Kombinationen einzelner Angebote von Kompetenzzellen muss aufgrund der Ergebnisse der folgenden fünften und sechsten Phase genau eine ausgewählt werden, deren Kompetenzzellen den Zuspruch für die zugehörigen Angebote erhalten. In der fünften findet dabei eine Bewertung nach qualitativen Faktoren, so genannten Soft-Facts, statt. Dabei werden beispielsweise soziale Kompetenzen, wie die Kommunikations- und Kooperationsfähigkeit oder die Zuverlässigkeit der einzelnen Partner untersucht.¹¹ Neben der Bewertung der Soft-Facts werden in den folgenden Phasen die so genannten Hard-Facts optimiert, welche quantifizierbare betriebswirtschaftliche Kenngrößen darstellen. Nach einer Optimierung dieser Größen findet die tatsächliche Auswahl einer Angebotskombination entsprechend den Präferenzen des Kunden statt.¹²

Durch die Auswahl einer konkreten Angebotsmenge entsteht in der siebenten Phase mit dem Netz- betrieb ein temporäres virtuelles Unternehmen, welches sich aus verschiedenen realen Unternehmen zusammensetzt und die Leistung der tatsächlichen physischen Herstellung des angefragten Produktes erbringt. Ergebnis dieser Phase ist die Lieferung des angefragten Produktes zu den angegebenen und geforderten Konditionen. Abschließend wird in der achten Phase die Arbeit und die Zusammenarbeit der Unternehmen bewertet und für eine spätere Abrechnung und Evaluierung zugänglich gemacht, bevor in der neunten und letzten Phase das temporäre Unternehmensnetzwerk aufgelöst wird.¹³

4.1.2 Prozessvariantenplan und Prozessplan

TEICH beschreibt in [Tei02] Prozessvariantenpläne, welche alle sinnvoll möglichen technologischen Her- stellungsvarianten für ein Produkt beinhalten, als Basis der Anfragen an Kompetenzzellen. Wie im vo- rigen Abschnitt bereits erläutert, wird für jede Kundenanfrage in der ersten Phase des EVCM-Modells zunächst ein Prozessvariantenplan ermittelt. Durch eine Enumeration aller Herstellungsmöglichkeiten entsteht dabei eine Reihe von Prozessplänen, welche jeweils genau eine Herstellungsalternative reprä- sentieren.¹⁴ Aus Gründen der Vereinfachung werden im Folgenden daher Prozesspläne als Basis eines Angebotsnetzes betrachtet. Da jedoch eine Ableitung der einzelnen Prozesspläne aus dem Prozessvari- antenplan stets möglich ist, stellt diese Vereinfachung keine Einschränkung der Allgemeinheit dar.¹⁵

Ein Prozessplan enthält alle Prozessschritte, deren Durchführung notwendig ist, um das geforderte Produkt sowie alle notwendigen Vorprodukte auf allen Stufen der Fertigung herzustellen. Somit können innerhalb eines Prozessplans ebenso Aktivitäten (Prozessschritte) als auch Zustände (durch Prozessschritte entstandene Zwischenprodukte) verzeichnet werden. In Abbildung 4.2 wird ein beispielhafter Prozessplan in Form eines gerichteten, zyklenfreien Digraphen dargestellt, welcher genau eine Herstellungsvariante für ein nachgefragtes Endprodukt repräsentiert.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4.2: Beispielhafter Graph eines Prozessplans für die Herstellung eines Produktes

Die Prozessschritte werden im Graphen durch die quadratischen Knoten symbolisiert. Jeder Prozess- schritt hat die Lieferung eines Zwischenproduktes zur Folge, welches als fünfeckiges Symbol darge- stellt wird. Ein Zwischenprodukt wird dabei in einem folgenden Prozessschritt weiterverarbeitet oder geht beispielsweise als Baugruppe in den nächsten Prozessschritt ein. Im Graph wird zusätzlich in konvergierende (Schritte 1-7) und divergierende Teilprozesse (Schritt 8) unterschieden.

Ein nachgefragtes Endprodukt setzt sich üblicherweise aus einer Reihe von Vorprodukten, wie bei- spielsweise Baugruppen, zusammen, sodass der Prozessplan hinsichtlich der zwischen den Prozessen entstehenden Zwischenprodukte als Gozintograph oder Struktur- beziehungsweise Baukastenstücklis- te darstellbar ist.¹⁶ Diese Prozesse entsprechen einer konvergierenden Wertschöpfung, da mehrere Zwi- schenprodukte durch einen Prozessschritt zu einem resultierenden Zwischen- oder Endprodukt ver- bunden werden. Es können jedoch auch Prozessschritte mit divergierendem Charakter auftreten. Dabei hat ein Prozessschritt mehrere verschiedene Zwischenprodukte zum Ergebnis, welche unter Umständen in verschiedenen anderen Prozessschritten weiterverarbeitet werden müssen. KAMINSKI beschreibt die Herstellung eines Getriebekastens als ein typisches Beispiel für einen divergierenden Prozessschritt.¹⁷ Ein solches zweiteiliges Gehäuse, welches sich aus Ober- und Unterseite zusammensetzt, durchlaufen mehrere Wellen und Stangen, welche exakt in den zugehörigen Bohrkanälen liegen müssen. Während dabei die Bohrungen für Ober- und Unterseite zusammen innerhalb eines Arbeitsgangs erfolgen müs- sen, um die notwendige Qualität zu gewährleisten, kann anschließend eine getrennte Weiterverarbei- tung der beiden Seiten erfolgen. Bei einer abschließenden Montage muss jedoch sichergestellt werden, dass Ober- und Unterseite richtig kombiniert werden.¹⁸ Der in Abbildung 4.2 dargestellte Prozessplan enthält mit Prozessschritt 8 einen divergierenden Prozessschritt. Divergierende Prozessschritte werden im Folgenden als Divergenzpunkte des Graphen bezeichnet. Da eine Anfrage jedoch auf genau ein kon- kretes Produkt in einer bestimmten Menge zielt, muss für jede im Laufe der Wertschöpfung entstandene Divergenz in späteren Abschnitten eine zugehörige Konvergenz stattfinden. Ein Prozessschritt, in wel- chem die Auflösung einer entstandenen Divergenz stattfindet, sei im Folgenden als zugehöriger oder auflösender Konvergenzpunkt bezeichnet. Im Beispiel von Abbildung 4.2 wird die durch Prozessschritt 8 entstehende Divergenz durch den zugehörigen Konvergenzpunkt in Prozessschritt 1 aufgelöst.

4.1.3 Angebotsnetze

Ausgehend von einem im vorigen Abschnitt vorgestellten Prozessplan, soll im Folgenden das Konzept des Angebotsnetzes als attribuierter Prozessplan detaillierter beschrieben werden. Ein Angebotsnetz stellt, wie in Abschnitt 4.1.1 bereits beschrieben, das Ergebnis des Aus- und Einrollprozesses dar und setzt sich aus konkreten Angeboten von Kompetenzzellen zusammen, welche jeweils die Konditionen für die Ausführung eines Prozessschrittes und damit die Liefermöglichkeit eines Zwischenproduktes an eine andere Kompetenzzelle beschreiben.

4.1.3.1 Vererbung der Prozessplaneigenschaften

Analog zur Darstellung des Prozessplans kann ein Angebotsnetz ebenfalls als gerichteter und azykli- scher Graph dargestellt werden, welcher unvollständig ist. Dabei werden wesentliche Eigenschaften des Prozessplans auf das Angebotsnetz vererbt. Im Prozessplan wurden Prozessschritte als Knoten und Lie- ferabhängigkeiten von eingehenden Zwischen- beziehungsweise Vorprodukten als Kanten dargestellt. Im Angebotsnetz erfolgt eine analoge Darstellung, wobei Angebote durch Knoten und Lieferbeziehun- gen durch Kanten repräsentiert werden. Das Angebotsnetz bildet daher eine konkrete Instanz des Pro- zessplans.¹⁹

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4.3: Beispielhaftes Angebotsnetz für ein Produkt

Diese Darstellung zeigt eine Instanz eines Angebotsnetzes für einen einfachen Prozessplan, welcher ausschließlich Konvergenzen enthält.

Da für jeden Prozessschritt mehrere Angebote von verschiedenen Kompetenzzellen vorliegen kön- nen, findet eine Gruppierung dieser Angebote nach Knotengruppen auf Basis des zugrunde liegenden Prozessschrittes statt. Angebote, welche zusätzlich Vorprodukte benötigen, die durch andere Kompe- tenzzellen geliefert werden, können dabei ebenfalls über mehrere Angebote zur Lieferung dieser Vor- produkte durch andere Kompetenzzellen verfügen. Seien A1 ein Angebot, welches ein Vorprodukt V1 in einer bestimmten Menge bis zu einem bestimmten Lieferzeitpunkt benötigt und die Angebote Bi mit i = 1, 2, ... Liefermöglichkeiten für V1 in der geforderten Menge zum bestimmten Lieferzeitpunkt, so können alle möglichen Lieferbeziehungen (Kanten) zwischen dem Angebot A1 und den Angeboten Bi in einer gemeinsamen Kantengruppe zusammengefasst werden, da sie lokale Alternativen für die Kombination mit dem Angebot A1 bilden.²⁰ Für eine Lieferbeziehung zwischen zwei Angeboten können dabei zusätzliche Kosten für die Logistik anfallen.²¹

In diesem Zusammenhang muss darauf hingewiesen werden, dass nicht alle Angebote einer Kno- tengruppe auch Mitglied einer Kantengruppe sein müssen, die sich auf das Zwischenprodukt bezieht, welches aus dem zugrunde liegenden Prozessschritt der Knotengruppe resultiert. Dies ergibt sich aus der Einschränkung, dass eine Kante und somit eine (mögliche) Lieferbeziehung nur dann existent sein kann, wenn zusätzlich einerseits die geforderte Menge durch ein Angebot erfüllt wird und anderer- seits der Lieferzeitpunkt nicht nach dem zugehörigen Bedarfszeitpunkt liegt.²² In Abbildung 4.3 werden Knoten, Knotengruppen, Kanten und Kantengruppen als Bestandteile des Angebotsnetzes anhand eines Beispiels erläutert. Angebote, welche auf Basis eines divergierenden Prozessschrittes durch eine Kom- petenzzelle abgegeben werden, enthalten dabei mehrere aneinander gekoppelte Lieferbeziehungen, da durch ein solches Angebot mehr als ein Zwischenprodukt für mehr als einen folgenden Prozessschritt zur Verfügung gestellt und somit an andere Kompetenzzellen geliefert wird. Das Angebot ist dabei an die Auslieferung aller Zwischenprodukte gebunden.²³

4.1.3.2 Datenstruktur von Angeboten und Referenzen

Wie bereits beschrieben, wird in Angebote und Lieferbeziehungen unterschieden, welche durch Knoten und Kanten im Angebotsnetz repräsentiert werden. Da sowohl Angebote als auch Referenzen durch Komptenzzellen (auch in getrennter Form) abgegeben werden können, soll im Folgenden geklärt wer- den, welche Daten in Angeboten und welche Daten in Referenzen hinterlegt werden, um das Angebots- netz vollständig abzubilden.²⁴ Als Grundlage für diese Beschreibungen wird der Stand der informa- tionstechnischen Umsetzung des EVCM im Rahmen des Arbeitskreises Logistische Informationssysteme (LogIs) am Lehrstuhl für Produktionswirtschaft und Industriebetriebslehre an der Technischen Univer- sität Chemnitz verwendet.²⁵

Für die Identifikation und Einordnung eines Angebotes werden neben dem Identifikationswert für das Angebot zunächst Angaben über den zugrunde liegenden Prozessschritt eines Prozessplans (be- ziehungsweise Prozessvariantenplans), über die Zugehörigkeit des Angebotes zu einem Auftrag und über die angebotsgenerierende Kompetenzzelle benötigt. Aus diesen Informationen ist bereits die Ab- leitung eines Knotens im Angebotsgraphen möglich, welcher entsprechend dem Prozessschritt einer Knotengruppe zugeordnet wird. Jedes Angebot muss weiterhin eine Information darüber enthalten, ob es sich bei dem zugrunde liegenden Prozessschritt um einen Divergenzpunkt im Prozessplan handelt. Neben den bisher beschriebenen Status- und Identifikationsdaten werden in einem Angebot ebenso alle notwendigen Zielwerte verzeichnet, welche sich aus dem Preis, der Liefermenge, der Lieferwahrschein- lichkeit und dem Liefertermin ergeben. Zusätzlich wird die Angabe der Liefermenge erforderlich, über die das Angebot erstellt wurde.²⁶

Eine Referenz stellt eine mögliche Lieferbeziehung dar und muss daher zunächst die Information enthalten, welches Produkt mit welchem Angebot an eine andere Kompetenzzelle mit einem anderen Angebot geliefert wird. Aus diesem Grund enthält eine Referenz zunächst einen Identifikationswert für das Zwischen- beziehungsweise Endprodukt, das geliefert wird. Das durch eine Lieferbeziehung zu liefernde Produkt steht deshalb in Abhängigkeit der Lieferbeziehung und nicht des Angebotes, da bei divergierenden Prozessschritten mehrere Zwischenprodukte durch ein Angebot geliefert werden.

Weiterhin sind die Identifikationswerte für das Quell- und das Zielangebot der möglichen Lieferung enthalten. Zusätzlich werden in der Referenz der Bedarfstermin und die Bedarfsmenge des entspre- chenden Zwischenproduktes verzeichnet, wobei sich diese Daten restriktiv über die Kompetenzzelle definieren, an welche die Lieferung durchgeführt werden soll. Handelt es sich um Angebote, deren Kompetenzzellen den letzten Schritt in Wertschöpfungsrichtung ausführen und folglich die Lieferung des Endproduktes zum Ziel haben, wird der Identifikationswert für das Zielangebot auf einen künst- lich angelegten Startknoten gesetzt, welcher den Einstiegspunkt des Angebotsnetzes darstellt und somit Bestandteil jeder Angebotskombination ist, die eine Lösung des Problems sein kann.²⁷

4.1.3.3 ATP- und CTP-Angebote

Vor der Generierung von Angeboten durch eine Kompetenzzelle wird die interne Ablaufplanung durch- geführt, innerhalb welcher zunächst eine ATP-Prüfung erfolgt, die die maximale Menge des angefragten Produktes bestimmt, die zum Bedarfszeitpunkt durch eine Lagerentnahme für die Angebotsgenerie- rung zur Verfügung gestellt werden kann. Tritt der Fall ein, dass die zum Bedarfszeitpunkt verfügbare Menge aus dem Lagerbestand vollständig die Anfragemenge abdecken kann, wird ein Angebot für die Anfragemenge generiert.²⁸

Bei nicht ausreichender ATP-Menge muss eine CTP-Prüfung durchgeführt werden, welche die Produzierfähigkeit des Produktes in der angefragten Menge bis zum Bedarfszeitpunkt überprüft. Ergibt diese Prüfung ein positives Resultat, kann ebenfalls ein Angebot über die angefragte Menge generiert werden. Da in diesem Fall die geforderte Menge vor der Lieferung explizit für den Auftrag produziert werden muss, besteht allerdings die Möglichkeit, dass zusätzlich Vorprodukte benötigt werden, welche durch andere Kompetenzzellen geliefert werden müssen. Die Einholung entsprechender Angebote erfolgt dabei, wie bereits erläutert, über den rekursiven Aus- und Einrollvorgang.²⁹

Dem entgegen stehen Lieferungen, welche aus der ATP-Menge befriedigt werden. Da die angefragte Menge direkt aus einem Lagerbestand entnommen wird, ist kein weiterer Ausrollvorgang über mögliche Vorprodukte notwendig und die zugehörige Kompetenzzelle fasst sämtliche Prozessschritte bis zum entsprechend angefragten Zwischenprodukt zusammen.

4.1.4 Problemstellung bei der Kompetenzzellenauswahl

Die sechste Phase des EVCM-Phasenmodells beschreibt die Auswahl der richtigen Kompetenzzellenangebote. Dabei finden neben den Soft-Facts die Hard-Facts wesentliche Berücksichtigung. Bei Hard-Facts handelt es sich, wie bereits beschrieben, um betriebswirtschaftliche Kenngrößen, die in Form von quantifizierbaren Bewertungskriterien repräsentiert werden. Im Umfeld des Extended Value Chain Managements sollen dabei die Kenngrößen genutzt werden, die im Rahmen der Angebotsgenerierung durch die Kompetenzzellen erstellt werden.

Jedes Angebot beinhaltet einen Preis, eine Lieferwahrscheinlichkeit und einen Liefertermin. In diesem Zusammenhang entsteht zwischen dem Bedarfstermin einer zu beliefernden Kompetenzzelle beziehungsweise des Endkunden und der beliefernden Kompetenzzelle ein zeitlicher Puffer, wobei auch eine Just-In-Time-Lieferung denkbar ist.³⁰

4.1.4.1 Zulässige Lösungen

Im Rahmen der Kompetenzzellenauswahl muss zunächst feststehen, wie Angebote zu einer Problemlö- sung kombiniert werden müssen oder dürfen, um eine zulässige Lösung als Pfad durch das Angebots- netz zu erzeugen.

Zunächst ist dabei offensichtlich die Auswahl eines Angebotes über den Prozessschritt notwendig, der am Ende der Wertschöpfung steht und somit die Lieferung des angefragten Endproduktes zum Ziel hat. In diesem Zusammenhang gilt, dass falls durch dieses Angebot Zwischenprodukte benötigt werden, die durch andere Komptenzzellen zur Verfügung gestellt werden müssen, auch die Annahme von Angeboten über diese Zwischenprodukte notwendig wird. Dieses Prinzip gilt rekursiv für alle Angebote, welche auf diese Weise Bestandteil einer Lösung werden. Durch Einführung eines künstlichen Startknotens, der die Lieferung des Endproduktes als Restriktion beinhaltet, wie es in Abschnitt 4.1.3.2 beschrieben wurde, kann diese Definition vereinfacht werden zu:

1. Der künstliche Startknoten ist Bestandteil jeder Lösung.
2. Ein Bedarf, der durch ein beliebiges Angebot (Knoten) der Lösung besteht, muss durch ein ande- res Angebot erfüllt werden, das ebenfalls Bestandteil der Lösung ist. Dabei muss zwischen dem Knoten, der den Bedarf und dem Knoten, welcher die Lieferung beinhaltet, eine Referenz (Kante) bestehen, die ebenfalls Bestandteil der Lösung ist.

Somit müssen unter Umständen mehrere parallele Pfade bis zum Ende des Graphen verfolgt werden, wobei das Ende eines solchen Zweiges durch Blattknoten repräsentiert wird, welche keine Restriktionen über die Annahme von Angeboten über einzugehende Vorprodukte besitzen.³¹

4.1.4.2 Restriktionen durch divergierende Prozessschritte

In Abschnitt 4.1.2 wurde bereits erläutert, dass sowohl konvergierende als auch divergierende Teilprozesse im Prozessplan auftreten können. Dabei ergeben sich bei Vorhandensein divergierender Prozessschritte bei der Kombination verschiedener Angebote, die einer zulässigen Lösung zugeordnet werden, Restriktionen, welche bei der Pfadkonstruktion beachtet werden müssen.

Die Annahme eines Angebotes, dessen zugrunde liegender Prozessschritt einen Divergenzpunkt darstellt, ist an die Lieferung mehrerer Vor- beziehungsweise Zwischenprodukte gebunden. Aus diesem Grund gilt bei der Entscheidung für eine Referenz (Lieferbeziehung) und somit der Auswahlentscheidung eines Angebotes zu beachten, dass auch genau eine Lieferbeziehung des Angebotes für jedes übrige Zwischenprodukt ausgewählt wird. Auf diese Weise kann die Auswahlentscheidung über ein Angebot auch die Alternativenmenge von Angeboten nachfolgender Prozessschritte einschränken, da eine Kompetenzzelle mit einem Angebot nicht notwendigerweise in der Lage sein muss, alle anfragenden Kompetenzzellen eines nachfolgenden Prozessschrittes zu beliefern. Die entstehende Restriktion kann sich rekursiv über alle Stufen des Prozessplans fortsetzen.³²

4.1.4.3 Optimierung

Im Rahmen der Alternativenauswahl müssen die Lösungen anhand der bereits erwähnten Zielkriterien bewertet werden, um eine möglichst gute Alternative auswählen zu können. In diesem Zusammen- hang kann nicht davon ausgegangen werden, dass für jede mögliche Angebotskombination eine Be- wertung stattfinden kann, da durch die Menge der einzelnen Angebote und Belieferungsmöglichkeiten eine kombinatorische Explosion hinsichtlich des Lösungsraums erzeugt wird, welche die Enumeration aller Lösungen im Allgemeinen nicht zulässt.³³ Demnach ist ein mehrkriterielles Optimierungsverfah- ren notwendig, um diese Phase bewerkstelligen zu können. Da mehrere Kriterien in die Bewertung einfließen, stellt sich des Weiteren die Frage, wie stark welches Kriterium berücksichtigt werden soll. Hierbei dürfen mögliche Präferenzvorstellungen des Kunden nicht vernachlässigt werden.³⁴

4.2 Formalisierung des Problems

In den vergangenen Abschnitten wurde das Optimierungsproblem von Angebotsnetzen im Rahmen des Extended Value Chain Managements verbal und beispielhaft beschrieben. Mit dem Ziel, in späteren Kapiteln Lösungsalgorithmen für dieses Problem zu entwerfen, soll es zunächst als erweitertes Parallel Path Problem formalisiert werden.

4.2.1 Problemgraph

Das resultierende Problem kann in Form eines Parallel Path Problem dargestellt werden. Das formale Modell des Parallel Path Problems, welches bereits in [Fis04a] und [Kam06] beschrieben wurde, soll im Folgenden vorgestellt und in der Form erweitert und modifiziert werden, dass eine vollständige Abbildung des Problems sowie die Lösung mittels dynamischer Programmierung möglich ist.³⁵ Das Problem sei in Form eines gerichteten Graphen G dargestellt, welcher sich durch das Tupel

Abbildung in dieser Leseprobe nicht enthalten

definiert. Dabei beschreibt V die Menge aller Knoten, E die Menge aller gerichteten Kanten, K die Menge der Kantengruppen und S das Restriktionssystem der Kanten. Dabei sei die Knotenmenge V durch den Ausdruck

Abbildung in dieser Leseprobe nicht enthalten

definiert, wobei ein einzelner Knoten vi durch die eindeutige Nummer i definiert ist und o die zugeordnete Knotengruppe bestimmt. Die Divergenzpunkteigenschaft wird durch den Wahrheitswert ω repräsentiert. Die Menge aller Kanten sei durch die folgende Gleichung definiert.

Abbildung in dieser Leseprobe nicht enthalten

Die Notation[Abbildung in dieser Leseprobe nicht enthalten] bedeutet in diesem Zusammenhang, dass die Kante ausgehend von Knoten vi zum Knoten vj führt und somit von vi nach vj gerichtet ist, wobei keine Schlingen erlaubt sind. Die Richtung der Kanten steht der Wertschöpfung im Angebotsnetz entgegen³⁶ und orientiert sich am Bedarf eines Produktes beziehungsweise Vorproduktes. Die Variable q repräsentiert eine weitere Gruppierungsei- genschaft für Kanten, welche sich auf den im Angebotsnetz entstehenden Bedarf durch den Knoten vi bezieht, der von vj geliefert wird und beinhaltet einen Identifikationswert des zu liefernden Vor- be- ziehungsweise Endproduktes. Jede Kante besitzt eine Restriktion [Abbildung in dieser Leseprobe nicht enthalten] und ist einer Kantengruppe [Abbildung in dieser Leseprobe nicht enthalten]eindeutig zugeordnet. Die Menge der Kantengruppen sei hierbei durch die Gleichung

Abbildung in dieser Leseprobe nicht enthalten

formalisiert. Dabei ergibt sich in Zusammenhang mit der Definition der Kantenmenge, dass alle Kanten, welche Bestandteil einer Kantengruppe sind, den selben Startknoten vi besitzen müssen und lediglich hinsichtlich ihres Endknotens differieren können. Da ausgehend von einem Knoten mehrere Kantengruppen existieren können, werden diese durch den zusätzlichen Indexwert g eindeutig identifiziert.³⁷ Der Graph verfüge außerdem über einen fest definierten, künstlichen Startknoten[Abbildung in dieser Leseprobe nicht enthalten] der als Ein-stiegspunkt für die Optimierung dient sowie einer Menge von künstlichen Startkanten [Abbildung in dieser Leseprobe nicht enthalten]welche den Startknoten mit Knoten des Graphen verbinden. Diese künstlichen Konstrukte seien dabei nicht Bestandteil der Knoten- beziehungsweise Kantenmenge des Graphen G.³⁸

Abbildung in dieser Leseprobe nicht enthalten

(4.5)

Des Weiteren wird gefordert, dass der Graph über die Eigenschaften der Zyklenfreiheit und des Zusammenhangs verfügt, was durch die folgenden Gleichungen definiert sei.³⁹

Abbildung in dieser Leseprobe nicht enthalten

(4.6)

Die Zyklenfreiheit muss gefordert werden, um sicherzustellen, dass ein Angebot, welches durch einen Knoten im Graphen definiert wird, nicht entlang eines sequentiellen Pfades mehrmals erreichbar ist, um die mehrmalige Annahme eines Angebotes per Definition auszuschließen. Die Eigenschaft des Zu- sammenhangs basiert auf der Forderung, dass es sich um ein gültiges Problem handeln muss. Für jedes Angebot muss die Möglichkeit einer Annahme bestehen, ohne die automatische Schlussfolgerung der Pfadungültigkeit ziehen zu müssen. Falls mehrere nicht verbundene Substrukturen im Graphen existie- ren, besteht die Möglichkeit, dass ein Vorprodukt für ein Angebot aufgrund einer nicht existierenden Kante nicht gewählt werden kann und somit die Ungültigkeit des Angebotes und möglicherweise wei- terer Angebote nach sich zieht. Für einen Graph sollte daher die Erfüllbarkeit aller Abhängigkeiten von allen Knoten geprüft werden. Alle übrigen nicht mit dem künstlichen Startknoten direkt oder indirekt verbundenen Substrukturen können nach Abschluss dieser erfolgreichen Prüfung aus dem Graph ent- fernt werden, wobei ein zusammenhängender Graph die unmittelbare Folge ist. Somit ergibt sich die Forderung des Zusammenhangs als legitim.

Da der Graph sowohl hinsichtlich seiner Knoten als auch seiner Kanten gewichtet ist, müssen neben der Graphstruktur des Weiteren Kosten- beziehungsweise Nutzenfunktionen für alle Zielkriterien z existieren, welche die Kosten beziehungsweise Zielfunktionsbeiträge für eine Kante oder einen Knoten bestimmen. Diese seien formal wie folgt durch die Abbildungen

Abbildung in dieser Leseprobe nicht enthalten

(4.7)

mit z = 1, ..., Z beschrieben, wobei Z die Anzahl der zu optimierenden Ziele respektive Kriterien reprä- sentiert.⁴⁰

4.2.2 Restriktionssystem

Das Restriktionssystem ist nicht Bestandteil der eigentlichen Problemstellung des Parallel Path Pro- blems, ergibt sich allerdings implizit aus den Betrachtungen über divergierende Prozessschritte und wird explizit zur Lösung des Problems von den in den folgenden Kapiteln vorgestellten Algorithmen verwendet.⁴¹ Im Folgenden wird dieses System zunächst in formalisierter Weise näher detailliert. An- schließend wird gezeigt, wie konkrete Restriktionen in einer zugrunde liegenden Probleminstanz abge- leitet werden können.

4.2.2.1 Repräsentation des Restriktionssystems

Das Restriktionssystem eines Graphen G wird durch die Menge S mit den Elementen Rij beschrieben, welche einer Kante [Abbildung in dieser Leseprobe nicht enthalten] eindeutig zugeordnet sind und als Restriktionsvektor der Kante ei→j bezeich- net seien. Um das Konzept des Restriktionssystems definieren zu können, sollen zunächst einige Ele- mente dieses Systems geklärt werden. Das Konzept für die nachfolgend beschriebenen Attribute und Restriktionen wurde dabei dem booleschen Retrievals entlehnt und an die Bedürfnisse der Problem- struktur angepasst.⁴²

Attribute. Attribute, im Folgenden auch als elementare Restriktionsfunktionen bezeichnet, haben einen binären Wertebereich und seien als Funktion [Abbildung in dieser Leseprobe nicht enthalten]entweder positiver[Abbildung in dieser Leseprobe nicht enthalten] oder negativer [Abbildung in dieser Leseprobe nicht enthalten] Natur. Die Abbildung muss dabei im Definitionsbereich nicht einelementig sein, sondern bezieht sich vielmehr auf eine beliebige Teilmenge[Abbildung in dieser Leseprobe nicht enthalten]. Formal können diese Attribute wie folgt beschrieben werden.

(positives Attribut) (4.8)

(negatives Attribut)

Restriktion. Eine Restriktion Rij setze sich entweder aus der Verknüpfung mittels binärem XOR von ausschließlich positiven oder aus der Verknüpfung mittels binärem AND von ausschließlich negativen Attributen zusammen und kann formal wie folgt beschrieben werden, wobei m ∈ N ∨ {0}.

Abbildung in dieser Leseprobe nicht enthalten

Dabei gelte für m = 0, dass die Restriktion leer ist[Abbildung in dieser Leseprobe nicht enthalten]. Da sich eine Restriktion aus Attributen zusammensetzt, bildet sie analog zu einem Attribut eine Funktion mit einem binären Wertebereich in der Form[Abbildung in dieser Leseprobe nicht enthalten].

Eine Restriktion Rij kann einer Kante ei→j zugeordnet werden und beschreibt über den binären Funktionswert, ob die Kombination der zugeordneten Kante mit einer Kantenmenge E′ aufgrund von Rij (E′) = 1 erlaubt oder aufgrund von Rij (E′) = 0 verboten ist. In diesem Zusammenhang gelte für [Abbildung in dieser Leseprobe nicht enthalten]immer R(E′) = 1, da die Kantenkombinationen zwischen nicht restriktionsbelasteten Kanten unproblematisch sind.

Restriktionsvektor. Da eine Kante ei→j über mehrere Restriktionen verfügen kann, werden dieser Kante nicht einzelne Restriktionen, sondern Vektoren von Restriktionen Rij zugeordnet. Zwar ist eine Zusammenfassung mehrerer Restriktionen durch eine AND-Verknüpfung zu einer Gesamtrestriktion prinzipiell möglich, jedoch aus informationstechnischen Gründen für positive Restriktionen nicht sinn- voll.⁴³ Negative Restriktionen können dagegen durch ein logisches AND zu einer Restriktion zusam- mengefasst werden. Ein Restriktionsvektor kann darauf aufbauend in der Form

Abbildung in dieser Leseprobe nicht enthalten

beschrieben werden, wobei die Parameter q1, ..., qm mit m ∈ N die einzelnen Restriktionen abgrenzen und identifizieren. Alternativ zu dieser Darstellung kann ein Restriktionsvektor leer sein, falls einer Kante keine Restriktion zugeordnet wurde. Abschließend kann die Menge S zu

Abbildung in dieser Leseprobe nicht enthalten

definiert werden, die das Restriktionssystem des Graphen beschreibt und alle Restriktionsvektoren aller Kanten beinhaltet.

4.2.2.2 Ableitung der Restriktionen

Aus der Definition des Prozessplans und einem zugehörigen Angebotsnetz kann das Restriktionssystem, welches über alle Kanten definiert ist, automatisch aus dem Angebotsgraphen abgeleitet werden. Es wurde bereits erläutert, dass Restriktionen nur dann notwendig werden, wenn das Angebotsnetz divergierende Prozessschritte beinhaltet. Für einen Prozessschritt, aus welchem mehr als ein Vorprodukt resultiert, muss bei der Annahme des Angebots sichergestellt werden, dass sämtliche Lieferungen differenter Vorprodukte durchgeführt werden können.

Algorithmus 1 Automatisierte Generierung des Restriktionssystems eines Angebotsnetzes

Abbildung in dieser Leseprobe nicht enthalten

Anmerkungen

Die Funktion MAKECONSTRAINTS erzeugt automatisch alle nichtleeren Restriktionsvektoren aller Kanten, deren Endpunkt ein Knoten auf Basis eines divergierenden Prozessschrittes ist. Die Funktion PREPRODUCT stellt eine Hilfsfunktion dar und ergibt den Identifikationswert q eines Vorproduktes, welches bei Annahme einer Kante ei→j von Knoten vj zu Knoten vi geliefert wird und nach Definition der Kantenmenge informativer Bestandteil einer Kante ist.

Die Lieferung eines Vorproduktes wird durch eine Kante des Graphen determiniert. Es ergibt sich damit, dass für jedes Vorprodukt, das durch ein Angebot A geliefert wird, genau eine Kante angenom- men werden muss, die als Startpunkt den Knoten vA aufweist. Bei Auswahl einer solchen Kante ver- bietet sich die gleichzeitige Annahme aller anderen Kanten, welche zu einem anderen zu vA ungleichen Knoten der gleichen Knotengruppe führen und als alternativ zur ausgewählten Kante betrachtet werden können. Dabei sind alle Kanten alternativ, die ebenfalls als Divergenzpunkt markiert sind. Nicht als Divergenzpunkt markierte Knoten stellen ergänzende Teillieferungen von Fehlmengen für die Vervollständigung eines Angebotes dar.⁴⁴

Aus diesen Überlegungen kann ein Algorithmus entwickelt werden, der in der Lage ist, automatisch auf Basis dieser Informationen das vollständige Restriktionssystem des Graphen abzuleiten. Dieser wird in Algorithmus 1 in Form von Pseudo-Code dargestellt.

4.2.3 Lösungskonstruktion und Problemstellung

Lösungen des Problems stellen parallele Pfade π ∈ Π dar, die nachfolgend formal definiert werden sollen. Dabei repräsentiere Π die Lösungsmenge des Problemgraphen G. Die Definition des Pfadkonstruktes erfolgt rekursiv. Die nachfolgenden Ausführungen basieren analog zu den Beschreibungen über den Problemgraphen auf den Ausführungen von FISCHER ET AL.⁴⁵ Nachfolgend soll die bisherige Definition modifiziert und erweitert werden.

Ein Pfad π setze sich zusammen aus Knoten v und Kanten e des Graphen G, wobei der Knoten vStart zusätzlich Element jedes Pfades sei. Für die Kombination der Knoten- und Kantenmenge des Pfades gelte dabei, dass aus jeder Kantengruppe git beziehungsweise gStart, welche von einem Knoten vi ∈ π oder vStart ausgeht, genau eine Kante[Abbildung in dieser Leseprobe nicht enthalten]beziehungsweise [Abbildung in dieser Leseprobe nicht enthalten] sowie der zugehörige Knoten vj ebenfalls Bestandteil des Pfades sei. Dieses Konzept soll zunächst formalisiert werden. Ein Pfad π sei definiert durch

Abbildung in dieser Leseprobe nicht enthalten

mit

Abbildung in dieser Leseprobe nicht enthalten

als Beziehungen und

Abbildung in dieser Leseprobe nicht enthalten

als (aufgelöste) Pfadrestriktionenanalog zur Darstellung von Kantenrestriktionen aus Abschnitt 4.2.2, welche für die Optimierungsalgorithmen in den späteren Kapiteln benötigt wird.⁴⁶ Formal ergibt sich ein gültiger Pfad, wenn die folgenden Bedingungen erfüllt sind:

Abbildung in dieser Leseprobe nicht enthalten

Aus dieser Definition ergibt sich rekursiv, dass alle Vorprodukte, welche von einer Kompetenzzelle zu einem Prozessschritt s benötigt werden, durch Angebote erfüllt werden müssen, um das Angebot für den Prozessschritt s von dieser Kompetenzzelle annehmen zu können, damit der Pfad die Eigenschaft der Gültigkeit besitzt, wobei keine Restriktion verletzt werden darf.

Ziel der Optimierung ist es, einen Pfad [Abbildung in dieser Leseprobe nicht enthalten] zu bestimmen, welcher optimale Zielfunktionswerte hinsichtlich der Funktionen[Abbildung in dieser Leseprobe nicht enthalten] aufweist. Diese Funktionen basieren auf den Funktionen fze und v und werden in Abschnitt4.3 gesondert behandelt.

4.3 Zielsetzungen der Optimierung

Jedes Angebot, welches von einer Kompetenzzelle zu einem Prozessschritt abgegeben wurde, besitzt die ökonomischen Attribute Preis, Lieferwahrscheinlichkeit und Liefertermin, welche als Zielkriterien der Optimierung zugrunde liegen sollen. Im Folgenden sollen die angebotsübergreifenden Zielfunktionen dieser Attribute für Lösungen des kombinatorischen Problems entwickelt werden, um Pfade durch den Angebotsgraphen nach diesen Attributen bewerten zu können.

4.3.1 Preis

Der Preis stellt ein Attribut eines Angebotes dar und repräsentiert die Kosten, welche bei der Durchführung des Prozessschrittes durch die angebotsabgebende Kompetenzzelle erzeugt werden.⁴⁷ Dies beinhaltet nicht die Kosten anderer vorgelagerter Prozessschritte oder eingehender Vorprodukte, welche durch andere Kompetenzzellen geliefert werden.

Da angenommen werden kann, dass ein Kunde des Netzwerkes einen möglichst niedrigen Gesamt- preis anstrebt, stellt der Preis ein zu minimierendes Zielkriterium dar. Die Aggregation über den Pfad erfolgt additiv über alle Pfadbestandteile, welche sich aus Kanten (Logistik) und Knoten (Herstellung) des Graphen ergeben.⁴⁸ Die Zielfunktion des Gesamtpreises FPreis kann daher anhand der Gleichung

Abbildung in dieser Leseprobe nicht enthalten

definiert werden.

4.3.2 Lieferwahrscheinlichkeit

Die Lieferwahrscheinlichkeit stellt die Wahrscheinlichkeit dar, mit der eine Kompetenzzelle ein abgegebenes Angebot bei Annahme korrekt zu den angegebenen Konditionen liefert. Sie wird definiert im Intervall [0, 1], wobei der Wert 0 der Lieferunfähigkeit und der Wert 1 der sicheren Lieferung der angebotenen Menge zum entsprechenden Termin entspricht.⁴⁹

Da jede Kompetenzzelle, welche abhängig von weiteren Prozessschritten anderer Kompetenzzellen ist, nur dann zu den angegebenen Konditionen liefern kann, wenn alle übrigen Kompetenzzellen eben- falls zu den angegeben Konditionen liefern, ergibt sich für die Einhaltung der Konditionen für die Lie- ferung des Endproduktes, dass alle Konditionen aller beteiligten Komptenzzellen eingehalten werden müssen. Die Gesamtlieferwahrscheinlichkeit einer kompletten Angebotskombination sollte sich dem- nach aus dem Produkt aller Lieferwahrscheinlichkeiten der einzelnen zugehörigen Angebote ergeben. Da eine möglichst hohe Lieferwahrscheinlichkeit anzustreben ist, handelt es sich um ein zu maximie- rendes Zielkriterium. Die Zielfunktion der Lieferwahrscheinlichkeit FLwk kann daher anhand der Glei- chung 4.16 definiert werden.⁵⁰

Abbildung in dieser Leseprobe nicht enthalten

4.3.2.1 Präzisionsmangel in der Wertrepräsentation

Diese multiplikative Verknüpfung stellt jedoch hinsichtlich der Umsetzung in ein informationstechnisches System ein Problem dar, welches zunächst beschrieben werden soll. Anschließend werden zwei Möglichkeiten vorgestellt und bewertet, wie dieses Problem gelöst werden kann.

Algorithmus 2 Testalgorithmus zur Analyse der Präzision des Datentyps double

Abbildung in dieser Leseprobe nicht enthalten

Anmerkungen

Die Variable P entspricht den testenden Datentyp (hier double). Der Wert n fungiert als Zählvariable, der so oft um 1 inkrementiert wird, bis die Abbruchbedingung erfüllt ist.

Da es sich bei diesem Kriterium um Wahrscheinlichkeiten handelt, kann ein Wertebereich im Inter- vall [0, 1] angenommen werden. Die Produktbildung nach Gleichung 4.16 führt bei großen Pfadlängen mit vielen Angeboten, deren Lieferwahrscheinlichkeit ≤ 1 beträgt, zu einer Konvergenz gegen den Wert 0. Da die informationstechnische Umsetzung der Optimierungsalgorithmen in der Programmiersprache C# erfolgen soll, wurde diese Sprache zur Evaluierung der Fragestellung nach der verfügaren Genauigkeit bei der Darstellung sehr kleiner Zahlen verwendet.⁵¹

Im Rahmen dieser Analyse wurde untersucht, bei welcher Anzahl von Faktoren (n) jeweils der gleichen Wahrscheinlichkeit (x) keine konsistenten Vergleiche zwischen den Produkten P1 = xn und P2 = xn−¹ mehr möglich sind, sondern der Test auf Gleichheit positiv ausfällt.

Dieser Test wurde sowohl für den Datentyp double als auch für den Datentyp decimal durchgeführt. Der Datentyp double stellt eine Rundungsfehler zulassende Gleitkommazahl der Größe von 64 Bit mit doppelter Genauigkeit nach dem Standard IEEE 754 dar, während der Datentyp decimal eine Festkommazahl mit der Ganzzahllänge von 96 Bit repräsentiert und keine Rundungsfehler zulässt.⁵² In Algorithmus 2 wird die zugehörige Programmlogik veranschaulicht. Die Ergebnisse dieser Analyse finden sich in den Diagrammen von Abbildung 4.4.

Es wird deutlich, dass insbesondere bei kleinen Einzelwahrscheinlichkeiten nur eine Aggregation von sehr wenigen Komponenten möglich ist, um konsistente Vergleiche zwischen den Zielwerten der Lieferwahrscheinlichkeit durchführen zu können. Wird die Pfadlänge n überschritten, können keine Vergleiche zwischen Lösungen und somit auch keine Prüfung auf Dominanz mittels des Optimierungsalgorithmus durchgeführt werden. Die multiplikative Verknüpfung der Wahrscheinlichkeiten scheint demnach mangels eines präzisen Datentyps nicht geeignet. Im Anschluss werden zwei unterschiedliche Vorgehensweisen zur Bewältigung dieses Problems vorgestellt.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4.4: Konvergenzreihen bei der Multiplikation vieler kleiner Werte für C#-Datentypen

Das obere Diagramm zeigt die Konvergenzreihe des Datentyps decimal, während das untere die Konvergenzreihe für den Datentyp double aufzeigt. Es ist ersichtlich, dass auch bei der hohen Genauigkeit des double-Datentyps nur eine verhältnismäßig geringe Potenz mit sehr kleinen Wahrscheinlichkeitswerten als Basis zu vergleichbaren Ergebnissen führen.

4.3.2.2 Numerischer Konzentrationsoperator

Da die multiplikative Verknüpfung der Einzelwahrscheinlichkeiten als Aggregationsfunktion für die Lieferwahrscheinlichkeit angestrebt wird, wurde eine Idee von Modifikatoren dem Konzept der Fuz- zy Logic entlehnt. In der Fuzzy Logic können linguistische Dilatations- und Konzentrationsoperatoren auf Zugehörigkeitsfunktionen unscharfer Mengen angewendet werden, um die Zugehörigkeit von Ele- menten zu einer Menge entweder numerisch zu verstärken oder abzuschwächen. Eine Möglichkeit für die Umsetzung eines linguistischen Dilatationsoperators, welcher eine numerische Konzentration be- wirkt, bildet das Potenzieren mit einem Wert α mit 0 < α < 1.⁵³ Wird die Lieferwahrscheinlichkeit als unscharfe Menge mit der Zugehörigkeitsfunktion der Form µ (x) = x betrachtet, kann, um einer Null- konvergenz der Gesamtlieferwahrscheinlichkeit entgegen zu wirken, eine Zielfunktion nach Gleichung

Abbildung in dieser Leseprobe nicht enthalten

Durch die Wurzel einer Wahrscheinlichkeit mit einem Parameter β ∈ R mit β > 1 können sehr klei- ne Wahrscheinlichkeiten deutlich verstärkt werden. Da der Operator für jede Einzelwahrscheinlichkeit angewendet wird und diese multiplikativ miteinander verknüpft werden, bleibt die Vergleichskonsis- tenz hinsichtlich der Präferenzordnung zwischen verschiedenen Lösungen erhalten.⁵⁴ Dennoch beein- flusst die Anwendung dieser Methode die Vergleichskonsistenz negativ. Insbesondere bei sehr hohen Parametern β werden sehr kleine Werte deutlich verstärkt. Hinsichtlich der Gesamtwahrscheinlichkeit ergibt sich dabei zwangsläufig das Phänomen, dass sich das Verhältnis zwischen den Zielfunktionswer- ten zweier Lösungen bei Anwendung der Funktion in Gleichung 4.16 im Vergleich zur Anwendung der Funktion aus Gleichung 4.17 ändert. Hierbei nähern sich die Zielfunktionswerte mit steigendem β im- mer mehr einem gleichen Wert und unterscheiden sich möglicherweise nur noch so gering, dass durch die Ungenauigkeit der Fließkommaarithmetik des Datentyps double keine Unterscheidung mehr mög- lich ist. Ein weiteres Problem bilden dabei Lieferwahrscheinlichkeiten mit dem Extremwert 1, da durch die numerische Konzentration keine Veränderung erfolgt.⁵⁵ Durch eine hohe numerische Konzentrati- on aller Werte würde demnach eine verhältnismäßig schlechte Bewertung für diesen Extremwert erfol- gen.⁵⁶ Des Weiteren erweisen sich wertende Vergleiche zwischen Lösungen als schwierig, da kein Faktor ermittelt werden kann, der angibt, um wie viel besser oder schlechter eine Lösung im Vergleich zu einer anderen zu betrachten ist. Aus den genannten Gründen ist dieser Operator nur bedingt zur Aggregation der Lieferwahrscheinlichkeit geeignet.

4.3.2.3 Technische Anpassung durch den Datentyp lFloat

Eine weitere Möglichkeit zur Lösung des Problems der Aggregation der Lieferwahrscheinlichkeit stellt die technische Anpassung der Entwicklungsumgebung an das Problem dar. Da die Standard-Datentypen für die Darstellung sehr kleiner Werte nicht geeignet sind, muss ein Datentyp geschaffen werden, wel- cher problemlos die geforderte Genauigkeit erfüllen kann. In diesem Zusammenhang ist das Grund- konzept einer Gleitkommazahl, das beispielsweise durch den Datentyp double repräsentiert wird, als Ausgangspunkt für einen sehr präzisen Typ mit der Genauigkeit einer festen Ziffernfolge und einem sehr großen Wertebereich vorstellbar.

Nach dem Standard IEEE 754 setzt sich eine binäre Fließkommazahl aus einer Mantisse m, einem vorzeichenbehafteten Exponenten x und einem Vorzeichenbit s für die Mantisse zusammen. Die einzelnen Bestandteile werden in binärer Form als Bitfolge repräsentiert.⁵⁷ Abbildung 4.5⁵⁸ zeigt eine schematische Darstellung eines allgemeinen Fließkommadatentyps.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4.5: Schematische Darstellung eines Fließkommadatentyps

Die Repräsentation einer Zahl r erfolgt hierbei in der Form [Abbildung in dieser Leseprobe nicht enthalten]

[...]

---

¹ Vgl. [For06, S. 1f.].

² Vgl. [DF06], [Log06].

³ Vgl. [Tei02].

⁴ Vgl. [Tei02, S. 481ff.].

¹ Im Rahmen dieser Arbeit werden jedoch ausschließlich Graphen mit endlichen Mengen betrachtet.

² Abkürzung für die engl. Bezeichnung »directed graph«.

³ In dieser Arbeit wurde die Notation abweichend in der Form ea→b gewählt.

⁴ Vgl. [Die00, S. 2f. i.V.m. S.25f.] und [Jun94, S. 18f].

⁵ Vgl. [Kla99, S. 40f.].

⁶ Vgl. [Kla99, S. 47].

⁷ Vgl. [Die00, S. 10f.].

⁸ Vgl. [BJ06, S. 6], [Dom97, S. 9f.].

⁹ Vgl. [Wag03, S. 138].

¹⁰ Vgl. [Weg03, S. V und S. 3f.].

¹¹ Vgl. [Weg03, S. V und S. 3f.].

¹² Vgl. [Weg03, S. 21]. Dies begründet sich auch auf der erweiterten churchschen These, welche besagt, dass alle Rechnermodelle sich gegenseitig mit polynomiellen Aufwand simulieren können und somit Probleme unabhängig vom gewählten Rechnermodell sind. Vgl. [Weg03, S. 22-25].

¹³ Vgl. [Weg03, S. 21], [Wag03, S. 138].

¹⁴ Vgl. [Wag03, S. 34].

¹⁵ Vgl. [Wag03, S. 34].

¹⁶ Vgl. [Wag03, S. 35f.].

¹⁷ Wobei auch logarithmische Komplexitätsmaße aufgrund von log n ≤ n als klassenzugehörig betrachtet werden. Vgl. [Sch01, S. 152f.].

¹⁸ Dabei sollte jedoch auch beachtet werden, dass nach dieser Definition die Komplexität O(n100 ) oder größer ebenfalls polynomieller Natur ist, jedoch kaum als effizient lösbar betrachtet werden kann. Vgl. [Grö05, S. 264].

¹⁹ Vgl. [Weg03, S. 44f.].

²⁰ Die Antwort auf die Frage, ob P ⊂ NP und somit P = NP oder P = NP gilt, zählt zu den 7 wichtigsten ungelösten Problemen der Mathematik, auf dessen Lösung ein Preisgeld von 1 Mio. $ ausgesetzt wurde. Vgl. [Grö05, S. 268].

²¹ Vgl. [Sch01, S. 153ff.].

²² Vgl. [Weg03, S. 71].

²³ Vgl. [Weg03, S. 65f.].

²⁴ Vgl. Beweis in [Coo71].

²⁵ Vgl. [Weg03, S. 82].

²⁶ Vgl. [Kis03, S. 4ff.].

²⁷ Vgl. u.a. [Tei02, S. 319], [Bom93, S. 431], [Kis03, S. 6].

²⁸ Vgl. [Bom93, S. 431], [Kis03, S. 6].

²⁹ Vgl. [Bom93, S. 432].

³⁰ Vgl. [Kis03, S. 6ff.].

³¹ Vgl.[Weg03, S. 17].

³² Vgl. [Kel04, S. 491].

³³ Vgl. [Kel04, S. 413f.].

³⁴ Vgl. [Kel04, S. 487ff.].

³⁵ Vgl. [Hop00, S. 373], [Wag03, S. 90f.].

³⁶ Ein Hamiltonkreis ist ein Kreis durch den Graphen, welcher alle Knoten des Graphen enthält. Vgl. Abschnitt 2.1.2 i.V.m. [Die00, S. 211].

³⁷ Vgl. [Hop00, S. 373], [Rei90, S. 247f.] sowie [Sch01, S. 165].

³⁸ Die nachfolgenden formalen Beschreibungen entstammen [Kal97, S. 214f.].

³⁹ Vgl. [Wag03, S. 117], [Sch01, S. 163., S. 178f.].

⁴⁰ Vgl. [Wag03, S. 117].

⁴¹ Vgl. [Dij59].

⁴² Vgl. [Wag03, S. 117] sowie [Flo62] und [War62].

¹ Vgl. ähnliche Darstellungen in [Zim91, S. V], [Rot98, S. 17], [Zim91, S. V] und [Kam06, S. 20].

² Eine gute Übersicht findet sich beispielsweise in [Bam96, S. 43].

³ Diese Problematik wird auch als Dilemma der Ablaufplanung bezeichnet. Vgl. [Käs04, S. 174].

⁴ Vgl. Kapitel 4.

⁵ Abkürzung für die engl. Bezeichnung »Single Objective Problem«.

⁶ Abkürzung für die engl. Bezeichnung »Multi Objective Problem«.

⁷ Vgl. [Tei01, S. 315f.].

⁸ Vgl. [Kle02, S. 372].

⁹ Vgl. [Bam96, S. 46f.], [Käs04, S. 173f.].

¹⁰ Vgl. [Dom91, S. 45].

¹¹ Symmetrische Komplementarität beschreibt eine wechselseitige Komplementarität zwischen mehreren Zielen. Vgl. [Bam96, S. 47].

¹² Vgl. [Dom91, S. 45].

¹³ Vgl. [Han02, S. 50].

¹⁴ Vgl. [Han02, S. 79].

¹⁵ Vgl. [Mer02, S. 113] und [Mie99, S. 10ff.].

¹⁶ Vgl. [Mer02, S. 113] und [Mie99, S. 10ff.].

¹⁷ Vgl. [Mer02, S. 113].

¹⁸ Dieses Konstrukt wird beispielsweise im Compromise Programming (Abschnitt 3.4.6) benötigt. Auch die in Kapitel 7 entwickelten hybriden Methoden greifen teilweise auf diese Punkte zurück.

¹⁹ Vgl. [Ehr05, S. 34], [Mie99, S. 15f.].

²⁰ Vgl. [Ehr05, S. 34], [Mie99, S. 15f.] i.V.m. [Dom91, S. 45].

²¹ Vgl. [Han98, S. 20].

²² Vgl. [Han98, S. 20], angepasst für ein Minimierungsproblem.

²³ Vgl. [Mie99, S. 16f.], [Yoo95, S. 38].

²⁴ Vgl. [Hwa81, S. 2f.] sowie [Ruh04, S. 10] und [Zim91, S. 25]. Einen guten Überblick über Anwendungsmöglichkeiten und Verfahren geben [Hwa79] für MODM und [Hwa81] für MADM.

²⁵ [Web93, S. 11]

²⁶ Vgl. [Zim91, S. 11 i..V.m. S. 25].

²⁷ Vgl. [Ant94, S. 14] i.V.m. [Ruh04, S. 10].

²⁸ Vgl. [Zim91, S. 25].

²⁹ Vgl. [Web93, S. 15], [Zel73].

³⁰ Angelehnt an [Ant94, S. 13].

³¹ Vgl. [Ruh04, S. 10f.].

³² Vgl. [Hwa81, S. 24f.], [Yoo95, S. 17].

³³ Vgl. [Yoo95, S. 44].

³⁴ Vgl. Methode der gewichteten Summe in Abschnitt 3.4.3 und Fuzzy Decision Making in Abschnitt 3.4.5.

³⁵ Vgl. Klassen in [Mie99, S. 63f.], auch [Zim91, S. 30f.].

³⁶ Vgl. [Mie99, S. 63f.], [Coe02, S. 29f.].

³⁷ Vgl. Ausführungen zu dieser Thematik in [Mie99, S. 132].

³⁸ Vgl. [Mie99, S. 132].

³⁹ Angelehnt an [Coe02, S. 30]. Vgl. hierzu auch [Mie99, S. 115]. GAGNÉ und GRAVEL verwenden ein solches Vorgehen beispielsweise in Kombination mit einem ACO-Verfahren. Vgl. [Gag04].

⁴⁰ Siehe Seite 22.

⁴¹ Vgl. [Hei99, S. 60].

⁴² Vgl. Compromise Programming in [Zel73] sowie Abschnitt 3.4.6 und TOPSIS in [Yoo95, S.38f.].

⁴³ Vgl. Abschnitte 3.4.1 und 3.4.2.

⁴⁴ Angelehnt an [Coe02, S. 30]. Vgl. hierzu auch [Mie99, S. 77].

⁴⁵ Vgl. Definition in Abschnitt 3.2.1.

⁴⁶ Vgl. Ausführungen zu Paretokriterium in Abschnitt 3.2 auf Seite 13.

⁴⁷ Vgl. [Mey04, S. 46f.].

⁴⁸ Vgl. Ausführungen zu den Verfahren in Abschnitt 3.4.

⁴⁹ Nähere Informationen in [Yoo95].

⁵⁰ Vgl. [Mer02, S. 111ff.] und [Gun04, S. 118ff.].

⁵¹ Siehe beispielsweise die Probleme der Methode der gewichteten Summe in Abschnitt 3.4.3 auf der nächsten Seite.

⁵² Vgl. [Neu93, S. 136], [Dom91, S. 45f.].

⁵³ Es muss hierbei darauf hingewiesen werden, dass die Optimalität bezüglich Ψ2 nicht für das ursprüngliche Problem, sondern ausschließlich im beschränkten Bereich gelten muss. Vgl. [Neu93, S. 136].

⁵⁴ Vgl. [Neu93, S. 136].

⁵⁵ Vgl. diese und weiterführende Kritik in [Mie99, S. 120], [Coe02, S. 63] und [Bam96, S. 52f.].

⁵⁶ Vgl. [Dom91, S. 46].

⁵⁷ Vgl. [Dom91, S. 46].

⁵⁸ Vgl. [Zim91, S. 62f.], [Coe02, S. 45], [Kle02, S. 372], [Rot98, S. 64f.].

⁵⁹ Vgl. [Kle02, S. 372f.].

⁶⁰ Vgl. [Gun04, S. 119].

⁶¹ Vgl. [Kle02, S. 373] sowie die Normierung in den Zugehörigkeitsfunktionen bei der Fuzzy-Nutzwertanalyse in [Rot98, S. 226] und die Normierung beim Compromise Programming in [Coe02, S. 31].

⁶² Siehe Seite 14.

⁶³ Der Fall der Minimierung stellt dabei die Inversion von Gleichung 3.12 dar.

⁶⁴ Vgl. [Ber05, Abschnitt 2.1].

⁶⁵ Vgl. [Das97, S. 63ff.].

⁶⁶ Vgl. [Das97, S. 63ff.].

⁶⁷ Vgl. [Gun04, S. 119].

⁶⁸ Vgl. [Gun04, S. 119].

⁶⁹ Vgl. [Saa94].

⁷⁰ Vgl. [Saa94, S. 25ff.], [Web93, S. 84].

⁷¹ Quelle: [Saa94, S. 26].

⁷² Vgl. [Tei02, S. 265ff.], [Web93, S. 89ff.].

⁷³ Vgl. [Tei02, S. 265].

⁷⁴ Die bei f verwendete Normierung ist analog zur Methode der gewichteten Summe in Abschnitt 3.4.3.

⁷⁵ Vgl. [Web93, S. 73ff.].

⁷⁶ Vgl. [Zad65].

⁷⁷ Nähere Informationen über die Theorie der unscharfen Mengen finden sich beispielsweise in [Zad65] und [Tra93].

⁷⁸ Vgl. [Ber00, S. 25].

⁷⁹ Vgl. [Ber00, S. 25f.].

⁸⁰ Vgl. [Ber00, S. 25ff.].

⁸¹ Vgl. [Bel70, S. 148f.] und [Ber00, S. 26f.].

⁸² Vgl. u.a. [Bel70, S. 149], [Ber00, S. 27], [Böh93, S. 32ff.] und [Tra93, S. 37f.].

⁸³ Vgl. u.a. [Bam96, S. 108] und [Zim97, S. 276f.]. Siehe auch: Indifferenzkurven in Abschnitt 3.3.1.3.

⁸⁴ Eine ähnliche Darstellung findet sich bei [Ber03, S. 3f.].

⁸⁵ Vgl. [Hil97, S. 229f.].

⁸⁶ Vgl. [Neu93, S. 141].

⁸⁷ Vgl. [Neu93, S. 141].

⁸⁸ Vgl. [Hil97, S. 235].

⁸⁹ Vgl. [Mie99, S. 67f.]. In [Dom91, S. 47f.] wird dennoch von Goal Programming gesprochen.

⁹⁰ Vgl. [Pro03, S. 359f.], [Gag04, S. 27].

⁹¹ Vgl. [Mie99, S. 115].

⁹² Solche zusätzlichen Informationen können beispielsweise aus dem positiven und negativen Idealpunkt oder auch zusätzlich dem Nadir-Punkt des Zielraums bestehen. Diese Punkte wurden bereits in Abschnitt 3.2.3 auf Seite 14 vorgestellt.

⁹³ Vgl. Abschnitt 3.3.3.

⁹⁴ Vgl. Abschnitt 3.1.

⁹⁵ Die Visualisierung ist hierbei jedoch im Rahmen eines Diagramms auf Probleme mit drei Zielkriterien beschränkt, da jedes Ziel einer räumlichen Dimension des Diagramms entspricht.

⁹⁶ Vgl. [Kam06, S. 33f.].

⁹⁷ Vgl. Abschnitt 3.3.3.2.

⁹⁸ Vgl. Anwendungen bei [Ire01] beziehungsweise [Mer02, S. 111ff.] sowie Abschnitt 6.3.3 auf Seite 97.

¹ [Tei02, S. 230]

² Quelle: [Tei02, S. 271].

³ Vgl. [Tei02].

⁴ Vgl. [For06, S. 19].

⁵ Vgl. [Tei02, S. 221], [Fis03, S. 61] und [Kam06, S. 43].

⁶ Vgl. [Tei02, S. 221].

⁷ Diese zentrale Datenbank wird durch den so genannten Informationstechnischen Modellkern (IMK) des EVCM realisiert. Vgl. [Zim05, S. 3f.].

⁸ Vgl. [Kam06, S. 43], [For06, S. 20], [Tei02, S. 271ff.].

⁹ Vgl. [Tei02, S. 222ff.], [For06, S. 20f.].

¹⁰ Vgl. [For06, S. 20f.], [Fis03, S. 62], [Tei02, S. 224].

¹¹ Vgl. [Tei02, S. 433ff., 484f.], [For06, S. 22ff.].

¹² Vgl. [For06, S. 22f.], [Fis03, S. 62f.].

¹³ Vgl. [For06, S. 23f.], [Zim05, S. 3].

¹⁴ Vgl. [Tei02, S. 482].

¹⁵ Andererseits ist auch eine Erweiterung der in den folgenden Kapiteln vorgestellten Verfahren für Prozessvariantenpläne denkbar.

¹⁶ Vgl. [Kam06, S. 43] i.V.m. [Käs04, S. 83f.].

¹⁷ Vgl. [Kam06, S. 46].

¹⁸ Vgl. [Kam06, S. 46].

¹⁹ Vgl. Ausführungen in [Kam06, S. 45ff.] sowie [Fis04a, S. 517ff.].

²⁰ Vgl. Knoten- und Kantengruppenkonstrukt in [Fis04a, S. 518f.], [Kam06, S. 48f.].

²¹ Vgl. [Kam06, S. 45 i.V.m. S. 52].

²² Vgl. [Tei02, S. 487], [Kam06, S. 50].

²³ Vgl. [Kam06, S. 46].

²⁴ Vgl. hierzu das Konzept der ähnlichen Anfragen in [For06, S. 71f.].

²⁵ Vgl. [Log06].

²⁶ Vgl. [For06, S. 58f.], [Kam06, S. 53]. Siehe auch: Klassenstruktur des Angebotes in [Kam06, S. 71].

²⁷ Vgl. Ausführungen in [Kam06, S. 53]. In Abbildung 4.3 wird dieser Knoten durch die künstliche Kantengruppe A (Endprodukt) repräsentiert.

²⁸ Vgl. [Zsc04, S. 67f.], [Zsc05, S. 300f.], [Tei02, S. 735f., S. 380].

²⁹ Vgl. [Tei02, S. 380ff.].

³⁰ Vgl. [Kam06, S. 45f.], [Tei02, S. 372f.].

³¹ Analog zur formalen Definition in Abschnitt 4.2.3. Ähnliche Ausführungen finden sich auch bei [Fis04a, S. 517ff.] sowie [Kam06, S. 45ff.].

³² Vgl. Problembeschreibung in [Kam06, S. 51f.].

³³ Vgl. Beweis der NP-Vollständigkeit des Problems in Abschnitt 4.5 auf Seite 57.

³⁴ Aus diesem Grund wurde ursprünglich das AHP-Verfahren zu mehrkriteriellen Bewertung angestrebt. Vgl. [Tei02, S. 262].

³⁵ Die folgenden Darstellungen basieren auf [Fis04a, S. 517ff.] und [Kam06, S. 53].

³⁶ Diese Repräsentationsform erweist sich als sinnvoll, da die Lösungskonstruktion der vorgestellten Methoden in den Kapiteln 5 (Dynamische Programmierung) und 6 (Ant Colony Optimization) beginnend beim Endprodukt entgegen der Wertschöpfung erfolgt.

³⁷ Die ursprüngliche Definition sieht kein Restriktionssystem vor und definiert das Kantengruppenkonstrukt abweichend zu den obigen Darstellungen. Vgl. [Fis04a, S. 517ff.], [Fis04a, S. 517ff.], [Kam06, S. 53].

³⁸ In [Fis04a, S. 519] wird zudem eine künstliche Senke als Knoten sowie eine Menge von Kanten, welche diesen erreichen, definiert. Diese Darstellung wird hier bewusst ausgelassen, da ein solcher Knoten nicht notwendig ist, weil das Ende eines Pfades auch über die Blattknoten-Eigenschaft gekennzeichnet werden kann.

³⁹ Vgl. [Fis04a, S. 517], [Kam06, S. 53].

⁴⁰ Die Definition dieser Funktionen erfolgte in [Fis04a, S. 519], [Kam06, S. 53] zu diesen Darstellungen abweichend in Form von Kantengewichten.

⁴¹ Siehe Abschnitt 5.2.2.2 auf Seite 74 i.V.m. nachfolgenden Darstellungen.

⁴² Boolesches Retrieval beschreibt ein Konzept zur Suche von Dokumenten in Information Retrieval Systemen. Vgl. [Fer03, S. 33ff.].

⁴³ In späteren Kapiteln werden Restriktionen algorithmisch bei der Lösungskonstruktion im Rahmen von so genannter Pfadrestriktionen aufgelöst, was eine Trennung einzelner Restriktionen zu abgegrenzten Objekten erforderlich macht.

⁴⁴ Vgl. Konzept der expliziten Fehlmengen in Abschnitt 4.4.2 auf Seite 55.

⁴⁵ Vgl. [Fis04a, S. 517ff.].

⁴⁶ Vgl. Auflösung von Restriktionen in Abschnitt 5.2.2.2 auf Seite 74.

⁴⁷ Vgl. [Tei02, S. 370f.].

⁴⁸ Vgl. Getrennte Betrachtung von Angebotskosten und Logistik in [Tei02, S. 372].

⁴⁹ Vgl. [Tei02, S. 385ff.], [Zsc05, Abschnitt 3] sowie [Zsc04, S.69].

⁵⁰ Vgl. [Tei02, S. 403f.].

⁵¹ Vgl. [For06, S. 45].

⁵² Vgl. [Mic06c] und [Mic06b].

⁵³ Vgl. [Böh93, S. 29ff.].

⁵⁴ Aufgrund des Zusammenhangs (a · b)x = ax · bx gilt ebenfalls [Abbildung in dieser Leseprobe nicht enthalten]. Da die Funktion [Abbildung in dieser Leseprobe nicht enthalten] außerdem stetig ist und streng monoton wächst, ergibt sich zwangsläufig, dass die Präferenzordnung bei der Berechnung von F im Vergleich zur reinen Produktfunktion gleich bleiben muss, da F (a) < F (b) ⇔ a < b abgeleitet werden kann. Vgl. Stetigkeit und Monotonie von Funktionen sowie Potenzrechnung in [Bro05, S. 8, 50, 59].

⁵⁵ Lieferwahrscheinlichkeiten mit dem Wert 0 würden ein ähnliches Problem hervorrufen. Da aus diesem Wert jedoch eine Nichtlieferung resultiert, wird das Angebot bereits im Vorfeld als ungültig eingestuft.

⁵⁶ Vgl. [Ban93, S. 106].

⁵⁷ Vgl. [IEE85, S. 9].

⁵⁸ Quelle: [Bro05, S. 967].