Submitted by Ronildo Prado (ronisp@ufscar.br) on 2017-08-23T12:44:58Z No. of bitstreams: 1 DissRFVS.pdf: 2728458 bytes, checksum: 4d07aa40b8f58f835e1e857098ff74a8 (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2017-08-23T12:45:05Z (GMT) No. of bitstreams: 1 DissRFVS.pdf: 2728458 bytes, checksum: 4d07aa40b8f58f835e1e857098ff74a8 (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2017-08-23T12:45:10Z (GMT) No. of bitstreams: 1 DissRFVS.pdf: 2728458 bytes, checksum: 4d07aa40b8f58f835e1e857098ff74a8 (MD5) / Made available in DSpace on 2017-08-23T12:45:16Z (GMT). No. of bitstreams: 1 DissRFVS.pdf: 2728458 bytes, checksum: 4d07aa40b8f58f835e1e857098ff74a8 (MD5) Previous issue date: 2017-02-14 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / The production scheduling activity is considered as one of the most complex activities in production management. This activity is part of the class of NP-Hard problems found in the area of computer science, that is, those problems that can not be solved deterministically in polynomial time. In addition, the complexity of this activity may increase according to the constraints imposed on each programming system/problem. In this research, the problem of programming of production the Flexible Job Shop (JSF) is studied. This problem is considered an extension of the Job Shop programming problem. In JSF, a group of jobs (i.e., products, items, part of an item) formed by a set of operations and each operation must be programmed by a resource (i.e., machine) that belongs to a group of resources that have the same functional characteristics (e.g., cut, sanding, painting). This problem is characterized in two sub-problems being routing and sequencing activity. Routing involves determining which resource will process a given operation. Sequencing is the order in which each operation will be processed on a resource. Through established programming, the objective of this research is to optimize performance multicriteria: the makespan (i.e., time spent to produce a set of jobs), processing time spent on the resource that worked by more time and total production time. In order to reach the objectives mentioned above, a hybrid swarm approach is proposed in this research. In this approach, two auxiliary methods are used to treat the abovementioned sub-problems: genetic operator of mutation to perform the routing activity and for the sequencing activity, an adaptive method of neighborhood structures is proposed. In order to deal with the multiobjectivity of the problem, we propose the Pareto dominance method. Experimental results obtained through commonly used benchmarks prove the efficacy and superiority of the proposed approach when compared to other approaches also applied to the problem studied. / A atividade de programação da produção é considerada como uma das atividades mais complexas no gerenciamento da produção. Essa atividade faz parte da classe de problemas NP-Difícil encontrados na área da ciência da computação, ou seja, aqueles problemas que não podem ser solucionados deterministicamente em tempo polinomial. Além disso, a complexidade dessa atividade pode aumentar de acordo com as restrições impostas a cada sistema/problema de programação. Nesta pesquisa, estuda-se o problema de programação da produção Job Shop Flexível (JSF). Esse problema é considerado como uma extensão do problema de programação Job Shop. No JSF, deve-se programar um grupo de jobs (i.e., produtos, itens, parte de um item) formados por um conjunto de operações e cada operação é processada por um recurso (i.e., máquina) que pertence a um grupo de recursos que possuam mesmas caraterísticas funcionais (e.g., cortar, lixar, pintar). Esse problema é caracterizado em dois sub-problemas, sendo eles, a atividade de roteamento e de sequenciamento. O roteamento implica em definir qual recurso irá processar uma determinada operação. O sequenciamento é a ordem em que cada operação será processada em um recurso. Por meio da programação estabelecida objetiva-se nessa pesquisa, otimizar multicritérios de desempenho, sendo eles: makespan (i.e., tempo gasto para produzir um conjunto de jobs), tempo de processamento gasto no recurso que trabalhou por mais tempo e tempo total de produção. Para alcançar os objetivos supracitados é proposto nessa pesquisa uma abordagem híbrida de enxame de abelhas. Nessa abordagem, utiliza-se dois métodos auxiliares para tratar os sub-problemas supracitados, sendo eles: operador genético de mutação para realizar a atividade de roteamento e para a atividade de sequenciamento é proposto um método adaptativo de estruturas de vizinhança. Para tratar a multiobjetividade do problema, propõe-se o método dominância de Pareto. Resultados experimentais obtidos por meio de benchmarks comumente usados comprovam a eficácia e a superioridade da abordagem proposta quando comparada com outras abordagens também aplicadas ao problema estudado.

This diploma thesis deals with the path planning by swarm intelligence. In the theoretical part it describes the best known methods of swarm intelligence (Ant Colony Optimization, Bee Swarm Optimization, Firefly Swarm Optimization and Particle Swarm Optimization) and their application for path planning. In the practical part particle swarm optimization is selected for the design and implementation of path planning in the C#.