Ein Teilgebiet der innerbetrieblichen Standortplanung oder Layoutplanung sind
Quadratische Zuordnungsprobleme (QZOP). Diese Formulierung geht auf Koopmans
und Beckmann 1957 [16] zurück. Grundproblem ist es einzelne Organisationseinheiten
auf einer rechteckigen Grundfläche so anzuordnen, dass die Summe der Transportkosten
minimiert wird. In diesem Zusammenhang wird zwischen Problemen mit
gleichem sowie ungleichem Flächenbedarf der Organisationseinheiten unterschieden.
Zunächst werden die grundlegenden Begriffe geklärt. Außerdem werden die
wichtigsten Modellierungsverfahren für Probleme mit gleichem und ungleichem Flächenbedarf
sowie wichtige Lösungsalgorithmen und Heuristiken vorgestellt. Diese
Arbeit gibt einen allgemeinen Überblick über die Literatur der Jahre 2001 bis 2008.
Sechs Arbeiten aus diesem Zeitraum werden in Abschnitt 3 kurz vorgestellt. Im darauffolgenden
Abschnitt wird auf drei ausgewählte Arbeiten detaillierter eingegangen.
Der Fokus liegt hier auf Lösungsmöglichkeiten für Probleme mit ungleichem Flächenbedarf,
die auch in der Praxis eine wichtigere Rolle spielen. Zum Verständnis des Themenkomplexes sowie der Einordnung von Quadratischen
Zuordnungsproblemen in den Gesamtkontext der innerbetrieblichen Standortplanung
werden im Folgenden die grundlegenden Fakten und Merkmale dieser Probleme
betrachtet. In dieser Sektion werden die Basisbegriffe der quadratischen Zuordnungsprobleme
erläutert, sowie deren Verwendung innerhalb der Problemlösungsstrategien aufgezeigt. Das quadratische Zuordnungsproblem wird im Deutschen auch als QZOP und im
Englischen als QAP abgekürzt. Bei Problemen mit ungleichem Flächenbedarf spricht
man auch von Generalized Quadratic Assignment Problems (GQAP). In dieser Arbeit
werden im Weiteren die Begriffe QZOP und GQZOP (für das generalisierte quadratische
Zuordnungsproblem) verwendet. Bei dem QZOP handelt es sich um ein Optimierungsverfahren
zur Anordnung von Organisationseinheiten auf einer zur Verfügung
stehenden Fläche.
Inhaltsverzeichnis
1 Einleitung
2 Überblick über die Problemstellung
2.1 Begriffe
2.1.1 Quadratisches Zuordnungsproblem
2.1.2 Organisationseinheiten
2.1.3 Standortträger
2.2 Komplexität
2.3 Modellierung bei gleichem Flächenbedarf der OE
2.4 Modellierung bei ungleichem Flächenbedarf der OE
2.5 Lösungsverfahren
2.5.1 Exakte Lösungsverfahren
2.5.2 Heuristische Lösungsverfahren
3 Aktuelle wissenschaftliche Arbeiten
3.1 A survey for the quadratic assignment problem
3.2 A Solution Method for the Quadratic Assignment Problem
3.3 Cunning Ant System for QAP with Local Search and Parallelization
3.4 A shape-based layout approach to facility layout problems using hybrid algorithms
3.5 An Algorithm for the generalized QAP
3.6 A hybrid optimization approach for layout design of unequal-area facilities
4 Ausführliche Beschreibung einzelner Arbeiten
4.1 Zwei Heuristische Lösungsansätze bei ungleichem Flächenbedarf
4.1.1 Verfahren von Mir & Imam 2001
4.1.2 Verfahren von Lee & Lee 2002
4.2 Exakte Lösung bei ungleichem Flächenbedarf
4.2.1 Überblick
4.2.2 Ansatzpunkte zur Verbesserung des B&B-Algorithmus
4.2.3 Formelle Problembeschreibung
4.2.4 Mathematische Vorgehensweise
4.2.5 Kalkulation des lower bound
4.2.6 Überlegungen zum Linear Programming
4.2.7 Vorteile von RLT1 Dual Ascent
4.2.8 Branch & Bound
4.2.9 Zusammenfassung
5 Fazit und Ausblick
6 Anhang
Zielsetzung & Themen
Die vorliegende Arbeit gibt einen Überblick über den Stand der Forschung zu Quadratischen Zuordnungsproblemen (QZOP) im Zeitraum von 2001 bis 2008. Das Ziel ist es, aktuelle Modellierungsansätze und Lösungsverfahren für Probleme mit sowohl gleichem als auch ungleichem Flächenbedarf von Organisationseinheiten zu analysieren und kritisch zu bewerten.
- Grundlagen des Quadratischen Zuordnungsproblems (QZOP) und der Generalized-Variante (GQZOP).
- Vergleich exakter und heuristischer Lösungsverfahren.
- Detaillierte Analyse von Ansätzen wie "Shape Based Layout" (SBL) und "Reformulation Linearization Technique" (RLT).
- Diskussion hybrider Algorithmen zur effizienten Lösung komplexer Layoutprobleme.
- Praktische Anwendungsgebiete und zukünftige Forschungsrichtungen.
Auszug aus dem Buch
3.1 A survey for the quadratic assignment problem
Loiola et al. 2007 [20] geben einen weiten Überblick über die Problemstellung und die Lösung des „Quadratischen Zuordnungsproblems“. Zunächst werden einige praktische Anwendungen aufgezeigt. Daraufhin zeigen sie verschiedene mathematische Formulierungen des Quadratischen Zuordnungsproblems und verwandter Probleme auf. Besonders herauszustellen sind hier die Formulierung als binäres und als gemischt ganzzahliges LP, die so genannte „Lawler-Formulierung“ (Lawler 1963, [17]) und die Formulierung über Permutationen. Verwandte Probleme sind etwa das quadratische Flaschenhals-Zuordnungsproblem oder das quadratische 3-dimensionale Zuordnungsproblem.
Weiterhin gehen die Autoren auf die Möglichkeit zur Ermittlung von unteren Schranken ein. Unter anderem stellen sie die Gilmore und Lawler Bound (GLB) vor, die das Problem auf ein lineares Zuordnungsproblem reduziert. Des Weiteren vergleichen sie die unteren Schranken hinsichtlich ihrer Qualität.
Daraufhin gehen sie auf Lösungsmöglichkeiten ein und differenzieren dort zwischen exakten und heuristischen Ansätzen. Bei dem ersten Ansatz werden die Methoden dynamische Programmierung, Branch & Bound, vollständige Enumeration und Branch & Cut vorgestellt. Diese Methoden werden hinsichtlich ihrer Geschwindigkeit verglichen. Die Autoren betonen hierbei auch die Bedeutung der Hardware-Entwicklung.
Als heuristische Methoden werden konstruktive Methoden und Verbesserungsmethoden sowie beschränkte Enumeration vorgestellt. Detaillierter wird auf den Bereich der Metaheuristiken eingegangen. Hier wird noch differenziert zwischen solchen, die auf natürlichen Phänomenen, und solchen, die auf theoretischen und experimentellen Überlegungen beruhen. Zur ersten Gruppe zählen Simulated Annealing, genetische Algorithmen, Scatter Search und die Ameisen-Kolonien-Optimierung. Zur zweiten gehören unter anderem Tabu Search, variable Nachbarschaftssuche und vor allem hybride Algorithmen, die auf mehreren Prinzipien beruhen.
Zusammenfassung der Kapitel
1 Einleitung: Einführung in das Themengebiet der Standort- und Layoutplanung sowie Erläuterung der Zielsetzung und Struktur der Arbeit.
2 Überblick über die Problemstellung: Theoretische Grundlegung mit Definitionen, Komplexitätsbetrachtungen und mathematischer Modellierung von Zuordnungsproblemen.
3 Aktuelle wissenschaftliche Arbeiten: Vorstellung und kurze Zusammenfassung relevanter Publikationen aus dem Zeitraum 2001 bis 2008.
4 Ausführliche Beschreibung einzelner Arbeiten: Vertiefende Analyse spezifischer heuristischer und exakter Lösungsverfahren für den Fall ungleicher Flächenbedarfe.
5 Fazit und Ausblick: Zusammenfassende Bewertung der Fortschritte in der Forschung und Diskussion potenzieller zukünftiger Anwendungsfelder.
6 Anhang: Enthält das Literaturverzeichnis sowie das Abbildungsverzeichnis der Arbeit.
Schlüsselwörter
Quadratisches Zuordnungsproblem, QZOP, GQZOP, Layoutplanung, Operations Research, Standortplanung, Heuristische Verfahren, Branch & Bound, Standortträger, Organisationseinheiten, Transportkosten, Reformulation Linearization Technique, Hybride Algorithmen, Simulated Annealing, Genetische Algorithmen.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit befasst sich mit der innerbetrieblichen Standort- und Layoutplanung unter Verwendung Quadratischer Zuordnungsprobleme (QZOP), wobei der Fokus insbesondere auf der Herausforderung liegt, Organisationseinheiten mit unterschiedlichem Flächenbedarf effizient anzuordnen.
Was sind die zentralen Themenfelder der Publikation?
Im Zentrum stehen mathematische Modellierungsansätze, die Klassifizierung von Problemen nach NP-Vollständigkeit sowie der Vergleich verschiedener exakter und heuristischer Lösungsalgorithmen.
Welches primäre Ziel verfolgt die Arbeit?
Das primäre Ziel ist es, einen Überblick über den Stand der Forschung zwischen 2001 und 2008 zu geben und verschiedene Lösungsansätze für das generalisierte quadratische Zuordnungsproblem (GQZOP) detailliert zu vergleichen.
Welche wissenschaftlichen Methoden werden behandelt?
Die Arbeit untersucht unter anderem das "Shape Based Layout" (SBL), die "Reformulation Linearization Technique" (RLT) im Rahmen von Branch-and-Bound-Verfahren sowie hybride genetische Algorithmen (HGA).
Was behandelt der Hauptteil der Arbeit?
Der Hauptteil gliedert sich in eine Übersicht aktueller wissenschaftlicher Paper und eine anschließende tiefgehende technische Analyse ausgewählter Verfahren zur exakten und heuristischen Lösung von GQZOPs.
Welche Schlüsselbegriffe charakterisieren die Arbeit?
Die wichtigsten Begriffe sind QZOP, GQZOP, Layoutplanung, Branch & Bound, Heuristiken, Standortträger und Transportkostenoptimierung.
Was ist das Besondere an der Modellierung von Lee & Lee (2002)?
Das Besondere ist die Kombination aus Simulated Annealing, Tabu Search und genetischen Algorithmen (HGA) sowie das "Shape Based Layout" (SBL) Schema, das eine explizite Nichtüberschneidungsbedingung unnötig macht.
Wie trägt die RLT1-Methode zur Effizienz bei?
Die Reformulation Linearization Technique (RLT1) ermöglicht die Konstruktion einer Folge nicht-fallender unterer Schranken, was den Suchraum im Branch-and-Bound-Verfahren effizienter einschränkt und somit die Rechenzeit reduziert.
- Quote paper
- Andreas Eismann (Author), Thomas Fischer (Author), 2008, Quadratische Zuordnungsprobleme in der Layoutplanung, Munich, GRIN Verlag, https://www.grin.com/document/117386
