Heurísticas baseadas em geração sequencial de padrões para o problema de corte de estoque unidimensional com número reduzido de padrões / Heuristics based on sequential pattern generation for the one-dimensional cutting stock problem with a reduced number of patterns

AUTOR(ES)
DATA DE PUBLICAÇÃO

2009

RESUMO

Neste trabalho, foca-se o problema de corte de estoque unidimensional em que são considerados dois objetivos: a minimização do desperdício e a redução do número de padrões na solução. Quatro novas heurísticas para resolver este problema são propostas. As três primeiras heurísticas possuem três fases: na primeira fase um conjunto inicial de padrões é gerado, na segunda fase um problema residual é resolvido, e, na terceira fase uma técnica de redução de padrões é aplicada à solução do problema. A metodologia aplicada nas fases 2 e 3 é a mesma para estas 3 heurísticas consideradas, que diferem apenas na fase 1 quanto à metodologia adotada na obtenção dos padrões. A quarta heurística tem apenas duas fases. Na primeira fase utiliza-se uma variante de uma heurística recentemente proposta na literatura em que várias soluções são geradas e a melhor é mantida. A segunda fase desta heurística 4 é idêntica à fase 3 das 3 heurísticas anteriores. Na heurística 1 os padrões são gerados levando-se em consideração a demanda média dos itens remanescentes, valorizando os itens maiores. Na heurística 2, os padrões são gerados a partir de uma divisão dos itens em dois grupos disjuntos de acordo com suas demandas. A heurística 3 é urna variante da heurística 2, em que modificamos a maneira de dividir os itens em grupos, que não necessariamente são disjuntos e a quantidade destes grupos é definida de acordo com a demanda residual dos itens a cada iteração. Na heurística 4 são gerados padrões que podem ser cortados com diferentes frequências pré-estabelecidas de acordo com as demandas dos itens existentes no problema. Propomos também uma variação do procedimento de redução de padrões da literatura conhecido como KOMBI, a fim de melhorar seu desempenho, possibilitando um maior número e combinação de padrões, contribuindo assim, para reduzir mais o número de padrões na solução do problema, o qual denominamos de KOMBI MODIFICADO ou KOMBI-M. São realizados testes computacionais com instâncias da literatura e observa-se que as heurísticas propostas apresentam um bom desempenho em termos de qualidade de solução quando comparadas com outras soluções geradas por métodos recentes da literatura, com média de tempo computacional aceitável.

ASSUNTO(S)

redução de padrões padrões de corte heurística programação linear problema de corte patterns reduction cutting patterns heuristic linear programming cutting problem

ACESSO AO ARTIGO

Documentos Relacionados