Massive parallel algorithm development with GPGPU to create discrete obstructive region mountain

• Grant number: 13/26532-9
• Support Opportunities: Regular Research Grants
• Start date: May 01, 2014
• End date: April 30, 2016
• Field of knowledge: Engineering - Mechanical Engineering - Manufacturing Processes
• Principal Investigator: Marcos de Sales Guerra Tsuzuki
• Grantee: Marcos de Sales Guerra Tsuzuki
• Host Institution: Escola Politécnica (EP). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• Associated researchers: Thiago de Castro Martins

Abstract

Two research projects 2008/11132-7 and 2010/18913-4 were performed in which the applicability of the collision-free region to solve the two-dimensional irregular packing with open containers (variable dimension). In these two projects, we achieved a set of internationally competitive results in quality, as published in indexed international journals. However, the computational time appeared too high. In this project, the computational time will be drastically reduced, by proposing, researching, developing a new algorithm that determines favorable positions for an item in a layout represented by discrete positions. In a pre-processing step, not fit polygon mountains indicating the degree of overlap associated with each position will be created. The no fit polygon mountains are discretized. The union of not fit polygon mountains internal to the inner fit polygon defines the obstructed region mountain. The obstructed region mountain indicates how much each polygon penetrates the layout. This process will be conducted in GPGPU allowing massively parallel processing. A preliminary version of the algorithm for containers with fixed dimensions was implemented in MatLab, demonstrating its applicability to Tangram and Fu problems. (AU)

Scientific publications

(6)

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

SATO, ANDRE KUBAGAWA; MARTINS, THIAGO CASTRO; GOMES, ANTONIO MIGUEL; GUERRA TSUZUKI, MARCOS SALES. Raster penetration map applied to the irregular packing problem. European Journal of Operational Research, v. 279, n. 2, p. 657-671, DEC 1 2019. (10/18658-4, 10/18913-4, 13/26532-9, 08/11132-7)

SATO, ANDRE KUBAGAWA; SETTER BAUAB, GUILHERME ELIAS; MARTINS, THIAGO DE CASTRO; GUERRA TSUZUKI, MARCOS DE SALES; GOMES, ANTONIO MIGUEL. A Study in Pairwise Clustering for Bi-dimensional Irregular Strip Packing Using the Dotted Board Model. IFAC PAPERSONLINE, v. 51, n. 11, p. 6-pg., 2018-01-01. (10/18913-4, 10/19646-0, 13/26532-9)

SATO, ANDRE KUBAGAWA; MARTINS, THIAGO CASTRO; GUERRA TSUZUKI, MARCOS SALES. Massive parallelization accelerated solution for the 2D irregular nesting problem. IFAC PAPERSONLINE, v. 52, n. 10, p. 6-pg., 2019-01-01. (13/26532-9)

SATO, ANDRE KUBAGAWA; MARTINS, THIAGO DE CASTRO; GUERRA TSUZUKI, MARCOS DE SALES. A pairwise exact placement algorithm for the irregular nesting problem. INTERNATIONAL JOURNAL OF COMPUTER INTEGRATED MANUFACTURING, v. 29, n. 11, p. 1177-1189, 2016. (10/18913-4, 13/26532-9, 10/19646-0)

SATO, ANDRE KUBAGAWA; MUNDIM, LEANDRO RESENDE; MARTINS, THIAGO CASTRO; TSUZUKI, MARCOS SALES GUERRA. A separation and compaction algorithm for the two-open dimension nesting problem using penetration-fit raster and obstruction map. EXPERT SYSTEMS WITH APPLICATIONS, v. 220, p. 16-pg., 2023-02-24. (10/18913-4, 10/19646-0, 13/26532-9)

SATO, ANDRE KUBAGAWA; MARTINS, THIAGO CASTRO; GUERRA TSUZUKI, MARCOS SALES. A study on GPU acceleration applied to 2D irregular packing problems. INTERNATIONAL JOURNAL OF COMPUTER INTEGRATED MANUFACTURING, v. 35, n. 4-5, p. 17-pg., 2022-03-21. (13/26532-9)