Submitted by Izabel Franco (izabel-franco@ufscar.br) on 2016-09-21T13:50:00Z No. of bitstreams: 1 TeseCCMT.pdf: 3540141 bytes, checksum: e392913d01ce26b3d8bd932aa7e84611 (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2016-09-27T19:31:27Z (GMT) No. of bitstreams: 1 TeseCCMT.pdf: 3540141 bytes, checksum: e392913d01ce26b3d8bd932aa7e84611 (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2016-09-27T19:31:38Z (GMT) No. of bitstreams: 1 TeseCCMT.pdf: 3540141 bytes, checksum: e392913d01ce26b3d8bd932aa7e84611 (MD5) / Made available in DSpace on 2016-09-27T19:42:35Z (GMT). No. of bitstreams: 1 TeseCCMT.pdf: 3540141 bytes, checksum: e392913d01ce26b3d8bd932aa7e84611 (MD5) Previous issue date: 2015-03-31 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / The generation of Reactive Production Scheduling (PRP) in order to minimize the makespan is an important activity in the manufacturing industry, in view of the numerous articles reflecting this search today. Among these studies highlight the global search use in hybridization or collaboration with local search, especially of Genetic Algorithm (GA) with Variable Neighborhood Search (VNS). But see that the neighborhood structures used are not related to the goal of makespan minimization or when they are, are difficult to obtain. In order to cover this topic, this thesis proposes the hypothesis that a strongly correlated neighborhood structure with objective of makespan minimization in PRP problems, based on spanning tree, and applied on a collaboration among a genetic algorithm with VNS, perform better or equal to those obtained by other studies using other neighborhood structures or without the use of local search. The purpose was to construct a collaboration of GA and VNS using a neighborhood structure based on the mapping of the solution in the spanning tree associated with the problem, in the local search time, and operating with the insert, swap and 2-opt operators. The planning of experiments for validation contemplated since the implementation and comparison of four variants of reactive production scheduling in three job shop scenarios of different sizes. Each pair of comparisons had its calculated sample size and has been tested with the appropriate hypothesis test. The four variants were compared: Genetic Algorithm only and three collaborations of GA with VNS using the neighborhood structure proposal and two other neighborhood structures (Critical Path and Natural Representation) found in the literature review. The scenarios came from Taillard base. The tests corroborate the hypothesis, with 95% confidence, compared to other works and the main contribution of this thesis is to create an efficient method for minimizing makespan in PRP. / A geração de Programação Reativa da Produção (PRP), com o objetivo de minimizar o makespan, é uma atividade importante na indústria manufatureira, tendo em vista os numerosos artigos que abordam esta pesquisa na atualidade. Dentre estas pesquisas, destaca-se o uso de hibridização ou colaboração de busca global com busca local, notadamente de Algoritmo Genético (AG) com Variable Neighborhood Search (VNS). Porém, nota-se que as estruturas de vizinhança utilizadas não são correlatas à função de minimização de makespan ou, quando o são, são de difícil obtenção. Com o intuito de cobrir tal tópico, esta tese propõe a hipótese de que uma estrutura de vizinhança fortemente correlata ao objetivo de minimização de makespan em problemas de PRP, baseando-se em árvore de cobertura e aplicada em uma colaboração de algoritmo genético e VNS, obtém resultados melhores aos obtidos por outros trabalhos, que fazem uso de outras estruturas de vizinhança ou que não utilizam a busca local. A proposta é a construção de um método de colaboração entre AG e VNS usando uma estrutura de vizinhança baseada no mapeamento da solução, em tempo de busca local, na árvore de cobertura associada ao problema, atuando com os operadores insert, swap e 2-opt. O planejamento dos experimentos para validação contempla a execução e comparação de quatro variantes de solução de problemas de Programação Reativa da Produção em três cenários de job shop de diversas dimensões. Cada par de comparações tem seu tamanho amostral calculado e é examinado com o teste de hipótese adequado. As quatro variantes comparadas são: Algoritmo Genético e três colaborações entre Algoritmo Genético e Variable Neighborhood Search (VNS) usando a estrutura de vizinhança proposta e outras duas estruturas de vizinhança (Caminho Crítico e Representação Natural) encontradas na revisão da literatura. Os cenários vem da base Taillard. Os testes corroboram a hipótese com 95% de confiança na comparação com outros trabalhos e a principal contribuição desta tese é a criação de um método eficiente para minimização de makespan em PRP.