Um estudo sobre heurísticas residuais para o problema de corte de estoque bidimensional
Carregando...
Arquivos
Data
2019-02-26
Autores
Chaves, Cheienne
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Estadual Paulista (Unesp)
Resumo
Neste trabalho apresentamos o problema de corte de estoque (PCE) e algumas de suas características e propriedades. Abordamos com mais detalhes o problema de corte de estoque bidimensional, guilhotinado, 2-estágios, exato e não-exato. Exibimos o modelo matemático do PCE e o método de geração de colunas proposto por Gilmore e Gomory na década de $60$. Apresentamos duas heurísticas residuais da literatura e sugerimos mudanças no método da ordenação dos padrões de corte de uma delas. Implementamos todo o algoritmo das heurísticas residuais utilizadas, realizamos testes computacionais usando três conjuntos de instâncias da literatura. As instâncias do Conjunto 1 foram geradas aleatoriamente e as dos Conjuntos 2 e 3 foram baseados em dados reais de uma fábrica de móveis. Os resultados obtidos com as heurísticas residuais foram comparadas com resultados disponíveis na literatura e resultados do Sistema CorteBiFur e do método branch-and-cut disponível no Cplex. Os resultados do estudo computacional indicam que a heurística residual estudada se mostra uma boa alternativa para ser implementada no sistema CorteBiFur.
In this research we presented the cutting stock problem (CSP), and some of its features and properties. The focus is the two-dimensional cutting stock problem, considering guillotine cuts and, two-staged cutting patterns and the exact and non-exact cases. We exhibit a mathematical model for the CSP and a method for its solution proposed by Gilmore and Gomory in the 1960’s. We present two residual heuristics from the literature and we suggest some changes on the criterion of sorting the cutting patterns in one of them. We implemented all the heuristics used in this research. We performed computacional tests with three sets of instances available in the literature. The instances of the Set 1 were randomly generated and the instances of the Sets 2 e 3 were based on real data from a furniture industry. The results obtained with the residuals heuristics were compared with results avaiable in the literature, with results from the Software CorteBiFur and the branch-and-cut method available on Cplex. The results indicated that the residual heuristic we studied its a good choice to be implemented on the CorteBiFur.
In this research we presented the cutting stock problem (CSP), and some of its features and properties. The focus is the two-dimensional cutting stock problem, considering guillotine cuts and, two-staged cutting patterns and the exact and non-exact cases. We exhibit a mathematical model for the CSP and a method for its solution proposed by Gilmore and Gomory in the 1960’s. We present two residual heuristics from the literature and we suggest some changes on the criterion of sorting the cutting patterns in one of them. We implemented all the heuristics used in this research. We performed computacional tests with three sets of instances available in the literature. The instances of the Set 1 were randomly generated and the instances of the Sets 2 e 3 were based on real data from a furniture industry. The results obtained with the residuals heuristics were compared with results avaiable in the literature, with results from the Software CorteBiFur and the branch-and-cut method available on Cplex. The results indicated that the residual heuristic we studied its a good choice to be implemented on the CorteBiFur.
Descrição
Palavras-chave
Problema de corte de estoque bidimensional., Padrão de corte 2- estágios, Heurística Residual, Problema exato, Problema não exato, Two-dimensional cutting stock problem, Residual heuristic, Two-staged pattern, Exact problem, Non-exact problem