Eindimensionales Zuschnittproblem

Das eindimensionale Zuschnittproblem (englisch one-dimensional cutting stock problem) ist ein NP-schweres ganzzahliges lineares Optimierungsproblem mit dem Ziel, eindimensionale Teile in vorgegebenen Bedarfszahlen aus möglichst wenig Stücken Material gegebener Länge zuzuschneiden. Dieses Problem verdankt seine große Bedeutung auch dem Umstand, dass es teilweise als Hilfsproblem in komplizierteren mehrdimensionalen Pack- und Zuschnittsproblemen verwendet wird, zum Beispiel beim Containerbeladeproblem mit Quadern, wenn man sich alle Teile in Streifen zerlegt denkt.

Problembeschreibung

Gegeben ist eine unbegrenzte Zahl von Stücken eindimensionalen Rohmaterials vorgegebener Länge ${\displaystyle L\geq 0}$. Daraus sollen ${\displaystyle b_{i}\in \mathbb {N} }$ Teile der Länge ${\displaystyle l_{i}\geq 0}$ zugeschnitten werden mit ${\displaystyle i=1,2,\dots ,m}$. Es werden insgesamt ${\displaystyle \sum _{i=1}^{m}b_{i}}$ Teile benötigt, mit dem Ziel für deren Herstellung möglichst wenige Stücke des Rohmaterials zu verbrauchen. Reststücke können nicht miteinander verbunden werden und zählen als Abfall.

Beispiel

In nebenstehendem Beispiel sollen sieben verschiedene Balkenarten der Längen 105, 74, 73, 70, 68, 64 und 42 in jeweils unterschiedlicher Anzahl aus beliebig vielen Balken der Länge 210 geschnitten werden. Abgebildet sind außerdem verschiedene mögliche Schnittmuster.

Anwendungen

Unmittelbare Anwendungen sind zum Beispiel das Zuschneiden von Rohren oder das Abspeichern von nicht teilbaren und nicht weiter komprimierbaren Dateien auf möglichst wenig Datenträgern einheitlicher Kapazität.

Zusammenhang zu anderen Problemen und Komplexität

Sind die Bedarfszahlen ${\displaystyle b_{i}}$ sehr klein, spricht man auch vom (eindimensionalen) Behälterproblem (Bin Packing Problem).

Das Problem ist ${\displaystyle {\mathcal {N}}P}$-schwer, denn schon die Frage, ob alle Teile aus nur zwei Stück Ausgangsmaterial geschnitten werden können, führt auf das Rucksackproblem, und dieses ist ${\displaystyle {\mathcal {N}}P}$-vollständig. Gemäß ist das eindimensionale Bin-Pack-Problem sogar stark ${\displaystyle {\mathcal {N}}P}$-vollständig. Trotz dieser ungünstigen Komplexität können für viele Instanzen in akzeptabler Zeit Optimallösungen bestimmt werden, zum Beispiel mittels geeigneter Heuristiken. Um die Güte einer zulässigen Lösung zu bewerten, benötigt man möglichst scharfe untere Schranken.

Lösungsmethoden

Das Zuschnittproblem wird in der Regel als ganzzahliges lineares Optimierungsproblem modelliert und gelöst. Es gilt in der Regel als Paradebeispiel für den Einsatz der sogenannten Column-Generation-Methode (auch Spaltengenerierung), bei denen nicht alle Entscheidungsvariablen zu Beginn betrachtet werden, sondern nur vielversprechende Kandidaten bei Bedarf eingeführt werden, um die Modellgröße zu reduzieren.

Verallgemeinerungen und Erweiterungen

• Erweiterung auf verschiedene Materialien mit Längen ${\displaystyle L_{1},\dots ,L_{M}}$ und Preisen ${\displaystyle p_{1},\dots ,p_{M}}$
• Welche Vorräte verschieden langen Ausgangsmaterials müssen gekauft werden, um mehrere Zuschnittaufträge möglichst billig erledigen zu können?
• Eine andere Verallgemeinerung des eindimensionalen Zuschnittproblems ist das mehrdimensionale Vektorpackproblem, das aus Planungsaufgaben entstehen kann. Anstelle der Zulässigkeitsbedingung werden hier mehrere Bedingungen gleichzeitig gestellt, zum Beispiel dass eine gewisse geometrische Länge und zugleich ein bestimmtes Gesamtgewicht der gepackten Teile nicht überschritten werden dürfen. Ebenso könnte auch die Zeit zu einer derartigen Nebenbedingung führen.
• Das Streifenpackproblem stellt eine weitere aus Planungsproblemen entstehende Verallgemeinerung des eindimensionalen Zuschnittproblems dar. Die Aufgabe besteht darin, in ein Rechteck der Abmessungen ${\displaystyle L\times W}$ mit fester Breite ${\displaystyle L}$ und möglichst kleiner Höhe ${\displaystyle W}$ nicht drehbare kleinere Rechtecke mit gegebenen Ausdehnungen und Bedarfszahlen überlappungsfrei zu packen. Wären die Höhen aller anzuordnenden Rechtecke gleich, handelte es sich um das eindimensionale Zuschnittproblem. Eine unmittelbare Anwendung des Streifenpackproblems besteht in der Planung mit einer begrenzt verfügbaren Ressource, so dass nach möglichst kurzer Zeit eine Liste von Aufträgen, die die Ressource benötigen, vollständig abgearbeitet ist.
• Eine völlig andere Erweiterung des eindimensionalen Zuschnittproblems liegt vor, wenn wegen begrenzten Platzes neben der Zuschnittanlage bei einem Großauftrag gefordert wird, dass stets höchstens ${\displaystyle k<m}$ verschiedene Teilesorten in Bearbeitung sind, wobei die positive ganze Zahl ${\displaystyle k}$ fest vorgegeben ist. Bevor also die ${\displaystyle (k+1)}$-te Sorte begonnen werden kann, muss eine andere Teilesorte abgeschlossen worden sein. Gesucht wird zusätzlich zu den Zuschnittvarianten eine Reihenfolge, die dafür sorgt, dass möglichst wenig Material verbraucht und die Zusatzbedingung eingehalten wird.
• Das „Zuschnittproblem mit Muster-Minimierung“ („cutting stock problem with pattern minimization“) ist eine Erweiterung des klassischen Zuschnittproblems. Die Erweiterung „Muster-Minimierung“ bedeutet, dass neben dem Rohmaterialverbrauch zusätzlich die Anzahl der verschiedenen verwendeten Zuschnittsvarianten minimiert werden soll. Dieses Problem tritt auf, wenn für jede Zuschnittsvariante einmalige Produktionskosten (Rüstkosten) anfallen, unabhängig davon, wie oft die Variante produziert wird, z. B. wenn für jede Variante, ein Rohr in mehrere Teilstücke zu zersägen, eine eigene Zuschnittschablone benötigt wird.

Ein Überblick über eine Vielzahl weiterer Pack- und Zuschnittprobleme, für die das eindimensionale Problem (2)–(4) auch als Relaxation dienen kann, wird unter anderem in gegeben.

Zur Geschichte

Bereits 1939 gab Leonid Witaljewitsch Kantorowitsch ein ganzzahliges Modell für das eindimensionale Zuschnittproblem an, aber die zu seinem Modell gehörende stetige Relaxation ist sehr schwach; sie liefert nur die Materialschranke. Nachdem bis 1960 die Grundlagen der linearen Optimierung, darunter das revidierte Simplexverfahren, bereitgestellt worden waren, veröffentlichten Gilmore und Gomory bereits 1961/63 das Lösungsverfahren für die stetige Relaxation, nämlich die Simplexmethode mit der Spaltengenerierung zu kombinieren. Damit konnten, ausreichend Rechenzeit vorausgesetzt, für nicht zu große Instanzen (fast) optimale Lösungen ermittelt werden. Da aber die Rechenzeit für größere Instanzen inakzeptabel hoch wird, weil viele Simplexschritte notwendig sind und viele Rucksackprobleme gelöst werden müssen, interessierte man sich auch für schnelle Heuristiken und ihre Qualitäten. Dies geschah in den 1970er Jahren. Noch Ende des 20. Jahrhunderts gelang es, für die exakte Lösung des ganzzahligen Problems als Alternative zum Branch-and-Bound das Schnittebenenverfahren von Gomory erfolgreich anzupassen. Inzwischen wurde das Verfahren weiterentwickelt zu Branch and price and cut.

Quellenangaben

1. ↑ M. R. Garey, D. S. Johnson: "Strong" NP-Completeness Results: Motivation, Examples, and Implications. Journal of the Association for Computing Machinery, Vol 25, No 3, July 1978, 499–508.
2. ↑ Hilary P. Williams: Model building in mathematical programming. Fifth Edition Auflage. John Wiley & Sons Ltd, Chichester 2013, ISBN 978-1-118-44333-0 (researchgate.net [abgerufen am 19. Januar 2024]). 
3. ↑ François Vanderbeck: Computational study of a column generation algorithm for bin packing and cutting stock problems. In: Mathematical Programming. Band 86, Nr. 3, 1. Dezember 1999, ISSN 0025-5610, S. 565–594, doi:10.1007/s101070050105 (springer.com [abgerufen am 19. Januar 2024]). 
4. ↑ J. Terno, R. Lindemann, G. Scheithauer: Zuschnittprobleme und ihre praktische Lösung. VEB Fachbuchverlag, Leipzig 1987.
5. ↑ H. Dyckhoff, G. Scheithauer, J. Terno: Cutting and Packing. in: Annotated Bibliographies in Combinatorial Optimization, herausgegeben von M. Dell'Amico, F. Maffioli und S. Martello, John Wiley & Sons Ltd., 1997, S. 393–412.
6. ↑ A. Müller: Anwendung des Schnittebenenverfahrens auf das eindimensionale Zuschnittproblem. Diplomarbeit, Technische Universität Dresden 1998.

Weblinks

• Auf der Seite der Interessengruppe Cutting and Packing an der TU Dresden finden Interessenten unter anderem 53 schwierige Testbeispiele ohne Ganzzahl-Aufrundungseigenschaft zum eindimensionalen Zuschnittproblem.
• winvedaga: Lösung des Eindimensionalen Zuschnittproblems mit Hilfe des Approximationsalgorithmus