Otimização do problema de corte bidimensional não guilhotinado usando meta-heurísticas especializadas

• Ano de defesa: 2018
• Autor(a) principal: Oliveira, Eliane Vendramini de
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Estadual Paulista (Unesp)
• Palavras-chave em Português: Problema de corte bidimensional não guilhotinado; Meta-heurísticas; Algoritmo genético; RVNS; Two-dimensional non-guillotine cutting problem; Metaheuristics; Genetic algorithm
• Link de acesso: http://hdl.handle.net/11449/154510

O Problema de Corte Bidimensional não guilhotinado tem sua aplicação prática quando comparado a problemas de indústrias que trabalham com aço, madeira, vidro, entre outros materiais, os quais necessitam de um padrão de corte que lhes proporcione maior lucro entre as peças cortadas, usando-se como técnica de corte o laser, e não a guilhotina, por isso existem diversas propostas para a resolução desse problema. Em particular, as propostas de solução utilizando-se meta-heurísticas foram o foco desta pesquisa. Vários trabalhos relevantes nessa área foram analisados, servindo de base para que esta tese trouxesse contribuições para a resolução do problema. A pesquisa sobre o problema permitiu que se apresentasse uma nova forma de representação da proposta de solução para o problema de corte bidimensional não guilhotinado. Outro resultado importante que se apresenta neste trabalho foi o desenvolvimento de duas meta-heurísticas especializadas na resolução do problema de corte bidimensional não guilhotinado. A primeira delas é o algoritmo genético de chaves aleatórias viciadas, e a segunda meta-heurística implementada foi RVNS. Foram realizados vários testes, utilizando-se instâncias conhecidas na literatura especializada, e os resultados encontrados pelas metaheurísticas algoritmo genético e RVNS propostas pela autora foram de boa qualidade, principalmente se comparados com os resultados já conhecidos na literatura. Os resultados obtidos com o algoritmo genético especializado, em muitos casos, foram iguais aos encontrados na literatura, e em dois casos de testes apresentaram-se superiores, contribuindo novamente para a área especializada no problema. Outro comparativo de resultados realizados pela autora está relacionado aos resultados obtidos pelas meta-heurísticas especialistas, propostas nesta tese, aos resultados encontrados utilizando-se o software AMPL para modelagem matemática em conjunto com o solver CPLEX. Nesse caso, novamente as meta-heurísticas algoritmo genético e RVNS apresentaram resultados iguais ou muito próximos do ótimo encontrado pelo modelo matemático. Os algoritmos desenvolvidos pela autora, além de resolverem o problema de corte bidimensional não guilhotinado, apresentaram bons resultados, visto que promoveram melhorias em relação ao que já existe na literatura. Os algoritmos foram escritos na linguagem de programação Fortran. Foram utilizados casos de teste de pequeno, médio e grande número de peças. Concluiu-se que o problema de corte bidimensional não guilhotinado é complexo e apresenta diversas variantes, sendo que as meta-heurísticas implementadas, neste trabalho, atendem a essa demanda com eficiência. Evidências empíricas mostram que esses algoritmos podem ser apropriados para solucionar instâncias associadas a situações reais.