Diese Arbeit beschäftigt sich mit neuen Ansätzen zur Lösung des Generalized-Assignment-Problems (GAP). Es werden werden verschiedene Heuristiken wie auch exakte Verfahren zur Lösung des GAP betrachtet.
Unter dem GAP versteht man ein
kombinatorisches Zuordnungsproblem, bei dem n Aufträge von m Arbeitern bearbeitet werden sollen.
Jeder Arbeiter ist durch seine maximale Arbeitszeit beschränkt und für jede Zuordnung eines Arbeiters an einen Auftrag entstehen Kosten.
Das Ziel des GAP ist es, die gesamten Kosten unter Berücksichtigung der gegebenen Schranken zu minimieren.
Inhaltsverzeichnis
1 Einleitung
1.1 Mathematische Darstellung des Generalized-Assignment-Problems
1.2 Der Lösungsraum des Generalized-Assignment-Problems
2 Heuristiken
2.1 Die Heuristik von Martello und Toth
2.1.1 Darstellung als Maximierungsproblem
2.1.2 Die Heuristik
2.1.3 Ein Beispiel für die Heuristik von Martello und Toth
2.2 Elliptische Schnitte
2.3 Weitere Heuristiken für das Generalized-Assignment-Problem
2.3.1 Genetische Algorithmen
2.3.2 Tabu-Search
2.3.3 Scatter-Search und Path-Relinking
3 Branch-and-Bound
3.1 Branch-and-Bound im Allgemeinen
3.2 Der Algorithmus von Martello und Toth
3.2.1 Den Lösungsraum reduzieren
3.2.2 Eine obere Schranke ermitteln
3.2.3 Die maximale Distanz
3.2.4 Die Branching-Strategie
3.2.5 Ein Beispiel für den Algorithmus von Martello und Toth
4 Branch-and-Cut
4.1 Das Schnittebenenverfahren
4.2 Die Branching-Strategie des Branch-and-Cut Verfahrens
4.3 Gültige Schnittebenen konstruieren
4.3.1 Gomory-Cuts
4.3.2 Ein Beispiel für Gomory-Cuts
4.3.3 Spezielle Schnittebenen
4.3.4 Ein Beispiel für spezielle Schnittebenen
5 Branch-and-Price
5.1 Die Dantzig-Wolfe Dekomposition
5.2 Die Set-Partition Zerlegung
5.3 Die Spaltengenerierung von Savelsbergh
5.4 Ein Beispiel für die Spaltengenerierung
5.5 Die Branching-Strategie
6 Branch-and-Cut-and-Price
6.1 Schnittebenen für Branch-and-Cut-and-Price
6.2 Das Stabilisieren der Spaltengenerierung
6.2.1 Die Methodik
6.2.2 Die Anwendung im Algorithmus
6.3 Ein Beispiel für die stabilisierte Spaltengenerierung
6.4 Testergebnisse
7 Glossar
7.1 Polytop
7.2 Set-Partition
7.3 Relaxation
7.4 0/1-Knapsackproblem
7.5 Metaheuristiken
7.6 Ejection-Chain
7.7 Nachbarschaft
7.8 OR-Library
A Ein vollständiges Beispiel für die stabilisierte Spaltengenerierung
Zielsetzung & Themen
Diese Arbeit widmet sich der Entwicklung und Analyse exakter Lösungsverfahren für das NP-schwere Generalized-Assignment-Problem (GAP), mit dem Ziel, die Effizienz bei der Lösung kombinatorischer Zuordnungsprobleme durch fortgeschrittene mathematische Methoden zu steigern.
- Mathematische Modellierung des Generalized-Assignment-Problems als Ganzzahliges Lineares Programm (ILP).
- Analyse und Anwendung von Heuristiken (insb. Martello und Toth) zur initialen Lösungsfindung.
- Detaillierte Untersuchung exakter Verfahren wie Branch-and-Bound, Branch-and-Cut und Branch-and-Price.
- Stabilisierungstechniken für die Spaltengenerierung zur Optimierung des Branch-and-Cut-and-Price Algorithmus.
- Praktische Erprobung der Ansätze anhand von Instanzen aus der OR-Library.
Auszug aus dem Buch
2.1.2 Die Heuristik
Für ihre Heuristik definieren Martello und Toth [33] die Gewichtsfunktionen ϕij für den Nutzen einer Zuweisung des Auftrags j an den Arbeiter i. Die Heuristik erzielt mit folgenden Gewichtsfunktionen gute Resultate:
ϕij = {pij, pij/bij, -bij, -bij/ri} (ri= noch verfügbare ZE des Arbeiters i). ∀i ∈ I, j ∈ J (2.3)
Im ersten Schritt der Heuristik wird für jeden Auftrag ein Regret berechnet. Diesen Wert kann man als Nutzeneinbuße für das Nichtzuordnen eines Auftrags an einen Arbeiter in diesem Schritt betrachten. Der Regret für den Auftrag j berechnet sich als die Differenz zwischen dem größten und dem zweitgrößten Nutzen ϕij der Arbeiter i, deren Kapazität für das Übernehmen des Auftrags j ausreicht. Daraufhin wird der Auftrag mit dem größten Regret dem Arbeiter zugeteilt, der damit den größten Nutzen hat.
Im zweiten Schritt wird versucht eine bessere Lösung zu finden, indem man unter Berücksichtigung der Kapazitätsbeschränkungen lokale Vertauschungen vornimmt (local exchange procedure). Die Idee dahinter ist, dass durch gezielte Vertauschungen (shift procedure) einzelner Aufträge j eine bessere Lösung gefunden werden kann. Bei der Vertauschung werden nacheinander alle Aufträge j betrachtet und unter Berücksichtigung der Kapazitätsrestriktionen dem Arbeiter i zugewiesen, für den der Profit pij am höchsten ist. Die Worst-Case Gesamtkomplexität für diese Heuristik ergibt sich als O(n^2m + nm) = O(n^2m).
Zusammenfassung der Kapitel
1 Einleitung: Definition des Generalized-Assignment-Problems und Darstellung der Zielsetzung sowie der mathematischen Grundlagen.
2 Heuristiken: Vorstellung heuristischer Verfahren zur schnellen Erzeugung von Näherungslösungen, einschließlich Martello und Toth sowie metaheuristischer Ansätze.
3 Branch-and-Bound: Erläuterung des exakten Branch-and-Bound Verfahrens und dessen Anwendung zur systematischen Problemlösung.
4 Branch-and-Cut: Erweiterung von Branch-and-Bound um das Schnittebenenverfahren zur effizienteren Einschränkung des Suchraums.
5 Branch-and-Price: Einführung der Spaltengenerierung zur Behandlung großskaliger Probleme mittels Dantzig-Wolfe Dekomposition.
6 Branch-and-Cut-and-Price: Kombination der Verfahren zur robusten Lösung des GAP und Stabilisierung der Spaltengenerierung.
7 Glossar: Definition zentraler Fachbegriffe zur mathematischen Optimierung.
A Ein vollständiges Beispiel für die stabilisierte Spaltengenerierung: Schrittweise praktische Demonstration des stabilisierten Spaltengenerierungsverfahrens.
Schlüsselwörter
Generalized-Assignment-Problem, GAP, Mathematische Optimierung, Branch-and-Bound, Branch-and-Cut, Branch-and-Price, Heuristiken, Martello und Toth, Spaltengenerierung, Gomory-Cuts, Ganzzahlige Lineare Programmierung, ILP, NP-schwer, Kombinatorik, Schnittebenenverfahren.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit beschäftigt sich mit der Entwicklung, Analyse und Optimierung von exakten Algorithmen zur Lösung des Generalized-Assignment-Problems (GAP), einem komplexen kombinatorischen Zuordnungsproblem.
Was sind die zentralen Themenfelder der Publikation?
Die Arbeit deckt ein breites Spektrum ab, von heuristischen Eröffnungsverfahren über klassische exakte Verfahren (Branch-and-Bound) bis hin zu modernen, kombinierten Ansätzen wie Branch-and-Cut-and-Price.
Was ist das primäre Ziel oder die Forschungsfrage?
Das Ziel ist die Reduzierung der Rechenzeit und die Steigerung der Lösungsgüte bei der Lösung des GAP, indem effiziente exakte Verfahren mathematisch fundiert und praktisch implementiert werden.
Welche wissenschaftlichen Methoden werden verwendet?
Es werden Methoden der mathematischen Optimierung verwendet, insbesondere ganzzahlige lineare Programmierung, Simplex-Verfahren, Dekompositionsalgorithmen sowie verschiedene Heuristiken und Nachbarschaftssuchen.
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil behandelt systematisch die Lösungsansätze für das GAP: angefangen bei der Heuristik von Martello und Toth über das Schnittebenenverfahren und die Spaltengenerierung bis hin zur Stabilisierung dieser Verfahren im Branch-and-Cut-and-Price Algorithmus.
Welche Schlüsselwörter charakterisieren die Arbeit am besten?
Die Arbeit wird durch Begriffe wie Generalized-Assignment-Problem, exakte Lösungsverfahren, Ganzzahlige Optimierung und Spaltengenerierung charakterisiert.
Warum ist das Generalized-Assignment-Problem als NP-schwer eingestuft?
Das GAP ist NP-schwer, da Garey und Johnson bewiesen haben, dass wahrscheinlich kein Algorithmus existiert, der das Problem in polynomialer Zeit lösen kann; daher sind effiziente exakte oder heuristische Verfahren für praktische Anwendungen notwendig.
Wie unterscheidet sich die "stabilisierte Spaltengenerierung" von der Standardmethode?
Die Stabilisierung reduziert das Oszillieren der Dualvariablen in den frühen Iterationen, was die Konvergenz beschleunigt und verhindert, dass ineffiziente Spalten unnötig in das Modell aufgenommen werden.
Welche Bedeutung haben die "elliptischen Schnitte" in dieser Arbeit?
Elliptische Schnitte sind ein Verfahren zur heuristischen Verbesserung, das den Suchraum in einer elliptischen Nachbarschaft zwischen zwei verschiedenen Lösungen einschränkt, um neue, bessere Optima zu finden, die mit Standardmethoden schwer erreichbar sind.
Was belegt der Anhang A?
Anhang A bietet eine detaillierte, schrittweise Demonstration eines Anwendungsfalls für die stabilisierte Spaltengenerierung, um die theoretischen Konzepte aus Kapitel 6 praktisch nachvollziehbar zu machen.
- Quote paper
- Christoph Holzbaur (Author), 2006, Neue Lösungsansätze für das Generalized-Assignment-Problem, Munich, GRIN Verlag, https://www.grin.com/document/186357
