Problemas de Corte e Empacotamento: Abordagens Práticas e Teóricas

• Processo: 16/23552-7
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Data de Início da vigência: 01 de junho de 2017
• Data de Término da vigência: 30 de novembro de 2019
• Área do conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Rafael Crivellari Saliba Schouery
• Beneficiário: Rafael Crivellari Saliba Schouery
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Pesquisadores associados: Eduardo Candido Xavier ; Flávio Keidi Miyazawa ; Lehilton Lelis Chaves Pedrosa
• Assunto(s): Algoritmos de aproximação Otimização combinatória Heurística
• Palavra(s)-Chave do Pesquisador: Algoritmos de Aproximação | Algoritmos Exatos | corte e empacotamento | heuristicas | Otimização Combinatória | Projeto e Análise de Algoritmos

Resumo

Nesse projeto de pesquisa pretendemos contribuir para o avanço científico na área de Otimização Combinatória focando, em particular, em problemas de corte e empacotamento.Tais problemas foram introduzidos por Kantorovich em 1939 e Brooks et al. em 1940 com aplicações na indústria em mente e são muito comuns em situações onde é necessário cortar materiais (como metal, vidro, papel, etc) em itens menores para se atender uma determinada demanda ou quando é necessário realizar o carregamento de veículos e contêineres. Outras aplicações para problemas de corte e empacotamento incluem o escalonamento de tarefas computacionais e a divulgação de propagandas em páginas da internet.Apesar de muito comuns, mesmo as versões simples de problemas de corte e empacotamento são NP-difícieis, isto é, não existem algoritmos para tais problemas que encontram soluções ótimas em tempo polinomial, a menos que P=NP. Assim, em vista da importância prática de tais problemas, é necessário resolver problemas de corte e empacotamento, obtendo soluções ótimas ou próximas de soluções ótimas, dentre de um limite de tempo aceitável, já que, na prática, é comum termos urgência no cálculo da solução. Devida a complexidade dos problemas considerados neste projeto, faz-se necessário propor novos algoritmos exatos, de aproximação e heurísticas e adaptar técnicas já utilizadas com sucesso em outros problemas para obter novos patamares na resolução de tais problemas. (AU)

Publicações científicas

(16)

(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)

LINTZMAYER, CARLA N.; MIYAZAWA, FLAVIO K.; MOURA, PHABLO F. S.; XAVIER, EDUARDO C.. Randomized approximation scheme for Steiner Multi Cycle in the Euclidean plane. THEORETICAL COMPUTER SCIENCE, v. 835, p. 134-155, OCT 2 2020. (16/23552-7, 16/21250-3, 17/22611-2, 15/11937-9, 16/01860-1)

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. (18/19217-3, 15/11937-9, 19/12728-5, 16/01860-1, 16/23552-7)

QUEIROZ, THIAGO A.; BRACHT, EVANDRO C.; MIYAZAWA, FLAVIO K.; BITTENCOURT, MARCO L.. An extension of Queiroz and Miyazawa's method for vertical stability in two-dimensional packing problems to deal with horizontal stability. ENGINEERING OPTIMIZATION, v. 51, n. 6, p. 1049-1070, JUN 3 2019. (16/23552-7, 16/01860-1, 15/11937-9)

FERNANDES, CRISTINA G.; FERREIRA, CARLOS E.; MIYAZAWA, FLAVIO K.; WAKABAYASHI, YOSHIKO. Prices of Anarchy of Selfish 2D Bin Packing Games. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, v. 30, n. 3, p. 355-374, APR 2019. (13/03447-6, 16/23552-7, 16/01860-1, 15/11937-9)

POVOA, MARCELO G.; XAVIER, EDUARDO C.. Approximation algorithms and heuristics for task scheduling in data-intensive distributed systems. International Transactions in Operational Research, v. 25, n. 5, p. 1417-1441, SEP 2018. (16/23552-7, 14/02104-0, 15/11937-9)

KOHAYAKAWA, YOSHIHARU; MIYAZAWA, FLAVIO KEIDI; WAKABAYASHI, YOSHIKO; BENDER, MA; FARACHCOLTON, M; MOSTEIRO, MA. A Tight Lower Bound for an Online Hypercube Packing Problem and Bounds for Prices of Anarchy of a Related Game. LATIN 2018: THEORETICAL INFORMATICS, v. 10807, p. 15-pg., 2018-01-01. (13/03447-6, 15/11937-9, 13/07699-0, 16/23552-7, 16/01860-1)

LINTZMAYER, CARLA NEGRI; MIYAZAWA, FLAVIO KEIDI; XAVIER, EDUARDO CANDIDO; BENDER, MA; FARACHCOLTON, M; MOSTEIRO, MA. Two-Dimensional Knapsack for Circles. LATIN 2018: THEORETICAL INFORMATICS, v. 10807, p. 14-pg., 2018-01-01. (15/11937-9, 16/14132-4, 16/23552-7, 16/01860-1)

RODRIGUES, FELIX CARVALHO; XAVIER, EDUARDO C.; SCHAFER, GUIDO. On Fair Cost Facility Location Games with Non-singleton Players. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, v. 342, p. 18-pg., 2019-04-28. (15/11937-9, 16/23552-7)

DA SILVA, MAURO R. C.; SCHOUERY, RAFAEL C. S.; PEDROSA, LEHILTON L. C.. A Polynomial-time Approximation Scheme for the MAXSPACE Advertisement Problem. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, v. 346, p. 12-pg., 2019-08-30. (17/21297-2, 15/11937-9, 16/23552-7)

BORGES, YULLE G. F.; SCHOUERY, RAFAEL C. S.; MIYAZAWA, FLAVIO K.; GRANELLI, FABRIZIO; DA FONSECA, NELSON L. S.; MELO, LUCAS P.. Smart energy pricing for demand-side management in renewable energy smart grids. International Transactions in Operational Research, v. 27, n. 6, NOV 2019. (16/23552-7, 13/21744-8, 15/11937-9, 16/01860-1)

LINTZMAYER, CARLA NEGRI; MIYAZAWA, FLAVIO KEIDI; XAVIER, EDUARDO CANDIDO. Online circle and sphere packing. THEORETICAL COMPUTER SCIENCE, v. 776, p. 75-94, JUL 12 2019. (16/23552-7, 16/14132-4, 15/11937-9, 16/01860-1)

YUCRA QUISPE, KENT E.; LINTZMAYER, CARLA N.; XAVIER, EDUARDO C.. An exact algorithm for the Blocks Relocation Problem with new lower bounds. Computers & Operations Research, v. 99, p. 206-217, NOV 2018. (16/23552-7, 16/14132-4, 15/11937-9)

BORGES, YULLE G. F.; MIYAZAWA, FLAVIO K.; SCHOUERY, RAFAEL C. S.; XAVIER, EDUARDO C.. Exact algorithms for class-constrained packing problems. COMPUTERS & INDUSTRIAL ENGINEERING, v. 144, JUN 2020. (16/23552-7, 16/01860-1, 15/11937-9, 14/25892-4)

WAINER, JACQUES; XAVIER, EDUARDO C.. A Controlled Experiment on Python vs C for an Introductory Programming Course: Student's Outcomes. ACM TRANSACTIONS ON COMPUTING EDUCATION, v. 18, n. 3, SEP 2018. (16/23552-7, 15/11937-9)

CREPALDI, THIAGO; DA FONSECA, NELSON L. S.; XAVIER, EDUARDO C.; IEEE. Selection of Servers for Video on Demand Service over Hybrid Cloud. 2018 IEEE INTERNATIONAL CONFERENCE ON COMMUNICATIONS (ICC), v. N/A, p. 7-pg., 2018-01-01. (15/11937-9, 16/23552-7)

LINTZMAYER, CARLA N.; MIYAZAWA, FLAVIO K.; MOURA, PHABLO F. S.; XAVIER, EDUARDO C.. Quasilinear Approximation Scheme for Steiner Multi Cycle in the Euclidean plane. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, v. 346, p. 13-pg., 2019-08-30. (15/11937-9, 17/22611-2, 16/23552-7, 16/01860-1, 16/21250-3)