Introdução

Empacotar ítens (por exemplo, caixas) em objetos maiores (palete) e cortar objetos (por exemplo, couro) para produzir ítens menores (carteiras) são problemas similares. O problema de empacotar um dado conjunto de peças em uma dada região maximizando o número total de peças, ocorrem em grande número de situações práticas, incluindo o carregamento de paletes do produtor e o estabelecimento de layout em indústrias de roupas. Muitos artigos foram publicados lidando com o problema de empacotamento. Um dos problemas mais populares e úteis nessa área é encontrar o número máximo de retângulos que podem ser empacotados ortogonamente em um retângulo maior.

O problema de carregamento de paletes pode ser visto como um problema de corte e empacotamento bidimensional [16], que consiste em determinar como arranjar retângulos (face das caixas) dentro de um retângulo maior (superfície do palete), de maneira a maximizar a utilização da superfície do palete. Supõe-se que as caixas, em geral disponíveis em grandes quantidades, devem ser arranjadas ortogonalmente, isto é, com seus lados paralelos aos lados do palete.

Hodgson [22], ao estudar o PCP, dividiu-o em dois possíveis casos: o PCP do produtor e o PCP do distribuidor. No primeiro caso, o produtor fabrica um bem que é embalado em caixas iguais de dimensões $(l,w,h)$. Estas caixas devem ser então carregadas em camadas horizontais sobre paletes de dimensões $(L,W,H)$ (onde H é a altura máxima tolerável do carregamento). Em cada camada, uma orientação vertical das caixas é fixada. No segundo caso, o distribuidor recebe vários bens de diversos fornecedores, que estão embalados em caixas diferentes de dimensões $(l_i,w_i,h_i), i=1,...,m$, que, então, serão carregadas sobre paletes. Nesse trabalho vamos trabalhar com caixas de dimensões iguais.

A motivação para estudar o carregamento de paletes, além de ser um problema díficil de otimização combinatória, é que ele é importante nas atividades de armazenagem, movimentação e transporte de produtos. Devido à escala de certos sistemas logísticos, um pequeno aumento do número de produtos carregados sobre cada palete pode resultar numa economia global significativa. Alguns estudos propõem métodos exatos para resolver o problema, tais como Dowsland [14], Tsai et al. [42] e Bharttacharya et al. [3]. Métodos heurísticos podem ser encontrados, por exemplo, em Steudel [40], Smith e De Cani [38], Bischoff e Dowsland [10], Nelissen [33,34], Arenales e Morabito [29], Scheithauer e Terno [37], Herbert e Dowsland [20], Scheithauer e Sommerweiss [36], Morabito e Morales [31,32], G e Kang [19] e Lins et al. [25]. Limites superiores para o problema foram estudados em Nelissen [34] , Letchford e Amaral [23] e Morabito e Farago [30]. Outras referências podem ser encontradas em Hodgson [22], Dowsland e Dowsland [15], Sweeney e Paternoster [41], Dyckhoff e Finke [17], Balasubramanian [2], Martello [28], Bischoff e Waescher [11], Dyckhoff et al. [18], Arenales et al. [1], Wang e Waescher [43] e Hifi [21].

Este trabalho apresenta duas abordagens para resolver o problema de empacotamento de retângulos. Uma abordagem apresenta o algoritmo L para empacotamento de retângulos em retângulos e a outra, apresenta modelos contínuos para o empacotamento de retângulos em conjuntos convexos arbitrários.

O trabalho está organizado da seguinte maneira. Na primeira parte do trabalho descrevemos o algoritmo L, a nossa implementação e os resultados obtidos com esse algoritmo. Na segunda parte do trabalho descrevemos os modelos contínuos e os resultados obtidos com esses modelos. Por fim, comentamos algumas conclusões.