Neue Lösungsansätze für das Generalized-Assignment-Problem

Travail d'étude , 2006 , 100 Pages , Note: 2

Gestion d'entreprise - Enquête d'entreprise, Recherche opérationnelle

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

• Inhaltsverzeichnis
• Abbildungsverzeichnis
• Tabellenverzeichnis
• Abkürzungsverzeichnis
• 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
• Literaturverzeichnis

Zielsetzung und Themenschwerpunkte

Die vorliegende Studienarbeit befasst sich mit dem Generalized-Assignment-Problem (GAP), einem kombinatorischen Optimierungsproblem, das in verschiedenen Bereichen der Wirtschaft und Logistik Anwendung findet. Ziel der Arbeit ist es, verschiedene Lösungsansätze für das GAP zu untersuchen und zu bewerten. Dabei werden sowohl klassische Heuristiken als auch moderne Verfahren wie Branch-and-Bound, Branch-and-Cut und Branch-and-Cut-and-Price betrachtet.

• Mathematische Modellierung des GAP
• Heuristische Lösungsansätze
• Exakte Lösungsverfahren
• Vergleich der Lösungsansätze
• Anwendungsmöglichkeiten des GAP

Zusammenfassung der Kapitel

Die Einleitung führt in das Generalized-Assignment-Problem ein und erläutert die mathematische Modellierung sowie den Lösungsraum. Kapitel 2 behandelt verschiedene Heuristiken, die zur Lösung des GAP eingesetzt werden können. Dazu gehören die Heuristik von Martello und Toth, elliptische Schnitte sowie weitere Ansätze wie genetische Algorithmen, Tabu-Search und Scatter-Search. Kapitel 3 befasst sich mit dem Branch-and-Bound Verfahren, einem exakten Lösungsverfahren, das auf der systematischen Suche nach der optimalen Lösung basiert. Der Algorithmus von Martello und Toth wird im Detail vorgestellt und anhand eines Beispiels illustriert. Kapitel 4 behandelt das Branch-and-Cut Verfahren, das auf der Kombination von Branch-and-Bound mit Schnittebenenverfahren basiert. Es werden verschiedene Arten von Schnittebenen vorgestellt, darunter Gomory-Cuts und spezielle Schnittebenen. Kapitel 5 befasst sich mit dem Branch-and-Price Verfahren, das auf der Dantzig-Wolfe Dekomposition und der Spaltengenerierung basiert. Die Spaltengenerierung von Savelsbergh wird im Detail erläutert und anhand eines Beispiels illustriert. Kapitel 6 behandelt das Branch-and-Cut-and-Price Verfahren, das die Vorteile von Branch-and-Cut und Branch-and-Price kombiniert. Es werden verschiedene Aspekte der stabilisierten Spaltengenerierung vorgestellt und anhand eines Beispiels illustriert. Abschließend werden die wichtigsten Ergebnisse der Arbeit zusammengefasst und ein Ausblick auf zukünftige Forschungsarbeiten gegeben.

Schlüsselwörter

Die Schlüsselwörter und Schwerpunktthemen des Textes umfassen das Generalized-Assignment-Problem, Heuristiken, Branch-and-Bound, Branch-and-Cut, Branch-and-Price, kombinatorische Optimierung, Operations Research, Logistik, Wirtschaft.

• Université: Technical University of Darmstadt
• Note: 2
• Auteur: Christoph Holzbaur (Auteur)
• Année de publication: 2006
• Pages: 100
• N° de catalogue: V186357
• ISBN (ebook): 9783656997726
• ISBN (Livre): 9783869431321
• Langue: allemand
• mots-clé: neue, lösungsansätze, generalized-assignment-problem