Algorithmus für die Montage von boards, um die verfügbaren Längen, die Minimierung der Abfälle

Ich Schreibe eine Anwendung in den lumber yard. Sie erhalten eine Reihe von Brett oder Balken Längen, das Ziel ist die Berechnung der Anzahl der boards gebraucht werden, während gleichzeitig die Minimierung der Abfälle. Man könnte beispielsweise die folgenden shopping-Liste für eine bestimmte dimension:

3x 2,9 m

5x 1,6 Meter

21 x 0,9 Meter

Am Holzplatz, man würde prüfen, ob die verfügbaren Längen der Dielen und geben Sie es in die Anwendung. Können sagen, dass diese dimension ist erhältlich in 4,8 Meter Länge.

Ein einfacher Ansatz wäre, zu versuchen und passen Sie die übrigen Bretter in absteigender Längen:

2.9 + 2.9 = 5.8, so dass die nicht passen auf einem 4,8-meter-Brett

2.9 + 1.6 = 4.5, so ist das ok.

Nein Länge ist weniger als die restlichen 0,3 Meter, so dass dieses board ist "voll". Wir passen zwei weitere dieser Art, und dann haben wir die folgenden Längen Links zu passen:

2x 1,6 Meter

21 x 0,9 Meter

Ok, damit dieser Algorithmus funktioniert auch Recht gut. Aber was, wenn wir statt der Montage der 2,9 + 1.6, passen wir 2.9 + 0.9 + 0.9 = 4.7 statt. Wir erhalten dann 0,1 m Abfall pro board, anstelle von 0,3 Meter.

Einem problem in der Aufzählung aller möglichen Kombinationen ist, dass jede Länge kann mehr als einmal erscheinen, in einem board, und die Anzahl der Längen, montiert auf einem board variieren, wie gut. Gibt es einen bekannten Algorithmus, den ich verwenden können, zu minimieren, den gesamten Abfall für alle boards?

Auch, was, wenn es zwei oder mehr Längen verfügbar am Holzplatz? Zum Beispiel 5.4, 4.8 und 3.6 Meter? Dies wird sicherlich die Dinge zu komplizieren. Man könnte ausführen der ausgewählten Algorithmus für jeden verfügbar, Länge und wählen Sie die Länge mit der geringsten Menge von Abfällen. Aber die eleganteste Lösung wäre das mischen der verfügbaren Längen, so dass die optimale Antwort wäre so etwas wie 1x 5.4, 3x 4.8, 6x 3.6. Aber für den Anfang würde ich glücklich sein, mit der Einschränkung das die Antwort auf eine Länge.

InformationsquelleAutor Anlo | 2012-05-03
  1. 2

    @Anlo,

    Ihr spezielles problem ist eine Variante des so genannten "Cutting Stock" - Klasse von Problemen.
    Werfen Sie einen Blick auf Wikipedia - " Cutting Stock Problem " (CSP) Seite

    Ich mag diese Erklärung in einfachem Englisch eine einfachere version des Cutting-Stock Problem.
    Von AIMMS:

    "Cutting stock problem: wie schneidet langen Rollen des Materials (bezogen auf
    als raw Dateien) in kleineren Rollen an einer vorgeschriebenen Größe (bezeichnet als
    Finale), da eine Nachfrage für die einzelnen Finale."

    Beachten Sie, dass es gibt eine ganze Reihe von Variationen zu den Grundlegenden Cutting Stock Problem, dass Forscher haben kommen mit. Diese Integer Programming lecture notes gute Formulierung des generalisierte Cutting Stock problem (siehe Seite 17)

    Diese MILP-Probleme sind nicht sehr schwer zu formulieren, da die Zielfunktion und die Nebenbedingungen Folgen die grundlegenden Muster der standard-CSP. Einen großen Körper der Forschung vorhanden ist, auf Techniken zu lösen, um Sie effizient.

    Wenn Sie Zugang zu einem LP - /IP-solver wie CPLEX, R oder Excel-Solver (für kleinere Probleme), es lohnt sich definitiv, formulieren Sie Ihr problem und versuchen Sie es auf diese Solver.

    Hoffe, das hilft.

    InformationsquelleAutor Ram Narasimhan
  2. 3

    Minimierung der Abfälle ist eigentlich Optimierungsproblem für die generalisierte subset-sum-problem, die NP-Vollständig, und somit gibt es keinen bekannten polynomialen Lösung für dieses problem,

    Zwar NP-Vollständig, man kann produzieren pseudo-polynomiale Lösung für dieses problem mit Hilfe der dynamischen Programmierung, oder reduzieren es auf Ranzen (Gewicht=Wert=Länge, B=board Größe), und seine pseudo-polynomiale Lösung, das ist sehr ähnlich.

    Aber hier ist es noch schwieriger, die pseudo-polynomial-Lösung übernimmt ganze zahlen, während Ihre Beispiele zeigen, dies ist nicht der Fall. Du kannst es lösen, indem Sie mit fixed-point Arithmetik repräsentieren die Längen (d.h. 4.8 wird dargestellt, wie 48, wenn Sie nur eine Ziffer nach dem Punkt pro Länge, wenn Sie mit 2 Ziffern nach dem Punkt, es werden 480,...).

    Hinweis: dieser Algorithmus minimiert den Abfall für Sie, aber es keine Garantie für die "minimale Anzahl der Protokolle" für die minimierte Verschwendung.

    In jedem Fall, da die Suche nach alle Lösung ist NP-Schwer, das finden der Lösung, verwendet mindestens logs ist auch NP-Schwer.

    • Ich habe etwas zu Lesen zu tun, zu verstehen, Ihre Antwort vollständig. Aber jetzt kann ich wenigstens kommentieren, dass die Minimierung der Abfälle ist gut genug, denn Sie bezahlen für die gesamte Länge gekauft. Ist es nicht eigentlich egal, wie viele boards es gibt, wenn die totale Verschwendung ist die gleiche.
    • In diesem Fall, ist der vorgeschlagene Algorithmus garantieren, aber hüten Sie sich exponentiell Verhalten, der Algorithmus möglicherweise erscheinen Polynom, aber es ist pseudo-polynomial und irreführend, zumal Sie mit Gebrochener Längen hier. Jedoch, da das problem NP-Hart, es sei denn, Sie verwenden können, approximation, algorithmen, Sie sind zu viel Auswahl hier..
    • Mit fixed-point Arithmetik ist überhaupt kein problem. Zentimeter (480) ist wahrscheinlich gut genug, Millimeter (4800) definitiv ist. Gibt es irgendeine Stelle in versuchen zu halten, die zahlen klein sind (D. H. mit 480 statt 4800)?
    • gute Frage! ja! Der Algorithmus der Komplexität ist (n*W), wo n ist die Anzahl der Protokolle und W ist die Größe des Vorstands. Die Suche nach einer Lösung für ein board von der Größe 4800 dauert 10 mal länger (und mehr Platz) dann ein board von der Größe 480.
    InformationsquelleAutor amit
Schreibe einen Kommentar