A branch-and-bound approach for the constrained K-staged 2-dimensional cutting stock problem

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.

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.