A new deterministic algorithm for two-dimensional rectangular packing problems based on polyomino packing models

The major theme of this paper is to discuss solution algorithms of the Cutting and Packing Problems, that is, problems to find optimal layout of given parts (items) on given material(object) in order to get maximal usage of the object. Especially in this paper, the authors deal with two-dimensional rectangular packing problems. Here, a new deterministic algorithm for the problems is proposed by extending the solution algorithms of so called polyomino packing problems, which was developed by authors. This algorithm is fully deterministic, and is not depending on the heuristic approaches nor meta-heuristic ones as the conventional algorithms were. In this paper, the superiority of the new algorithm over the conventional ones is verified by testing on benchmark data.