Track: Operations Research

Abstract

The cutting stock problem is a classic problem of combinatorial optimization. However, the variant of the problem with two-dimensional irregular items has been scarcely explored. In this problem, the items have a free shape and must be located within a set of identical sheets with fixed dimensions. The main objective is to minimize waste, which is the same as reducing the number of bins where a specific demand for objects can fit. In this work, the items can be rotated freely and be placed without a fixed orientation; this allows the solution of this problem to be more consistent with the different applications in the industry where it appears.

The literature proposes classical techniques of column generation and metaheuristics. However, integrate column generation procedure and simulation environment using the Unity engine is novel.
The methodology considers a column generation procedure to select the subset of sheets composing the solution.  An auxiliary problem will create each of the proposed bins to be given to the master problem as columns. Through a two-phase construction procedure, the slave problem is solved. With the Unity engine, a local search with exchange and insertion operators is implemented.
The proposed technique was validated with instances from the literature of cutting stock problem. New best-known solutions were obtained for three different test cases. Compared to previous works, the computing time is satisfactory and reasonable. In general terms, the methodology presents successful results. For future work, it is recommended to use the simulation environment not only to execute classic perturbation movements on the items but to introduce physical moves that are applied on the sheets.