O presente trabalho aborda o ambiente de produção conhecido como flowshop híbrido. Devido a crescente complexidade dos sistemas de produção, este ambiente é frequentemente encontrado em situações reais de manufatura. No caso estudado existem estágios em série e em cada estágio existe um número de máquinas idênticas em paralelo. Os tempos de processamento em cada estágio são dependentes da tarefa, já a rota através do sistema é a mesma para todas as tarefas. O objetivo é minimizar o atraso total, ou seja, a soma do atraso de todas as tarefas. Um modelo de programação linear inteira mista é apresentado para este problema e, dada a sua complexidade, ele é abordado através de uma meta-heurística relativamente nova e que, conforme revisão da literatura, nunca foi aplicada a este problema. Conhecida por BRKGA (Biased Random-Key Genetic Algorithm), este método codifica as soluções de maneira a obter um melhor desempenho em comparação com algoritmos genéticos tradicionais. Com o objetivo de avaliar a melhor estratégia, são propostas diversas versões de BRKGA para o problema considerado. Estas versões buscam explorar características das melhores heurísticas construtivas da literatura, dentre estas: ordens direta e inversa de programação das tarefas dentro do ambiente produtivo, identificação do estágio gargalo e diferenciação da programação do gargalo dos demais estágios. Experimentos computacionais foram realizados com 432 problemas teste de grande porte. Os métodos apresentados são comparados entre si e os resultados mostraram que uma versão do BRKGA se destaca frente às demais, visto que ela atingiu o melhor resultado em 61% dos problemas. Destaca-se que o método de melhor desempenho da literatura obteve a melhor solução em apenas 15% dos problemas. Devido às dimensões dos problemas teste da literatura, não foi possível encontrar suas soluções ótimas. Deste modo, este trabalho propõe um novo limitante inferior para o mínimo atraso total. Além disso, 576 novos problemas teste de menores dimensões são propostos e seus resultados ótimos são utilizados para aprofundar as comparações. Os resultados deste experimento indicaram que o BRKGA proposto apresentou um bom desempenho visto que, na média, seus resultados estão apenas a 2,4% dos resultados ótimos. / This work addresses a scheduling problem in hybrid flowshops. Due to the increasing complexity of production systems, this production environment is often encountered in real manufacturing situations. In hybrid flowshops, there are stages in series and, in each stage, a number of similar parallel machines. Processing times in each stage are dependent on the job, and the route through the system is the same for all jobs. The objective is to minimize the total tardiness, that is, the sum of all jobs tardiness. A mixed integer linear programming model is presented for the problem considered. Given its complexity, this problem is approached by a relatively new meta-heuristic, known as BRKGA (Biased Random-Key Genetic Algorithm). A literature review showed that BRKGA had never been applied to this problem. The BRKGA codes solutions in order to obtain a better performance compared with traditional genetic algorithms. Several versions of BRKGA were developed in order to evaluate the best strategy to solve the problem considered. These versions aim to exploit features of the best constructive heuristic from the literature, among them: scheduling jobs in direct and inverse order within the production environment, identification of the bottleneck stage and distinction of the bottleneck stage schedule from the others. Computational experiments were conducted with 432 large instances. The methods were compared and the results showed that one of these versions stood out against the others. This version achieved better results in 61% of instances, while the best heuristic from the literature achieved 15%. Due to the size of these instances, optimal solutions were not found. Therefore, this work develops a new lower bound for the minimum total tardiness. Additionally, in order to find optimal results, a set of 576 new instances is proposed. This experiment indicated that the BRKGA proposed performed well since, on average, their results are only 2.4% away from the optimal results.

O presente trabalho aborda o ambiente de produção conhecido como flowshop híbrido. Devido a crescente complexidade dos sistemas de produção, este ambiente é frequentemente encontrado em situações reais de manufatura. No caso estudado existem estágios em série e em cada estágio existe um número de máquinas idênticas em paralelo. Os tempos de processamento em cada estágio são dependentes da tarefa, já a rota através do sistema é a mesma para todas as tarefas. O objetivo é minimizar o atraso total, ou seja, a soma do atraso de todas as tarefas. Um modelo de programação linear inteira mista é apresentado para este problema e, dada a sua complexidade, ele é abordado através de uma meta-heurística relativamente nova e que, conforme revisão da literatura, nunca foi aplicada a este problema. Conhecida por BRKGA (Biased Random-Key Genetic Algorithm), este método codifica as soluções de maneira a obter um melhor desempenho em comparação com algoritmos genéticos tradicionais. Com o objetivo de avaliar a melhor estratégia, são propostas diversas versões de BRKGA para o problema considerado. Estas versões buscam explorar características das melhores heurísticas construtivas da literatura, dentre estas: ordens direta e inversa de programação das tarefas dentro do ambiente produtivo, identificação do estágio gargalo e diferenciação da programação do gargalo dos demais estágios. Experimentos computacionais foram realizados com 432 problemas teste de grande porte. Os métodos apresentados são comparados entre si e os resultados mostraram que uma versão do BRKGA se destaca frente às demais, visto que ela atingiu o melhor resultado em 61% dos problemas. Destaca-se que o método de melhor desempenho da literatura obteve a melhor solução em apenas 15% dos problemas. Devido às dimensões dos problemas teste da literatura, não foi possível encontrar suas soluções ótimas. Deste modo, este trabalho propõe um novo limitante inferior para o mínimo atraso total. Além disso, 576 novos problemas teste de menores dimensões são propostos e seus resultados ótimos são utilizados para aprofundar as comparações. Os resultados deste experimento indicaram que o BRKGA proposto apresentou um bom desempenho visto que, na média, seus resultados estão apenas a 2,4% dos resultados ótimos. / This work addresses a scheduling problem in hybrid flowshops. Due to the increasing complexity of production systems, this production environment is often encountered in real manufacturing situations. In hybrid flowshops, there are stages in series and, in each stage, a number of similar parallel machines. Processing times in each stage are dependent on the job, and the route through the system is the same for all jobs. The objective is to minimize the total tardiness, that is, the sum of all jobs tardiness. A mixed integer linear programming model is presented for the problem considered. Given its complexity, this problem is approached by a relatively new meta-heuristic, known as BRKGA (Biased Random-Key Genetic Algorithm). A literature review showed that BRKGA had never been applied to this problem. The BRKGA codes solutions in order to obtain a better performance compared with traditional genetic algorithms. Several versions of BRKGA were developed in order to evaluate the best strategy to solve the problem considered. These versions aim to exploit features of the best constructive heuristic from the literature, among them: scheduling jobs in direct and inverse order within the production environment, identification of the bottleneck stage and distinction of the bottleneck stage schedule from the others. Computational experiments were conducted with 432 large instances. The methods were compared and the results showed that one of these versions stood out against the others. This version achieved better results in 61% of instances, while the best heuristic from the literature achieved 15%. Due to the size of these instances, optimal solutions were not found. Therefore, this work develops a new lower bound for the minimum total tardiness. Additionally, in order to find optimal results, a set of 576 new instances is proposed. This experiment indicated that the BRKGA proposed performed well since, on average, their results are only 2.4% away from the optimal results.

Em nosso mundo altamente conectado, novas tecnologias provêm contínuas mudanças na velocidade e eficiência das redes de telecomunicações e de transporte. Muitas dessas tecnologias são originárias de pesquisas em problemas de otimização em redes aplicadas a diferentes áreas. Nesta tese, investigamos três problemas de otimização combinatória que podem ser abordados como estruturas de redes. Primeiramente, são abordados problemas de engenharia de tráfego em redes de transporte. O objetivo principal é investigar os efeitos de alterar o custo de um subconjunto de arcos da rede, considerando que os clientes desta rede agem com um comportamento bem definido. O objetivo é controlar o fluxo na rede de modo a obter uma melhor distribuição do fluxo, minimizando o congestionamento ou maximizando o fluxo em um subconjunto de arestas. No primeiro problema considerase instalar um número fixo de postos de pedágios e definir os valores das tarifas para minimizar o tempo médio de viagem dos usuários. No segundo problema abordado, o objetivo é definir os valores das tarifas para maximizar a receita arrecadada nos arcos com pedágios. Em ambos os problemas, os usuários escolhem as rotas com base nos caminhos de menor custo da origem para o destino. Em redes de telecomunicações, um problema de alocação sujeito às condições da rede é considerado. O objetivo é alocar um conjunto de recursos, minimizando o custo de comunicação. Uma aplicação de computação em nuvem é considerada, onde os recursos são máquinas virtuais que devem ser alocadas em um conjunto de centros de dados. Condições da rede como largura de banda e latência são consideradas de modo a garantir a qualidade dos serviços. Para todos estes problemas, os modelos matemáticos são apresentados e avaliados usando um solver comercial de propósito geral como um método exato. Além disso, abordagens heurísticas são propostas, incluindo uma classe de algoritmo genético de chaves aleatórias viciadas (BRKGA). Resultados experimentais demonstram o bom desempenho das abordagens heurísticas propostas, mostrando que o BRKGA é uma ferramenta eficiente para resolver diferentes tipos de problemas de otimização combinatória, especialmente sobre estruturas de rede. / In our highly connected world, new technologies provide continuous changes in the speed and efficiency of telecommunication and transportation networks. Many of these technologies come from research on network optimization problems with applications in different areas. In this thesis, we investigate three combinatorial optimization problems that arise from optimization on networks. First, traffic engineering problems in transportation networks are addressed. The main objective is to investigate the effects of changing the cost of some links in the network regarding some well-defined user behavior. The goal is to control the flow in the network and seek a better flow distribution over the network and then minimize the traffic congestion or maximize the flow on a subset of links over network conditions. The first problem considered is to install a fixed number of tollbooths and define the values of tariffs to minimize the average user travel time. The second problem considered is to define the values of tariffs to maximize the revenue collected in the tolled arcs. In both problems, users choose the routes based on the least cost paths from source to destination. From telecommunication networks, a placement problem subjected to network conditions is considered. The main objective is to place a set of resources minimizing the communication cost. An application from cloud computing is considered, where the resources are virtual machines that should be placed in a set of data centers. Network conditions, such as bandwidth and latency, are considered in order to ensure the service quality. For all these problems, mathematical models are presented and evaluated using a general-purpose commercial solver as an exact method. Furthermore, new heuristics approaches are proposed, including some based on biased random-key genetic algorithm (BRKGA). Experimental results demonstrate the good performance of the proposed heuristic approaches, showing that BRKGA is an efficient tool for solving different kinds of combinatorial optimization problems, especially over network structures.

Em nosso mundo altamente conectado, novas tecnologias provêm contínuas mudanças na velocidade e eficiência das redes de telecomunicações e de transporte. Muitas dessas tecnologias são originárias de pesquisas em problemas de otimização em redes aplicadas a diferentes áreas. Nesta tese, investigamos três problemas de otimização combinatória que podem ser abordados como estruturas de redes. Primeiramente, são abordados problemas de engenharia de tráfego em redes de transporte. O objetivo principal é investigar os efeitos de alterar o custo de um subconjunto de arcos da rede, considerando que os clientes desta rede agem com um comportamento bem definido. O objetivo é controlar o fluxo na rede de modo a obter uma melhor distribuição do fluxo, minimizando o congestionamento ou maximizando o fluxo em um subconjunto de arestas. No primeiro problema considerase instalar um número fixo de postos de pedágios e definir os valores das tarifas para minimizar o tempo médio de viagem dos usuários. No segundo problema abordado, o objetivo é definir os valores das tarifas para maximizar a receita arrecadada nos arcos com pedágios. Em ambos os problemas, os usuários escolhem as rotas com base nos caminhos de menor custo da origem para o destino. Em redes de telecomunicações, um problema de alocação sujeito às condições da rede é considerado. O objetivo é alocar um conjunto de recursos, minimizando o custo de comunicação. Uma aplicação de computação em nuvem é considerada, onde os recursos são máquinas virtuais que devem ser alocadas em um conjunto de centros de dados. Condições da rede como largura de banda e latência são consideradas de modo a garantir a qualidade dos serviços. Para todos estes problemas, os modelos matemáticos são apresentados e avaliados usando um solver comercial de propósito geral como um método exato. Além disso, abordagens heurísticas são propostas, incluindo uma classe de algoritmo genético de chaves aleatórias viciadas (BRKGA). Resultados experimentais demonstram o bom desempenho das abordagens heurísticas propostas, mostrando que o BRKGA é uma ferramenta eficiente para resolver diferentes tipos de problemas de otimização combinatória, especialmente sobre estruturas de rede. / In our highly connected world, new technologies provide continuous changes in the speed and efficiency of telecommunication and transportation networks. Many of these technologies come from research on network optimization problems with applications in different areas. In this thesis, we investigate three combinatorial optimization problems that arise from optimization on networks. First, traffic engineering problems in transportation networks are addressed. The main objective is to investigate the effects of changing the cost of some links in the network regarding some well-defined user behavior. The goal is to control the flow in the network and seek a better flow distribution over the network and then minimize the traffic congestion or maximize the flow on a subset of links over network conditions. The first problem considered is to install a fixed number of tollbooths and define the values of tariffs to minimize the average user travel time. The second problem considered is to define the values of tariffs to maximize the revenue collected in the tolled arcs. In both problems, users choose the routes based on the least cost paths from source to destination. From telecommunication networks, a placement problem subjected to network conditions is considered. The main objective is to place a set of resources minimizing the communication cost. An application from cloud computing is considered, where the resources are virtual machines that should be placed in a set of data centers. Network conditions, such as bandwidth and latency, are considered in order to ensure the service quality. For all these problems, mathematical models are presented and evaluated using a general-purpose commercial solver as an exact method. Furthermore, new heuristics approaches are proposed, including some based on biased random-key genetic algorithm (BRKGA). Experimental results demonstrate the good performance of the proposed heuristic approaches, showing that BRKGA is an efficient tool for solving different kinds of combinatorial optimization problems, especially over network structures.

Em nosso mundo altamente conectado, novas tecnologias provêm contínuas mudanças na velocidade e eficiência das redes de telecomunicações e de transporte. Muitas dessas tecnologias são originárias de pesquisas em problemas de otimização em redes aplicadas a diferentes áreas. Nesta tese, investigamos três problemas de otimização combinatória que podem ser abordados como estruturas de redes. Primeiramente, são abordados problemas de engenharia de tráfego em redes de transporte. O objetivo principal é investigar os efeitos de alterar o custo de um subconjunto de arcos da rede, considerando que os clientes desta rede agem com um comportamento bem definido. O objetivo é controlar o fluxo na rede de modo a obter uma melhor distribuição do fluxo, minimizando o congestionamento ou maximizando o fluxo em um subconjunto de arestas. No primeiro problema considerase instalar um número fixo de postos de pedágios e definir os valores das tarifas para minimizar o tempo médio de viagem dos usuários. No segundo problema abordado, o objetivo é definir os valores das tarifas para maximizar a receita arrecadada nos arcos com pedágios. Em ambos os problemas, os usuários escolhem as rotas com base nos caminhos de menor custo da origem para o destino. Em redes de telecomunicações, um problema de alocação sujeito às condições da rede é considerado. O objetivo é alocar um conjunto de recursos, minimizando o custo de comunicação. Uma aplicação de computação em nuvem é considerada, onde os recursos são máquinas virtuais que devem ser alocadas em um conjunto de centros de dados. Condições da rede como largura de banda e latência são consideradas de modo a garantir a qualidade dos serviços. Para todos estes problemas, os modelos matemáticos são apresentados e avaliados usando um solver comercial de propósito geral como um método exato. Além disso, abordagens heurísticas são propostas, incluindo uma classe de algoritmo genético de chaves aleatórias viciadas (BRKGA). Resultados experimentais demonstram o bom desempenho das abordagens heurísticas propostas, mostrando que o BRKGA é uma ferramenta eficiente para resolver diferentes tipos de problemas de otimização combinatória, especialmente sobre estruturas de rede. / In our highly connected world, new technologies provide continuous changes in the speed and efficiency of telecommunication and transportation networks. Many of these technologies come from research on network optimization problems with applications in different areas. In this thesis, we investigate three combinatorial optimization problems that arise from optimization on networks. First, traffic engineering problems in transportation networks are addressed. The main objective is to investigate the effects of changing the cost of some links in the network regarding some well-defined user behavior. The goal is to control the flow in the network and seek a better flow distribution over the network and then minimize the traffic congestion or maximize the flow on a subset of links over network conditions. The first problem considered is to install a fixed number of tollbooths and define the values of tariffs to minimize the average user travel time. The second problem considered is to define the values of tariffs to maximize the revenue collected in the tolled arcs. In both problems, users choose the routes based on the least cost paths from source to destination. From telecommunication networks, a placement problem subjected to network conditions is considered. The main objective is to place a set of resources minimizing the communication cost. An application from cloud computing is considered, where the resources are virtual machines that should be placed in a set of data centers. Network conditions, such as bandwidth and latency, are considered in order to ensure the service quality. For all these problems, mathematical models are presented and evaluated using a general-purpose commercial solver as an exact method. Furthermore, new heuristics approaches are proposed, including some based on biased random-key genetic algorithm (BRKGA). Experimental results demonstrate the good performance of the proposed heuristic approaches, showing that BRKGA is an efficient tool for solving different kinds of combinatorial optimization problems, especially over network structures.