ALGORITMO GENÉTICO DE CHAVES ALEATÓRIAS VICIADAS ESPECIALIZADO PARA O PROBLEMA DE CORTE BIDIMENSIONAL NÃO GUILHOTINADO
Palavras-chave:
Problema de Corte Bidimensional, Meta-Heurística, Algoritmo GenéticoResumo
O Problema de Corte Bidimensional tem relação direta com problemas de indústrias que trabalham com aço, madeira, vidro, entre outros que necessitam encontrar um padrão de corte que lhes proporcione maior lucro entre as peças cortadas. Existem diversas propostas para a resolução desse problema. Em particular, as propostas de solução utilizando meta-heurísticas foram o foco desta pesquisa. Assim neste artigo é apresentado um algoritmo genético especializado de chaves aleatórias viciadas. Foram realizados vários testes utilizando instâncias conhecidas na literatura específica, e os resultados encontrados pela meta-heurística proposta foram em muitos casos, iguais ou superiores, aos resultados já publicados na literatura. Outro comparativo de resultados apresentado neste artigo está relacionado aos resultados obtidos pela meta-heurística especialista e resultados encontrados por modelagem matemática utilizando software comercial. Nesse caso, novamente o algoritmo genético apresentou resultados iguais ou muito próximos do ótimo encontrado pelo modelo matemático. Adicionalmente, a proposta de otimização foi ampliada para corte bidimensional não guilhotinado sem orientação das peças.
Downloads
Referências
ALVAREZ-VALDES, R.; PARREÑO, F.; TAMARIT, J. M. A GRASP algorithm for constrained two-dimensional non-guillotine cutting problems. Journal of the Operational Research Society, n. 56, p. 414–425, 2005. https://doi.org/10.1057/palgrave.jors.2601829
ALVAREZ-VALDES, R.; PARREÑO, F.; TAMARIT, J. M. A tabu search algorithm for a two-dimensional non-guillotine cutting problems. European Journal of Operational Research, n.183, p. 1167–1182, 2007. https://doi.org/10.1016/j.ejor.2005.11.068
BEAN, J.C. Genetic algorithms and random keys for sequencing and optimzation. ORSA Journal on Computing, vol. 6, p. 154-160, 1994. https://doi.org/10.1287/ijoc.6.2.154
BEASLEY, J. E. An exact two-dimensional non-guillotine cutting tree search procedure. Operations Research, n. 33, p. 49-64, 1985. https://doi.org/10.1287/opre.33.1.49
CHRISTOFIDES, N. E WHITLOCK, C. An algorithm for two-dimensional cutting problems. Operations Research, n. 25, vol. 1, p. 30–44, 1977. https://doi.org/10.1287/opre.25.1.30
FEKETE, S. P.; SCHEPERS, J. On more-dimensional packing iii: Exact algorithms. Technical Report 97-290, Technical University of Berlin. 1997.
LAI, K. K.; CHAN, J. W. M. Developing a Simulated Annealing Algorithm for the Cutting Stock Problem. Computers & Industrial Engineering, n. 32, p. 115-127, 1997. https://doi.org/10.1016/S0360-8352(96)00205-7
Gilmore, P. e Gomory, R. (1961). A linear programming approach to the cutting stock problem. Operational Research, v. 9, p. 849–859.
https://doi.org/10.1287/opre.9.6.849
GONÇALVES, J. F.; RESENDE, M. G. C. A Biased Random-Key Genetic Algorithm for a 2D and 3D Bin Packing Problem. International Journal of Production Economics, n. 145, p. 500-510, 2013. https://doi.org/10.1016/j.ijpe.2013.04.019
HADJICONSTANTINOU. E.; CHRISTOFIDES. N. An exact algorithm for general, orthogonal, two-dimensional knapsack problems. European Journal of Operational Research, n. 83, p. 39-56, 1995.https://doi.org/10.1016/0377-2217(93)E0278-6
OR-LIBRARY. Operations Research (OR) problems. 2017. Online. Disponível em: <http://people.brunel.ac.uk/~mastjjb/jeb/info.html>. Acesso em: 20 abr. 2017.
SPEARS, W.M.; DEJONG, K.A. On the virtues of parameterized uniform crossover. International conference on Genetic Algorithms, 4., 1991, Sa Diego. Proceedings. San Diego: University of California, San Diego, 1991. p. 230-236.
WANG, P. Y. Two algorithms for constrained two-dimensional cutting stock problems. Operations Research, n. 31, vol. 3, p. 573–586, 1983. https://doi.org/10.1287/opre.31.3.573