Abstrato

UM NOVO ALGORITMO BASEADO EM GRÁFICOS PARA O PROBLEMA DE EMBALAMENTO DE COMPARTIMENTOS UNIDIMENSIONAIS

Debajit Sensarma, Samar Sen Sarma

O Bin Packing Problem (BPP) é um dos problemas de otimização combinatória mais conhecidos. O principal objetivo do problema é minimizar o número de caixas utilizadas e embalar os artigos de diferentes tamanhos num número finito de caixas de forma eficiente. Este artigo apresenta um novo algoritmo baseado em grafos para o problema de empacotamento unidimensional. O algoritmo proposto é implementado e testado com instâncias de benchmark bem conhecidas e é fornecida uma comparação com o algoritmo First-Fit Decreasing (FFD) existente em relação ao número de caixas e ao espaço residual. Na maioria dos casos, o novo algoritmo produz soluções quase ótimas e tem um melhor desempenho que o FFD.