Publicação
Um comparativo de duas metaheurísticas aplicadas a problemas de bin packing bidimensional
| Resumo: | Corte e empacotamento são processos bastante utilizados pelas indústrias e são constantemente estudados pela Pesquisa Operacional, pois seus custos afetam significativamente no custo final do produto. A redução destes gastos é importante para a diminuição dos desperdícios e obtenção de maiores lucros. Porém, são considerados problemas de natureza combinatória NP-hard, inviáveis de serem solucionados por algoritmos exatos, pois necessitam um tempo computacional avançado. O objetivo deste trabalho é realizar um comparativo no desempenho das metaheurísticas Busca Tabu e Algoritmo Genético na resolução de problemas de bin packing bidimensionais com bins de múltiplos tamanhos, com o intuito de alcançar soluções viáveis que otimizem o número de bins utilizados em um tempo computacional reduzido. Códigos computacionais foram desenvolvidos para ambas as metaheurísticas para a resolução de 15 problemas de bin packing contidos na OR-Library com até 150 objetos de no máximo 30x30 unidades de área. A utilização única e exclusiva da heurística de encaixe Bottom-Left se mostrou mais eficiente que as metaheurísticas implementadas e a Busca Tabu levou vantagem nos resultados em relação ao Algoritmo Genético em 80% dos problemas resolvidos. |
|---|---|
| Autores principais: | Souza, Isabella Lima de |
| Outros Autores: | Franco, Raul Ferreira de Andrade |
| Assunto: | CNPQ::ENGENHARIAS::ENGENHARIA DE PRODUCAO::PESQUISA OPERACIONAL Metaheurística Busca Tabu Algoritmo Genético Bin Packing Metaheuristics Tabu Search Genetic Algorithm |
| Ano: | 2019 |
| País: | Brasil |
| Tipo de documento: | trabalho de fim de curso |
| Tipo de acesso: | acesso aberto |
| Instituição associada: | IBICT |
| Idioma: | português |
| Origem: | Oasisbr |
| Resumo: | Corte e empacotamento são processos bastante utilizados pelas indústrias e são constantemente estudados pela Pesquisa Operacional, pois seus custos afetam significativamente no custo final do produto. A redução destes gastos é importante para a diminuição dos desperdícios e obtenção de maiores lucros. Porém, são considerados problemas de natureza combinatória NP-hard, inviáveis de serem solucionados por algoritmos exatos, pois necessitam um tempo computacional avançado. O objetivo deste trabalho é realizar um comparativo no desempenho das metaheurísticas Busca Tabu e Algoritmo Genético na resolução de problemas de bin packing bidimensionais com bins de múltiplos tamanhos, com o intuito de alcançar soluções viáveis que otimizem o número de bins utilizados em um tempo computacional reduzido. Códigos computacionais foram desenvolvidos para ambas as metaheurísticas para a resolução de 15 problemas de bin packing contidos na OR-Library com até 150 objetos de no máximo 30x30 unidades de área. A utilização única e exclusiva da heurística de encaixe Bottom-Left se mostrou mais eficiente que as metaheurísticas implementadas e a Busca Tabu levou vantagem nos resultados em relação ao Algoritmo Genético em 80% dos problemas resolvidos. |
|---|
Atividades financiadas
Não foram encontrados projetos financiados.