Quadratische Zuordnungsprobleme in der Layoutplanung


Seminararbeit, 2008

34 Seiten, Note: 2,3


Leseprobe


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
6.1 Literaturverzeichnis
6.2 Abbildungsverzeichnis

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

1 Einleitung

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 Organisationseinhei- ten auf einer rechteckigen Grundfläche so anzuordnen, dass die Summe der Trans- portkosten minimiert wird. In diesem Zusammenhang wird zwischen Problemen mit gleichem sowie ungleichem Flächenbedarf der Organisationseinheiten unterschie- den. 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 dar- auffolgenden 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.

2 Überblick über die Problemstellung

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.

2.1 Begriffe

In dieser Sektion werden die Basisbegriffe der quadratischen Zuordnungsprobleme erläutert, sowie deren Verwendung innerhalb der Problemlösungsstrategien aufge- zeigt.

2.1.1 Quadratisches Zuordnungsproblem

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 Ar- beit werden im Weiteren die Begriffe QZOP und GQZOP (für das generalisierte quad- ratische Zuordnungsproblem) verwendet. Bei dem QZOP handelt es sich um ein Op- timierungsverfahren zur Anordnung von Organisationseinheiten auf einer zur Verfü- gung stehenden Fläche.

2.1.2 Organisationseinheiten

Im Kontext der betrachteten Zuordnungsprobleme sind Organisationseinheiten (OE) quadratische Felder, die auf einem Koordinatensystem bzw. Raster positioniert wer- den. Bei Zuordnungsproblemen mit gleichem Flächenbedarf sind alle OE gleich groß und nehmen im Regelfall ein Quadrat der Fläche 1x1 auf dem Standortträger ein. Werden Zuordnungsprobleme mit ungleichem Flächenbedarf betrachtet, so kann die Form der OE von der des Quadrates abweichen. Dabei besteht eine OE aus mehre- ren, aneinander gereihten Quadraten, welche untrennbar miteinander verbunden sind.

2.1.3 Standortträger

Der Standortträger ist derjenige Raum, auf welchem die OE angeordnet werden sol- len. Wird das Problem quadratisch gelöst, so wird über den Standortträger ein Koor- dinatensystem mit quadratischem Raster gelegt. Die Granularität des Rasters richtet sich dabei an der Größe der OE aus.

2.2 Komplexität

Quadratische Zuordnungsprobleme befinden sich in der Komplexitätsklasse der NP- vollständigen Probleme (Cook 1971 [5], Sahni und Gonzalez 1976 [23]). Für keines der Probleme in dieser Komplexitätsklasse wurde bisher ein Algorithmus gefunden, der eine exakte Lösung in polynomieller Zeit liefert. Daher sind QZOP nur für kleine Probleme in der Größenordnung von etwa 20 - 30 OE exakt lösbar. Eine exakte Lö- sung von Problemen mit wesentlich größerer Anzahl an OE ist aufgrund der be- schränkten Rechenleistung nicht möglich. Sind dennoch größere Mengen an OE zu bewältigen oder genauer gesagt anzuordnen, so wählt man in diesem Fall stattdes- sen heuristische Verfahren, welche allerdings lediglich eine Annäherung an die exak- te Lösung errechnen können.

2.3 Modellierung bei gleichem Flächenbedarf der OE

In dem folgenden Abschnitt werden herkömmliche Modellierungsansätze für Quadra- tische Zuordnungsprobleme für Modelle mit gleichem Flächenbedarf vorgestellt. Hierbei sind alle OE - wie in Abbildung 1 zu sehen - identisch groß. Die blauen Käst- chen stellen hierbei die freien Flächen auf dem Standortträger dar.

Minimiert werden soll die Summe der Transportkosten, die abhängig sind von dem Produkt der Distanz djk und der Transportintensität thi zwischen den Organisations- einheiten h und i, wenn diese an den Positionen j und k des kontinuierlichen geras- terten Standortträger angeordnet sind. Insgesamt sollen n OE auf einem Standortträ- ger mit n Plätzen angeordnet werden. Die Kosten seien proportional zur zurückgeleg- ten Entfernung und der Distanz. Der Proportionalitätsfaktor ist der Einfachheit halber auf 1 gesetzt. Die allgemeine Formulierung wird auch QZOP1 genannt (Domschke und Drexl 1996, S.195, [6]).

Abbildung in dieser Leseprobe nicht enthalten

xhj sind Binärvariablen, wobei der Wert eins bedeutet, dass die OE h an der Stelle j angeordnet werden soll. Nebenbedingung (3) sagt aus, dass jede OE genau einem Platz zugeordnet ist. Nebenbedingung (4) bedeutet, dass jeder Platz mit genau einer OE besetzt ist.

Möchte man den Fall modellieren, dass es mehr freie Plätze m auf dem Standortträ- ger als Organisationseinheiten n gibt (n[Abbildung in dieser Leseprobe nicht enthalten]m), muss man das Gleichheitszeichen in (4) durch ein [Abbildung in dieser Leseprobe nicht enthalten] ersetzen. Außerdem erfolgt die Summation in der Zielfunktion bei k und j sowie in der Nebenbedingung (3) nur bis m.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: QZOP unter gleichem Flächenbedarf

Des Weiteren unterscheidet man den Fall asymmetrischer und symmetrischer QZO- Pen. Im zweiten Fall gilt für alle i und j: dij=dji. Bei der Modellierung dieses Falles kann die Indexbildung auf den Teil unterhalb der Hauptdiagonale beschränkt werden. Die Zielfunktion sieht wie dann wie folgt aus:

Abbildung in dieser Leseprobe nicht enthalten

Sind die Transportintensitäten auch symmetrisch (thi=tih), kann analog auch die In- dexbildung von k=j+1,…,n erfolgen.

Das Produkt aus Distanz und Transportintensitäten thidjk (vierdimensionale Matrix) wird in einigen Arbeiten auch durch eine Matrix = chijk der Dimension P4 dargestellt (Hahn 1998, [10]). Diese Formulierung wird in der Literatur nach ihrem Begründer auch „Lawler-Formulierung“ genannt (Lawler 1963, [17]).

2.4 Modellierung bei ungleichem Flächenbedarf der OE

Die bisherige Modellformulierung berücksichtigte ausschließlich OE mit gleichgroßem Flächenbedarf. In der Realität haben OE für gewöhnlich jedoch unterschiedlichen Flächenbedarf. Auch dieser Bereich wird in der Literatur intensiv diskutiert.

Eine generelle Formulierung für dieses Problem findet sich in Domschke und Drexl 1996 (S.201) [6]. Hier werden die OE mit ungleichem Flächenbedarf zurückgeführt auf ganzzahlige Vielfache von Rasterelementen der Seitenlänge 1 mit gleichem Flä- chenbedarf. Wichtig hierbei ist, dass die Rasterelemente, aus denen eine OE be- steht, „benachbart“ sind. Zwei OE sind benachbart, falls ihre Rasterelemente mindes- tens eine gemeinsame Kante bilden. In Abbildung 2 werden die OE durch gleichfar- bige zusammenhängende Flächen dargestellt.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2: QZOP unter ungleichem Flächenbedarf

Um die notwendigen Distanzen zwischen den OE zu berechnen, finden sich in der Literatur (Mir und Imam 2001, [22]) vor allem die euklidische (1), die quadrierte eukli- dische (2) und die rechtwinklige Entfernungsmessung (3).

Abbildung in dieser Leseprobe nicht enthalten

Realistisch ist die euklidische, die dem Abstand als Luftlinie entspricht. Bei Planung auf einem Firmengelände ist jedoch auch die so genannte „Manhattan“-Metrik (3) sinnvoll, da die Verkehrswege dort wahrscheinlich eher einem Schachbrettmuster entsprechen und direkte Wege aufgrund der Maschinenabmessungen nicht möglich sind. Domschke und Drexl 1996 (S.223) [6] empfehlen die Messung der Abstände zwischen den Mittelpunkten der OE, die über den Schwerpunkt definiert sind.

Abbildung in dieser Leseprobe nicht enthalten

Hierbei stellt ri die Anzahl der OE mit dem zugehörigen Abzissenwert ui dar. Die Be- rechnung des Ordinatenwertes erfolgt analog. Alternativ kann die Entfernungsmes- sung auch zwischen zuvor festgelegten festen Ein- und Ausgängen der OE erfolgen. Problematisch bei dem vorgestellten Verfahren ist, dass OE ausschließlich durch ihre Größe und nicht durch ihre geometrische Form definiert sind. Um eine realistischere Modellformulierung zu gewährleisten, beschäftigen sich aktuelle Arbeiten deswegen mit OE mit vorgegebener geometrischer Form. Castillo und Sim 2004 [3] modellieren si als Kreise. Die meisten Arbeiten stellen sie jedoch in Rechteckform dar. Hierbei ist noch zu differenzieren zwischen solchen mit konstanter Größe (Mir und Imam 2001, [22]) und solchen mit konstanten Seitenverhältnissen und in definierten Schranken veränderlichen Größen (Lee und Lee 2002, [19]). Vielfach werden die OE auch nicht auf einem fest vorgegebenen diskreten Raster angeordnet. Vielmehr ist ihre Position durch ihre kontinuierlichen Koordinaten xi und yi bestimmt (Castillo und Sim 2004, [3]). Hierbei ist zu beachten, dass eine zusätzliche Nebenbedingung in Form einer Nichtüberschneidungsbedingung notwendig ist.

Im Bereich des GQZOP ist eine geringere Anzahl an Publikationen zu finden als bei solchen, die sich auf das einfache QZOP beschränken. So gibt es zur exakten Lö- sung des GQZOP nur sehr wenige Ausarbeitungen und Lösungsverfahren. Hahn et al. 2007 [11] nennen lediglich eine weitere Publikation (Lee und Ma 2004, [18] ) be- züglich eines exakten Lösungsverfahrens. Zusammen mit der dort vorgestellten He- rangehensweise gibt es somit nur zwei Arbeiten auf diesem Gebiet.

2.5 Lösungsverfahren

Im Anschluss an die Modellierung folgen bei kleinen Problemgrößen Algorithmen, welche eine exakte Lösung errechnen, bzw. bei einer großen Anzahl von zu platzie- renden OE heuristische Lösungsansätze. Im Folgenden wird nun eine Auswahl von gängigen Verfahren zur Errechnung von (exakten und heuristischen) Lösungen be- trachtet.

2.5.1 Exakte Lösungsverfahren

Als exakte Lösungsverfahren kommen die vollständige Enumeration sowie Branch & Bound-Ansätze in Frage. Die vollständige Enumeration des Suchraumes durch geordnetes Evaluieren aller zulässigen Anordnungen im Suchraum stellt die einfach- ste und klassischste, rein explorative („brute force") Lösung für Such- und Optimie- rungsprobleme dar. Durch die Abarbeitung aller Lösungen ist garantiert, dass das globale Minimum der Transportkosten zwischen den OE gefunden wird. Der Nachteil der vollständigen Enumeration ist die Problemgröße, welche sich hierbei ergibt. Schon beim QZOP unter gleichem Flächenbedarf ergeben sich n! mögliche Anord- nungen, wobei n die Anzahl der OE ist. Die Nebenbedingungen müssen bei dieser Herangehensweise für jeden Fall einzeln geprüft werden. Fälle, die nicht jede Ne- benbedingung, beispielsweise hinsichtlich der Kapazität, erfüllen, fallen aus dem Raster heraus. Im Anschluss daran wird über alle gültigen Formationen das kosten- günstigste globale Minimum gesucht.

Branch-and-Bound-Ansätze haben das Ziel, diese Komplexität durch eine intelligente Herangehensweise weiter zu verringern. Bei der Verwendung dieses Verfahrens wird ein Entscheidungsbaum gebildet, der je nach Problemstellung mit einem auf die Auf- gabe spezifizierten Algorithmus abgearbeitet wird. Dies geschieht beispielsweise durch Ausschluss von Lösungszweigen, die nicht mehr zum Ziel - im Falle von QZOP das Minimum zu erreichen - gelangen können.

2.5.2 Heuristische Lösungsverfahren

Auch bei heuristischen Verfahren besteht eine grundlegende Herausforderung, wel- che sich ebenfalls aus der Komplexität der QZOPe ergibt (vgl. Abschnitt 2.2): Es gilt, möglichst schnell und damit für große Problemstellungen in annehmbarer Zeit eine gute Lösung zu finden. Unter „schnell" ist in diesem Kontext die benötigte Rechenzeit bzw. die Komplexität der Heuristik zu verstehen. Die gefundene Lösung entspricht in den meisten Fällen nicht dem globalen Kostenminimum. Dies ist jedoch die notwen- dige Einschränkung, welche man dadurch hinnehmen muss, dass man die Problem- größe im Unterschied zu exakten Verfahren (fast) frei wählen kann. Heuristische Ver- fahren versuchen das globale Kostenminimum jedoch anzunähern (Hahn et al. 2007, [11]). Je nach Größe und Art der Problemstellung können verschiedene Heuristiken unterschiedlich gute Ergebnisse berechnen.

3 Aktuelle wissenschaftliche Arbeiten

In diesem Abschnitt werden die aktuell verfügbaren wissenschaftlichen Arbeiten zur Thematik vorgestellt und kurz zusammengefasst. Abschnitt 3.1 gibt einen allgemei- nen Überblick über die Modellierung und Lösung des QZOP. In Abschnitt 3.2 und 3.3 werden neue Lösungsalgorithmen für das Problem mit gleichem Flächenbedarf vor- gestellt. Abschnitte 3.4 bis 3.6 stellen Lösungsansätze für das Problem mit unglei- chem Flächenbedarf dar. Diese Veröffentlichungen werden in Abschnitt 4 noch aus- führlicher behandelt.

3.1 A survey for the quadratic assignment problem

Loiola et al. 2007 [20] geben einen sehr weiten Überblick über die Problemstellung und die Lösung des „Quadratischen Zuordnungsproblems“. Zunächst werden einige praktische Anwendungen aufgezeigt. Daraufhin zeigen sie verschiedene mathemati- sche Formulierungen des Quadratischen Zuordnungsproblems und verwandter Prob- leme 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 Schran- ken 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 Verbesserungsme- thoden 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 experimentel- len Überlegungen beruhen. Zur ersten Gruppe zählen Simulated Annealing, geneti- sche Algorithmen, Scatter Search und die Ameisen-Kolonien-Optimierung. Zur zwei- ten gehören unter anderem Tabu Search, variable Nachbarschaftssuche und vor allem hybride Algorithmen, die auf mehreren Prinzipien beruhen.

Zum Abschluss dokumentieren die Autoren, welche Problemformulierungen, Lö- sungstechniken und Methoden zur Ermittlung unterer Schranken in der jüngeren Lite- ratur eine große Rolle spielen.

3.2 A Solution Method for the Quadratic Assignment Problem

Im Rahmen des sechsten Symposiums zu Operations Research und seinen Anwen- dungen (ISORA’06) befassten sich Ji et al. 2006 [14] mit Lösungsansätzen zum Quadratischen Zuordnungsproblem. Nach der Schilderung der bereits existierenden Algorithmen und Lösungsansätzen entwickeln die Autoren einen neuen Algorithmus. Dieser basiert auf einem Array als Datenstruktur sowie dem „uniformed crossover algorithm“(Spears und De Yong 1991, [25]). Die Funktionsweise des Algorithmus wird anhand eines Arrays mit 10 Elementen veranschaulicht (Ji et al. 2006, [14]). Zu Beginn werden drei der zehn Felder zufällig als Kreuzungspunkte ausgewählt. Aus jeder der entstehenden Sektionen wird eine zufällige Anzahl an Feldern über den Kreuzungspunkt getauscht, wobei eine Permutation der Einträge des Arrays - auch als Kind bezeichnet - entsteht. Abschließend werden die entstandenen Kinder mit ihrem Vater verglichen. Ergibt der Vergleich, dass durch die Permutation eine schlechtere Konstellation entstanden ist, so wird das Kind verworfen, andernfalls tritt es an die Stelle des Vaters (intra-kindred selection). Zusätzlich wird in einer vorher definierten Frequenz auch zwischen den einzelnen entstandenen Zweigen des bei diesem Verfahren entstehenden Baums verglichen (inter-kindred selection). Ebenso wie beim Vergleich zwischen Vater und Kind werden diejenigen Permutationen mit den schlechtesten Werten für das behandelte Problem verworfen. Dieser Ansatz ist angelehnt an die Darwin'sche Evolutionstheorie - "survival of the fittest".

3.3 Cunning Ant System for QAP with Local Search and Par- allelization

Tsutsui 2007 [28] versucht mittels eines angepassten Ameisen-Algorithmus eine bessere bzw. effizientere Annäherung von QZOPen zu erzielen. Er beschäftigte sich schon in vorhergehenden Publikationen mit Ameisen-Algorithmen und wendete diese u. a. auch auf das Travelling Salesman Problem (TSP) an. Dies geschah mit einem modifizierten Ant Colony Optimization-Algorithmus (ACO), welchen der Autor mit „cunning Ant System“ (cAS) bezeichnete. Der vorliegenden Arbeit zufolge hat der cAS beim TSP vielversprechende Ergebnisse erzielt.

[...]

Ende der Leseprobe aus 34 Seiten

Details

Titel
Quadratische Zuordnungsprobleme in der Layoutplanung
Hochschule
Technische Universität Darmstadt  (Fachgebiet Operations Research)
Veranstaltung
Seminar Operations Research
Note
2,3
Autoren
Jahr
2008
Seiten
34
Katalognummer
V117386
ISBN (eBook)
9783640199549
ISBN (Buch)
9783640205455
Dateigröße
1179 KB
Sprache
Deutsch
Schlagworte
Quadratische, Zuordnungsprobleme, Layoutplanung, Seminar, Operations, Research, BWL, TSP, Optimierung, Prozesse, Mathematisches Modell
Arbeit zitieren
Andreas Eismann (Autor:in)Thomas Fischer (Autor:in), 2008, Quadratische Zuordnungsprobleme in der Layoutplanung, München, GRIN Verlag, https://www.grin.com/document/117386

Kommentare

  • Noch keine Kommentare.
Blick ins Buch
Titel: Quadratische Zuordnungsprobleme in der Layoutplanung



Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden