Das Cutting-Stock-Problem verständlich erklärt
Was das Cutting Stock Problem ist, warum es NP-schwer ist und wie 1D-/2D-Optimierer (Guillotine vs. True Nesting) schnell gute Lösungen finden.
Was ist das Cutting-Stock-Problem?
Aus Lagerlängen (Stangen, Bretter, Platten) soll eine Liste benötigter Teile mit möglichst wenig Material geschnitten werden. Das klingt simpel, ist mathematisch aber NP-schwer — die Kombinationszahl explodiert mit jeder weiteren Position.
1D, 2D und Guillotinenschnitte
1D heißt eine Dimension: Rohre, Profile, Balken. Bei 2D kommt die Breite dazu — Sperrholz, Glas, Blech. Guillotinenschnitte laufen über die ganze Kante (Plattensäge); True Nesting erlaubt jede Drehung und nicht-guillotineförmige Layouts (Laser, Router).
Warum exakte Lösungen selten sind
Nur kleine Instanzen lassen sich exakt lösen (dynamische Programmierung, Integer Programming). In der Praxis dominieren Heuristiken — First Fit Decreasing, Best Fit Decreasing, Shelf-Algorithmen — meist wenige Prozent vom Optimum, in Millisekunden.
Sägeblattbreite und andere Fallen
Jeder Schnitt kostet Material: 3 mm Sägeblattbreite × 50 Schnitte = 150 mm Verlust. Resteverwertung, Faserrichtung und Besäumung spielen mindestens genauso eine Rolle wie das Packen selbst.
Mit der eigenen Schnittliste testen
Der Längszuschnitt-Rechner optimiert Stangen- und Profillisten; der Plattenzuschnitt-Rechner erzeugt Guillotine-Plattenlayouts mit Drehung und Sägeblattbreite. Liste einfügen und den Materialbedarf vorher/nachher vergleichen.