High school timetabling problems consist in assigning meetings between classes and teachers, with the goal of minimizing the violation of specific soft requisites. This category of problems has been extensively studied since the 1950s, mostly via mixed-integer programming and metaheuristic techniques. However, the computation of optimal or near-optimal solutions using mixed-integer programs or metaheuristics is still a challenge for most practical problems. In this thesis, we investigate new mixed-integer programming formulations, column generation approaches and parallel metaheuristic based algorithms to compute lower bounds and solutions for high school timetabling problems. Extensive computational experiments conducted with real-world instances demonstrate that our best formulations are competitive with best-known formulations, while our parallel algorithms present superior performance than the state-of-the-art methods. / Problemas de horários escolares consistem em alocar encontros entre turmas e professores, com objetivo de minimizar violações a requisitos qualitativos específicos. Esta categoria de problemas tem sido largamente estudada desde 1950, particularmente via técnicas de programação linear inteira mista e metaheurísticas. Entretanto, a computação de soluções ótimas ou quase ótimas usando programas inteiro-mistos ou metaheurísticas ainda é um desafio na maioria dos problemas práticos. Nesta tese, nós investigamos novas formulações inteiro-mistas, decomposições por geração de colunas e algoritmos baseados em metaheurísticas paralelas para computar limitantes inferiores e soluções para problemas de horários escolares. Extensivos experimentos computacionais conduzidos com instâncias reais demonstram que nossas melhores formulações são competitivas com as melhores formulações existentes, enquanto nossos algoritmos paralelos são superiores em performance computacional quando comparados com métodos que são estado-da-arte.

O principal objetivo deste estudo é propor uma nova metodologia para lidar com o problema de Planejamento da Expansão de Redes de Transmissão de Energia Elétrica com Múltiplos Cenários de Geração (PERTEEG). Com a metodologia proposta neste trabalho almeja-se construir planos de expansão de redes de transmissão de energia elétrica que sejam capazes de, no menor custo de investimento possível, satisfazer às novas exigências dos sistemas elétricos modernos, tais como construção de redes de transmissão livres de congestionamento e robustas à incerteza em relação aos cenários de geração futuros. Através de estudos realizados na literatura do problema, verificou-se que novos modelos e metodologias de abordagem do PERTEEG se fazem necessários. Ao se modelar o PERTEEG visando construir redes de transmissão que contornem as incertezas em relação aos cenários de geração futuros e concomitantemente minimizar o custo de investimento para a expansão do sistema, o planejador se depara com um problema de otimização multiobjetivo. Existem na literatura da pesquisa operacional diversos algoritmos que visam lidar com problemas multiobjetivos. Nesta tese, foram aplicados dois desses algoritmos: Nondominated Sorting Genetic Algorithms-II (NSGA-II) e SPEA2: Strength Pareto Evolutionary Algorithm (SPEA2). Em primeira análise, se destacou uma das maiores dificuldade de lidar com o PERTEEG, a saber, o esforço computacional elevado. Por isso, vislumbrou-se que uma possível solução para contornar esta dificuldade esteja na computação paralela. Para se confirmar esta suspeita, nesta tese foram implementadas versões paralelas dos algoritmos sequenciais testados. A qualidade das soluções encontradas pelos algoritmos foram bastante superiores às soluções encontradas pelos algoritmos sequenciais. Neste trabalho também será mostrado que as soluções ótimas clássicas considerando somente o objetivo de m´mínimo custo são incapazes de atender às novas necessidades dos sistemas elétricos de potência. Testes computacionais foram realizados e analisados neste trabalho. Considerando as metodologias conhecidas na literatura para medição da qualidade das soluções encontradas por algoritmos multiobjetivo, se pode afirmar de que a proposta de abordagem do problema de PERTEEG pode ser viável tanto do ponto de vista de engenharia como do ponto de vista da computação matemática. / The main objective of this study is to propose a new methodology to deal with the long-term transmission system expansion planning with multiple generation dispatch scenarios problem (TEP-MDG). With the methodology proposed in this thesis we aim to build expansion plans with minimum investment cost and also capable of meeting the new demands of modern electrical systems, such as uncertainty about the future generation scenarios and congestion in the transmission systems. By modeling the TEP-MDG aiming to build transmission networks that circumvent the uncertainties regarding the future generation scenarios and simultaneously minimize the cost of investment for transmission networks expansion, the planner faces a multiobjective optimization problem. One can find various algorithms that aim to deal with multiobjective problems in the literature of operations research. In this thesis, we apply two of these algorithms: Nondominated Sorting Genetic Algorithms-II (NSGA-II) and SPEA2: Strength Pareto Evolutionary Algorithm (SPEA2). In a first analysis, we have found that the most critical issue with the TEP-MOG is the high computational demand. Therefore, in order to circumvent this difficulty we have implemented parallel versions of the sequential algorithms tested. In performed tests, the parallel algorithms have found solutions of superior quality than the solutions found by the sequential algorithms. In this thesis we also show that optimal solutions considering only the classical least cost objective are unable to meet the electric power systems new demands. Tests have been performed and analyzed in this work. By considering the methods known in the literature convinced to measure the quality of solutions found by multiobjective algorithms, we concluded that the proposed approach to TEP-MDG may be feasible from the point of view of both engineering and computational mathematics.

Submitted by camilla martins (camillasmmartins@gmail.com) on 2017-04-24T14:28:25Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_NovaSolucaoOtimizacao.pdf: 10585711 bytes, checksum: 308bde75f6d5505c2d6512b1449776ba (MD5) / Approved for entry into archive by Edisangela Bastos (edisangela@ufpa.br) on 2017-04-24T17:00:26Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_NovaSolucaoOtimizacao.pdf: 10585711 bytes, checksum: 308bde75f6d5505c2d6512b1449776ba (MD5) / Made available in DSpace on 2017-04-24T17:00:26Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_NovaSolucaoOtimizacao.pdf: 10585711 bytes, checksum: 308bde75f6d5505c2d6512b1449776ba (MD5) Previous issue date: 2016 / FAPEAM - Fundação de Amparo à Pesquisa do Estado do Amazonas / Devido ao crescimento industrial da Região Norte, principalmente do Polo Industrial de Manaus (PIM) e consequentemente o aumento da necessidade de geração de energia, que nesta região é fornecida em mais de 90% de seu total por Usinas Termoelétricas (UTE), tornou-se necessário a implementação de ferramentas computacionais que propiciem ao especialista, ou operador de sistemas elétricos, tomar decisões sobre o despacho de potência ótima de cada unidade geradora, contemplando não somente a redução de custos, mas também a diminuição dos índices de poluição na atmosfera. O Despacho Econômico (DE), ou despacho ótimo, é uma das tarefas mais antigas e importantes na gestão de usinas de energia elétrica, e atualmente, devido às crescentes preocupações com o meio ambiente, este problema vem sendo estendido para a otimização do Despacho Econômico e Ambiental (DEA). Esta tese tem como objetivo geral analisar uma nova proposta de solução para o antigo problema de otimização do DE e do DEA implementada por diversos métodos Determinísticos (Iteração Lambda, Programação Quadrática e Método de Newton) e métodos Heurísticos (Algoritmos Genéticos, Enxame de Partículas, Evolução Diferencial, Recozimento Simulado, Otimização por Lobo Cinzento e Colônia de Abelhas Artificiais) para o problema do DE e para o problema do DEA (Algoritmo Genético de Classificação Não-dominado, NSGA II e NSGA III), considerando o desligamento dos geradores com maior custo de operação, com a consequente redução no custo dos combustíveis. O método do custo incremental e as perdas de transmissão são utilizados para determinar os valores de potência ativa de cada unidade geradora, assegurando o balanço energético entre a potência total gerada, a demanda do sistema elétrico, as perdas, e minimizando, por outro lado, o custo total do combustível, reduzindo as emissões, e ainda melhorando a eficiência não somente dos geradores, mas também da UTE como um todo. A solução proposta nesta tese tem as seguintes contribuições: contempla o desligamento dos sistemas de geração que apresentam maior custo com combustível, reduz os custos totais permitindo uma manutenção preditiva nestas máquinas; determina soluções ótimas para a potência de saída em vários cenários característicos e não característicos das usinas, considerando variações na geração de potência ativa e na redução das emissões de gases poluentes como, NOx e o CO2. Para analisar a viabilidade da solução proposta por esta tese, utilizou-se um conjunto de dez unidades geradoras térmicas como parâmetros para o estudo de caso e três conjuntos de geradores, descritos na literatura, como sistema de teste para validação da robustez da proposta de solução apresentada. Foram aplicados diversos métodos determinísticos e de computação Bio-inspirada para a otimização mono-objetivo e multiobjetivo. Os resultados apresentados na tese, a partir da análise de vários exemplos práticos, mostram as vantagens da nova solução proposta. / Due to the significant industrial growth in the North of Brazil, especially at the Industrial Pole of Manaus (PIM), it has been an increased necessity for energy generation, which in this region is provided by thermoelectric plants (UTEs) in over 90% of its total. Thus, it became necessary the use of computational tools that help the specialists or operators of electrical systems, for making decisions about the optimal power dispatch of each generating unit that contemplate not only to reduce costs but also reduce the atmospheric pollution levels. Optimization of Economic Dispatch (ED) is one of the oldest and most important tasks in power plant management, and currently, due to growing concerns about the environment, this problem is extended to the optimization of the Economic and Environmental Dispatch (EAD). This thesis has as main objective to analyze a new proposal to solve the old optimization problem of ED and the EAD implemented by several Deterministic methods (Iteration Lambda, Quadratic Programming and Newton method) and Heuristic methods (Genetic Algorithms, Particle Swarm, Differential evolution, Simulated Annealing, Optimization by Grey Wolf and Artificial Bee Colonies) for the ED problem. Non-dominated Sorting Genetic Algorithms (NSGA II and NSGA III), were used for evaluating the problem of EAD, considering the shutdown of the generators with higher losses and thus reducing the fuel cost. The method of incremental cost and transmission losses are used to determine the best active power values for each generating unit. It was ensured the energy balance between the total generated power, the demand of the electrical system, losses and minimizing, on the other hand, the total cost of fuel, reducing emissions, and further improving efficiency not only for generators but also to UTE as a whole. Consequently, the proposed new solution has the following contributions: contemplates the turning off generation systems that have higher fuel cost, reducing the overall costs and enabling predictive maintenance on these machines. This approach also determines optimal solutions for the power output in various scenarios characteristic and not characteristic of UTEs or power plants, considering changes in active power generation and reducing greenhouse gas emissions as NOx and CO2. To explore the feasibility of the new solution proposed by this theory, it was used as a test system a set of ten (10) generating units for the case study and three sets of generators´ parameters described in the literature. They were used for demonstrating the robustness of the proposed solution considering the use of various deterministic and Bioinspired computing methods for mono-objective and multi-objective optimization. The results presented here, from an analysis of several practical examples show the advantages of the new proposed solution.

Submitted by camilla martins (camillasmmartins@gmail.com) on 2017-04-27T13:48:43Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_MetaheuristicasPopulacionaisEstudo.pdf: 1773087 bytes, checksum: f28cd56459c0645ef2523053a2599d4e (MD5) / Approved for entry into archive by Edisangela Bastos (edisangela@ufpa.br) on 2017-05-04T12:54:50Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_MetaheuristicasPopulacionaisEstudo.pdf: 1773087 bytes, checksum: f28cd56459c0645ef2523053a2599d4e (MD5) / Made available in DSpace on 2017-05-04T12:54:50Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_MetaheuristicasPopulacionaisEstudo.pdf: 1773087 bytes, checksum: f28cd56459c0645ef2523053a2599d4e (MD5) Previous issue date: 2016-12-02 / CNPq - Conselho Nacional de Desenvolvimento Científico e Tecnológico / As metaheurísticas populacionais são técnicas pertencentes ao campo da Inteligência Computacional baseadas em modelos naturais e surgiram como alternativas para resolver problemas de otimização, onde as técnicas tradicionais não podem ser aplicadas, ou ainda onde não se dispõe de um modelo de solução para o problema, fazendo com que a solução seja encontrada por intermédio de meios empíricos. Diante da capacidade de oferecer soluções aceitáveis, em um tempo hábil, para muitos dos problemas complexos encontrados, as metaheurísticas populacionais vêm sendo aplicadas com êxito diferentes problemas de sistemas de controle encontrados na literatura. Este trabalho apresenta, de um modo geral, como as metaheurísticas vêm sendo aplicadas na solução de problemas de controle e realiza um estudo comparativo de desempenho entre quatro algoritmos bioinspirados na sintonia dos parâmetros de um controlador Proporcional-Integral-Derivativo (PID). Foram utilizados os seguintes algoritmos: Algoritmo Genético (AG), Algoritmo genético no Modelo de Ilhas (AGMI), Bacterial Foraging Optimization (BFO) e o Particle Swarm Optimization (PSO). Os resultados demonstram que os algoritmos apresentam um ótimo desempenho para a sintonia do PID, produzindo resposta que atendem as exigências de projetos. Foram utilizados diferentes sistemas com características distintas para avaliar os algoritmos. Considerando os resultados obtidos, o PSO se mostrou como o melhor algoritmo entre os quatros usados, produzindo resposta em um tempo mais rápido e apresentando menor desvio padrão nos ensaios realizados. / Population metaheuristics are techniques belonging to the field of Computational Intelligence and are based on natural models, have emerged as alternatives to solve optimization problems where the traditional techniques cannot be applied, or even where a solution model for the problem is not available with which the solution is found through empirical means. Given these capabilities to provide acceptable solutions in a timely manner for most of the complex problems encountered, metaheuristics has been applied successfully in most of the control system problems found in the literature. This work presents in general how the metaheuristics are being applied in the solution of control problems and performs a comparative study of performance among four algorithms bioinspirados in the tuning of the PID parameters. The following algorithms were used: Genetic Algorithm (AG), Genetic Algorithm in the Islands Model (AGMI), Bacterial Foraging Optimization (BFO) and Particle Swarm Optimization (PSO). The results demonstrate that the algorithms present an excellent performance in the tuning of the PID producing response that met the project requirements. Different systems with different characteristics were used to evaluate the algorithms. The PSO was shown as the best algorithm among the four used, producing response in a faster time and presented lower deviated standard in the trials.

Submitted by Silvana Teresinha Dornelles Studzinski (sstudzinski) on 2017-02-08T15:41:51Z No. of bitstreams: 1 Wagner Lourenzi Simões_.pdf: 1389162 bytes, checksum: 302aec842d2f4e8b0a7c78ecbae24357 (MD5) / Made available in DSpace on 2017-02-08T15:41:51Z (GMT). No. of bitstreams: 1 Wagner Lourenzi Simões_.pdf: 1389162 bytes, checksum: 302aec842d2f4e8b0a7c78ecbae24357 (MD5) Previous issue date: 2016-12-06 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Neste estudo, foi desenvolvida uma ferramenta computacional baseada em metaheurísticas para a otimização do sequenciamento de produção em Flow Shop permutacionais aplicados à montagem de placas eletrônicas que operam em ambientes High-Mix, Low-Volume. O ambiente High-Mix, Low-Volume exige a realização de um grande número de setups para atender à flexibilidade exigida. Esse elevado número de sucessivos setups para a produção de pequenos lotes impacta negativamente nos custos operacionais da empresa. Uma das formas de se obter vantagem ao lidar com um grande mix de produção é explorando características similares entre os produtos, de forma que, através de um sequenciamento adequado, seja possível reduzir o tempo total de parada para setup e, por consequência, reduzir também o tempo total de processamento (makespan). A literatura apresenta muitos exemplos de sucesso na aplicação de técnicas de otimização para o sequenciamento da produção como forma de ganho de vantagem competitiva. Porém, a complexidade e o grande esforço computacional exigidos na solução deste problema, por muitas vezes, inviabilizam sua aplicação na rotina das indústrias. Neste contexto, as metaheurísticas emergem como uma opção para a viabilização de ferramentas para otimização do sequenciamento de produção. Dentre as abordagens metaheurísticas existentes, destacam-se as abordagens híbridas que combinam estratégias de busca local com algoritmos evolutivos como opções para a geração, de forma rápida, de boas soluções para o problema de sequenciamento, ainda que estes métodos não possam garantir a otimalidade da solução. A ferramenta desenvolvida, baseada no uso combinado das metaheurísticas Busca Tabu e Algoritmo Genético, busca a melhor sequência possível dentro do tempo computacional disponível de forma a reduzir os tempos gastos com operações de tempo de setup, e consequentemente o makespan. O Algoritmo Hibrido foi avaliado utilizando instâncias da literatura e instâncias advindas de um caso real. Os resultados dos testes indicam a superioridade da abordagem híbrida sobre as abordagens canônicas do algoritmo Genético e Busca Tabu. Os resultados obtidos na avaliação de instâncias reais indicam a aplicabilidade da ferramenta em ambientes reais, obtendo bons resultados na otimização dos tempos de setup, mesmo para o sequenciamento de grandes quantidades de produtos diferentes. / This work proposes the development of a metaheuristics based computation tool, to solve the permutation flow shop scheduling problem (PFSSP) in the electronic manufacturing operating in High-mix, Low-volume enviroment. To operate in HMLV enviroment is demanded a large number of setup changes to comply the flexibility required. This elevated number of successive setup changes to produce little batches have negative impacts on the operation costs. One way for to obtain advantages handling a large product mix is to explore the similar features between this products. Through a proper scheduling we can reduce the total downtime to setup changes, and consequently reduces the process time (makespan). The literature brings many success examples in the production scheduling optimization as a way to obtain competitive advantages. But, the complexity and the computational effort demanded to solve this problems, sometimes, turns the practical application unfeasible in the factories routine. In this contexto emerges the metaheuristics as an option to viability this type of application. Among the mataheuristics approaches, outstands the hybrid approaches that combine local search strategies with evolutionary algorithms as a way to obtain good and fast solutions for the scheduling problems, although the optimality is not been guaranted. The tool proposed combine the metaheuristics Genetic Algorithm and Tabu Search to optimize the flow shop scheduling in the shortest possible time to allow the practical application in industry. The tool was evaluate based on quality metrics like makespan and mean setup time. The Hybrid Algorithm has been evaluated using instances of the literature and instances arising from a real case. The results of the tests indicate a superiority of the hybrid approach over canonical approaches of the Genetic algorithm and Tabu Search. The results obtained in the evaluation of real instances indicate an applicability of the tool in real environments, obtaining good results in the optimization of textit setup times, also for the sequencing of large products. The Hybrid Algorithm has been evaluated using instances of the literature and instances arising from a real case. The tests results indicate a superiority of the hybrid approach over canonical approaches of the Genetic algorithm and Tabu Search. The results obtained in the evaluation of real instances indicate an applicability of the tool in real environments, obtaining good results in the setup time optimization, also for the sequencing of large products.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / The generalized minimum spanning tree problem is present in several situations of the real world, such as in the context of the telecommunications, transports and grouping of data, where a net of necessary clusters to be connected using a node of each cluster. In that work it is presented the project and the implementation of an algorithm of tabu search with path relinking and iterated local search for the generalized minimum spanning tree problem and your variant with at least one vertex by group. In the computational tests 271 instances of TSPLIB were used generated through the grouping methods Center Clustering and Grid Clustering, and more 20 instances for the extension of the problem with at least one vertex by group. The results demonstrate the efficiency of the algorithm proposed in the obtaining of satisfactory solutions for the two problems. / O problema da árvore geradora mínima generalizado está presente em várias situações do mundo real, tais como no contexto das telecomunicações, transportes e agrupamento de dados, nas quais uma rede de grupos precisa ser conectada utilizando um nodo de cada grupo. Nesse trabalho é apresentado o projeto e a implementação de um algoritmo de busca tabu com reconexão de caminhos e busca local iterativa para o problema da árvore geradora mínima generalizado e sua variante com pelo menos um vértice por grupo. Nos testes computacionais foram utilizadas 271 instâncias da TSPLIB geradas através dos métodos de agrupamento Center Clustering e Grid Clustering, e mais 20 instâncias para a extensão do problema com pelo menos um vértice por grupo. Os resultados demonstram a eficiência do algoritmo proposto na obtenção de soluções satisfatórias para os dois problemas.

Made available in DSpace on 2014-06-11T19:22:32Z (GMT). No. of bitstreams: 0 Previous issue date: 2011-05-20Bitstream added on 2014-06-13T18:08:28Z : No. of bitstreams: 1 oliveira_mbc_me_ilha.pdf: 670316 bytes, checksum: 7becc0c6eda68736bd3c8cea58146dea (MD5) / Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) / Neste trabalho a metaheurística GRASP é utilizada para resolver o problema de reconfiguração de sistemas de distribuição de energia elétrica modelado como um problema de programação não linear binário misto. O objetivo é minimizar as perdas de potência ativa do sistema sujeito a restrições físicas e operacionais do sistema de distribuição. As variáveis binárias do problema representam a abertura e/ou fechamento de chaves de interconexão existentes nos ramos do sistema e as variáveis contínuas representam as tensões nodais e ângulos das tensões nodais. Na metodologia utilizada todas as chaves de interconexão do sistema de distribuição estão fechadas no início do processo e a cada passo da fase construtiva do GRASP um ramo é desconectado do sistema e um fluxo de carga é resolvido. Na fase de melhoria, tendo em vista que a solução da fase construtiva é um sistema radial, foi utilizado a cada iteração um fluxo de carga especializado para sistemas radiais. Para garantir que o sistema de distribuição opere de forma radial, foi introduzido na metodologia de solução uma rotina na qual é verificada a formação de laços e a conectividade do sistema em cada iteração das fases de construção e de melhoria local. São apresentados testes realizados utilizando os sistemas de 14, 33, 84,119 e 136 barras para avaliar a eficiência e robustez da metodologia proposta. Os resultados obtidos foram comparados aos resultados encontrados na literatura com o objetivo de validar a proposta deste trabalho / In this work the GRASP is used to solve the problem of reconfiguring systems for electricity distribution modeled as a nonlinear programming problem of binary mixture. The goal is to minimize the power losses of the system subject to physical constraints and operating the distribution system. The problem of binary variables represents the opening and/or closing braces interconnecting branches existing in the system and the continuous variables represent the nodal voltages and angles of nodal voltages. In the methodology used to interconnect all the keys of the distribution system are closed at the beginning of the process and every step of the constructive phase of GRASP a branch is disconnected from the system and a load flow is solved. In the improvement phase, given that the solution of the constructive phase is a radial system was used at each iteration a load flow for radial systems specialist. To ensure that the distribution system operates in a radial manner, was introduced into the solution methodology is a routine in which verified the formation of linkages and connectivity of the system in each iteration of the phases of construction and local improvement. Tests are presented using the systems 14, 33, 84, 119 and 136 bus to evaluate the efficiency and robustness of the proposed methodology. The results were compared to results from the literature in order to validate the proposal of this work

Made available in DSpace on 2016-06-02T19:50:09Z (GMT). No. of bitstreams: 1 3195.pdf: 2024810 bytes, checksum: 9ca884455df82d8694112f060501c5fe (MD5) Previous issue date: 2010-08-25 / Althought the scheduling-related literature has a high level of diversity, just a small group have been considering the possibility of outsource a set of tasks. During a literature review, only two papers related to this theme were found, both dealing on scheduling projects with outsource possibilities on single-machine environments. Along with this scenario, it was possible to stablish the ACO (Ant Colony Optimization) algorithm as a promissing tecnique to solve combinatorial problems, including scheduling problems. This thesis approaches two scheduling problems with outsourcing allowed: (i) a scheduling problem in single machine manufacturing environment and (ii) a scheduling problem in a flowshop environment. For each problem, a new ACO algorithm is proposed and implemented. To verify the quality of the results, are also proposed and implemented: (i) a mathemetical programming model for the single machine environment problem; (ii) a branch and bound algorithm for the single machine environment problem and (iii) a a mathemetical programming model for the flowshop environment problem. The results shown that both ACO algorithms generate close-to-optimal results in a shorter computational time. In the case of the single machine environment problem, the presented results are best than the results related on the literature. / Embora a literatura de scheduling seja vasta, poucas pesquisas até o momento levam em consideração a possibilidade de terceirização de tarefas. Dentre a literatura pesquisada, apenas dois trabalhos trataram deste problema multicritério, ambos para ambientes de máquina única. Juntamente com isso, uma análise preliminar da literatura p ode estabelecer o algoritmo ACO (do inglês Ant Colony Optimization - Otimização por Colônia de Formigas) como uma estratégia promissora para a solução de problemas combinatórios, incluindo problemas de scheduling. Neste cenário, a presente tese de doutoramento trata de dois problemas de scheduling com possibilidade de terceirização: (i) um problema de scheduling em ambiente de máquina única, já proposto na literatura e (ii) problema inédito de scheduling em ambientes flowshop.Em ambos os casos, são propostos algoritmos ACO inéditos (um para o problema de scheduling em ambientes de máquina única e um para o problema de scheduling em ambientes flowshop), que são comparados com valores ótimos obtidos através de métodos exatos. Para permitir essa comparação, são propostos três métodos exatos: (i) Um modelo de programação matemática para o problema que trata do ambiente de máquina única; (ii) Um algoritmo branch and bound para o mesmo problema e (iii) Um modelo de programação matemática para o problema que trata do ambiente flowshop. Os resultados obtidos no trabalho mostraram que ambos os algoritmos ACO propostos conseguiram respostas próximas ao ótimo. Quando se tratando de problemas de maiores dimensões, o tempo computacional necessário para a execução do algoritmo foi muito menor que o tempo computacional requerido pelos métodos exatos. No caso do problema de scheduling em ambientes de máquina única, ainda pode-se ressaltar que a qualidade dos resultados (em termos de resultados e tempos computacionais) foram melhores que os relatados na literatura pesquisada.

Submitted by Fernando Souza (fernandoafsou@gmail.com) on 2017-08-15T11:46:12Z No. of bitstreams: 1 arquivototal.pdf: 884446 bytes, checksum: 92314027dddef8365b4a2e655b65bd78 (MD5) / Made available in DSpace on 2017-08-15T11:46:13Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 884446 bytes, checksum: 92314027dddef8365b4a2e655b65bd78 (MD5) Previous issue date: 2016-05-20 / The Static Bike Rebalancing Problem (SBRP) is a recent problem motivated by the task of repositioning bikes among stations in a self-service bike-sharing systems. This problem can be seen as a variant of the one-commodity pickup and delivery vehicle routing problem, where multiple visits are allowed to be performed at each station, i.e., the demand of a station is allowed to be split. Moreover, a vehicle may temporarily drop its load at a station, leaving it in excess or, alternatively, collect more bikes (even all of them) from a station, thus leaving it in default. Both cases require further visits in order to meet the actual demands of such station. This work deals with a particular case of the SBRP, in which only a single vehicle is available and the objective is to nd a least-cost route that meets the demand of all stations and does not violate the minimum (zero) and maximum (vehicle capacity) load limits along the tour. Therefore, the number of bikes to be collected or delivered at each station should be appropriately determined in order to respect such constraints. This is a NP-Hard problem since it contains other NP-Hard problems as special cases, hence, using exact methods to solve it is intractable for larger instances. Several methods have been proposed by other authors, providing optimal values for small to medium sized instances, however, no work has consistently solved instances with more than 60 stations. The proposed algorithm to solve the problem is an iterated local search (ILS) based heuristic combined with a randomized variable neighborhood descent (RVND) as local search procedure. The algorithm was tested on 980 benchmark instances from the literature and the results obtained are quite competitive when compared to other existing methods. Moreover, the method was capable of nding most of the known optimal solutions and also of improving the results on a number of open instances. / O Problema do Rebalanceamento Est atico de Bicicletas (Static Bike Rebalancing Problem, SBRP) e um recente problema motivado pela tarefa de reposicionar bicicletas entre esta c~oes em um sistema self-service de compartilhamento de bicicletas. Este problema pode ser visto como uma variante do problema de roteamento de ve culos com coleta e entrega de um unico tipo de produto, onde realizar m ultiplas visitas a cada esta c~ao e permitido, isto e, a demanda da esta c~ao pode ser fracionada. Al em disso, um ve culo pode descarregar sua carga temporariamente em uma esta c~ao, deixando-a em excesso, ou, de maneira an aloga, coletar mais bicicletas (at e mesmo todas elas) de uma esta c~ao, deixando-a em falta. Em ambos os casos s~ao necess arias visitas adicionais para satisfazer as demandas reais de cada esta c~ao. Este trabalho lida com um caso particular do SBRP, em que apenas um ve culo est a dispon vel e o objetivo e encontrar uma rota de custo m nimo que satisfa ca as demandas de todas as esta c~oes e n~ao viole os limites de carga m nimo (zero) e m aximo (capacidade do ve culo) durante a rota. Portanto, o n umero de bicicletas a serem coletadas ou entregues em cada esta c~ao deve ser determinado apropriadamente a respeitar tais restri c~oes. Trata-se de um problema NP-Dif cil uma vez que cont em outros problemas NP-Dif cil como casos particulares, logo, o uso de m etodos exatos para resolv^e-lo e intrat avel para inst^ancias maiores. Diversos m etodos foram propostos por outros autores, fornecendo valores otimos para inst^ancias pequenas e m edias, no entanto, nenhum trabalho resolveu de maneira consistente inst^ancias com mais de 60 esta c~oes. O algoritmo proposto para resolver o problema e baseado na metaheur stica Iterated Local Search (ILS) combinada com o procedimento de busca local variable neighborhood descent com ordena c~ao aleat oria (randomized variable neighborhood descent, RVND). O algoritmo foi testado em 980 inst^ancias de refer^encia na literatura e os resultados obtidos s~ao bastante competitivos quando comparados com outros m etodos existentes. Al em disso, o m etodo foi capaz de encontrar a maioria das solu c~oes otimas conhecidas e tamb em melhorar os resultados de inst^ancias abertas.

Submitted by ELENILSON DE VARGAS FORTES null (vargasfortes@yahoo.com.br) on 2016-10-27T22:01:08Z No. of bitstreams: 1 Tese.pdf: 4090366 bytes, checksum: c721654fbc082e717b79dc074adcbfa0 (MD5) / Approved for entry into archive by Juliano Benedito Ferreira (julianoferreira@reitoria.unesp.br) on 2016-11-03T18:32:27Z (GMT) No. of bitstreams: 1 fortes_ev_dr_ilha.pdf: 4090366 bytes, checksum: c721654fbc082e717b79dc074adcbfa0 (MD5) / Made available in DSpace on 2016-11-03T18:32:27Z (GMT). No. of bitstreams: 1 fortes_ev_dr_ilha.pdf: 4090366 bytes, checksum: c721654fbc082e717b79dc074adcbfa0 (MD5) Previous issue date: 2016-10-21 / Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) / Este trabalho apresenta o Algoritmo Genético de Chu-Beasley Especializado para realizar o ajuste coordenado dos parâmetros de controladores Proporcional-Integral e suplementares de amortecimento (Estabilizadores de Sistemas de Potência e Interline Power Flow Controller - Power Oscillation Damping) em sistemas elétricos de potência multimáquinas. O objetivo principal deste trabalho é inserir amortecimento adicional às oscilações eletromecânicas de baixa frequência classificadas como local e interárea. Para representar o sistema, é utilizado o Modelo de Sensibilidade de Corrente. Desse modo, todos os seus dispositivos e componentes foram modelados por injeção de corrente e, portanto, um novo modelo de injeção de corrente para o Interline Power Flow Controller é apresentado. Três sistemas teste foram utilizados nas simulações realizadas neste trabalho, sendo: Simétrico de Duas Áreas, New England e o Sul Brasileiro Reduzido. O desempenho da metodologia proposta (Algoritmo Genético de Chu-Beasley Especializado), no que concerne ao ajuste dos parâmetros dos controladores, foi comparado a outros dois algoritmos bastantes difundidos na literatura: Particle Swarm Optimization e o Algoritmo Genético com Elitismo. Os resultados demonstraram que o algoritmo Genético de Chu-Beasley Especializado foi mais eficiente que as demais técnicas apresentadas, obtendo soluções robustas quando variações de cargas foram consideradas, sendo, portanto, credenciado como ferramenta no estudo da análise da estabilidade a pequenas perturbações. / CNPq: 141084/2016-2