Exact solutions for constrained two-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 that 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 shaped. In 1983, Wang proposed an algorithm for incremental development of rectangles. Later, Oliveira and Ferreira not only proposed but numerically tested an improvement to the algorithm. A generalization of these methods is proposed. It will be stated that such methods are particular 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 search process, while reducing the required computer memory and time, are defined. Using an adequate selection of an heuristic function it is possible to guarantee the determination of a best solution. Such ideas are numerically tested in this work. The results indicate the superiority of the proposed algorithm.