Um refinamento do algoritmo tabu de Dowsland para o problema de carregamento de paletes do produtor Translated title: A refinement of Dowsland's tabu search algorithm for the manufacturer's pallet loading problem

Abstract

O Problema de Carregamento de Paletes do Produtor consiste em arranjar, ortogonalmente e sem sobreposição, o máximo número de caixas retangulares idênticas de dimensões (l,w) sobre um palete (L,W). Este problema vem sendo tratado com sucesso por heurísticas de blocos, as quais constroem padrões de carregamento com um ou mais blocos, cujas caixas possuem a mesma orientação. Os arranjos gerados por estes métodos estão limitados aos chamados padrões não-guilhotinados de primeira ordem. Neste trabalho, foi elaborada uma implementação baseada no algoritmo de busca tabu de Dowsland, que, ao contrário das heurísticas de blocos, provê arranjos não limitados a padrões particulares de empacotamento. Experimentos computacionais com um conjunto de 34 exemplos extraídos da literatura e de contextos reais indicam que a abordagem é capaz de resolver otimamente a maioria dos exemplos; para os exemplos não resolvidos, é proposto um procedimento adicional simples, cuja aplicação resultou na obtenção de padrões ótimos.

Translated abstract

The Manufacturer's Pallet Loading Problem (MPLP) consists in arranging, orthogonally and without overlapping, the maximum number of rectangular and identical pieces of sizes (l, w) onto a pallet (L, W). The MPLP has been successfully handled by block heuristics, which generate loading patterns with one or more blocks where the pieces have the same orientation. The resulting patterns produced by these methods are limited to the so-called 1st order non-guillotine patterns. In this work we present a tabu search implementation based on the algorithm proposed by Dowsland to solve the MPLP; differently than block heuristics, the solutions are not limited to particular loading patterns. Computational experiments with a set of 34 instances extracted from the literature as well as from practical contexts indicate that this approach is capable to solve most of the examples. For the unsolved instances, we propose a simple additional procedure, which resulted in optimal patterns.