Orientador: Flavio Keidi Miyazawa / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-07T21:41:01Z (GMT). No. of bitstreams: 1
Xavier_EduardoCandido_D.pdf: 20666026 bytes, checksum: 5e051653d938a813e227b1e2eebcd415 (MD5)
Previous issue date: 2006 / 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. / 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. / Doutorado / Doutor em Ciência da Computação
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.unicamp.br:REPOSIP/275871 |
| Date | 12 May 2006 |
| Creators | Xavier, Eduardo Candido, 1979- |
| Contributors | UNIVERSIDADE ESTADUAL DE CAMPINAS, Miyazawa, Flávio Keidi, 1970-, Wakabayashi, Yoshiko, Souza, Cid Carvalho de, Lee, Orlando, Yanasse, Horacio Hideki |
| Publisher | [s.n.], Universidade Estadual de Campinas. Instituto de Computação, Programa de Pós-Graduação em Ciência da Computação |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | 134p. : il., application/octet-stream |
| Source | reponame:Repositório Institucional da Unicamp, instname:Universidade Estadual de Campinas, instacron:UNICAMP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0026 seconds