Algoritmos para problemas de empacotamento
Eduardo Candido Xavier
TESE
Português
T/UNICAMP X19a
[Algorithms for packing problems]
Campinas, SP : [s.n.], 2006.
134p. : il.
Orientador: Flavio Keidi Miyazawa
Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação
Resumo: Neste trabalho estudamos diversos problemas de empacotamento considerados NP-difíceis. Assumindo a hipótese de que P ? NP, sabemos que não existem algoritmos eficientes (complexidade de tempo polinomial) exatos para resolver tais problemas. Uma das abordagens consideradas para tratar tais...
Ver mais
Resumo: Neste trabalho estudamos diversos problemas de empacotamento considerados NP-difíceis. Assumindo a hipótese de que P ? NP, sabemos que não existem algoritmos eficientes (complexidade de tempo polinomial) exatos para resolver tais problemas. Uma das abordagens consideradas para tratar tais problemas é a de algoritmos de aproximação, que são algoritmos eficientes e que geram soluções com garantia de qualidade. Neste trabalho apresentamos alguns algoritmos aproximados para problemas de empacotamento com aplicações práticas. Outra maneira de se lidar com problemas NP-difíceis é o desenvolvimento de heurísticas. Neste trabalho também apresentamos heurísticas baseadas no método de geração de colunas para problemas de corte e empacotamento bidimensional. Resultados computacionais sugerem que tais heurísticas são eficientes e geram soluções de muito boa qualidade.
Ver menos
Abstract: In this work we study several packing problems that are NP-hard. If we consider that P ? NP, we know that there are no efficient (polynomial time complexity) exact algorithms to solve these problems. One way to deal with these kind of problems is to use approximation algorithms, that are...
Ver mais
Abstract: In this work we study several packing problems that are NP-hard. If we consider that P ? NP, we know that there are no efficient (polynomial time complexity) exact algorithms to solve these problems. One way to deal with these kind of problems is to use approximation algorithms, that are efficient algorithms that produce solutions with quality guarantee. We present several approximation algorithms for some packing problems that have practical applications. Another way to deal with NP-hard problems is to develop heuristics. We also consider column generation based heuristics for packing problems. In this case, we present column generation algorithms for some two dimensional packing problems and also present computational tests with the proposed algorithms. The computational results shows that the heuristics are efficient and produce solutions of very good quality.
Ver menos
Miyazawa, Flávio Keidi, 1970-
Orientador
Wakabayashi, Yoshiko
Avaliador
Souza, Cid Carvalho de, 1963-
Avaliador
Lee, Orlando, 1969-
Avaliador
Yanasse, Horacio Hideki
Avaliador
Algoritmos para problemas de empacotamento
Eduardo Candido Xavier
Algoritmos para problemas de empacotamento
Eduardo Candido Xavier
Exemplares
Nº de exemplares: 2
Não existem reservas para esta obra