Problemas de Corte e Empacotamento
Prof. Flávio Keidi Miyazawa


Os problemas de empacotamento, como muitos de natureza combinatória, podem ser facilmente formulados e compreendidos, escondendo atrás de sua aparente simplicidade, a sua real complexidade. São problemas NP-difíceis não aproximáveis ---em termos absolutos--- além de certas constantes, a menos que P=NP. Esse caráter complexo em termos de aproximabilidade absoluta, justifica o estudo desses problemas quanto à sua aproximabilidade em termos assintóticos.

Consideramos aqui diversos problemas de empacotamento bi- e tridimensional, muitos deles já investigados sob essa abordagem, e descrevemos para esses problemas algoritmos de aproximação cujos limites de desempenho assintótico são melhores do que os encontrados na literatura.

Primeiramente, vamos introduzir o leitor a vários problemas de empacotamento, ilustrando a ocorrência de vários deles no processo de construção de um prédio.

Primeiro, considere a estrutura de concreto armado de um prédio. Mais precisamente, considere as colunas de concreto contendo barras de aço em seu interior. Estas colunas podem ter diferentes comprimentos e conseqüentemente cada uma delas requer barras com certo comprimento. Em geral, a fábrica que produz estas barras somente as produz com um comprimento específico, digamos 12 metros. Assim, a construtora deve comprar estas barras grandes e cortá-las conforme sua necessidade. Claramente, para minimizar os custos, o seu objetivo é comprar o menor número de barras necessário na construção. Este é um problema muito comum que também aparece em problemas de corte de vigas, estruturas metálicas, canos, esquadrias, etc. Trata-se de um problema de empacotamento unidimensional. Exemplo:

Exemplo de empacotamento unidimensional

Prosseguindo na construção do prédio, considere agora as janelas e divisórias de vidro retangulares, necessárias em quantidade e tamanhos diferentes. A construtora faz o pedido de compra a uma vidraçaria, especificando as dimensões e quantidades de cada item. A vidraçaria deve cortar estes pedaços a partir de placas de vidro de tamanhos fixos, que são fornecidas pelo fabricante de vidro. Novamente, para minimizar os custos, o objetivo da vidraçaria é usar o menor número destas placas. Este problema também aparece no corte de chapas, divisórias, compensados, etc. Temos aqui um problema de empacotamento (bidimensional) em placas. Exemplo:

Exemplo de empacotamento bidimensional

Considere agora o seguinte problema. A construtora, tendo terminada a construção do prédio, contrata uma empresa de publicidade para fazer bandeiras, faixas, bonés e camisetas com a propaganda do prédio. Para fazer todo este material publicitário, a empresa precisa comprar uma certa quantidade de tecido. As tecelagens produzem tecidos com uma largura fixa e com comprimento variável, sendo que seu custo é proporcional ao comprimento. Assim, para minimizar os seus gastos o objetivo da empresa de publicidade é comprar o menor comprimento de tecido necessário para cortar todos os itens requisitados. Este é um problema de empacotamento (bidimensional) em faixa. Exemplo:

Empacotamento em Faixa

Um outro problema que ocorre está relacionado ao transporte de produtos e cargas para o local de construção do prédio. Vários produtos (como vidros, pisos, azulejos) devem ser encaixotados e então transportados em furgões de dimensões fixas. Para minimizar os custos o objetivo aqui é fazer o menor número de viagens da loja de materiais para o local de construção. O problema consiste em empacotar as caixas no menor número de furgões e conseqüentemente, minimizar o número de viagens. Trata-se aqui de um problema de empacotamento em contêineres. Exemplo:

Empacotamento em Container

Uma vez que os produtos são transportados para o local da construção, estes devem ser armazenados em um galpão (de forma retangular), de forma a ficarem protegidos até seu uso. Surge aqui o problema de empacotar estas caixas dentro do galpão. O objetivo é encontrar um empacotamento cuja altura seja a menor possível.

Os problemas envolvidos nos exemplos acima são chamados de problemas de corte e/ou problemas de empacotamento. Segundo a definição de empacotamento que apresentamos, os problemas de corte de barras, vidros, tecidos ou outros materiais podem ser vistos como problemas de empacotamento (de pedaços de barras em barras, de moldes em vidros ou tecidos).

De uma forma geral, os problemas de empacotamento consistem em empacotar uma lista de itens em recipientes. Dependendo da natureza dos itens sendo empacotados dizemos que os problemas são uni-, bi- ou tridimensionais.

Os problemas abordados podem diferir em duas linhas conforme a função objetivo do problema de otimização em questão. Em uma destas linhas, o objetivo é minimizar o número de recipientes usados para empacotar os itens da lista. Em outra linha, os itens devem ser empacotados em apenas um recipiente, sendo que este recipiente tem apenas uma dimensão ilimitada e todas as outras são limitadas (por exemplo, uma caixa com fundo limitado e altura ilimitada). Neste caso, o objetivo é minimizar o `tamanho' do empacotamento com relação à dimensão ilimitada do recipiente. Nos referimos a este tamanho como sendo a altura do empacotamento.

Algumas das aplicações de problemas de corte e empacotamento são: alocação de comerciais em TV, alocação de programas em discos e fitas magnéticas, carregamento de veículos, problema da programação de veículos, corte de bobinas (papel, aço, ...), corte de vigas (em madeireiras, construção civil, ...), pré-paginação, corte de placas (vidro, chapas, madeira, compensado, ...), corte de retalhos em fábrica de tecidos, ou em confecção de roupas, empacotamento de caixas em galpões, empacotamento em contêineres, carregamento de cargas em furgões e corte de espumas para colchões.

Flávio Keidi Miyazawa's Homepage