Strip based compact formulation for two-dimensional guillotine cutting problems

Autor(es)

Rodrigues, Carlos Diego ; Cherri, Adriana Cristina ; Araujo, Silvio Alexandre de

• Tipo de documento: Artigo Científico
• Fonte: Computers & Operations Research; v. 149, p. 14-pg., 2023-01-01.

Resumo

In this paper, we present a new mixed integer programming formulation for two-dimensional guillotine cutting and packing problems based on a strip decomposition of the rectangular spaces. The formulation covers most of the main related problems in the literature by setting parameters accordingly. The strip concept commonly used for problems with a limited number of stages (two or three stages) has been, in this study, extended to a general concept that can cover an arbitrary number of stages. Due to the easy adaptation of the proposed formulation, which is presented in both heuristic and exact version, an extensive set of computational experiments was performed with instances for the two-dimensional guillotine knapsack, cutting stock and bin packing problems. The experiments, which involve existing benchmark instances and randomly generated instances from the literature, showed that our proposed formulation, considering its heuristic version, can output competitive results both in terms of computational time and percentage of optimally solved instances. (AU)

• 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/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