Geração de Colunas e GRASP para o Problema de Corte Unidimensional

Favoritar este trabalho
Como citar esse trabalho?
Detalhes
  • Tipo de apresentação: Iniciação Científica-Poster
  • Eixo temático: 2.3 IFF - Engenharias
  • Palavras chaves: Padrões de Corte Unidimensional; geração de colunas; grasp;
  • 1 Instituto Federal Fluminense

Geração de Colunas e GRASP para o Problema de Corte Unidimensional

João Vitor Bernardo Moreira da Silva

Instituto Federal Fluminense

Resumo

O presente projeto de pesquisa aborda uma variante clássica dos Problemas de Corte e Empacotamento e de grande importância na área de Pesquisa Operacional, que é conhecida como Problema de Corte Unidimensional - PCU. Este problema é encontrado em diversos setores produtivos que consideram as ações de corte na transformação de materiais em produtos semiacabados ou finais, tais como: construção civil, metal mecânica, cartonagem, entre outros. Entre as abordagens desenvolvidas para resolver o problema em destaque, a clássica técnica Geração de Colunas [Gilmore e Gomory 1961] e a metaheurística Greedy Randomized Adaptive Search Procedure - GRASP [Vieira Neto, Velasco e Galdino 2013] são evidenciadas na literatura. Com o objetivo de encontrar boas soluções, ou até mesmo o ótimo, em tempos de execução condizentes com a realidade, são propostos os algoritmos G1D e GCG1D para resolução do PCU, fundamentados na utilização dos métodos supracitados. Basicamente, o algoritmo G1D se baseia nas fases de construção e de melhoria da GRASP, onde a cada solução construída escolhem-se alguns padrões de corte por critérios que ponderam perdas, número de repetições e quantidade de itens para compor uma instância menor que deve ser tratada na fase de melhoria. Já o algoritmo GCG1D constitui-se um híbrido com a aplicação conjugada entre a Geração de Colunas e a GRASP. Este algoritmo inicia com a Geração de Colunas, em que o subproblema é relaxado de forma a permitir padrões de corte unidimensionais, possivelmente, possuindo mais cópias de certo item do que realmente é demandado. Ao final desta fase, caso a solução da Geração de Colunas não seja inteira, esta solução é arredondada para baixo, atendendo a uma parte da demanda, e determina-se um problema residual a ser tratado. Na fase seguinte, a demanda residual deve ser atendida com a execução do G1D para compor a solução inteira do PCU. Os testes computacionais em instâncias da literatura e, também, em instâncias práticas retiradas de fábricas e obras da construção civil na cidade de Campos dos Goytacazes são utilizados na validação dos algoritmos e indicam um desempenho significativo.

Compartilhe suas ideias ou dúvidas com os autores!

Sabia que o maior estímulo no desenvolvimento científico e cultural é a curiosidade? Deixe seus questionamentos ou sugestões para o autor!

Faça login para interagir

Tem uma dúvida ou sugestão? Compartilhe seu feedback com os autores!