Algorithms and models for cutting and packing problems

Abstract

Cutting and packing problems have applications on many industrial sectors. Cutting problems aim to obtain smaller objects cut from larger objects, while packing problems aim to pack items on containers. Those two kind of problems are related in the sense that most of the times, a same formulation can be used to solve both packing and cutting problems. The aim of this project is to investigate cutting and packing problems considering guillotine and non-guillotine cuts, and also the possibility of cargo stability constraints for packing problems. These problems are known to be NP-hard, which requires more elaborate methods for the exact resolution of these problems in practicable time. Therefore, we propose the investigation of exact algorithms and models for these problems, as well as a framework based on the branch-and-price method for the exact resolution of cutting and packing problems for one, two or three dimensions. It is also proposed the investigation and the development of new meshes for packing into containers. From computational experiments, we intend to prove the efficiency of the proposed algorithms, comparing the obtained results with the results presented in the literature. Finally, it is expected that the proposed methodologies can obtain better results than the methodologies presented in the literature, as well as efficiently solve outstanding problems in the literature. (AU)