Submitted by Erika Demachki (erikademachki@gmail.com) on 2016-03-17T17:31:58Z
No. of bitstreams: 2
Dissertação - Santiago Valdés Ravelo - 2011.pdf: 730949 bytes, checksum: 92c89c8c1f240082004834898896b9ba (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Erika Demachki (erikademachki@gmail.com) on 2016-03-17T17:35:15Z (GMT) No. of bitstreams: 2
Dissertação - Santiago Valdés Ravelo - 2011.pdf: 730949 bytes, checksum: 92c89c8c1f240082004834898896b9ba (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2016-03-17T17:35:15Z (GMT). No. of bitstreams: 2
Dissertação - Santiago Valdés Ravelo - 2011.pdf: 730949 bytes, checksum: 92c89c8c1f240082004834898896b9ba (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)
Previous issue date: 2011-02-18 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work considers three relevant NP-hard problems. The firstone is the one-dimensional
cutting stock problem in which the non-used material in the cutting patterns may be used
in the future. For this problem we analyze the existing mathematical models, propose new
models, design a heuristic and two metaheuristic approaches, being their performances
improved by using parallel programming, and solve instances, practical and randomly
generated, from the literature. The computational experiments were quite good for all
tested instances. The second problem we consider is the stable roommates problem (a
variant of the stable matching problem). For this we give two mathematical programming
models, sequential and parallel implementations of a Tabu Search, and a Branch-andBound. Also, we report computational experiments to instances of the problem. The
last problem we consider is the compartmentalized knapsack problem (a generalization
of the knapsack problem) for which we analyze a quadratic integer model and give a
linear integer model. We design a greedy heuristic and a GRASP algorithm, that uses
path-relinking, and solve randomly generated instances. All parallel implementations use
Graphics Processing Units (GPUs). / Este trabalho considera três problemas, NP-difíceis, relevantes de estudo em otimização
combinatória. O primeiro deles é o problema de corte uni-dimensional de objetos,
onde o material não usado pelos padrões de corte pode ser usado no futuro. Para este
problema analisamos os modelos matemáticos existentes, propomos novos modelos,
projetamos uma heurística construtiva e duas metaheurísticas, sendo seus desempenhos
melhorados com programação paralela, e resolvemos instâncias, práticas e aleatórias,
encontradas na literatura; sendo os experimentos computacionais muito bons para todas as
intânciastestadas.Osegundoproblemaqueconsideramoséoproblemadoscompanheiros
estáveis (stable roommates problem), uma variante do problema de emparelhamento
estável (stable matching problem). Para este propomos dois modelos matemáticos, uma
implementação sequencial e uma paralela de uma Tabu Search, e um Branch-andBound. Também reportamos experimentos computacionais para instâncias do problema.
O último problema considerado é o da mochila compartimentada (uma generalização do
problema clássico da mochila), para o qual analisamos uma modelagem quadrática inteira
e propomos um modelo linear inteiro; também projetamos uma heurística gulosa, um
algoritmo GRASP, que usa path-relinking, e resolvemos intâncias geradas aleatóriamente.
Todas as implementações em paralelo usam unidades de processamento gráfico (Graphics
Processing Units, GPUs).
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.bc.ufg.br:tede/5354 |
| Date | 18 February 2011 |
| Creators | Ravelo, Santiago Valdes |
| Contributors | Meneses, Claudio Nogueira de, Meneses, Cláudio Nogueira de, Longo, Humberto José, Morabito, Reinaldo |
| Publisher | Universidade Federal de Goiás, Programa de Pós-graduação em Ciência da Computação (INF), UFG, Brasil, Instituto de Informática - INF (RG) |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFG, instname:Universidade Federal de Goiás, instacron:UFG |
| Rights | http://creativecommons.org/licenses/by-nc-nd/4.0/, info:eu-repo/semantics/openAccess |
| Relation | -3303550325223384799, 600, 600, 600, 600, -7712266734633644768, 3671711205811204509, 2075167498588264571 |
Page generated in 0.0026 seconds