Industrielles Partitionierungsproblem

StackOverflow https://stackoverflow.com/questions/1405837

Frage

Wir reden über Metall-Werk. Es gibt Maschine, die lange Eisenstangen auf kleinere Teile schneiden, die für die Erstellung von verschiedenen Produkten, die später verwendet werden.

Zum Beispiel habe ich Anforderung Bars zu produzieren folgende Länge und Menge: 2 Stücke von 248mm, 5 von 1150mm, 6 von 2843mm, 3 von 3621mm.

Das ist die Partitionierung ausgegeben.

Am Eingangsseite habe ich (wieder zum Beispiel) 3 Balken von 2500mm, 2 bar von 5000mm, 6 bar von 8000mm und 3 Bars von 10.000 mm.

soll ich einen Weg finden, wie die Eingabestangen optimal schneiden -. Den Rest (Teile übrigen, die zu klein sind, um verwendet zu werden) nach dem Schneiden soll kleinste wie möglich sein

Ich habe Algorithmus erstellt, die einfach alle möglichen Kombinationen erzeugt und dann am besten unter ihnen auszuwählen. Code funktioniert, aber sobald Eingang und Ausgang ist etwas größer, kann die Berechnung sehr lange dauern, also muß ich neuen Herangehensweise an das Problem finden.

Haben Sie irgendwelche Hinweise haben?

War es hilfreich?

Lösung

Ihr Problem ist ziemlich weit verbreitetes Problem in Operations Research. Ansehen Lager Problem Schneiden. Dieses Problem ist im Wesentlichen NP-schwer, wie Sie auf eigene Faust herausgefunden haben. Es ist nicht sehr gut skalieren.

Wie es zu lösen? Nachdem Sie in der Lage sind, das Modell, um herauszufinden, wäre es am besten einige gemischten Integer Programming-Solver zu nennen. Ich habe früher verwendet LPSolve 5.5

Es kann simplier Algorithmen, die Sie, die sich mit diesem Problem insbesondere codieren könnte. Das Problem mit diesen Algorithmen entsteht in der Regel, wenn Sie einige Nebenbedingungen hinzufügen müssen, dass die Autoren nicht gedacht. Der MIP-Löser ist viel mehr generisches Werkzeug.

Andere Tipps

Dies ist das variable Größe Bin Packing Problem genannt. Es ist NP hart, was bedeutet, dass Ihre Lösung wird immer für großen Eingang scheitern. Dieser Artikel, hier , die ich leider keinen Zugang haben, Adressen dieses Problem und verwendet die spanabhebende Industrie als Beispiel.

Lineare Programmierung ist dein Freund. Siehe http://en.wikipedia.org/wiki/Linear_programming im Allgemeinen und, besonders , http://en.wikipedia.org/wiki/Linear_programming#Uses , < a href = "http://en.wikipedia.org/wiki/Linear_programming#Algorithms" rel = "nofollow noreferrer"> http://en.wikipedia.org/wiki/Linear_programming#Algorithms .

Sieht aus wie es auf dem Knapsackproblems ähnlich ist (weiß wirklich böse zu sein) fand ich diese auf den NIST DADS (praktische Referenz) leichter als ACM zu erhalten für Nichtmitglieder a href = "http <: //www.itl .nist.gov / div897 / SQG / Väter / HTML / binpacking.html“rel = "nofollow noreferrer"> Bin Packing

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top