Problemas de corte guilhotinado e restritos: formulações matemáticas e métodos de solução

Abstract

We address the Constrained Guillotine Cutting Problems (CGCP) in this doctoral thesis. The CGCP consist of producing items from objects using guillotine cuts, i.e., cuts that divide the rectangular materials into two rectangular sub-objects without restricting the number of guillotine stages, and with a limitation over the maximum number of copies per item type to be cut from the object. New linear mathematical formulations are proposed for the Constrained Two-dimensional Guillotine Cutting Problem (C2GCP). The first proposed formulation is based on object discretization, which is also extended to deal with 2-staged and 1-group patterns, and a Benders decomposition algorithm is developed from it. Two other formulations are proposed to the C2GCP, based on the concept of successive combination of copies of item types and sub-patterns, i.e., the bottom-up approach; from the proposed additional constraints, these models strictly deal with d-staged cutting patterns, where d is a positive integer scalar. Two extensions of the C2GCP are also addressed in this thesis. The first extension is the Constrained Two-dimensional Guillotine Cutting Problem with Defects (C2GCP-D). The linear model and the Benders decomposition algorithm, both based on object discretization, are extended to deal with this variant, and then a new solution method based on Constraint Programming is developed. The second extension is the Constrained Three-Dimensional Guillotine Cutting Problem (C3GCP), which is addressed by models and by a tree-search algorithm. All these proposed approaches are evaluated through computational experiments, using instances of the literature or randomly generated ones, and compared to another approaches in the literature. Despite the applicability of these problems, the literature took more than three decades to present mathematical formulations to the CGCP. Therefore, this thesis contributes to new formulation paradigms for the CGCP and effective methods to solve them, which are competitive with those known in the literature.