Advanced search
Start date
Betweenand
Related content
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

An innovative data structure to handle the geometry of nesting problems

Full text
Author(s):
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]
Total Authors: 6
Affiliation:
[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
Total Affiliations: 3
Document type: Journal article
Source: INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH; v. 56, n. 23, p. 7085-7102, 2018.
Web of Science Citations: 1
Abstract

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)

FAPESP's process: 10/10133-0 - Cutting, packing, lot-sizing and scheduling problems and their integration in industrial and logistics settings
Grantee:Reinaldo Morabito Neto
Support Opportunities: Research Projects - Thematic Grants
FAPESP's process: 12/18653-8 - Nesting problem
Grantee:Luiz Henrique Cherri
Support Opportunities: Scholarships in Brazil - Doctorate
FAPESP's process: 14/10740-4 - Nesting Problem
Grantee:Luiz Henrique Cherri
Support Opportunities: Scholarships abroad - Research Internship - Doctorate