Otimização do problema de corte bidimensional não guilhotinado usando meta-heurísticas especializadas
Carregando...
Data
2018-05-25
Autores
Oliveira, Eliane Vendramini de
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Estadual Paulista (Unesp)
Resumo
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.
The two-dimensional non-guillotine cutting problem has its practical application when compared to problems in industries that work with steel, wood, glass, among other materials, which require a cut pattern that provides more profit among the cut pieces, using laser as a cut technique, not the guillotine. Thus, there are several potential answers for this question. In particular, the potential solutions using metaheuristics were the focus of this research. Several relevant papers in this area were analyzed, forming a base so that this dissertation can bring solutions for the problem. The research about this issue allowed us to present a new form of representation of the proposal of solution for the two-dimensional non-guillotine problem. Another important result presented in this paper is the development of two metaheuristics specialized in the resolution of the two-dimensional non-guillotine problem. The first is the biased random-key genetic algorithm. The second metaheuristics was the RVNS. Several tests were performed, using methods well-known in the specialized literature, and the results found by the metaheuristics genetic algorithm and the RVNS suggested by the author were of good quality, mainly if compared to the results already known in the literature. The results obtained by the specialized genetic algorithm, in many cases, were equal to the ones found in the literature, and, in two tests, they were superior, once more contributing to the specialized field of the problem. Another comparison between the results performed by the author is related to the outcomes obtained by the specialized metaheuristics, suggested in this dissertation, and the ones found using the AMPL software to the mathematical modeling together with the CPLEX solver. In this case, once more, the genetic algorithm and RVNS metaheuristics presented resulted identical or very similar to the optimum one found by the mathematical model. The algorithms developed by the author not just solved the two-dimensional non-guillotine cutting problem, but present good results, given that they promoted improvements, comparing to what already exists in the literature. The algorithms were written in the Fortran programming language. Small, medium and big number of pieces’ case-tests were performed. The conclusion was that the two-dimensional non-guillotine cutting problem is complex and presents several variants. However, the metaheuristics implemented by this research efficiently meet this demand. Empirical evidences show that these algorithms can be used to solve issues associated with real situations.
The two-dimensional non-guillotine cutting problem has its practical application when compared to problems in industries that work with steel, wood, glass, among other materials, which require a cut pattern that provides more profit among the cut pieces, using laser as a cut technique, not the guillotine. Thus, there are several potential answers for this question. In particular, the potential solutions using metaheuristics were the focus of this research. Several relevant papers in this area were analyzed, forming a base so that this dissertation can bring solutions for the problem. The research about this issue allowed us to present a new form of representation of the proposal of solution for the two-dimensional non-guillotine problem. Another important result presented in this paper is the development of two metaheuristics specialized in the resolution of the two-dimensional non-guillotine problem. The first is the biased random-key genetic algorithm. The second metaheuristics was the RVNS. Several tests were performed, using methods well-known in the specialized literature, and the results found by the metaheuristics genetic algorithm and the RVNS suggested by the author were of good quality, mainly if compared to the results already known in the literature. The results obtained by the specialized genetic algorithm, in many cases, were equal to the ones found in the literature, and, in two tests, they were superior, once more contributing to the specialized field of the problem. Another comparison between the results performed by the author is related to the outcomes obtained by the specialized metaheuristics, suggested in this dissertation, and the ones found using the AMPL software to the mathematical modeling together with the CPLEX solver. In this case, once more, the genetic algorithm and RVNS metaheuristics presented resulted identical or very similar to the optimum one found by the mathematical model. The algorithms developed by the author not just solved the two-dimensional non-guillotine cutting problem, but present good results, given that they promoted improvements, comparing to what already exists in the literature. The algorithms were written in the Fortran programming language. Small, medium and big number of pieces’ case-tests were performed. The conclusion was that the two-dimensional non-guillotine cutting problem is complex and presents several variants. However, the metaheuristics implemented by this research efficiently meet this demand. Empirical evidences show that these algorithms can be used to solve issues associated with real situations.
Descrição
Palavras-chave
Problema de corte bidimensional não guilhotinado, Meta-heurísticas, Algoritmo genético, RVNS, Two-dimensional non-guillotine cutting problem, Metaheuristics, Genetic algorithm