Berechnung einer Schnittliste mit der geringsten Menge an Schnittabfall

Question

Ich arbeite an einem Projekt, bei dem ich eine Zuschnittsliste für Aluminium-Strangpressprofile erstelle.

Die Aluminiumprofile sind in Längen von 5 m erhältlich.

Ich habe eine Liste mit kleineren Längen, die aus den 5 m langen Aluminiumstrangpressprofilen geschnitten werden müssen.

Die kleineren Längen müssen in der Reihenfolge geschnitten werden, bei der bei den 5 m langen Aluminiumstrangpressprofilen am wenigsten Abfall anfällt.

Derzeit ordne ich die Zuschnittliste so, dass im Allgemeinen die längste der kleineren Längen zuerst und die kürzeste der kleineren Längen zuletzt geschnitten wird.Die Ausnahme von dieser Regel besteht darin, dass ich immer dann, wenn eine kürzere Länge nicht in den Rest der 5 m langen Aluminiumstrangpresslänge passt, die längste kürzere Länge verwende, die passt.

Dies scheint eine sehr effiziente Schnittliste (sehr wenig Abfall) zu erstellen, und die Berechnung dauert nicht lange.Ich stelle mir allerdings vor, dass es sich zwar um die Schnittliste handelt sehr effizient, es ist nicht unbedingt das am meisten effizient.

Kennt jemand eine Möglichkeit, die effizienteste Schnittliste zu berechnen, die in angemessener Zeit berechnet werden kann?

BEARBEITEN:Vielen Dank für die Antworten. Ich werde weiterhin den „gierigen“ Ansatz verwenden, da er offenbar sehr gute Arbeit leistet (alle menschlichen Versuche, eine effiziente Schnittliste zu erstellen, übertrifft) und sehr schnell ist.

Answer 1

Dies ist ein klassisches, schwer effizient zu lösendes Problem.Der von Ihnen beschriebene Algorithmus klingt wie ein Gieriger Algorithmus.Weitere Informationen finden Sie in diesem Wikipedia-Artikel: Das Schnittgutproblem

Answer 2

Ich fürchte, es gibt keine konkreten Ideen zu diesem Problem – aber Sie könnten sich eine Frage stellen.genetischen Algorithmus' (was gehen würde etwas so was)...

Ordnen Sie die zu schneidenden Längen in zufälliger Reihenfolge an und bewerten Sie diese Reihenfolge danach, wie gut sie mit Ihrer idealen Lösung übereinstimmt (vermutlich 0 % Abfall).

Nehmen Sie dann iterativ zufällige Änderungen an der Reihenfolge vor und bewerten Sie sie erneut.Wenn die Punktzahl höher ist, lassen Sie das Ergebnis fallen.Wenn die Punktzahl niedriger ist, behalten Sie sie und verwenden Sie sie als Grundlage für Ihre nächste Berechnung.Machen Sie weiter, bis Ihr Punktestand innerhalb akzeptabler Grenzen liegt.

Answer 3

Was Sie beschrieben haben, ist tatsächlich als klassifiziert Schneiden von Material Problem, als Wheelie erwähnt, und nicht a Behälterverpackung Problem, weil Sie versuchen, den Abfall (Summe der Reste) zu minimieren und nicht die Anzahl der verwendeten Extrusionen.

Beide Probleme können sehr schwer zu lösen sein, aber der von Ihnen erwähnte „Best-Fit“-Algorithmus (unter Verwendung der längsten „kleinen Länge“, die zur aktuellen Extrusion passt) wird Ihnen wahrscheinlich sehr gute Antworten mit einer sehr geringen Komplexität liefern.

Answer 4

Da die Größe des Materials feststeht, die Anforderungen jedoch nicht, handelt es sich tatsächlich um ein Problem mit der Behälterverpackung.

Wieder, Wikipedia zur Rettung!

(Etwas, nach dem ich vielleicht auch suchen muss, um Arbeit zu finden, also juhuu!)

Answer 5

Das ist ein interessantes Problem, denn ich nehme an, es hängt von der Menge der einzelnen Längen ab, die Sie produzieren.Wenn es alle die gleiche Menge gibt und Sie jede unterschiedliche Länge auf ein 5-m-Profil bringen können, dann haben Sie die optimale Lösung.

Wenn jedoch nicht alle auf ein Profil passen, liegt ein größeres Problem vor.Um die gleiche Anzahl an Schnitten für jede Länge beizubehalten, müssen Sie berechnen, wie viele Längen (nicht unbedingt in der richtigen Reihenfolge) auf eine Extrusion passen, und dann in der Reihenfolge durch jede Extrusion gehen.

Answer 6

Ich habe auch hier mit genau diesem Problem zu kämpfen (die Länge für mein Problem beträgt 6 m).

Die Lösung, an der ich arbeite, ist etwas hässlich, aber ich gebe mich nicht mit Ihrer Lösung zufrieden.Lassen Sie mich erklären:

Lagergröße 5 m

Muss in folgende Größen geschnitten werden (jeweils 1 Stück):

**3,5

1

1,5**

Ihre Lösung:

3,5 | 1 mit einem Abfall von 0,5

1,5 mit einem Rest von 3,5

Sehen Sie das Problem?

Die Lösung, an der ich arbeite -> Brute Force

1 – Testen Sie jede mögliche Lösung

2 - Ordnen Sie die Lösung nach Abfall

3 – Wählen Sie die beste Lösung

4 – Entferne die Elemente in der Lösung aus dem „Universum“

5 – Gehe zu 1

Ich weiß, dass es zeitaufwändig ist (aber ich brauche 1 Stunde und 30 Minuten zum Mittagessen ...Also...:) )

Ich brauche wirklich die optimale Lösung (ich erstelle eine nahezu optimale Lösung per Hand (+-) in Excel), nicht nur, weil ich aufdringlich bin, sondern auch, weil das Produkt nicht billig ist.

Wenn jemand eine einfache, bessere Lösung hat, würde ich mich freuen