Problemas de Corte Bidimensional Guilhotinado e Restrito: Formulações Matemáticas e Métodos de Solução

Resumo

Este projeto aborda Problemas de Corte Bidimensional Guilhotinado e Restrito (PGR). Esses problemas consistem em produzir retângulos menores (peças), a partir de retângulos maiores (objetos), ao utilizarem operações de corte que repartam os materiais em dois retângulos e que atendam à quantidade de vezes que as peças podem aparecer nos padrões de corte, sem restrição sobre o número de estágios. Embora o PGR esteja presente em alguns contextos industriais, não há registros na literatura de formulações matemáticas para esse problema. Este projeto propõe o desenvolvimento de modelos de programação matemática para o PGR e de métodos para sua solução. O PGR será analisado no contexto dos seguintes problemas: Problema da Alocação (Placement Problem), Problema de Corte de Estoque (Cutting Stock Problem) e Problema de Empacotamento (Bin Packing Problem). Três estratégias de solução são propostas. A primeira estratégia envolve o desenvolvimento de formulações compactas de programação matemática para esses problemas, visando lidar com conjuntos pequenos de peças e objetos. A segunda e terceira estratégias envolvem lidar com conjuntos maiores de peças e objetos, a partir do desenvolvimento de formulações extensivas para esses problemas, no contexto de Geração de Colunas. A segunda estratégia lida com o desenvolvimento de um modelo programação matemática para gerar padrões de corte ao PGR e a terceira estratégia propõe uso de métodos de programação dinâmica para gerar esses padrões. O desenvolvimento de modelos matemáticos contribui com a pesquisa de métodos de soluções para o problema, a partir da análise de estruturas particulares que permitam reformular o problema por meio de técnicas de decomposição ou relaxação. A robustez dos métodos será avaliada por experimentos computacionais usando instâncias da literatura, o que também permitirá compará-los a outras abordagens.