Algorithms for 3D guillotine cutting problems: Unbounded knapsack, cutting stock and strip packing☆

Publication year: 2012
Source: Computers & Operations Research, Volume 39, Issue 2, February 2012, Pages 200-212

Thiago A., de Queiroz , Flávio K., Miyazawa , Yoshiko, Wakabayashi , Eduardo C., Xavier

We present algorithms for the following three-dimensional (3D) guillotine cutting problems: unbounded knapsack, cutting stock and strip packing. We consider the case where the items have fixed orientation and the case where orthogonal rotations around all axes are allowed. For the unbounded 3D knapsack problem, we extend the recurrence formula proposed by [1] for the rectangular knapsack problem and present a dynamic programming algorithm that uses reduced raster points. We also consider a variant of the unbounded knapsack problem in which the cuts must be staged. For the 3D cutting stock problem and its variants in which the bins have…