11 |
Modelos matemáticos e algoritmos para problemas combinatóriosRavelo, Santiago Valdes 18 February 2011 (has links)
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).
|
12 |
Aplicação de algoritmos genéticos para minimização do número de objetos processados e o setup num problema de corte unidimensional / Analysis of cutting stock problem using genetic algorithmJulliany Sales Brandão 22 May 2009 (has links)
Esta dissertação apresenta a aplicação de uma nova abordagem utilizando Algoritmo Genético na resolução do Problema de Corte Unidimensional na minimização de dois objetivos, geralmente conflitantes, o número de objetos processados e o setup, simultaneamente. O problema de corte consiste, basicamente, em encontrar a melhor maneira de obter peças de tamanhos distintos (itens) a partir do corte de peças maiores (objetos) com o objetivo de minimizar alguma espécie de custo ou maximizar o lucro. A disposição dos itens no objeto para a realização de cortes durante sua produção é denominada padrão de corte. E o setup é o tempo de preparação de máquina. O modelo do problema, a função objetivo e o método proposto denominado SingleGA, bem como os passos utilizados para sua resolução, também são apresentados. Os resultados obtidos pelo SingleGA são comparados com os métodos SHP, Kombi234, ANLCP300 e Symbio, encontrados na literatura, a fim de verificar a capacidade de encontrar soluções viáveis e competitivas. Os resultados computacionais mostram que o método proposto, o qual utiliza apenas um algoritmo genético para resolver esses dois objetivos inversamente relacionados, proporciona bons resultados.
|
13 |
Aplicação de algoritmos genéticos para minimização do número de objetos processados e o setup num problema de corte unidimensional / Analysis of cutting stock problem using genetic algorithmJulliany Sales Brandão 22 May 2009 (has links)
Esta dissertação apresenta a aplicação de uma nova abordagem utilizando Algoritmo Genético na resolução do Problema de Corte Unidimensional na minimização de dois objetivos, geralmente conflitantes, o número de objetos processados e o setup, simultaneamente. O problema de corte consiste, basicamente, em encontrar a melhor maneira de obter peças de tamanhos distintos (itens) a partir do corte de peças maiores (objetos) com o objetivo de minimizar alguma espécie de custo ou maximizar o lucro. A disposição dos itens no objeto para a realização de cortes durante sua produção é denominada padrão de corte. E o setup é o tempo de preparação de máquina. O modelo do problema, a função objetivo e o método proposto denominado SingleGA, bem como os passos utilizados para sua resolução, também são apresentados. Os resultados obtidos pelo SingleGA são comparados com os métodos SHP, Kombi234, ANLCP300 e Symbio, encontrados na literatura, a fim de verificar a capacidade de encontrar soluções viáveis e competitivas. Os resultados computacionais mostram que o método proposto, o qual utiliza apenas um algoritmo genético para resolver esses dois objetivos inversamente relacionados, proporciona bons resultados.
|
Page generated in 0.0757 seconds