Die Zuschnittoptimierung verständlich erklärt

Kabel gibt es nur auf Rollen mit festen Längen, und die längere Rolle ist je Meter billiger. Wer für jedes Stück die billigste passende Rolle kauft, kann trotzdem zu viel zahlen. Die Seite zeigt an einem kleinen Rechenbeispiel, warum, und wie ein Rechenverfahren einen besseren Einkauf findet.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Kabel von der Rolle

Stellen Sie sich vor, Sie verlegen Kabel für eine Gartenbeleuchtung. Sie brauchen fünf Stücke zu je 6 Metern und fünf Stücke zu je 4 Metern. Kabel gibt es nur auf Rollen mit fester Länge, und Sie schneiden Ihre Stücke von der Rolle ab.

Im Laden liegen zwei Rollen: 6 Meter für 6 € und 10 Meter für 9 €. Was von einer Rolle übrig bleibt, ist Abfall, den Sie trotzdem bezahlt haben. Fachleute sagen Verschnitt.

Rechnen Sie je Meter: Die kurze Rolle kostet einen Euro je Meter, die lange weniger. Die lange Rolle spart aber nur Geld, wenn Sie sie gut füllen. Landet ein großer Teil im Abfall, ist der Vorteil dahin.

Die Faustregel: je Stück die billigste Rolle

Eine naheliegende Faustregel lautet: Nimm für jedes Stück die billigste Rolle, die lang genug ist. Sie beginnt mit den längsten Stücken. Jedes Stück schneidet sie zuerst von einer schon angebrochenen Rolle ab, wenn der Rest reicht. Fachleute nennen das First-Fit-Decreasing, kurz FFD.

Angenommen, Sie wenden sie an. Für ein 6-Meter-Stück ist die kurze Rolle die billigste, die reicht, und sie geht ohne Rest auf. So geht es allen fünf. Dann folgen die 4-Meter-Stücke. Nach einem Stück bleiben von der kurzen Rolle zwei Meter übrig, zu wenig für ein weiteres. Jedes Stück bekommt also eine eigene kurze Rolle.

Das macht 10 Rollen für 60 €. Besser ist es, fünf lange Rollen zu kaufen und von jeder ein 6-Meter- und ein 4-Meter-Stück abzuschneiden. Es bleibt nichts übrig, und es kostet 45 €.

Warum übersieht die Faustregel das? Für das 6-Meter-Stück allein wirkt die lange Rolle zu teuer, denn 9 € sind mehr als 6 €. Dass später ein 4-Meter-Stück daneben passt, sieht sie nicht. Sie entscheidet immer nur für das Stück in der Hand.

Billiger geht es hier nicht. Sie brauchen nicht weniger Länge, als alle Stücke zusammen messen. Die fünf langen Rollen haben genau diese Länge, und die lange Rolle ist je Meter die billigste. Also kann der Einkauf nicht weniger kosten.

Wie ein Rechenverfahren das findet

Bei zwei Stücklängen sieht man den besseren Plan sofort. Bei sechs Längen und drei Rollen nicht mehr. Es gibt zu viele Arten, eine Rolle zu zerschneiden, um sie von Hand durchzugehen.

Hier hilft ein Rechenverfahren, das in der Fachsprache Column Generation heißt. Es arbeitet mit Schnittplänen. Ein Schnittplan sagt, wie viele Stücke welcher Länge Sie aus einer Rolle schneiden. Fachleute sagen Schnittmuster. Das Verfahren beginnt mit einfachen Schnittplänen: Jede Rolle liefert nur Stücke einer Länge.

Dann fragt es immer wieder: Gibt es einen weiteren Schnittplan, der den bisherigen Einkauf billiger macht? Dazu rechnet es zuerst aus, was ein zusätzliches Stück einer Länge den jetzigen Einkauf kosten würde. Das ist der Preis dieser Länge im jetzigen Einkauf.

Im Beispiel kostet im ersten Plan jedes 6-Meter-Stück eine kurze Rolle, also 6 €. Auch ein 4-Meter-Stück bekommt eine eigene kurze Rolle und kostet damit 6 €. Ein 6er und ein 4er auf einer langen Rolle sind im jetzigen Plan zusammen mehr wert, als die lange Rolle kostet. Dieser Schnittplan spart Geld, und das Verfahren nimmt ihn auf. Dann rechnet es die Preise neu aus.

So sucht das Verfahren gezielt statt alles durchzuprobieren. Es hört auf, wenn kein Schnittplan mehr mehr wert ist, als seine Rolle kostet.

Für diese Rechnung erlaubt sich das Verfahren einen Trick: Es darf vorübergehend Teile von Rollen kaufen, etwa eine halbe. Das ist unrealistisch, liefert aber eine Untergrenze. Wer sich an weniger Regeln halten muss, zahlt nie mehr als jemand mit strengeren Regeln. Ganze Rollen sind strenger, also kann der echte Einkauf nicht billiger sein.

Am Ende rundet das Verfahren auf ganze Rollen. Es kauft zuerst die ganzen Rollen, die der Plan sicher braucht, und deckt den Rest mit der Faustregel ab. Liegt der gerundete Plan genau auf der Untergrenze, ist er nachweislich der billigste.

Was die Demo zeigt

Zu dieser Seite gehört ein Programm zum Ausprobieren im Browser, kurz Demo. Ganz unten in diesem Teil gibt es zwei Knöpfe: Der erste öffnet es, der zweite führt zum zweiten Teil für Fachleute. Zum Verstehen brauchen Sie es nicht. Alles hier ist ein vereinfachtes Rechenbild mit erfundenen Preisen.

Die Demo vergleicht die Faustregel mit dem Rechenverfahren. Beim Start zeigt sie ein Beispiel: eine Bestellung mit sechs Stücklängen knapp über oder unter 5 Metern, je zwölf Stück. Es gibt drei Rollenlängen: 12, 20 und 30 Meter. Die 30-Meter-Rolle ist je Meter am billigsten. Je ein Stück jeder der sechs Längen füllt sie genau.

Die Faustregel nimmt für jedes Stück die billigste Rolle, die reicht. Das ist hier die 12-Meter-Rolle. Auf sie passen zwei Stücke derselben Länge, drei nicht, und der Rest ist für jedes andere Stück zu kurz. Das Rechenverfahren kauft nur 30-Meter-Rollen und schneidet sie ohne Rest.

Die Demo nennt für dieses Beispiel: Die Faustregel kostet etwa 27 % mehr, und das Rechenverfahren spart etwa 22 %. Das ist derselbe Unterschied, einmal auf den kleineren und einmal auf den größeren Preis bezogen. Genau gerechnet sind es gut 27 % und knapp 22 %; die Demo rundet. Die Untergrenze liegt genau auf dem Preis des Rechenverfahrens. Billiger geht es in diesem Beispiel nicht.

Wie viel das Rechenverfahren spart, hängt von der Bestellung ab. Die Demo bringt vier Beispielbestellungen mit und würfelt auf Wunsch eine neue.

Häufige Missverständnisse

• „Die lange Rolle ist die bessere Wahl, weil sie je Meter billiger ist.“ Das gilt nur, wenn Sie sie füllen können. Brauchen Sie ein einziges 4-Meter-Stück, zahlen Sie für die lange Rolle 9 € statt 6 €.
• „Mehrkosten kommen nur vom Abfall.“ Auch der Preis je Meter zählt. In der Demo kauft die Faustregel mehr Länge als nötig, und diese Länge ist je Meter auch noch teurer.
• „Eine Untergrenze ist ein Preis, den man auch bekommt.“ Sie ist nur eine Grenze nach unten. Weil niemand Rollen in Bruchteilen kauft, kann der beste echte Preis darüber liegen.

Woran Sie das im Alltag erkennen

• Stoff, Tapete oder Bretter gibt es nur in festen Längen. Der Rest, den Sie wegwerfen, hat Geld gekostet.
• Beim Tapezieren bleiben von jeder Bahn Reste, die zur nächsten Wand nicht passen.

Wie ernst ist das Rechenbild zu nehmen?

Das Rechenbild kennt nur Längen und Preise. Es kennt keine Schnittbreite, keine Liefergrenzen und keine Reste, die Sie später aufbrauchen. Es zeigt, wie sich Faustregel und Rechenverfahren zueinander verhalten, nicht, was ein echter Einkauf kostet.

Was Sie mitnehmen

• Rechnen Sie bei festen Packungsgrößen je genutzter Einheit, nicht je Packung.
• Legen Sie vor dem Kauf aus, welche Stücke zusammen auf eine Packung passen, bevor Sie die kleinste wählen.
• Fragen Sie bei einer Faustregel, wie billig es mindestens sein könnte. Eine Untergrenze zeigt, ob sich das Suchen lohnt.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Das Modell ist das eindimensionale Zuschnittproblem mit mehreren Rollentypen (Cutting Stock Problem): Aus Rollen verschiedener Länge und verschiedenen Preises werden bestellte Stücke geschnitten, und nur die Länge zählt.

• Bestellung: \(m\) Stückarten; Art \(i\) hat die Länge \(\ell_i\) und den Bedarf \(d_i\) (Stückzahl).
• Rollenkatalog: \(K\) Rollentypen; Typ \(k\) hat die Länge \(L_k\) und den Preis \(c_k\) je Rolle. Der Preis ist frei wählbar und nicht proportional zur Länge; der Vorrat jedes Typs ist unbegrenzt. In der Voreinstellung gibt es drei Typen mit zwölf, zwanzig und dreißig Metern zu acht Euro fünfzig, vierzehn und zwanzig Euro. Der Preis je Meter sinkt mit der Länge.
• Schnittmuster: Ein Muster ist ein Vektor ganzer Zahlen \(a_i \ge 0\) (Stücke der Art \(i\) aus einer Rolle) mit \(\sum_i \ell_i a_i \le L_k\) für den Typ \(k\), aus dem geschnitten wird. Ein Muster kann für mehrere Typen zulässig sein, zu verschiedenem Preis; deshalb zählt jedes Muster zusammen mit seinem Typ.
• Ziel: Der Gesamtpreis der geschnittenen Rollen soll minimal sein. Der Bedarf muss mindestens gedeckt sein, nicht genau; mehr Stücke als bestellt sind zulässig. In der Verschnittkennzahl der Demo zählen solche Überschüsse als Verschnitt, damit der Vergleich mit FFD fair bleibt, das nie mehr schneidet als bestellt.
• Bestellung der Voreinstellung: sechs Stückarten mit Längen zwischen vier Meter fünfundachtzig und fünf Meter zwanzig, je zwölf Stück. Die sechs Längen summieren sich auf dreißig Meter, die Länge des längsten Rollentyps.
• Zufällige Bestellungen: Die Demo erzeugt auf Wunsch zwei bis zehn Stückarten mit Längen von fünfzehn bis fünfundsechzig Prozent der längsten Rolle (auf einen Dezimeter gerundet) und einem ganzzahligen Bedarf von fünf bis fünfundzwanzig je Art.
• Nicht im Modell: Schnittbreite, Reihenfolge und Rüstzeiten, aufbewahrte Reste, begrenzte Liefermengen und Mindestbestellmengen.

Die beiden Verfahren

• First-Fit-Decreasing (FFD): Die Stücke werden einzeln nach absteigender Länge abgearbeitet. Jedes Stück kommt in die erste bereits geöffnete Rolle, deren Rest reicht. Reicht keine, wird eine neue Rolle des billigsten Typs geöffnet, der für dieses Stück lang genug ist (bei gleichem Preis die kürzere). Die Entscheidung ist rein lokal: weder der Preis je Meter noch die noch folgenden Stücke gehen ein.
• Column Generation: Start mit je einem Muster je Stückart, geschnitten aus dem kürzesten Typ, der ein Stück dieser Art aufnimmt, mit so vielen Kopien des Stücks, wie hineinpassen. Dann wiederholt sich: Die LP-Relaxierung des Master-Problems wird gelöst (die Zahl der Rollen je Muster darf reell sein), aus ihr werden die Dualwerte \(y_i\) abgelesen, für jeden Rollentyp wird ein Rucksack-Teilproblem gelöst, und das Muster mit den kleinsten reduzierten Kosten über alle Typen kommt als neue Spalte hinzu. Das endet, wenn keine reduzierten Kosten mehr unterhalb einer kleinen absoluten Toleranz (ein Millionstel) negativ sind oder das gefundene Muster schon enthalten ist.
• Teilproblem: exakte dynamische Programmierung auf einem Raster (Zentimeter, bei Längen mit feinerer Stufung Millimeter). Stücklängen werden aufgerundet und Rollenlängen abgerundet, damit kein gefundenes Muster länger als seine Rolle ist.
• Rundung: Von der reellen Lösung werden die ganzen Rollen je Muster übernommen (abgerundet), der verbleibende Bedarf wird mit FFD gedeckt, und zwar mit dem ganzen Katalog und neu geöffneten Rollen; angebrochene Rollen der abgerundeten Lösung werden dabei nicht aufgefüllt. Das Ergebnis ist zulässig, aber nicht notwendig optimal.

Die Formeln

Zur Schreibweise: \(a_{ij}\) gehört zu einer Spalte \(j\) des Master-Problems, \(a_i\) ist der Eintrag eines einzelnen neuen Musters im Teilproblem. Eine Spalte \(j\) ist ein Paar aus einem Rollentyp \(k(j)\) und einem Muster mit den Einträgen \(a_{ij}\) (Stücke der Art \(i\)); \(x_j \ge 0\) ist die Zahl der Rollen, die nach Spalte \(j\) geschnitten werden. Das Master-Problem wählt die billigste Mischung:

\[\min \sum_j c_{k(j)}\, x_j \quad \text{s.t.} \quad \sum_j a_{ij}\, x_j \geq d_i \ \ \forall i, \quad x_j \geq 0\]

Die LP-Relaxierung lässt reelle \(x_j\) zu. Ihre Dualwerte \(y_i \ge 0\) geben an, wie viel eine zusätzliche Einheit Bedarf der Art \(i\) den Plan verteuern würde. Zu einem Rollentyp \(k\) fragt das Teilproblem, welches Muster mit den Einträgen \(a_i\) die Dualwerte am besten ausnutzt:

\[\max \sum_i y_i\, a_i \quad \text{s.t.} \quad \sum_i \ell_i\, a_i \leq L_k, \quad a_i \in \mathbb{Z}_{\geq 0}\]

Die reduzierten Kosten dieses Musters sind \(c_k - \sum_i y_i a_i\). Ist der kleinste Wert über alle Typen negativ, kommt das Muster als neue Spalte hinzu. Gibt es keinen negativen Wert mehr, ist die LP-Relaxierung optimal. Ihr Wert ist dann eine untere Schranke für den Preis jeder ganzzahligen Lösung, sofern das Teilproblem exakt gelöst wurde (auf dem Raster der Demo gilt das bis auf die Rundung der Längen, siehe Grenzen).

Herleitung: Schranke und Voreinstellung durchgerechnet

Dieser Abschnitt ist eine Rechnung dieser Seite, keine Messung der Demo. Die Längen und Preise der Voreinstellung stehen darin in Worten, weil sie nicht in der Beschreibung der Demo vorkommen.

• Schritt 1, die Schranke: Jede ganzzahlige zulässige Lösung ist auch für die LP-Relaxierung zulässig. Ihr Preis ist also mindestens der LP-Wert. Erreicht ein ganzzahliger Plan den LP-Wert, ist er optimal. Liegt er darüber, folgt aus der Schranke allein nicht, ob eine bessere ganzzahlige Lösung existiert.
• Schritt 2, eine einfache Schranke: Sei \(\rho = \min_k c_k/L_k\) der kleinste Preis je Meter und \(D = \sum_i \ell_i d_i\) die bestellte Gesamtlänge. Eine Rolle des Typs \(k\) liefert höchstens \(L_k\) Meter und kostet \(c_k \ge \rho L_k\). Jede zulässige Lösung kostet also mindestens \(\rho D\). Derselbe Beweis über die Dualität: Die Dualwerte \(y_i = \rho\,\ell_i\) sind zulässig, denn \(\sum_i y_i a_i \le \rho L_k \le c_k\) gilt für jedes Muster; der LP-Wert ist also mindestens \(\rho D\).
• Schritt 3, Voreinstellung, Column Generation: Die lange Rolle hat den kleinsten Preis je Meter. Die bestellte Gesamtlänge ist zwölfmal die Summe der sechs Längen, also zwölfmal dreißig Meter. Damit ist \(\rho D\) gleich dem Preis von zwölf langen Rollen. Zwölf lange Rollen ohne Rest erreichen diesen Wert, und die Demo findet einen solchen Plan. Er liegt auf der Schranke und ist damit optimal.
• Schritt 4, Voreinstellung, FFD: Jedes Stück passt auf eine kurze Rolle, zwei Stücke derselben Art passen zusammen darauf, drei nicht. Der Rest nach zwei Stücken ist höchstens zwei Meter dreißig lang, kürzer als jede Stückart; FFD kann also keine andere Stückart hinzulegen. Zweiundsiebzig Stücke ergeben sechsunddreißig kurze Rollen. FFD zahlt dreihundertsechs Euro (sechsunddreißig mal acht Euro fünfzig), Column Generation zweihundertvierzig Euro (zwölf mal zwanzig). Das ist ein Aufschlag von siebenundzwanzigeinhalb Prozent auf den Preis von Column Generation, und die Ersparnis von Column Generation beträgt knapp zweiundzwanzig Prozent des FFD-Preises.
• Schritt 5, Zerlegung des Aufschlags: Sechsunddreißig kurze Rollen haben zusammen sechsunddreißigmal zwölf Meter Länge für dreihundertsechzig Meter bestellte Stücke: ein Fünftel mehr gekaufte Länge als bestellt, ein Sechstel der gekauften Länge ist Verschnitt. Außerdem kostet ein Meter kurzer Rolle ein Sechzehntel mehr als ein Meter langer Rolle. Beide Aufschläge multiplizieren sich zu siebenundzwanzigeinhalb Prozent.

Befunde

Die erste Zeile stammt aus den Angaben der Demo. Die übrigen Zeilen sind Nachrechnungen dieser Seite mit dem Code der Demo (Master-Problem, Teilproblem und FFD unverändert) oder Ergebnisse der automatischen Tests der Demo; sie sind keine Messungen der Demo selbst. Preise sind Gesamtpreise der gekauften Rollen. Ersparnis ist der Preisunterschied bezogen auf den FFD-Preis.

Frage	Befund
Voreinstellung (sechs Stückarten, drei Rollentypen): wie viel teurer ist FFD?	FFD ist etwa 27 % teurer als Column Generation, bezogen auf deren Preis. Umgekehrt spart Column Generation etwa 22 %, bezogen auf den FFD-Preis. Die LP-Schranke liegt auf dem Preis von Column Generation, diese Lösung ist damit optimal.
Handbeispiel mit einem Rollentyp (Länge 10, Stücke 6 und 4, Bedarf je 5)	Optimal sind fünf Rollen mit dem gemischten Muster aus je einem Stück beider Arten, ohne Rest. Allein mit Mustern aus nur einer Stückart wären es von Hand gerechnet acht Rollen. Der Test der Demo verlangt fünf Rollen und das gemischte Muster in der Lösung.
Vier Beispielbestellungen der Demo (Schnellstart-Knöpfe „Worst Case für FFD“, das ist die Voreinstellung, „Standard-Sortiment“, „Wenige, lange Stücke“, „Viele, kurze Stücke“), Katalog der Voreinstellung: Ersparnis und Abstand zur Schranke	Ersparnis von Column Generation: Voreinstellung knapp zweiundzwanzig Prozent, „Wenige, lange Stücke“ gut fünfzehn, „Standard-Sortiment“ gut siebeneinhalb, „Viele, kurze Stücke“ knapp vier Prozent. Auf der Schranke liegt Column Generation bei der Voreinstellung und beim „Standard-Sortiment“; bei „Wenige, lange Stücke“ liegt der Preis unter einem Prozent darüber, bei „Viele, kurze Stücke“ gut sieben Prozent.
Dieselben Bestellungen: wie nah am Ganzzahloptimum?	Bei „Wenige, lange Stücke“ liegt Column Generation fünfzig Cent über dem Ganzzahloptimum (Aufzählung aller Muster mit einem Ganzzahlprogramm). Bei „Viele, kurze Stücke“ blieb das Optimum nach zwei Minuten Rechenzeit unbewiesen: Column Generation liegt gut sechs Prozent über der besten gefundenen Lösung, das Optimum liegt zwischen der Schranke und dieser Lösung. Beim „Standard-Sortiment“ und bei der Voreinstellung stimmen Preis und Optimum überein.
Wie viele zulässige Muster gibt es? (alle Rollentypen zusammen, ohne das leere Muster)	Voreinstellung unter tausend, „Standard-Sortiment“ gut hundert, „Wenige, lange Stücke“ elf, „Viele, kurze Stücke“ knapp siebenundfünfzigtausend. Die Aufzählung wäre in allen vier Beispielen möglich.
Hundert zufällige Bestellungen (Startwerte des Zufallsgenerators von null bis neunundneunzig, vier Stückarten, Längen und Bedarf gleichverteilt wie im Abschnitt Modell, Katalog der Voreinstellung, Bestellgenerator der Demo)	Mittlere Ersparnis knapp sechzehn Prozent (Mittel der hundert Einzelwerte), höchstens gut fünfunddreißig. In einer Bestellung waren beide Verfahren gleich teuer, in keiner war Column Generation teurer. In zweiunddreißig Fällen lag der Preis auf der Schranke, über alle hundert gemittelt gut ein Prozent darüber, höchstens knapp sechs Prozent.
Test der Demo gegen vollständige Aufzählung	Auf achtzig zufälligen kleinen Bestellungen (ein bis drei Rollentypen, ein bis vier Stückarten, Stücklängen bis neun Meter, Bedarf bis neun) stimmt der LP-Wert von Column Generation mit dem LP-Wert über alle Muster überein (absolute Toleranz ein Millionstel). Die Preise von Column Generation und FFD liegen nie unter dem Ganzzahloptimum, und der FFD-Preis stimmt mit einer unabhängigen Nachimplementierung überein. Der Test verlangt nicht, dass Column Generation das Ganzzahloptimum trifft.

Grenzen und was die Messung zeigt

Das belegen die Befunde: Die Voreinstellung ist ein bewusst für FFD ungünstig gewähltes Beispiel; ihr Aufschlag ist eine Folge der Preise und Längen, die darin stehen, kein Maß für übliche Aufträge. Die Demo nennt sie „Worst Case für FFD“, doch ein schlimmster Fall ist sie nicht: Schon mit einer einzigen Stückart (einundzwanzig Stücke zu vier Meter zehn, Katalog der Voreinstellung) ist FFD nach Nachrechnung dieser Seite mehr als die Hälfte teurer als Column Generation. Die hundert Zufallsbestellungen sind eine einzelne Stichprobe mit vier Stückarten und dem Katalog der Voreinstellung. Sie zeigen, dass der Vorteil in diesen Fällen im Mittel groß war, aber nicht, wie er sich bei echten Auftragslisten verteilt.

• Vergleichsmaßstab: FFD ist hier eine einfache Regel mit Preis je Rolle. Bessere Heuristiken (etwa mit Blick auf den Preis je Meter) oder ein ganzzahliges Verfahren mit Verzweigung sind nicht Teil des Vergleichs; die Ersparnis gilt nur gegenüber FFD.
• Optimalität: Bewiesen ist sie nur dort, wo der Preis auf der Schranke liegt. Die Rundung ist eine Heuristik; sie kann über dem Ganzzahloptimum enden, in einem der vier Beispiele um mehr als sechs Prozent (Vermutung dieser Seite, nicht geprüft: bei so kleinen Bestellungen fällt der Rest nach dem Abrunden stärker ins Gewicht als bei großen). Dass Column Generation nie teurer ist als FFD, ist nicht garantiert; die Tests der Demo prüfen es nur für zwei Bestellungen, und die hundert Zufallsbestellungen enthielten keinen Gegenfall.
• Schranke und Raster: Das Teilproblem wird auf einem Raster gelöst, bei dem Stücke aufgerundet werden. Bei Längen, die auch auf den Millimeter nicht genau sind, kann dadurch ein günstiges Muster fehlen, und der angezeigte Schrankenwert läge dann etwas über dem Wert des unveränderten Problems (Folgerung dieser Seite aus dem Verfahren, nicht getestet).
• Zahl der Muster: In den vier Beispielen lässt sich die Menge aller Muster aufzählen. Das Beispiel zeigt also das Verfahren, nicht, dass eine Aufzählung dort scheitert; erst bei vielen Stückarten und kurzen Stücken wächst die Zahl der Muster schnell.
• Bestellung: Stücke, die länger sind als die längste Rolle, lässt die Demo ohne Hinweis aus der Bestellung weg (eine Warnung gibt es nur, wenn gar keine Bestellung übrig bleibt). Die Ergebnisse gelten dann nur für den Rest der Bestellung.
• Modell: Schnittbreite, Reste, Lieferbegrenzungen und Reihenfolgen fehlen (siehe Modell und Annahmen); echte Zuschnittplanung braucht sie meist.

Quellen

• Gilmore, P. C. und Gomory, R. E.: A linear programming approach to the cutting-stock problem. Operations Research 9 (1961); Teil II ebenda 11 (1963). Ursprung der Column Generation für den Zuschnitt.
• Johnson, D. S. u. a.: Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM Journal on Computing 3 (1974). Grenzen von First-Fit-Decreasing für Packen mit einer einzigen Behältergröße.

Die Literaturangaben sind aus dem Gedächtnis, nicht geprüft; die Beschreibung der Demo nennt keine Quellen.