Busca avançada
Ano de início
Entree

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

Processo: 16/23552-7
Modalidade de apoio:Auxílio à Pesquisa - Regular
Vigência: 01 de junho de 2017 - 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)

Matéria(s) publicada(s) na Agência FAPESP sobre o auxílio:
Matéria(s) publicada(s) em Outras Mídias (0 total):
Mais itensMenos itens
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

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, . (16/23552-7, 16/21250-3, 17/22611-2, 15/11937-9, 16/01860-1)
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, . (13/03447-6, 16/23552-7, 16/01860-1, 15/11937-9)
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, . (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, . (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, . (16/23552-7, 14/02104-0, 15/11937-9)
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., . (17/21297-2, 15/11937-9, 16/23552-7)
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., . (15/11937-9, 16/23552-7)
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., . (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., . (15/11937-9, 16/14132-4, 16/23552-7, 16/01860-1)
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, . (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, . (16/23552-7, 16/14132-4, 15/11937-9, 16/01860-1)
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, . (16/23552-7, 16/01860-1, 15/11937-9, 14/25892-4)
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, . (16/23552-7, 16/14132-4, 15/11937-9)
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, . (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., . (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., . (15/11937-9, 17/22611-2, 16/23552-7, 16/01860-1, 16/21250-3)

Por favor, reporte erros na lista de publicações científicas utilizando este formulário.