Instituto de Informática – UFG

e-mail

Palavras-chave: corte guilhotinado bidimensional, otimização combinatória.

Os cortes bidimensionais são efetuados por industrias que utilizam materiais planos, como industrias especializada em vidros planos, metalúrgica, papeis, plásticos serralheria, etc. Dependendo da característica do material, têm-se vários tipos de cortes, como o guilhotinado, não-guilhotinado e o poligonal.

Os cortes guilhotinados e não-guilhotinados envolvem retângulos de tamanhos variados que podem ser rotacionados em 90 graus para que se encaixem da melhor forma possível na chapa a ser cortada.

Já nos cortes poligonais, existem diferenças quanto aos corte guilhotinados e não-guilhotinados, porque envolvem possibilidades combinatórias bem maiores, e isto é causado devido à forma das peças que são usadas, os quais são polígonos não necessariamente retangulares. Apesar deste detalhe temos várias semelhanças entre este corte e os outros.

No geral, o problema do corte bidimensional (para ambos os casos) é a geração um layout que indique como cortar uma ou várias peças de uma chapa (matéria-prima) de forma que se obtenha o máximo possível de aproveitamento de espaço. O problema é importante para empresas que realizam atividades de corte, pois quanto menos desperdício de matéria prima maior será à margem de lucro.

Esta ferramenta usa um algoritmo com a seguinte heurística:

1. Cortar a maior peça cuja dimensão caiba no menor pedaço possível;
2. Cortar uma peça sempre no canto inferior esquerdo de uma chapa ou pedaço disponível da mesma, devendo o corte ser processado de forma guilhotinada a fim de que a peça possa ser imediatamente destacada. Basicamente, dois tipos de corte são possíveis: corte principal vertical e corte principal horizontal. Se a dimensão da peça a ser cortada for menor que o pedaço de chapa disponível, então o corte origina um ou dois pedaços restantes;
3. Escolher o tipo de corte (vertical ou horizontal) a ser realizado com base em algumas estratégias simples que definimos como, por exemplo, maximizar o menor pedaço restante ou maximizar o maior pedaço restante. A orientação das peças também deve ser considerada na escolha do tipo de corte, caso seja possível rotacioná-las.

Neste algoritmo, quando as entradas são uma chapa quadrada cuja medida das arestas é múltiplo de 10 e as dimensões das peças são números inteiros, teremos um caso de 100% de aproveitamento.

A questão do corte de polígonos é bem mais complexa do que a do corte guilhotinado. Para pensarmos no corte de polígonos, é essencial termos conhecimento dos problemas que envolvem cortes em objetos de formas e medidas variadas, pois o corte poligonal também é da mesma natureza que estes outros problemas.

Para a realização desse trabalho, vamos precisar dos seguintes materiais: referências bibliográficas e computadores para estudo e implementação de softwares.

Durante o decorrer da pesquisa, cumpriremos as seguintes etapas: estudaremos as propriedades peculiares de algoritmos de corte bidimensionais tradicionais como aqueles baseados nas heurísticas First Fit e Best Fit; Construiremos uma representação matemática para o algoritmo do INF e faremos uma prova formal de que ele tem uma das propriedades peculiares comentadas acima – apresenta desempenho igual a 100% para instâncias de tamanho 10 x 10; Também é nosso objetivo uma possível publicação de um artigo sobre a prova formal das propriedades do algoritmo do INF; Estudaremos algoritmos específicos para corte de peças poligonais; Implementaremos um algoritmo para corte poligonal e comparação com um algoritmo de corte de retângulos; Também queremos escrita e publicar um artigo sobre corte poligonal.

Até o presente momento, já realizamos ou estamos realizando as seguintes tarefas: começamos a estudar o problema de corte guilhotinado e a heurística do algoritmo de corte de vidro, problemas de empacotamento e da mochila para os quais existem algoritmos exatos de tempo polinomial. Iniciamos também a implementação de um algoritmo para gerar instâncias de corte para que possamos realizar análises sobre o algoritmo do INF.

Até o final da pesquisa, esperamos obter os seguintes resultados: Ter uma melhor análise do desempenho do algoritmo do INF; Ter implementado bons algoritmos de cortes para serem integrados à uma ferramenta de corte atualmente em desenvolvimento pelo INF e finalmente, publicar artigos na área.

Espera-se, com esse trabalho contribuir para uma melhor descrição do funcionamento de alguns algoritmos de corte, conseqüentemente, aumentar a produtividade do setor industrial que empregam diretamente os resultados científicos sobre corte bidimensional.

BAASE, SARA. "Computer algorithms" / Sara Baase, Allen Van Gelder. – 3rd ed.

LEVINE, JOHN., DUCATELLE, FREDERICK. "Ant Colony Optimisation and Local Search for Bin Packing and Cutting Stock Problems".

NASCIMENTO, HUGO A. D. DO., LONGO, HUMBERTO JOSE., ALOISE, DARIO JOSÉ. "Uma Heurística O(mn) para Corte Bidimensional Guilhotinado".