Fábio Henrique Nishihara
Orientador: Ernesto G. Birgin
December 8, 2003
Um dos problemas mais clássicos de empacotamento é encontrar o número máximo de objetos que podem ser empacotados em uma dada regiã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.
Neste trabalho estudamos dois enfoques diferentes para resolver o problema de empacotamento de retângulos. Nos dois enfoques consideramos que os retângulos devem ser empacotados ortogonalmente, isto é, seus lados paralelos aos eixos.
Na primeira parte implementamos e testamos o algoritmo L para o
empacotamento de retângulos em retângulos, recentemente introduzido em [26].
Este algoritmo é recursivo e empacota retângulos de dimensões 
em peças
com formato de L e em peças retangulares maiores. O algoritmo particiona
recursivamente um retângulo ou um L em duas novas peças, cada uma podendo
ser de novo um retângulo ou um L.
Na segunda parte introduzimos modelos contínuos para o empacotamento de
retângulos em conjuntos convexos arbitrários. Esses modelos estão baseados
em [6] e em [7]. Experimentos numéricos mostram que tanto
os modelos introduzidos como a metodologia proposta para resolver os
problemas de otimização contínua são promissores.
Palavras-chaves: problemas de empacotamento, problemas de corte, carregamento de paletes, algoritmo recursivo, modelos contínuos, sentinelas