Algorithmus für das Fertigungslayout?

Ich bin gestern auf ein Unterrichtsproblem gestoßen (wirtschaftsorientierte Klasse, nicht Informatik) und fand es aus algorithmischer Sicht interessant.

Das Problem sieht ungefähr so aus:
Angenommen, es gibt eine Werkstatt mit N verschiedenen Räumen, und Sie haben N verschiedene Abteilungen, die in diese Räume gehen müssen. Die Abteilungen und Räume sind alle gleich groß, sodass jede Abteilung in jeden Raum gehen kann. Es gibt eine bekannte Reisedistanz von jedem Raum zu jedem anderen Raum. Es ist auch eine bekannte Anzahl von Fahrten von einer Abteilung zur anderen erforderlich (Fahrten werden gleich gezählt, unabhängig davon, aus welchem ​​Raum sie stammen, sodass eine Fahrt von A nach B einer Reise von B nach A entspricht). Bestimmen Sie anhand dieser Eingaben eine Anordnung der Abteilungen in Räumen, die die Reisezeit minimiert.

Was ist der beste Weg, um dieses Problem algorithmisch anzugehen? Gibt es bereits einen bestimmten Algorithmus oder eine bestimmte Klasse von Algorithmen, mit denen diese Art von Problem gelöst werden kann? Hat diese Art von Problem einen Namen in der Informatik?

Ich suche nicht, dass Sie einen Algorithmus entwerfen , um dies zu lösen, obwohl Sie dies gerne tun, wenn Sie möchten. Ich frage mich, ob dies ein Problembereich ist, der bereits gut definiert und algorithmisch untersucht wurde, und wenn ja, erhalten Sie einige Links zur weiteren Forschung. Ich kann viele verschiedene Datenstrukturen und Algorithmen sehen, die darauf zutreffen könnten, und ich bin gespannt, welcher Ansatz "am besten" wäre.

Und keine Sorge, du machst meine Hausaufgaben nicht für mich. Dies ist an sich kein Hausaufgabenproblem, da es sich um einen Business-Kurs handelt und wir lediglich die Konzepte diskutierten und nicht versuchten, das Problem algorithmisch zu lösen.

Dies wird als Standortproblem der Einrichtung bezeichnet , bei dem es sich um ein NP-schwieriges Problem handelt. Eine typische algorithmische Lösung für ein solches Problem ist die Verwendung von Approximationsalgorithmen .

Eine pragmatische Lösung:

1) Verteilen Sie alle Abteilungen nach dem Zufallsprinzip (geben Sie die Abteilungsnamen in eine Box und ziehen Sie sie zusammen mit der Anzahl der Räume heraus). 2) Geben Sie allen Mitarbeitern neue Schuhe. 3) Messen Sie den Schuhverbrauch (Laufsohlen und Absätze) nach zwei Wochen. 4) Stellen Sie die Abteilungen, deren Angestelltenschuhe den Hauptverbrauch aufweisen, direkt in die Nähe. 5) Wiederholen Sie diese Methode n-mal (n = Anzahl der Abteilungen) ) 6) Nach n Versuchen messen Sie den Durchschnitt des Schuhverbrauchs und wissen, welche die beste Verteilung der Abteilungen ist. Aber wenn ich in Ihren Schuhen stecke, würde ich diesen Versuch als mentale Erfahrung mit Hilfe von Algorithmen machen (Sie müssen dieses Verfahren nur formalisieren, wenn Sie gut in Mathe sind, raten Sie bereits, wie ... wenn Sie es nicht herausfinden).

Der einfachste Weg ist: Holen Sie sich das zivile Layout des Gebäudes, markieren Sie die Abteilungsorte bildlich mit einem Diagrammblatt (am besten verwenden Sie Auto-CAD oder eine andere 2D / 3D-Software). Sie müssen dann beurteilen, wie viel Platz Sie haben und wie Sie die Abteilungen platzieren möchten. Auf dem Blatt können Sie die Entfernungen zwischen den Abteilungen abrufen.