Um algoritmo exato para o problema de empacotamento bidimensional em faixas

Autor(es)

Carlos Eduardo de Andrade

• Tipo de documento: Dissertação de Mestrado
• Imprenta: Campinas, SP.
• Instituição: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Data de defesa: 2006-09-26

Membros da banca

Flávio Keidi Miyazawa; Carlos Eduardo Ferreira; Cid Carvalho de Souza

• Orientador: Flávio Keidi Miyazawa

Resumo

Problemas de corte e empacotamento aparecem freqüentemente na indústria e comércio, e sua solução de forma otimizada pode trazer grandes ganhos em diversos setores.Um problema muito comum, notadamente no setor têxtil e do papel, é o corte de um rolo ou faixa de um determinado material para obtenção de itens menores, onde temos por objetivo utilizar a menor extensão do rolo/faixa possível. Este problema, conhecido como Problema de Empacotamento Bidimensional em Faixas (PEBF), é tido como um problema de otimização combinatória de difícil resolução. Neste trabalho, apresentamos um algoritmo exato para o PEBF restrito a cortes de dois estágios (PEBF2). O algoritmo usa a técnica de branch-and-price, que utiliza, por sua vez, heurísticas baseadas em algoritmos aproximados para a obtenção de limitantes superiores. O algoritmo se mostrou eficaz na obtenção de soluções para instâncias de pequeno e médio porte (AU)

• Processo FAPESP: 04/12711-0 - Problemas de corte e empacotamento bidimensional em placas
• Beneficiário: Carlos Eduardo de Andrade
• Modalidade de apoio: Bolsas no Brasil - Mestrado