1D-Zuschnittoptimierung

So funktioniert die 1D-Zuschnittoptimierung

Das eindimensionale Zuschnittproblem (Cutting-Stock-Problem) fragt, wie sich die benötigten Teile aus Material in Standardlänge (Stäbe, Rohre, Profile, Strangpressprofile) mit möglichst wenigen Stangen schneiden lassen. Das Problem ist NP-schwer, daher setzen praxistaugliche Werkzeuge auf schnelle Heuristiken, die bei typischen Werkstatt-Stücklisten sehr nahe ans Optimum herankommen.

First Fit Decreasing (FFD) sortiert alle Teile von der längsten zur kürzesten Länge und legt jedes Teil in die erste Stange, die noch Platz hat; passt es nirgends, wird eine neue Stange angebrochen. Best Fit Decreasing (BFD) sortiert ebenfalls absteigend, legt jedes Teil aber in die Stange, die danach den geringsten Restplatz hätte — das kann enge Kombinationen bei manchen Auftragsmischungen etwas besser packen.

Jeder Schnitt verbraucht Material in Höhe der Sägeschnittbreite. Dieser Rechner setzt die Schnittfuge zwischen aufeinanderfolgenden Teilen derselben Stange an (n Teile benötigen n − 1 Schnitte), sodass der ausgewiesene Verschnitt den echten Endabschnitt vom Schnittfugenverlust trennt. Für FFD garantiert die Theorie, dass das Ergebnis nie mehr als 11/9 × Optimum + 6/9 Stangen benötigt (Dósa, 2007) — in der Praxis ist es meist optimal oder höchstens eine Stange vom Optimum entfernt.

Wann dieses Werkzeug einsetzen

• Zuschneiden von Stücklisten für Betonstahl, Baustahl, Rohre oder Aluminiumprofile aus Standardstangen von 6 m oder 12 m
• Abschätzen, wie viele Stangen für einen Fertigungsauftrag eingekauft werden müssen, bevor Material bestellt wird
• Vergleich des Verschnitts zweier vom Lieferanten angebotener Stangenlängen, um die günstigere Variante zu wählen
• Erstellen einer Schnittfolgenliste für den Sägebediener mit beschrifteten Teilen je Stange
• Getrennte Quantifizierung von Schnittfugenverlust und Endabschnitt-Verschnitt, etwa zur Begründung eines dünneren Sägeblatts

Häufige Fehler vermeiden

• Schnittfuge ignorieren — bei einer 6-m-Stange mit 20 Teilen verbraucht eine 3-mm-Fuge ~57 mm, was das letzte Teil auf eine neue Stange verschieben kann
• Einheiten zwischen Stangenlänge und Teileliste mischen (Stange in Metern, Teile aber in Millimetern eingeben)
• Brutto-Stückzahlen für mehrere Baugruppen eintragen statt die Stückzahlspalte zu nutzen — das macht die Stückliste schwer prüfbar
• Das Heuristik-Ergebnis als garantiertes Optimum für sicherheitskritische Materialbudgets behandeln — bei großen Industrieserien können LP-Verfahren mit Spaltengenerierung einige Stangen zusätzlich einsparen
• Vergessen, dass nutzbare Reststücke (lange Endabschnitte) hier als Verschnitt zählen — wer Reste zur Wiederverwendung einlagert, muss sie vom ausgewiesenen Verschnitt abziehen

Ergebnisse richtig interpretieren

• Stangen benötigt ist die Kernzahl — vergleichen Sie sie mit der unteren Schranke ⌈Gesamtteilelänge ÷ Stangenlänge⌉, um zu beurteilen, wie dicht der Plan ist
• Eine Ausnutzung über ~90% ist bei gemischten Stücklisten gut; über 95% ist hervorragend und bedeutet meist, dass sich die Teilelängen gut mit der Stangenlänge kombinieren
• Der Verschnitt je Muster zeigt, welche Stangen den Endabschnitt tragen — eine einzelne Stange mit dem Großteil des Verschnitts liefert oft ein nutzbares Reststück
• Der Schnittfugenverlust wächst mit der Teileanzahl, nicht mit der Teilelänge — viele kurze Teile verlieren anteilig mehr Material an das Sägeblatt
• Liefern FFD und BFD dieselbe Stangenzahl, ist der Plan für diese Stangenlänge mit hoher Sicherheit optimal; weichen sie ab, nehmen Sie den besseren

Zugehörige Normen & Literatur

• Gilmore & Gomory (1961) — A Linear Programming Approach to the Cutting-Stock Problem (Operations Research 9:849-859), das grundlegende exakte Verfahren
• Dósa (2007) — scharfe Worst-Case-Schranke für First Fit Decreasing: FFD(I) ≤ 11/9·OPT(I) + 6/9
• Johnson (1973) — Near-optimal bin packing algorithms (MIT), die klassische Analyse der FFD/BFD-Heuristikfamilie
• Handelsübliche Stangenlängen folgen häufig den Walzlängen 6000 mm und 12000 mm für Betonstahl und Stahlprofile; prüfen Sie vor der Optimierung die Liste Ihres Lieferanten

Häufig gestellte Fragen

Soll ich FFD oder BFD wählen?

Beide sortieren die Teile beginnend mit dem längsten und unterscheiden sich nur in der Stangenwahl: FFD nimmt die erste Stange mit Platz, BFD die mit der engsten Passung. Meist liefern sie dieselbe Stangenzahl; weichen sie ab, beträgt der Unterschied eine Stange. Rechnen Sie beide (ein Klick) und behalten Sie den besseren Plan.

Wie wird die Schnittfuge angesetzt?

Die Schnittfuge wird zwischen aufeinanderfolgenden Teilen derselben Stange addiert — n Teile benötigen n − 1 Schnitte, der Endabschnitt am Ende braucht keinen zusätzlichen Schnitt. Stellen Sie die Fuge auf Ihre tatsächliche Sägeblatt- oder Brennerbreite ein (typisch 2-4 mm bei Kaltkreissägen, 1-2 mm bei Bandsägen).

Kann das Ergebnis schlechter als das echte Optimum sein?

Ja, aber nur um eine beweisbar kleine Marge: FFD benötigt nie mehr als 11/9 der optimalen Stangenzahl plus eine Konstante. Für Stücklisten im Werkstattmaßstab ist das Ergebnis fast immer optimal; bei Serien im Walzwerksmaßstab mit Tausenden Teilen können exakte Spaltengenerierungs-Solver gelegentlich weitere Stangen einsparen.