Problemas de corte e empacotamento

Os problemas de corte e empacotamento são importantes problemas que ocorrem na prática. Os mesmos se caracterizam pela existência de um conjunto de ordens de produção para itens menores, os quais devem ser cortados a partir de objetos maiores ou empacotados nesses. Em geral, o principal objetivo refere-se à minimização da perda de material, o que se configura como minimização de custos de produção.

Dentre os problemas de corte, destacam-se os problemas de corte de rolos em indústria de papel, corte de barras de aço na construção civil, cortes de peças de madeira, vidro e tecido, e corte de pedras ornamentais, como granito. Nesses problemas, o objetivo principal é determinar como cortar peças menores a partir de peças maiores em estoque de forma a minimizar a perda de material por meio de rebarbas e sobras.

Por sua vez, os problemas de empacotamento tratam do encaixe de peças menores em peças maiores, chamadas de bins, de forma a minimizar o número de bins utilizados ou maximizar a utilização do espaço nos bins. Esse tipo de problema ocorre por exemplo na montagem de paletes, no carregamento de baús de caminhões de transporte de carga.

Os problemas de corte e empacotamento são problemas de otimização combinatória de difícil solução. (Também chmado de problemas NP-hard segundo a teoria de complexidade computacional.) Tais problemas se caracterizam pelo crecimento exponencial no número de soluções possíveis, de forma que é praticamente impossível obter boas soluções para problemas reais de larga escala por tentativa e erro. No entanto, é possível obter boas soluções ou até soluções ótimas por meio de algoritmos que explorem inteligentemente a estrutura matemática do problema.

Neste projeto, investiga-se uma classe particular de problemas de corte nos quais as decisões quanto ao corte de materiais é integrada às decisões de programação de ordens de produção. Estudos de caso são realizados principalmente em problemas de construção civil dentre os quais se destacam a produção de vigotas pré-moldadas, corte de pedras ornamentais como granito, e corte de barras metálicas.

As principais tecnologias utilizadas nesse projeto são o solver IBM CPLEX, e as linguagens Python e Julia.


Integrantes do projeto

Bruno A. Prata (Coordenador)

Anselmo R. Pitombeira Neto (Pesquisador)

Tibérius O. Bonates (Pesquisador)

Arthur H. F. Murta (Mestrando)

Éden M. Santos (Mestrando)