Abordagens exata e não-exata para o problema de corte bidimensional com sobras aproveitáveis

No Problema de Corte de Estoque (PCE) bidimensional, um conjunto de placas retangulares disponíveis em estoque é cortado para produzir itens retangulares menores. O processo de corte deve ser planejado de modo a atender a demanda dos itens e otimizando uma função objetivo. Uma variação do PCE, que tem sido considerada em situações práticas como uma estratégia para reduzir o desperdício de matéria-prima, consiste em gerar sobras aproveitáveis que retornam ao estoque para ser utilizadas em futuros processos de corte. Essa variação é chamada de Problema de Corte de Estoque com Sobras Aproveitáveis (PCESA). No PCESA, padrões de corte são criados com o objetivo de gerar sobras aproveitáveis com alta probabilidade de uso futuro, trazendo vantagens em termos de sustentabilidade e desenvolvimento econômico.
Esta pesquisa propõe um modelo linear para representar o PCESA bidimensional. Este modelo cria padrões de corte e determina suas frequências simultaneamente. Para a construção dos padrões de corte, as placas retangulares em estoque são divididas em faixas horizontais, enquanto que os itens demandados são alocados sequencialmente em cada faixa. Além disso, itens podem ser combinados para criar novos tipos de itens chamados “macro-itens”, que também podem ser alocados nas faixas. Cada padrão de corte pode gerar apenas uma sobra aproveitável, obtida a partir de um único corte horizontal guilhotinado, garantindo que a sobra tenha a mesma largura da placa cortada e altura variando dentro de um intervalo pré-definido. Apesar de considerarmos a presença de sobras em estoque, apenas placas padronizadas (obtidas de fornecedores) podem gerar novas sobras aproveitáveis. Esse modelo foi resolvido a partir de um solver comercial, que pôde fornecer soluções ótimas para instâncias de pequeno e médio porte.
Um procedimento heurístico foi proposto para resolver instâncias maiores. Esse procedimento decompõe o problema original em problemas menores, reduzindo o tempo computacional necessário para a obtenção de soluções inteiras de boa qualidade. A eficiência do modelo e do procedimento heurístico foi verificada através de testes computacionais com instâncias geradas aleatoriamente e instâncias da literatura.
Os autores agradecem à FAPESP (Processos: 2016/01860-1 e 2018/16600-0) e ao CNPq (Processos: 421130/2018-0 e 306558/2018-1) pelo apoio financeiro.