A top-down cutting approach for modeling the constrained two- and three-dimensional guillotine cutting problems

Autor(es)

Martin, Mateus ^[1] ; Morabito, Reinaldo ^[2] ; Munari, Pedro ^[2]

Afiliação do(s) autor(es)

^[1] Univ Fed Sao Paulo, Sao Paulo - Brazil

^[2] Univ Fed Sao Carlos, Sao Carlos - Brazil

• Tipo de documento: Artigo Científico
• Fonte: Journal of the Operational Research Society; v. 72, n. 12, p. 2755-2769, DEC 2 2021.
• Citações Web of Science: 0

Resumo

In this article, we address the Constrained Two-dimensional Guillotine Cutting Problem (C2GCP) and the Constrained Three-dimensional Guillotine Cutting Problem (C3GCP). These problems consist of cutting a rectangular two-/three-dimensional object with orthogonal guillotine cuts to produce ordered rectangular two-/three-dimensional items seeking the most valuable subset of items cut. They often appear in manufacturing settings that cut objects to produce item types of low demand, such as in the cutting of flat glass in the glass industry, rocks in the granite and marble industries and steel blocks in the metallurgical industry. To model and solve these problems, we propose a novel top-down cutting approach that leads to effective mixed integer linear programming models for the C2GCP and the C3GCP. The insight of the proposed approach is to represent the cutting pattern as a binary tree, in which the root node is the object, and branches correspond to guillotine cuts. The results of computational experiments with a general-purpose optimization solver and using three sets of benchmark instances showed that the proposed models are competitive with state-of-the-art formulations of the C2GCP and the C3GCP in quality of solution and processing times, particularly when the number of items in an optimal solution is moderate. (AU)

• Processo FAPESP: 16/01860-1 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento, localização e suas integrações em contextos industriais e logísticos
• Beneficiário: Reinaldo Morabito Neto
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 13/07375-0 - CeMEAI - Centro de Ciências Matemáticas Aplicadas à Indústria
• Beneficiário: Francisco Louzada Neto
• Modalidade de apoio: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs
• Processo FAPESP: 16/08039-1 - Problemas de Corte Bidimensional Guilhotinado e Restrito: Formulações Matemáticas e Métodos de Solução
• Beneficiário: Mateus Pereira Martin
• Modalidade de apoio: Bolsas no Brasil - Doutorado