1  Einleitung  1

2  Überblick über die Problemstellung  1

2.1  Begriffe  1

2.1.1  Quadratisches Zuordnungsproblem  1

2.1.2  Organisationseinheiten  2

2.1.3  Standortträger  2

2.2  Komplexität  2

2.3  Modellierung bei gleichem Flächenbedarf der OE  2

2.4  Modellierung bei ungleichem Flächenbedarf der OE  4

2.5  Lösungsverfahren  5

2.5.1  Exakte Lösungsverfahren  6

2.5.2  Heuristische Lösungsverfahren  6

3  Aktuelle wissenschaftliche Arbeiten  7

3.1  A survey for the quadratic assignment problem  7

3.2  A Solution Method for the Quadratic Assignment Problem  8

3.3  Cunning Ant System for QAP with Local Search and Parallelization  8

3.4  A shape-based layout approach to facility layout problems using hybrid  

algorithms   9

3.5  An Algorithm for the generalized QAP  10

3.6  A hybrid optimization approach for layout design of unequal-area facilities  11

4  Ausführliche Beschreibung einzelner Arbeiten  11

4.1  Zwei Heuristische Lösungsansätze bei ungleichem Flächenbedarf  12

4.1.1  Verfahren von Mir Imam 2001  12

4.1.2  Verfahren von Lee Lee 2002  16

4.2  Exakte Lösung bei ungleichem Flächenbedarf  19

4.2.1  Überblick  19

4.2.2  Ansatzpunkte zur Verbesserung des B B-Algorithmus  20

4.2.3  Formelle Problembeschreibung  20

4.2.4  Mathematische Vorgehensweise  21

4.2.5  Kalkulation des lower bound  22

4.2.6  Überlegungen zum Linear Programming  23

4.2.7  Vorteile von RLT1 Dual Ascent.  24

4.2.8  Branch Bound  24

4.2.9  Zusammenfassung  25

5  Fazit und Ausblick  26

6  Anhang  28

Seite II

6.1  Literaturverzeichnis  28

6.2  Abbildungsverzeichnis  30

Seite III

Abkürzungsverzeichnis AC Adaptive Crossover Rate ACO Ant Colony Optimization AOT Analytische Optimierungstechnik B&B Branch & Bound cAS cunning Ant System DAP Dual Ascent Procedure GA Genetischer Algorithmus GLB Gilmore Lawler Bound GQAP Generalized Quadratic Assignment Problem GQZOP Generalisiertes quadratisches Zuordnungsproblem HGA Hybrider Genetischer Algorithmus HOT Hybride Optimierungstechnik LIP Linearized mixed Integer Problem LP Linear Programming MMAS Max Min Ant System OE Organisationseinheit(en) RLT Reformulation Linearization Technique SA Simulated Annealing SBL Shape Based Layout TS Tabu Search TSP Travelling Salesman Problem QAP Quadratic Assignment Problem QZOP Quadratisches Zuordnungsproblem

Seite IV

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 Organisationseinheiten 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 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.

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 aufgezeigt.

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

Seite 1

2.1.2 Organisationseinheiten

Im Kontext der betrachteten Zuordnungsprobleme sind Organisationseinheiten (OE) quadratische Felder, die auf einem Koordinatensystem bzw. Raster positioniert werden. 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 mehreren, 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 sollen. Wird das Problem quadratisch gelöst, so wird über den Standortträger ein Koordinatensystem 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 NPvollstä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 beschrä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 stattdessen heuristische Verfahren, welche allerdings lediglich eine Annäherung an die exakte 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 Quadratische Zuordnungsprobleme für Modelle mit gleichem Flächenbedarf vorgestellt. Hierbei sind alle OE - wie in Abbildung 1 zu sehen - identisch groß. Die blauen Kästchen 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 d jk und der Transportintensität t hi zwischen den Organisationseinheiten h und i, wenn diese an den Positionen j und k des kontinuierlichen gerasterten Standortträger angeordnet sind. Insgesamt sollen n OE auf einem Standortträ-

Seite 2

ger mit n Plätzen angeordnet werden. Die Kosten seien proportional zur zurückgelegten 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]).

(1) –

Unter den Nebenbedingungen:

(2) ò (3) ò

(4) ò

x hj 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 (nm), muss man das Gleichheitszeichen in (4)

durch ein ersetzen. Außerdem erfolgt die Summation in der Zielfunktion bei k und j sowie in der Nebenbedingung (3) nur bis m.

Des Weiteren unterscheidet man den Fall asymmetrischer und symmetrischer QZO-Pen. Im zweiten Fall gilt für alle i und j: d ij =d ji. 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:

(5) – –

Sind die Transportintensitäten auch symmetrisch (t hi =t ih ), kann analog auch die Indexbildung von k=j+1,…,n erfolgen.

Das Produkt aus Distanz und Transportintensitäten t hi d jk (vierdimensionale Matrix) wird in einigen Arbeiten auch durch eine Matrix = c hijk der Dimension P ⁴ 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 besteht, „benachbart“ sind. Zwei OE sind benachbart, falls ihre Rasterelemente mindestens eine gemeinsame Kante bilden. In Abbildung 2 werden die OE durch gleichfarbige zusammenhängende Flächen dargestellt.

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 euklidische (2) und die rechtwinklige Entfernungsmessung (3).

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.

Hierbei stellt r i die Anzahl der OE mit dem zugehörigen Abzissenwert u i dar. Die Berechnung des Ordinatenwertes erfolgt analog. Alternativ kann die Entfernungsmessung 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 x i und y i 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]) bezüglich eines exakten Lösungsverfahrens. Zusammen mit der dort vorgestellten Herangehensweise 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 platzierenden OE heuristische Lösungsansätze. Im Folgenden wird nun eine Auswahl von

Seite 5