Advanced search
Start date
Betweenand

Algorithms and models for cutting and packing problems

Grant number: 18/19217-3
Support type:Scholarships abroad - Research Internship - Doctorate (Direct)
Effective date (Start): February 09, 2019
Effective date (End): August 08, 2019
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal Investigator:Flávio Keidi Miyazawa
Grantee:Vinícius Loti de Lima
Supervisor abroad: Manuel Iori
Home Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
Local de pesquisa : Università degli Studi di Modena e Reggio Emilia, Modena (UNIMORE), Italy  
Associated to the scholarship:17/11831-1 - Algorithms and models for cutting and packing problems, BP.DD

Abstract

Cutting and Packing Problems are often considered as applications in the real world. Bothclasses of problems can be considered theoretically equivalent, as cutting an item from a recipientmay be equivalent to placing an item into a bin. In this project, we consider orthogonal packingproblems, mainly on their versions with two- and three-dimensions. These problems consider theplacement of hyper-rectangles called items inside of larger hyper-rectangles called bins. Manyof the packing problems presented in the literature can be solved by an algorithm that relies ona decision problem, that determines the existence of a feasible packing of items into a bin. Thisdecision problem, referred to as orthogonal packing problem, is an NP-Complete problem, thathas been extensively studied in the literature. To the best of our knowledge, the last survey ontwo-dimensional packing problems has been presented more than a decade ago. Since then, theliterature has changed a lot, concerning two-dimensional packing problems. Therefore, one of theobjectives of this project is to propose an extensive study on two-dimensional packing problems,aiming to write a survey addressing these problems. From this extensive study, we also aim topropose efficient algorithms and models for two- and three-dimensional packing problems, mainlyfor the Orthogonal Packing Problem, with the motivation that it can be used as a sub-routineto solve other problems. We intend to make an extensive computational study of the proposedmethods, to analyze their efficiency, aiming to improve the results from the methods proposed inthe literature.

Scientific publications
(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)
IORI, MANUEL; DE LIMA, VINICIUS L.; MARTELLO, SILVANO; MIYAZAWA, FLAVIO K.; MONACI, MICHELE. Exact solution techniques for two-dimensional cutting and packing. European Journal of Operational Research, v. 289, n. 2, p. 399-415, MAR 1 2021. Web of Science Citations: 0.

Please report errors in scientific publications list by writing to: cdi@fapesp.br.