Algorithms and models for cutting and packing problems

• Grant number: 17/11831-1
• Support Opportunities: Scholarships in Brazil - Doctorate (Direct)
• Start date: September 01, 2017
• End date: December 31, 2021
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Flávio Keidi Miyazawa
• Grantee: Vinícius Loti de Lima
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Associated research grant: 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points, AP.TEM
• Associated scholarship(s): 18/19217-3 - Algorithms and models for cutting and packing problems, BE.EP.DD

Abstract

Cutting and packing problems have applications on many industrial sectors. Cutting problems aim to obtain smaller objects cut from larger objects, while packing problems aim to pack items on containers. Those two kind of problems are related in the sense that most of the times, a same formulation can be used to solve both packing and cutting problems. The aim of this project is to investigate cutting and packing problems considering guillotine and non-guillotine cuts, and also the possibility of cargo stability constraints for packing problems. These problems are known to be NP-hard, which requires more elaborate methods for the exact resolution of these problems in practicable time. Therefore, we propose the investigation of exact algorithms and models for these problems, as well as a framework based on the branch-and-price method for the exact resolution of cutting and packing problems for one, two or three dimensions. It is also proposed the investigation and the development of new meshes for packing into containers. From computational experiments, we intend to prove the efficiency of the proposed algorithms, comparing the obtained results with the results presented in the literature. Finally, it is expected that the proposed methodologies can obtain better results than the methodologies presented in the literature, as well as efficiently solve outstanding problems in the literature. (AU)

Scientific publications

(8)

(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)

BOLSI, BEATRICE; DE LIMA, VINICIUS LOTI; DE QUEIROZ, THIAGO ALVES; IORI, MANUEL. Heuristic algorithms for integrated workforce allocation and scheduling of perishable products. INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, v. N/A, p. 16-pg., 2022-11-29. (17/11831-1)

LILIANE DE AZEVEDO OLIVEIRA; VINÍCIUS LOTI DE LIMA; THIAGO ALVES DE QUEIROZ; FLÁVIO KEIDI MIYAZAWA. COMPARING A STATIC EQUILIBRIUM BASED METHOD WITH THE SUPPORT FACTOR FOR HORIZONTAL CARGO STABILITY IN THE CONTAINER LOADING PROBLEM. Pesquisa Operacional, v. 41, 2021-10-11. (17/11831-1, 16/01860-1, 15/11937-9)

CURCIO, EDUARDO; DE LIMA, VINICIUS L.; MIYAZAWA, FLAVIO K.; SILVA, ELSA; AMORIM, PEDRO. The integrated lot-sizing and cutting stock problem under demand uncertainty. INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, v. N/A, p. 27-pg., 2022-11-22. (15/11937-9, 18/08879-5, 17/11831-1)

DE LIMA, VINICIUS L.; ALVES, CLAUDIO; CLAUTIAUX, FRANCOIS; IORI, MANUEL; VALERIO DE CARVALHO, JOSE M.. Arc flow formulations based on dynamic programming: Theoretical foundations and applications. European Journal of Operational Research, v. 296, n. 1, p. 3-21, JAN 1 2022. (17/11831-1, 19/12728-5)

BOLSI, BEATRICE; DE LIMA, VINICIUS LOTI; DE QUEIROZ, THIAGO ALVES; IORI, MANUEL; DOLGUI, A; BERNARD, A; LEMOINE, D; VONCIEMINSKI, G; ROMERO, D. Integrated Workforce Scheduling and Flexible Flow Shop Problem in the Meat Industry. ADVANCES IN PRODUCTION MANAGEMENT SYSTEMS: ARTIFICIAL INTELLIGENCE FOR SUSTAINABLE AND RESILIENT PRODUCTION SYSTEMS, APMS 2021, PT II, v. 631, p. 9-pg., 2021-01-01. (17/11831-1)

DE LIMA, VINICIUS L.; IORI, MANUEL; MIYAZAWA, FLAVIO K.; SINGH, M; WILLIAMSON, DP. New Exact Techniques Applied to a Class of Network Flow Formulations. INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, IPCO 2021, v. 12707, p. 15-pg., 2021-01-01. (15/11937-9, 17/11831-1, 16/01860-1)

DE LIMA, VINICIUS LOTI; IORI, MANUEL; MIYAZAWA, FLAVIO KEIDI. Exact solution of network flow models with strong relaxations. MATHEMATICAL PROGRAMMING, v. 197, n. 2, p. 34-pg., 2022-03-07. (15/11937-9, 17/11831-1, 16/01860-1)

BORGES, YULLE G. F.; DE LIMA, VINICIUS L.; MIYAZAWA, FLAVIO K.; PEDROSA, LEHILTON L. C.; DE QUEIROZ, THIAGO A.; SCHOUERY, RAFAEL C. S.. Algorithms for the bin packing problem with scenarios. JOURNAL OF COMBINATORIAL OPTIMIZATION, v. 48, n. 4, p. 28-pg., 2024-11-01. (22/05803-3, 17/11831-1)

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

LIMA, Vinícius Loti de. Métodos baseados em programação inteira aplicados em problemas de corte, empacotamento e escalonamento. 2021. Doctoral Thesis - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.