Algorithms for 3D guillotine cutting problems : unbounded knapsack, cutting stock and strip packing
Thiago A. de Queiroz, Flávio K. Miyazawa, Yoshiko Wakabayashi, Eduardo C. Xavier
ARTIGO
Inglês
Agradecimentos: The authors thank the referees for the suggestions, comments and issues raised, which helped improving the presentation of this paper
Abstract: 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...
Ver mais
Abstract: 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 different sizes (and the cuts must be staged), we present column generation-based algorithms. Modified versions of the algorithms for the 3D cutting stock problems with stages are then used to build algorithms for the 3D strip packing problem and its variants. The computational tests performed with the algorithms described in this paper indicate that they are useful to solve instances of moderate size
Ver menos
Fechado
Algorithms for 3D guillotine cutting problems : unbounded knapsack, cutting stock and strip packing
Thiago A. de Queiroz, Flávio K. Miyazawa, Yoshiko Wakabayashi, Eduardo C. Xavier
Algorithms for 3D guillotine cutting problems : unbounded knapsack, cutting stock and strip packing
Thiago A. de Queiroz, Flávio K. Miyazawa, Yoshiko Wakabayashi, Eduardo C. Xavier
Fontes
Computers & operations research (Fonte avulsa) |