Mathematical Fun

Das Single-Row Facility Layout Problem (SRFLP)

Spiel: Das Ruheproblem im Tierheim

Im Tierheim ist das Chaos los! Schaffst du es, die Käfige der Tiere so anzuordnen, dass jene Tiere, die sich untereinander gut verstehen, möglichst nahe beisammen sind – und gleichzeitig aber jene, die sich gegenseitig stören würden möglichst weit auseinander unterzubringen?

Das Problem

Beim Single-Row Facility Layout Problem wird nach einer optimalen Anordnung von $n$ Maschinen in einer Reihe nebeneinander gesucht.

Dabei hat jede Maschine eine vorgegebene Länge $\ell_i$, $i\in \{1,\dots, n\}$ und für jedes Paar von Maschinen ist die Menge an Material $f_{ij}$, $i,j\in\{1, \dots, n\}$ gegeben, die während des Betrachtungszeitraumes zwischen den Maschinen transportiert wird. Das Ziel ist es, die Maschinen so anzuordnen, dass die Summe der Abstände $d_{ij}$ zwischen den Maschinen, gewichtet mit dem Materialfluss $f_{ij}$ minimiert wird, also \[ \min \sum_{i,j} f_{ij}d_{ij}. \]

Maschinenpaare, zwischen denen viel Material fließt, sollen entsprechend möglichst nahe nebeneinander angeordnet werden.

Das SRFLP ist ein NP-schweres Optimierungsproblem, d.h. es ist sehr schwierig (sogar für die leistungsfähigsten Computer der Welt) eine optimale Lösung in vernünftiger Zeit zu finden, insbesondere für größere Instanzen mit vielen Maschinen.

Maschinenanordnung

Ein flexibles Fertigungssystem. Material muss zwischen den einzelnen Maschinen transportiert werden.

Lange Nacht der Forschung 2014

"Wer bringt Ruhe ins Tierheim?" wurde von den BesucherInnen zur besten Station der Langen Nacht der Forschung 2014 gewählt.

Referenzen

Anwendungen

Das SRFLP tritt, neben der praktisch wichtigsten Anwendung bei der Anordnung von Maschinen in einem flexiblen Fertigungssystem, noch in vielen weiteren Bereichen auf. Zum Beispiel...

Ein Beispiel

Bei gegebenen Maschinenlängen $\ell_1 = 1$, $\ell_2 = 2$, $\ell_3 = 3$, $\ell_4 = 4$ errechnet sich die Distanz zwischen zwei Maschinen (blau) als Abstand zwischen den jeweiligen Mittelpunkten. Bei Materialflüssen (rot) $f_{12} = f_{14} = f_{34} = 1$, $f_{13} = f_{24} = 2$ ergeben sich in der nachfolgenden Anordnung Kosten von $22.5$.

Die gezeichnete Anordnung ist eine optimale Lösung des SRFLP.