Algoritmos Heurísticos para o Problema de Nesting com Rotações Livres.
Nesting, Rotação Livre, Heurísticas, Algoritmo Genético.
O problema de corte e empacotamento de peças irregulares, ou problema de Nesting, visa encontrar a melhor posição de peças dentro de uma faixa, tentando minimizar a altura utilizada (e, consequentemente, o espaço utilizado pelas peças). É grande a relevância este problema, visto que o corte e o empacotamento de peças ocorrem no contexto de indústrias de móveis, têxteis e de calçados, entre outras. O problema abordado consiste em um âmbito bidimensional com peças convexas e não convexas, com rotação livre. Nosso objetivo é conseguir responder à seguinte pergunta de pesquisa: “Existe alguma forma de melhorar a eficiência da resolução do problema de Nesting bidimensional com rotações livres, seja por resolução de um modelo ou por heurísticas?". Buscando responder a esta pergunta, foram implementadas inicialmente cinco regras de posicionamento, cinco regras de ordenação e duas regras de rotação. Foram propostas vinte e cinco heurísticas construtivas usando, cada uma, combinações de uma regra de posicionamento, uma de ordenação e ambas de rotação. Os resultados computacionais feitos com doze instâncias da literatura indicaram que, dentre estas, as que usam duas regras de posicionamento (chamadas α e β) se destacaram. Em particular, uma delas obteve resultados melhores (apesar de similares às demais). Também foi implementada uma heurística chamada de Heurística de Múltiplos Posicionamentos e um Algoritmo Genético, que utilizam a combinação dessas duas regras de posicionamento que se destacaram. Após uma comparação dentre os métodos propostos, foi possível perceber que a Heurística de Múltiplos Posicionamentos obteve resultados melhores em oito das doze instâncias testadas. Depois de definido qual nosso melhor método, comparamos o mesmo com os resultados presentes na literatura. Os resultados da abordagem foram promissores, superando em três das oito instâncias comparadas com os resultados da literatura.