In this paper we study a complex real-world workforce scheduling problem. We propose a method of splitting the problem into smaller parts and solving each part using exhaustive search. These smaller parts comprise a combination of choosing a method to select a task to be scheduled and a method to allocate resources, including time, to the selected task. We use reduced Variable Neighbourhood Search (rVNS) and hyperheuristic approaches to decide which sub problems to tackle. The resulting methods are compared to local search and Genetic Algorithm approaches. Parallelisation is used to perform nearly one CPU-year of experiments. The results show that the new methods can produce results fitter than the Genetic Algorithm in less time and that they are far superior to any of their component techniques. The method used to split up the problem is generalisable and could be applied to a wide range of optimisation problems.

Submitted by Eliane Vendramini De Oliveira (eliane@fai.com.br) on 2018-07-13T03:04:17Z No. of bitstreams: 1 Tese - versão pós defesa - 120718 (2).pdf: 24296114 bytes, checksum: b4e157585cf2618ae6be232afa8e33e6 (MD5) / Approved for entry into archive by Cristina Alexandra de Godoy null (cristina@adm.feis.unesp.br) on 2018-07-13T18:36:58Z (GMT) No. of bitstreams: 1 oliveira_ev_dr_ilha.pdf: 24296114 bytes, checksum: b4e157585cf2618ae6be232afa8e33e6 (MD5) / Made available in DSpace on 2018-07-13T18:36:59Z (GMT). No. of bitstreams: 1 oliveira_ev_dr_ilha.pdf: 24296114 bytes, checksum: b4e157585cf2618ae6be232afa8e33e6 (MD5) Previous issue date: 2018-05-25 / 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.

Orientador: Rubén Augusto Romero Lázaro / 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 mui... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: 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 p... (Complete abstract click electronic access below) / Doutor