Dissertação apresentada para obtenção do grau de Mestre em Engenharia Electrotécnica e de Computadores (Ramo de Informática Industrial), na Faculdade de Engenharia da Universidade do Porto, sob a orientação do professor Doutor Eugénio da Costa Oliveira e co-orientação do Mestre Luís Paulo Reis

Submitted by Aelson Maciera (aelsoncm@terra.com.br) on 2017-06-08T18:50:10Z No. of bitstreams: 1 DissGDAA.pdf: 2724824 bytes, checksum: 6fd66731c51c75a18c506fe7ab991ec4 (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2017-06-13T19:33:47Z (GMT) No. of bitstreams: 1 DissGDAA.pdf: 2724824 bytes, checksum: 6fd66731c51c75a18c506fe7ab991ec4 (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2017-06-13T19:33:53Z (GMT) No. of bitstreams: 1 DissGDAA.pdf: 2724824 bytes, checksum: 6fd66731c51c75a18c506fe7ab991ec4 (MD5) / Made available in DSpace on 2017-06-13T19:37:52Z (GMT). No. of bitstreams: 1 DissGDAA.pdf: 2724824 bytes, checksum: 6fd66731c51c75a18c506fe7ab991ec4 (MD5) Previous issue date: 2016-08-19 / Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) / The companies today are looking for ways to expand their competitive advantages, optimizing their production, and in this context, they found solutions in activities of production scheduling. The production scheduling of the type job-shop, results in one of the most complex problems of combination, the Job-shop Scheduling Problem (JSP), which deterministic resolution is not feasible in polynomial computational time. The Flexible Job-shop Scheduling Problem (FJSP) is a classic extension of the JSP and has been widely reported in the literature. Thus, optimization algorithms have been developed and evaluated in the last decades, in order to provide more efficient production planning, with emphasis to artificial intelligence algorithms of the swarm type, that the latest research presented favorable results. The FJSP allows an operation to be processed for any machine arising from a set of machines along different routes. This problem is commonly dismembered into two sub-problems, the assignment of machines for operations, which is called routing, and operation scheduling. In the FJSP context, this research presents the resolution of the FJSP multi-objective, using a hierarchical approach that divides the problem into two subproblems, being the Particle Swarm Optimization (PSO), responsible for resolving the routing sub-problem, and tasking three local search algorithms, Random Restart Hill Climbing (RRHC), Simulated Annealing (SA) and Tabu Search (TS), for the resolution of scheduling sub-problem. The implementation of the proposed algorithm has new strategies in the population initialization, displacement of particles, stochastic allocation of operations, and management of scenarios partially flexible. Experimental results using technical benchmarks problems are conducted, and proved the effectiveness of the hybridization, and the advantage of RRHC algorithm compared to others in the resolution of the scheduling subproblem. / As empresas atualmente buscam meios de ampliarem suas vantagens competitivas, otimizando sua produção, e neste contexto, encontraram soluções nas atividades de programação da produção. A programação da produção do tipo job-shop, resulta em um dos problemas mais complexos de combinação, o Job-shop Scheduling Problem (JSP), cuja resolução determinística é inviável em tempo computacional polinomial. O Flexible Job-shop Scheduling Problem (FJSP) é uma extensão do clássico JSP e tem sido amplamente relatado na literatura. Desta forma, algoritmos de otimização têm sido desenvolvidos e avaliados nas últimas décadas, com o intuito de fornecer planejamentos de produção mais eficientes, com destaque para os algoritmos de inteligência artificial do tipo enxame, que nas pesquisas mais recentes obtiveram resultados satisfatórios. O FJSP permite que uma operação seja processada por qualquer recurso produtivo advindo de um conjunto de recursos ao longo de diferentes roteiros. Este problema é comumente desmembrado em dois subproblemas, a atribuição de recursos para as operações, que é chamado de roteamento, e programação das operações. No contexto do FJSP, a proposta dessa pesquisa apresenta a resolução do FJSP em caráter multiobjetivo, utilizando a abordagem hierárquica, que divide o problema em dois subproblemas, sendo o Enxame de Partículas (PSO), responsável pela resolução do subproblema de roteamento e incumbindo três algoritmos de busca local, Reinício Aleatório de Subida de Colina (RRHC), Arrefecimento Simulado (SA) e Busca Tabu (TS), para a resolução do subproblema de programação. A implementação do algoritmo proposto, dispõe de novas estratégias na inicialização da população, deslocamento das partículas, alocação estocástica das operações e tratamento de cenários parcialmente flexíveis. Resultados experimentais obtidos em base de testes comumente usada, comprovam a eficácia da hibridização proposta, e a vantagem do algoritmo RRHC em relação aos outros na resolução do subproblema de programação.