CarpeDiem - Di 11.03.08 11:38
Titel: Zuschnittproblem

---

Hallo,

ich suche eine Möglichkeit um das Zuschnittproblem zu löschen.
Habe unter http://de.wikipedia.org/wiki/Zuschnittproblem
schon was gefunden, aber bin in Mathe nicht so fit, um das zu
kapieren.


Das Programm soll wie folgt funktionieren:

- Ich habe z. B. 10 Stangen mit je einer Länge von 9990mm
- Ich will diese Stangen so zerteilen, daß es möglichs wenig Verschnitt gibt
- Die Blattstärke der Säge muss berücksichtigt werden
- Ich will verschiedene Längen(mit Anzahl) vorgeben
z. B. 5x600mm, 12x720mm, 3x340mm, .... usw.


Vielleicht kennt jemand von Euch das Problem schon und hat
dafür auch schon einen Quellcode geschrieben.

Vielen Dank gleich mal.


Stefan

Gausi - Di 11.03.08 13:04

---

Laut dem Wikipedia-Artikel ist das Problem NP-schwer (ich würde dann sogar tippen, dass es NP-vollständig ist). Grob gesagt heißt das heißt für einen Algorithmus, der das Problem löst: Einfach alles durchprobieren.

Pack deine Stangen, die du raushaben willst, in eine Liste und fange an, die Stangen aus den Rohlingen rauszuschneiden. Merke dir dann den Verschnitt.

Dann nimmst du eine Permutation der Liste und machst das gleiche nochmal und guckst, ob du damit weniger Verschnitt hast. Das wiederholst du, bis du alle Permutationen deiner Liste durch hast.

CarpeDiem - Di 11.03.08 13:30

---

Ok, danke.

Dann werd ich es wohl so machen müssen.

uko - Di 11.03.08 16:17

---

Das hört sich ein bischen wie Bin-Packing Problem an. Schau mal nach Bin-Packing, First-Fit und genetischen Algorithmen

Grüße,
Uli

Reinhard Kern - Di 11.03.08 16:24

---

stefan.gayr hat folgendes geschrieben:

Ok, danke. Dann werd ich es wohl so machen müssen.

Nicht unbedingt: ich empfehle, eine Stange zu nehmen und davon soviele Abschnitte wie möglich (und natürlich wie gebraucht) mit dem längsten Mass abzuschneiden, dann soviele wie möglich mit dem 2längsten Mass usw. Das ist schreiend einfach und in der Praxis relativ nah am Optimum - umso näher, je mehr zuzuschneiden ist und je kleiner die Stücke sind im Vergleich zum Rohmaterial.

Falls es dich theoretisch interessiert, kannst du ja mal die Ergebnisse dieser und der Brute Force Methode vergleichen - ist natürlich in jedem konkreten Fall anders.

Gruss Reinhard

CarpeDiem - Di 11.03.08 19:02

---

Danke uko und Reinhard,

sieht so aus, als ob die FirstFit-Methode am Besten wäre.
Wenn ich es ausprobiert habe, dann stelle ich den Quellcode
ins Forum.