Development and application of a metaheuristic algorithm for the 2D cutting-stock problem at a Brazilian small-sized furniture maker

Abstract

RESUMO: O problema de corte de estoque consiste em alocar itens menores em objetos maiores sem sobreposição, respeitando restrições específicas e buscando um objetivo definido, como a minimização do número de bins utilizados. Embora estudado desde a década de 1960 e com relevância econômica significativa em setores como o de chapas metálicas e o moveleiro, a literatura sobre o tema permanece fragmentada em dois aspectos: as limitações das revisões sistemáticas existentes e a raridade de aplicações reais, sobretudo em Pequenas e Médias Empresas (PMEs). Para endereçar essas lacunas, esta dissertação propõe dois artigos complementares. O primeiro conduz uma revisão sistemática da literatura sobre o problema de corte e empacotamento bidimensional, utilizando o método Methodi Ordinatio para seleção e classificação dos estudos mais relevantes, analisando 116 artigos dentre 447 classificados como elegíveis. Os principais achados incluem: a predominância de métodos exatos (45 artigos) frente a metaheurísticas (23 artigos); a escassez de aplicações industriais reais (apenas 14 dos 116 artigos); e a quase ausência de estudos aplicados a PMEs (apenas três artigos). A partir dos achados da revisão, o segundo artigo propõe um Algoritmo Genético para o problema de corte bidimensional com cortes guilhotinados de três estágios, número ilimitado de bins e sem rotação de itens, aplicado tanto a instâncias da literatura quanto a instâncias reais de uma PME brasileira do setor moveleiro. Comparado com a literatura, o algoritmo alcança um gap global de 1,89%, com desempenho variando entre 0% nas instancias da Classe 9 e 6,36% nas instancias da Classe 6. Para as instâncias reais, o algoritmo obtém resultados equivalentes ao planejamento manual em todos os casos testados, com redução média de 94.06% no tempo de solução. O método é disponibilizado por meio de uma interface web que dispensa instalação ou conhecimento em programação, bem como por meio dos arquivos-fonte executáveis em linha de comando, dispensando infraestrutura computacional avançada ou conhecimento especializado em algoritmos de otimização, tornando-o diretamente aplicável ao contexto de pequenas e médias empresas (PMEs). Em conjunto, os dois artigos demonstram que a sequência metodológica revisão sistemática-desenvolvimento-aplicação industrial constitui uma abordagem rigorosa e replicável para o avanço do campo dos problemas de corte e empacotamento.

ABSTRACT: The cutting stock problem consists of allocating smaller items into larger objects without overlap, while respecting specific constraints and pursuing a defined objective, such as minimizing the number of bins used. Although it has been studied since the 1960s and has significant economic relevance in sectors such as sheet metal and furniture, the literature on the topic remains fragmented in two aspects: the limitations of the existing systematic reviews and the rarity of real-world applications, especially in Small and Medium-sized Enterprises (SMEs). To address these gaps, this dissertation proposes two complementary articles. The first conducts a systematic literature review on the two-dimensional cutting and packing problem, using the Methodi Ordinatio method to select and rank the most relevant studies, analyzing 116 articles out of 447 classified as eligible. The main findings include: the predominance of exact methods (45 articles) over metaheuristics (23 articles); the lack of real industrial applications (only 14 out of the 116 articles); and the near absence of studies applied to SMEs (only three articles). Based on the review findings, the second article proposes a Genetic Algorithm for the two-dimensional cutting problem with three-stage guillotine cuts, an unlimited number of bins, and no item rotation, applied both to instances from the literature and to real instances from a Brazilian SME in the furniture sector. Compared with the literature, the algorithm achieves a global gap of 1.89%, with performance ranging from 0% in Class 9 instances to 6.36% in Class 6 instances. For the real instances, the algorithm obtains results equivalent to manual planning in all tested cases, with an average reduction of 94.06% in solution time. The method is made available through a web interface that requires no installation or programming knowledge, as well as through source files executable via command line, dispensing with advanced computational infrastructure or expertise in optimization algorithms, making it directly applicable to the context of SMEs. Taken together, the two articles demonstrate that the methodological sequence systematic review-development-industrial application constitutes a rigorous and replicable approach for advancing the field of cutting and packing problems.