An innovative data structure to handle the geometry of nesting problems

Autor(es)

Cherri, Luiz Henrique ^[1] ; Cherri, Adriana Cristina ^[2] ; Carravilla, Maria Antonia ^[3] ; Oliveira, Jose Fernando ^[3] ; Bragion Toledo, Franklina Maria ^[1] ; Goncalves Vianna, Andrea Carla ^[2]

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

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

^[2] Univ Estadual Paulista, UNESP, Fac Ciencias, Bauru - Brazil

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

• Tipo de documento: Artigo Científico
• Fonte: INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH; v. 56, n. 23, p. 7085-7102, 2018.
• Citações Web of Science: 1

Resumo

As in many other combinatorial optimisation problems, research on nesting problems (aka irregular packing problems) has evolved around the dichotomy between continuous (time consuming) and discrete (memory consuming) representations of the solution space. Recent research has been devoting increasing attention to discrete representations for the geometric layer of nesting problems, namely in mathematical programming-based approaches. These approaches employ conventional regular meshes, and an increase in their precision has a high computational cost. In this paper, we propose a data structure to represent non-regular meshes, based on the geometry of each piece. It supports non-regular discrete geometric representations of the shapes, and by means of the proposed data structure, the discretisation can be easily adapted to the instances, thus overcoming the precision loss associated with discrete representations and consequently allowing for a more efficient implementation of search methods for the nesting problem. Experiments are conducted with the dotted-board model - a recently published mesh-based binary programming model for nesting problems. In the light of both the scale of the instances, which are now solvable, and the quality of the solutions obtained, the results are very promising. (AU)

• 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: 12/18653-8 - O problema de corte de peças irregulares
• Beneficiário: Luiz Henrique Cherri
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Processo FAPESP: 14/10740-4 - O problema de corte de peças irregulares
• Beneficiário: Luiz Henrique Cherri
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Doutorado