Algorithms and models for cutting and packing problems

Abstract

Cutting and Packing Problems are often considered as applications in the real world. Both classes of problems can be considered theoretically equivalent, as cutting an item from a recipient may be equivalent to placing an item into a bin. In this project, we consider orthogonal packing problems, mainly on their versions with two- and three-dimensions. These problems consider the placement of hyper-rectangles called items inside of larger hyper-rectangles called bins. Many of the packing problems presented in the literature can be solved by an algorithm that relies on a decision problem, that determines the existence of a feasible packing of items into a bin. This decision problem, referred to as orthogonal packing problem, is an NP-Complete problem, that has been extensively studied in the literature. To the best of our knowledge, the last survey on two-dimensional packing problems has been presented more than a decade ago. Since then, the literature has changed a lot, concerning two-dimensional packing problems. Therefore, one of the objectives of this project is to propose an extensive study on two-dimensional packing problems,aiming to write a survey addressing these problems. From this extensive study, we also aim to propose efficient algorithms and models for two- and three-dimensional packing problems, mainly for the Orthogonal Packing Problem, with the motivation that it can be used as a sub-routine to solve other problems. We intend to make an extensive computational study of the proposed methods, to analyze their efficiency, aiming to improve the results from the methods proposed in the literature. (AU)