ALGORITMO GENÉTICO DE CHAVES ALEATÓRIAS VICIADAS ESPECIALIZADO PARA O PROBLEMA DE CORTE BIDIMENSIONAL NÃO GUILHOTINADO

Autores

  • Eliane Vendramini de Oliveira

Palavras-chave:

Problema de Corte Bidimensional, Meta-Heurística, Algoritmo Genético

Resumo

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

Não há dados estatísticos.

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

Downloads

Publicado

2023-01-05

Como Citar

Oliveira, E. V. de. (2023). ALGORITMO GENÉTICO DE CHAVES ALEATÓRIAS VICIADAS ESPECIALIZADO PARA O PROBLEMA DE CORTE BIDIMENSIONAL NÃO GUILHOTINADO. Colloquium Exactarum. ISSN: 2178-8332, 14(1), 136–145. Recuperado de https://journal.unoeste.br/index.php/ce/article/view/4517