A comparative numerical analysis for the guillotine two-dimensional cutting problem |
| |
Authors: | Victor Parada Rodrigo Palma Daniel Sales Arlindo Gómes |
| |
Institution: | (1) Departamento de Ingeniería Informática, Universidad de Santiago de Chile, Av. Ecuador, 3659 Santiago, Chile Email;(2) Departamento de Ingeniería Eléctrica, Universidad de Santiago de Chile, Av. Ecuador, 3659 Santiago, Chile;(3) Departamento de Informática, Universidad Federal de Esprito Santo, Campus Goiabeiras s/n, Vitoria, Brazil Email |
| |
Abstract: | In this work, the behavior of four algorithms in the resolution of the two-dimensional constrained guillotine cutting problem
is analyzed. This problem is concerned about the way a set of pieces should be cut from a plate of greater dimensions, considering
guillotine cutting and a constrained number of times a piece can be cut from the plate. In this study three combinatorial
and two heuristic methods are considered. In the combinatorial methods from the set of pieces, a minimum loss layout is constructively
generated based on Wang's algorithm. In addition, an evolutionary and an annealing type approach are considered. All of these
models have been implemented on a high performance Silicon Graphics machine. Performance of each algorithm is analyzed both
in terms of percentage waste and running time. In order to do that, a set of 1000 instances are classified according to their
combinatorial degree and subsequently evaluated.
This revised version was published online in June 2006 with corrections to the Cover Date. |
| |
Keywords: | guillotine cutting stock heuristics combinatorial optimization |
本文献已被 SpringerLink 等数据库收录! |
|