Busca avançada
Ano de início
Entree

Problemas de corte e empacotamento: abordagens práticas e teóricas

Processo: 16/23552-7
Linha de fomento: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
Pesq. associados:Eduardo Candido Xavier ; Flávio Keidi Miyazawa ; Lehilton Lelis Chaves Pedrosa
Assunto(s):Algoritmos de aproximação   Otimização combinatória  Heurística 

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 (6)
(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 NEGRI; MIYAZAWA, FLAVIO KEIDI; XAVIER, EDUARDO CANDIDO. Online circle and sphere packing. THEORETICAL COMPUTER SCIENCE, v. 776, p. 75-94, JUL 12 2019. Citações Web of Science: 0.
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. Citações Web of Science: 0.
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. Citações Web of Science: 0.
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. Citações Web of Science: 3.
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. Citações Web of Science: 0.
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. Citações Web of Science: 0.

Por favor, reporte erros na lista de publicações científicas escrevendo para: cdi@fapesp.br.
Mapa da distribuição dos acessos desta página
Para ver o sumário de acessos desta página, clique aqui.