A comparative numerical analysis for the guillotine two-dimensional cutting problem

In this work, the behavior of four algorithms in the resolution of the two- dimensional constrained guillotine cutting problem is analyzed. This proble m 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 combinator ial and two heuristic methods are considered. In the combinatorial methods from the set of pieces, a minimum loss layout is constructively generated b ased on Wang's algorithm. In addition, an evolutionary and an annealing typ e approach are considered. All of these models have been implemented on a h igh 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 combinator ial degree and subsequently evaluated.