Column generation at strip level for the K-staged two-dimensional Cutting Stock Problem

Abstract

Viele industrielle Anwendungen existieren für das Packen von kleineren Objekten in größere Behälter, so-genannte Bins, sodass die Anzahl der verwendeten Bins minimal ist. Beispiele sind die Holz, Metall oder Glass Industrien, in der die Kundenbestellungen aus größeren Stücken Lagermaterial zugeschnitten werden müssen.Wenn sowohl Bins, als auch die kleineren Objekte, so-genannte Elements, rechteckig sind, ist vom 2-dimensionalem Bin Packing Problem (2BP) bzw. dem 2-dimensionalem Cutting Stock Problem (2CS) die Rede. In dieser Diplomarbeit werden weiters nur so-genannte Guillotinenschnitte erlaubt, was orthogonale Schnitte von einer Seite des Bins zur anderen sind. Diese Schnitte haben zur Folge, dass man das 2CS weiters über ihre Anzahl an Stages definieren kann, die mit K bezeichnet wird. Ein Stage ist hier eine Reihe paralleler Schnitte. Das Ziel dieser Diplomarbeit ist es, eine neue Variante von Column Generation für das 2-staged und 3-staged 2CS zu präsentieren, die auf der Generation von so-genannten Strips basiert. Zuerst wird das Problem formal definiert, und das Prinzip der Column Generation genauer erläutert. Darauf folgt eine Untersuchung der Litertur über das 2CS. Literatur zu dem Knapsack Problem wird auch vorgestellt, da es sich dabei um ein relevantes Subproblem der Column Generation handelt. Dies beinhaltet Varianten für das Unbounded als auch für das Bounded Knapsack Problem (UKP und BKP). Danach wird das Stage Shifted Column Generation (SSCG) präsentiert. Dazu gehören Definitionen für das Master Problem als auch für die relevanten Pricing Probleme für den Fall K = 2 und K = 3. Das Master Problem wird als ILP formuliert, genauer einem Set Covering Problem, während die Pricing Probleme Varianten eines Knapsack Problems darstellen. Für das UKP wird der effiziente algorithmus EDUK implementiert, während für das BKP ein neuer Algorithmus vorgestellt wird, der den gesamten Knapsack immer Element für Element bearbeitet, und BKP-Generator heißt. Für K = 3 wird BKP-Generator adaptiert, und DP-Generator genannt. Zwei Heuristiken, die auf der Randomisierung von DP-Generator beruhen, werden ebenfalls vorgestellt. Es wird außerdem eine Integrality Heuristic vorgestellt, da die Ergebnisse des Master Problems meist nicht integral sind. Die verschiedenen Pricing Probleme werden experimentell miteinander, und mit einer Insertion Heuristic als auch einer Dynamic Programming Implementation verglichen. Die Resultate zeigen gute Lösungen für die LP Relaxierung, und auch die integralen Lösungen können teils besser als die vorherigen Implementationen sein.

Several industrial applications exist for packing non overlapping objects, called elements, into larger objects, called bins, such that the total number of used bins is minimal. Examples are wood, metal and glass industries, where the customers- orders must be cut from larger pieces of stock material. Particularly when high volumes of stock material are used, even small improvements can directly increase profitability. Assuming both elements and bins are rectangular, the problem is called the 2-dimensional bin packing problem (2BP) or cutting stock problem (2CS), both of which are NP-hard. Only guillotine cuts are allowed, which are orthogonal cuts from one side to another. This leads to a further specification of the 2CS, which is the number of stages it allows, denoted by K. A stage is a series of parallel cuts. The aim of this thesis is to present an efficient implementation of a new strip-based column generation approach for the 2-staged and 3-staged 2CS with guillotine cuts. First, the problem and column generation are introduced and formally defined. This is followed by a study of relevant literature concerning the 2CS and 2BP. Literature for the knapsack problem is also studied, as this is a relevant subproblem of column generation. This includes variants of dynamic programming both for the unbounded and bounded knapsack problem (UKP and BKP). After that, the Stage Shifted Column Generation (SSCG) is presented. This entails both definitions for the master problem and the relevant pricing problems for K = 2 and K = 3. The master problem is formulated as a set covering problem, while the pricing problems are variants of knapsack problems. EDUK is an efficient implementation for the UKP, while a new algorithm is developed for the BKP, called BKP-Generator. It essentially processes the entire knapsack element by element. For K = 3, BKP-Generator is adapted, and called DP-Generator. Two heuristic algorithms are also presented, which rely on randomizing DP-Generator. Finally, an integrality heuristic is introduced, as the master problem offers possibly fractional results. The different pricing problems are experimentally tested and compared to an insertion heuristic and a dynamic programming implementation. The results show good LP relaxed solutions, and integral results are competitive with previous implementations.