[Back]


Diploma and Master Theses (authored and supervised):

B. Bonigl:
"A Branch-and-Bound Approach for the Constrained K-Staged 2-Dimensional Cutting Stock Problem";
Supervisor: G. Raidl; Institut für Computergraphik und Algorithmen, 2016; final examination: 2016-02-11.



English abstract:
The K-staged two-dimensional cutting stock problem with variable sheet size (K-2CSV)
represents a common problem in industry where a cutting pattern to cut rectangular
shaped elements out of large stock sheets is required. The NP-hard nature of the problem
makes it difficult to find a good pattern, which directly translates to unused waste
material of the stock sheet. The historical approach is to try and find an optimal pattern
through dynamic programming, which later was supplemented by Branch-and-Bound
and heuristic approaches.
In this paper we develop a bottom-up Branch-and-Bound approach, creating an
optimal cutting pattern for a singular stock sheet. While top-down approaches sucessively
subdivide the sheet into smaller rectangles and ultimately into the required elements,
bottom-up approaches combine elements and combinations thereof together to create
whole patterns.
The process is supplemented with a general framework to integrate it into the
implementation of the Algorithms and Complexity Group at the TU Wien. The framework
allows to solve problem instances spanning multiple stock sheets by applying the algorithm
multiple times.
We then boost the performance of the algorithm by improving the used lower and
upper bounds as well as reducing the search space through the detection of dominated or
duplicate patterns.
Lastly, using different settings we apply the algorithm to problem instances taken
from the literature to obtain computational results.

German abstract:
Das K-stufige 2-dimensionale Zuschnittproblem mit variabler Plattengröße (K-2CSV ) ist
ein häufig in der Industrie auftretendes Problem. Oftmals sollen rechteckige Elemente
aus großen Platten oder Blättern herausgeschnitten werden. Die NP-harte Natur dieses
Problems macht es schwer ein gutes Schnittmuster zu finden das möglichst wenig Ausschuss
produziert. Der historische Ansatz ist mittels Dynamic Programming ein optimales Muster
zu finden. Später wurde diese Vorgehensweise durch Branch-and-Bound und heuristische
Ansätze ergänzt.
In dieser Arbeit entwickeln wir einen bottom-up Branch-and-Bound Ansatz welcher
ein optimales Schnittmuster für eine einzelne Platte aus dem Bestand berechnet. Während
ein top-down Ansatz die Platte Schritt für Schritt in kleinere Rechtecke unterteilt um
letztendlich an die geforderten Elemente zu gelangen, kombiniert ein bottom-up Ansatz
Elemente und Kombinationen von Elementen um sein Ziel zu erreichen.
Dieser Prozess wird um ein generelles Framework erweitert um es in die Implementierung
der Algorithms and Complexity Group der TU Wien zu integrieren. Das Framework
erlaubt das Lösen von Probleminstanzen die mehrere Platten benötigen indem es den
Algorithmus auf jede Platte einzeln anwendet.
Anschließend verbessern wir die Leistung des Algorithmus indem wir bessere Schranken
finden und den Suchraum durch Erkennung von dominierten oder doppelten Mustern
einschränken.
Zu guter Letzt wird der Algorithmus in verschiedenen Konfigurationen auf Probleminstanzen
aus der Literatur angewandt um an rechnerische Ergebnisse zu gelangen.


Electronic version of the publication:
http://publik.tuwien.ac.at/files/publik_254589.pdf


Created from the Publication Database of the Vienna University of Technology.