Trabalho De Otimizao

Modelagem e Resolução de um Problema de Corte Bidimensional com e sem Rotações de Itens

Nome:
César Henrique Maciel Ribeiro
Diego Rafael Monteiro Diniz
Diogo Rodrigues Prado

Dezembro/2009
Introdução

A alocação de itens retangulares em planos está presente em diversos ramos industriais. A necessidade de cortar chapas metálicas, placas de vidros, peças de tecidos e entre outros materiais para a comercialização é grande e o desperdício de material pode acarretar em grandes prejuízos para as corporações envolvidas. Na publicação de pequenas notícias em revistas, propagandas e jornais, matérias e notícias são divididas em quadros e devem ser alocados de modo a não haver desperdício de espaço e que o máximo de informação possa ser passada em uma mesma folha.

Desse modo, surgiu a necessidade de se formular um sistema ou algoritmo para minimizar o desperdício de material, de acordo com alguns dos exemplos citados anteriormente. O problema de otimização resultante desta necessidade é conhecido na literatura por Open Dimensional Problem (ODP). Trata-se de um modelo que possui diversas variações dependendo de sua aplicação e restringe-se a aplicação de cortes em formas, chapas ou objetos retangulares de modo a minimizar o desperdício de material.
O ODP pode ser tratado como um problema unidimensional ou bidimensional. Em um ODP bidimensional, o mesmo é denominado de two-dimensional bin packing problem (2BP). Neste trabalho, será abordado e aplicado o two-dimensional strip packing problem (2SP), que é uma variação do 2BP. O mesmo será aplicado de forma guilhotinada, ou seja, o corte se estende de um lado para o outro. Outro tipo de 2SP que pode ser trabalhado em otimização é o 2SP não guilhotinado em que o corte acompanha o contorno do item, sem descaracterizar o objeto.

Objetivos

O objetivo do trabalho é obter a solução