Uma heurística de busca tabu simples para o problema de carregamento de paletes do produtor

摘要

O problema de carregamento de paletes do produtor consiste em arranjar, ortogonalmente e sem sobreposi??o, o máximo número de caixas de dimens?es (l,w) ou (w,l), sobre um palete retangular de dimens?es (L,W). Este problema vem sendo tratado com sucesso por heurísticas de blocos, onde s?o gerados padr?es de carregamento compostos por um ou mais blocos, cujas pe?as possuem a mesma orienta??o. Uma característica desses métodos é que os padr?es gerados est?o limitados aos chamados padr?es n?o-guilhotinados de primeira ordem. Neste trabalho é proposta uma abordagem baseada na incorpora??o de busca tabu simples (sem estruturas de memória de longo prazo) em heurísticas de bloco. Partindo-se de uma solu??o inicial, s?o realizados movimentos de aumento de blocos, que resultam na diminui??o, elimina??o e cria??o de outros blocos. Resultados computacionais indicam que esta abordagem é capaz de gerar padr?es ótimos de ordem superior em problemas de difícil resolu??o para outros métodos da literatura.