Detalhes bibliográficos
Ano de defesa: |
2016 |
Autor(a) principal: |
Dantas, Bianca de Almeida |
Orientador(a): |
Cáceres, Edson Norberto |
Banca de defesa: |
Não Informado pela instituição |
Tipo de documento: |
Tese
|
Tipo de acesso: |
Acesso aberto |
Idioma: |
por |
Instituição de defesa: |
Não Informado pela instituição
|
Programa de Pós-Graduação: |
Não Informado pela instituição
|
Departamento: |
Não Informado pela instituição
|
País: |
Não Informado pela instituição
|
Palavras-chave em Português: |
|
Link de acesso: |
https://repositorio.ufms.br/handle/123456789/2970
|
Resumo: |
O problema da mochila multidimensional ´e amplamente conhecido na área de otimização combinatória e possui diversas aplicações práticas, tais como, dimensionamento de cargas, orçamento de capital, alocação de recursos em sistemas distribuídos, entre outros. Apesar de sua popularidade, sua solução não é trivial, de fato, ele pertence a uma classe de problemas conhecidos como NP-difíceis, para os quais não são conhecidos algoritmos polinomiais capazes de obter uma solução exata para todas as instancias. Essa situação motiva a busca por técnicas alternativas para obter soluções em menor tempo, ainda que aproximadas e, nesse cenário, as metaheurısticas têm se mostrado de especial interesse, pois são capazes de alcançar soluções de boa qualidade para uma ampla variedade de problemas. Entretanto, mesmo as metaheurısticas podem ser relativamente demoradas, em especial para instâncias de tamanho grande, o que encoraja a aplicação de t´técnicas, como as estratégias de paralelização, para reduzir os seus tempos de execução ou, ainda, melhorar a qualidade das soluções. Neste trabalho, apresenta-se o estudo, implementação e análise de um conjunto de metaheurısticas para a solução do problema da mochila multidimensional. São apresentadas e avaliadas diferentes alternativas para a paralelização e os resultados obtidos são comparados com os de outros trabalhos da literatura pesquisada. Para comprovar que os bons resultados possibilitados pelo uso das metaheurısticas estudadas não foram obtidos ao acaso, as soluções foram validadas com a utilização de testes estatísticos. |