A BIASED RANDOM-KEY GENETIC ALGORITHM FOR THE 2D STRIP PACKING PROBLEM WITH ORDER AND STABILITY CONSTRAINTS

Autor(es)

Santosh Kumar Mandal ^[1] ; Thiago Alves de Queiroz ^[2] ; Flávio Keidi Miyazawa ^[3]

Afiliação do(s) autor(es)

^[1] University of Campinas. Institute of Computing - Brasil

^[2] Federal University of Catalão. Institute of Mathematics and Technology - Brasil

^[3] University of Campinas. Institute of Computing - Brasil

• Tipo de documento: Artigo Científico
• Fonte: Pesquisa Operacional; v. 44, 2024-10-28.

Resumo

ABSTRACT This paper deals with the two-dimensional strip packing problem (2D-SPP) with the order/or multi-drop and vertical stability constraints. The existing exact algorithm that solves this problem is not able to provide optimal solutions on large instances in a reasonable amount of time. Hence, with a view to quickly obtain a physically stable packing of minimum height while satisfying the order constraint, the Biased Random-Key Genetic Algorithm (BRKGA) is combined with Bottom-Left-Fill (BLF) and Open Space (OS) heuristics. Both versions of the algorithm (BRKGA+BLF and BRKGA+OS) retrieved optimal solutions on many benchmark instances, consuming lesser computational time than the exact algorithm. A comparative study was also performed between the BRKGA, Simulated Annealing (SA) and Particle Swarm Optimization (PSO) algorithms on newly generated large instances. Moreover, the effectiveness of the BRKGA has also been checked on the classical 2D-SPP and two-dimensional orthogonal packing problem (2D-OPP) datasets. (AU)

• Processo FAPESP: 22/05803-3 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento e localização e suas integrações em contextos industriais e logísticos
• Beneficiário: Reinaldo Morabito Neto
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 22/06707-8 - Algoritmos para problemas de empacotamento
• Beneficiário: Santosh Kumar Mandal
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
• Beneficiário: Flávio Keidi Miyazawa
• Modalidade de apoio: Auxílio à Pesquisa - Temático