EXACT-SOLUTIONS FOR CONSTRAINED 2-DIMENSIONAL CUTTING PROBLEMS

The constrained two-dimensional cutting problem is concerned with the way a set of pieces should be cut from a plate, taking into account th at the cuts are of the guillotine type and that the number of times a piece can be cut is limited. Both plate and pieces are rectangular sha ped. Yr 1983, Wang proposed an algorithm for incremental development o f rectangles. Later, Oliveira and Ferreira not only proposed but numer ically tested an improvement to the algorithm as, A generalization of these methods is proposed. It will be stated that such methods are par ticular cases of uninformed search methods, widely studied in the area of Artificial Intelligence. Knowing that more efficient methods exist , namely 'informed methods', different alternatives to orientate the s earch process, while reducing the required computer memory and time, a re defined. Using an adequate selection of an heuristic function it is possible to guarantee the determination of a best solution. Such idea s are numerically tested in this work. The results indicate the superi ority of the proposed algorithm.