Integrating irregular strip packing and cutting path determination problems: A discrete exact approach

Autor(es)

Oliveira, Larissa Tebaldi ^[1] ; Silva, Everton Fernandes ^[1] ; Oliveira, Jose Fernando ^[2] ; Bragion Toledo, Franklina Maria ^[1]

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

^[1] Univ Sao Paulo, Inst Ciencias Matemat & Comp, Sao Carlos, SP - Brazil

^[2] Univ Porto, Fac Engn, INESC TEC, Porto - Portugal

• Tipo de documento: Artigo Científico
• Fonte: COMPUTERS & INDUSTRIAL ENGINEERING; v. 149, NOV 2020.
• Citações Web of Science: 0

Resumo

The irregular strip packing problem arises in a wide variety of industrial sectors, from garment and footwear to the metal industry, and has a substantial impact in raw-material waste minimization. The goal of this problem is to find a layout for a large object to be cut into smaller pieces. What differentiates this problem from all the other cutting and packing problems, and is its primary source of complexity, is the irregular (non-rectangular) shape of the small pieces. However, in practical applications, after a layout has been determined, a second problem arises: finding the path that the cutting tool has to follow to actually cut the pieces, as previously planned. This second problem is known as the cutting path determination problem. Although the solution of the first problem strongly influences the resolution of the second one, only a few studies are dealing with cutting/packing and cutting path determination together, and, to the best of the authors' knowledge, none of them considers the irregular strip packing problem. In this paper, we propose the first mathematical programming model that integrates the irregular strip packing and the cutting path determination problems. Computational experiments were run to show the correctness of the proposed model and the advantage of tackling the two problems together. Two variants of the cutting path determination problem were considered, the fixed vertex and the free cut models. The strengths and drawbacks of these two variants are also established through computational experiments. Overall, the computational results show that the integration of these problems is advantageous, even if only small instances could be solved to optimality, given that solving to optimality the integrated is at least as difficult as solving each one of the other problems individually. As future research, it should be highlighted that the proposed integrated model is a solid basis for the development of matheuristics aiming at tackling real-world size problems. (AU)

• Processo FAPESP: 13/25743-6 - Uma integração dos problemas de empacotamento de peças irregulares e do caminho mínimo de corte
• Beneficiário: Larissa Tebaldi de Oliveira
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• 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/09476-6 - Métodos de resolução para o problema integrado de empacotamento de peças irregulares e caminho mínimo de corte
• Beneficiário: Larissa Tebaldi de Oliveira
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Doutorado
• Processo FAPESP: 10/10133-0 - Problemas de corte, empacotamento, dimensionamento de lotes e programação da produçã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/27162-0 - Modelos matemáticos para um problema de caminho de corte
• Beneficiário: Everton Fernandes da Silva
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Processo FAPESP: 15/09109-0 - O problema de caminho de corte
• Beneficiário: Everton Fernandes da Silva
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Mestrado