Contributions to the two-dimensional guillotine cutting stock problem

Abstract

In this work we present two new variants of the two-dimensional guillotine cutting stock problem. We propose mathematical formulations and solution methods to deal with such problems. Firstly, we deal with the two-stage two-dimensional guillotine cutting stock problem in which items are identical, bins are different in size and the objective is to determine the optimal size of the identical items. Two solution procedures are presented to solve the case in which the orientation of the items is fixed and the case in which orthogonal rotation of items is allowed. The two procedures deal with the problem iteratively solving a knapsack problem for each possible item size and returning the best solution found. Numerical experiments are conducted on two- hundred randomly generated instances to evaluate the scalability of the approaches. Lastly, we deal with the k-stage two-dimensional guillotine cutting stock problem in which setup cost associated with stages of cut are considered relevant. A mathematical programming formulation with O(n²pk) variables and O(npk) constraints is present, in which n, p and k are the number of items, bins and stages, respectively. Numerical experiments are conducted on twenty small-scale randomly generated instances to evaluate the quality of the approach.