Modelos matemáticos para o problema de empacotamento em faixas de peças irregulares

Resumo

O problema de empacotamento em faixas de peças irregulares consiste em cortar umconjunto de peças bidimensionais a partir de um objeto de largura fixa utilizando omenor comprimento possível. Apesar de sua importância econômica para diversos setoresindustriais, há poucos trabalhos que abordam o problema de forma exata devido a suadificuldade de resolução. Recentemente, Toledo et al. (2013) propuseram um modelointeiro misto para este problema, no qual as peças são posicionadas em uma malha depontos. Este modelo obteve bons resultados provando a otimalidade para instânciascom até 21 peças. No entanto, o modelo possui um grande número de restrições denão-sobreposição, que cresce rapidamente de acordo com a discretização utilizada e aquantidade de peças distintas que devem ser alocadas. Neste trabalho, são propostas novasformulações matemáticas baseadas neste modelo, com o objetivo de reduzir o número derestrições. Na primeira abordagem, são propostos dois modelos reduzidos que mostraramser eficientes para instâncias com poucas repetições de peças. Na segunda abordagem,foi proposto um modelo de cobertura por cliques para o problema. Este modelo obtevedesempenho igual ou superior ao modelo da literatura para todas as instâncias avaliadas,obtendo uma solução ótima para instâncias com até 28 peças.