Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / The evolution of computer hardware as well as new applications of mathematical programming techniques, efficiently implemented in many commercial solvers, has given rise to new algorithms called hybrid metaheuristic, which have been applied to solve combinatorial problems. This work presents several approaches which try to deal with the hybridization of local search based metaheuristics with exact algorithms to solve two problems of combinatorial optimization. More specifically, the first problem, capacitated p-median problem, the proposed approach considers heuristic elimination of variable of the original mathematical model, that produce solutions of very good quality in a short amount of time, and a combination with an iterative procedure in which only a certain subset of points is considered. As regards the second problem, unrelated parallel machine scheduling with sequence and machine dependent setup time problem of minimizing makespan, is proposed a mathematical model to search the neighborhood of a solution and identify movement sequences to minimize the objective function. In both cases, mathematical models are solved using a commercial solver. Extensive computational experiments are carried out to demonstrate the good performance of the proposed approaches. / A recente evolução dos computadores como também dos métodos exatos oriundos da programação matemática, muitos destes eficientemente implementados em otimizadores comerciais, propiciou o surgimento de novos algoritmos, denominados metaheurísticas híbridas, que têm sido aplicados para resolução de problemas combinatoriais. Este trabalho apresenta abordagens que hibridizam metaheurísticas baseadas em busca local com algoritmos exatos de programação matemática para resolver dois problemas de otimização combinatória. Mais especificamente, para o primeiro problema, o problema das p-medianas capacitado, a proposta considera a eliminação heurística de variáveis do modelo matemático, que permite a obtenção de soluções de boa qualidade em um curto tempo computacional, e a combinação com um procedimento iterativo no qual apenas um determinado subconjunto de pontos é considerado. No que se refere ao segundo problema, programação de tarefas em máquinas paralelas não relacionadas com tempo de preparação dependente da sequência e da máquina com objetivo de minimizar o tempo de processamento total da máquina com maior carga entre todas (makespan), propõe-se um modelo matemático para varrer a vizinhança de uma solução e identificar sequências de movimentos de tarefas que podem ser aplicadas na respectiva solução de modo a minimizar a função objetivo. Nos dois casos os modelos matemáticos são resolvidos utilizando um otimizador comercial. Extensivos testes computacionais são realizados para demonstrar o bom desempenho das abordagens propostas.

In spite tropical forests are the most important terrestrial global carbon sinks due to carbon storage in aboveground biomass, it is also the primary target of deforestation. The conversion of Tropical forests into anthropogenic areas might disrupt biological flux and also lead to severe microclimatic changes at forest edges. These combined effects can trigger profound changes in plant composition through both high mortality of fragmentation-sensitive species and proliferation of disturbed-adapted species which will ultimately impacts carbon storage. Thus, our main objective in this study was understand the role of human-induced disturbances in modulate the dimension of biomass loss at tropical forests. We applied a systematic literature review searching for empirical evidences that edge effects can drive biomass loss in tropical forests (Chapter 2). Our findings highlighted the gap of knowledge about the pattern and process related to biomass loss in tropical forests. To strengthen this understanding, we formulated a conceptual model linking landscape structure and patch-level attributes to severity of edge effects affecting aboveground biomass. Our model hypothesizes that habitat amount, isolation, time since edge creation, and the synergism between edge distance, patch size, and matrix type are the main drivers of biomass loss in anthropogenic tropical forests. We thus used a large plant dataset (18 503 trees ≥ 10 cm dbh) from 146 sites distributed across four Mexican and four Brazilian rainforest regions to test our conceptual model predictions, specifically the influence of forest cover, site isolation, edge distance, patch size and type of matrix on biomass (Chapter 3). We observed that carbon-rich sites presented species that are typical of old-growth forests (shade-tolerant, large-seeded, zoocoric) contrasting to carbon-poor sites composed by disturbed-adapted species (pioneer occupying the understory). Large shade-tolerant trees (≥ 40 cm dbh) were impacted severely by the combination of forest loss and edge effects. Edge distance, patch size, and the amount of open-matrix strongly influence small shade-tolerant trees (≤ 20 cm dbh). Although our results do not fully corroborate the initial predictions of the conceptual model, they support the idea that landscape composition interact with patch structure and ultimately impacts biomass stocks in fragmented tropical forests. Finally, we further investigated if the disturbance level of the region influences plant-structure responses to forest loss (Chapter 4). Biomass, but not plant density, was affected by forest loss in regions with intermediate disturbance levels, i.e. regions showing a combination of moderate deforestation (20-40% of remaining forest cover) disturbed during the past 30-60 years, high defaunation but harboring relictual populations of large-mammals, and areas mostly composed by heterogeneous matrices. In general, our findings highlight that both landscape composition and patch structure are the main drivers of biomass loss in Neotropical forests, and that the landscape context must be considered to obtain more reliable estimations of carbon emissions due to forest degradation. Landscape planning (e.g. restoration of forest cover) should be included in conservation strategies in order to sustain carbon storage. Moreover, we advocate that conservation initiatives will be less costly and more effective if implemented in areas under intermediate disturbance levels / Apesar das florestas tropicais serem a mais importante fonte mundial de carbono da porção terrestre do globo devido ao armazenamento de carbono na biomassa acima do solo, elas são também o alvo primário do desmatamento. A conversão das florestas Tropicais em áreas antropogênicas pode interromper o fluxo biológico e também levar a severas mudanças microclimáticas na borda dos fragmentos. A combinação desses efeitos pode engatilhar profundas mudanças na composição da vegetação através tanto da mortalidade de espécies sensíveis à fragmentação como também pela proliferação de espécies adaptadas distúrbios, com impactos finais nos estoques de carbono. Assim, o maior objetivo desse estudo foi compreender o papel dos distúrbios induzidos pelo homem na modulação da dimensão da perda de biomassa em florestas Tropicais. Nós aplicamos uma revisão sistemática da literatura procurando por evidências empíricas de que o efeito de borda pode levar a perda de biomassa em florestas tropicais (Capítulo 2). Nossos resultados destacam a lacuna de conhecimento entre padrões e processos relacionados à perda de biomassa em florestas Tropicais. Para fortalecer esse conhecimento, nós formulamos um modelo conceitual conectando estrutura da paisagem e atributos na escala do fragmento à severidade do efeito de borda, e assim afetando a biomassa acima do solo. Nosso modelo hipotetiza que a quantidade de hábitat, o isolamento, o tempo desde a formação da borda e o sinergismo entre tamanho do fragmento, distância da borda e tipo de matriz são os principais condutores de perda de biomassa em florestas Tropicais antropogênicas. Utilizando um grande banco de dados (18 503 árvores ≥ 10 cm dap) provenientes de 146 locais distribuídos em quatro regiões de floresta úmida no México e quatro no Brasil, nós então testamos as predições do nosso modelo conceitual. Especificamente, a influência da cobertura florestal, isolamento, distância da borda, tamanho do fragmento e tipo de matriz sobre a biomassa (Capítulo 3). Nós observamos que áreas com muito carbono apresentaram espécies típicas de florestas maduras (tolerantes ao sombreamento, zoocóricas, com sementes grandes) contrastando com áreas com pouco carbono compostas por espécies adaptadas à distúrbio (pioneiras ocupando o sub-bosque). Árvores grandes tolerantes ao sombreamento (≥ 40 cm dap) foram impactadas severamente pela combinação de perda de cobertura florestal e efeitos de borda. Distância da borda, tamanho do fragmento e a extensão da área de matriz aberta influenciaram fortemente as árvores pequenas tolerantes a sombreamento (≤ 20 cm dap). Apesar dos nossos resultados não corroborarem completamente as predições iniciais do nosso modelo conceitual, eles dão suporte à ideia de que a composição da paisagem interage com a estrutura do fragmento com impactos finais nos estoques de biomassa em florestas Neotropicais. Por fim, nós investigamos se o nível de distúrbio da região pode influenciar nas respostas da estrutura da vegetação à perda de cobertura florestal. Biomassa, mas não a densidade de indivíduos, foi afetada pela perda de cobertura florestal em regiões com nível intermediário de distúrbio, i.e. regiões apresentando uma combinação de níveis moderados de desmatamento (20-40% de cobertura florestal remanescente) em que a perturbação ocorreu ao longo dos últimos 30-60 anos, com alto grau de defaunação mas ainda abrigando populações relictuais de grandes mamíferos e, em sua maioria, compostos por uma matriz heterogênea. Em geral, nossos resultados destacaram que tanto a composição da paisagem como a estrutura do fragmento são os principais condutores de perda de biomassa em florestas Neotropicais e que o contexto da paisagem deve ser considerado para se obter estimativas mais confiáveis de emissão de carbono devido à degradação florestal. O planejamento da paisagem (e.g. restauração da cobertura florestal) deve ser incluído em estratégias de conservação em ordem de sustentar o armazenamento de carbono. Além disso, nós defendemos que iniciativas de conservação serão menos custosas e mais efetivas se implementadas em áreas sob níveis intermediários de distúrbio

No contexto da operação de sistemas de distribuição, um dos problemas com os quais os operadores lidam frequentemente é o de restabelecimento de energia. Este problema surge na ocorrência de uma falta permanente e pode ser tratado por meio de manobras em chaves presentes na rede primária. Uma vez que tais redes operam com topologia radial, a ocorrência de uma falta pode resultar no desligamento de consumidores saudáveis. Desta maneira, o problema consiste em definir, num curto intervalo de tempo, um número mínimo de chaves que devem ser operadas a fim de isolar a falta e restaurar o máximo de consumidores saudáveis desligados. Os esforços para a obtenção de ferramentas computacionais para fornecimento de soluções para o problema de restabelecimento têm sido intensificados nos últimos anos. Isto ocorre, em especial, devido aos enormes prejuízos causados pela falta de energia às companhias de eletricidade e a toda a sociedade. Neste sentido, o objetivo deste trabalho é a obtenção de um método para auxiliar o trabalho dos operadores através do fornecimento de planos adequados de restabelecimento em curtos intervalos de tempo. Os diferenciais deste método proposto são a sua capacidade de: lidar, em especial, com redes reais de grande porte com reduzido esforço computacional; considerar a existência de vários níveis de prioridade de atendimento entre os consumidores (note, por exemplo, que um hospital ou um centro de segurança pública devem ter maior prioridade de atendimento que um grande supermercado ou unidades residenciais) e priorizar o atendimento deles de acordo a sua prioridade; fornecer uma sequência por meio da qual as chaves possam ser operadas a fim de isolar os setores em falta e reconectar o maior número de consumidores saudáveis desligados executando-se o mínimo de manobras em chaves e priorizando os consumidores com maior prioridade; ser capaz de selecionar cargas menos prioritárias para permaneceram desligadas nas situações em que não é possível obter uma solução que restaure todas as cargas saudáveis fora de serviço; e, adicionalmente, priorizar a operação de chaves controladas remotamente, que, diferentemente das chaves controladas manualmente, podem ser operadas com menores custos e de maneira mais rápida. O método proposto consiste, de maneira sintética, na união de uma busca exaustiva aplicada localmente a um novo algoritmo evolutivo multi-objetivo em tabelas de subpopulação que faz uso de uma estrutura de dados eficiente denominada Representação Nó-Profundidade. Para avaliar a performance relativa do método proposto, simulações foram realizadas num sistema de distribuição de pequeno porte e os resultados foram comparados com os obtidos por um método de Programação Matemática. Na sequência, novos experimentos foram realizadas em diversos casos de falta na rede de distribuição da cidade de Londrina-PR e cidades adjacentes. As soluções fornecidas mostraram-se adequadas ao tratamento dos casos de falta, assim como as sequências de chaveamento associadas a elas, as quais foram capazes de priorizar o restabelecimento dos consumidores prioritários seguindo seus níveis de prioridade. Adicionalmente, estudos avaliaram a variação do tempo de processamento computacional do método proposto com a dimensão das redes de distribuições e também com o número de gerações realizadas pelo algoritmo evolutivo multi-objetivo proposto e os resultados mostraram-se satisfatórios às necessidades do problema Portanto, pode-se comprovar que o método proposto atingiu os objetivos especificados, em especial, o tratamento de aspectos práticos do problema. Além do próprio método proposto, algumas contribuições desta pesquisa são a proposição um novo algoritmo evolutivo multiobjetivo em tabelas de subpopulação e de um novo operador para manipulação de florestas de grafo armazenadas pela Representação Nó-Profundidade e voltado ao problema de restabelecimento. / In the context of distribution systems operation, service restoration is one of the problems with which operators constantly deal. It arises when a permanent fault occurs and is treated trough operations in switches at primary grid. Since distribution systems are usually radial, fault occurrence turns-off healthy customers. Thereby, the service restoration problem consists in defining, in a short processing time, the minimum amount of switches that must be operated for the isolation of the fault and reconnection of the maximum amount of healthy out-of-service customers. The efforts of developing computational tools for getting solution to this problems has increased in the last years. It is, in special, due to enormous losses caused to the utilities and to the whole society. In this sense, the main objective of this research is getting a method able to help the distribution system operator\'s work through providing service restoration plans quickly. The differentials of this research are its ability to: deal, in special, with large scale grids whit a reduced computational effort; consider costumers of several priority levels (note, for instance, a hospital has a higher supply priority in relation to a big supermarket) and prioritize the higher priority customers; provide a switching sequence able to isolate and reconnect the maximum amount of healthy out-of-service customer by the minimum amount of switching actions; select lower priority customers to keep out-of-service in order to reconnect higher priority customers when a it is not possible to restore all customers; and, additionally, prioritize switching operation in remotely controlled switches, whose operation is faster and cheapest than the operation of manually controlled switches. The proposed method mixes a local exhaustive search and a new multi-objective evolutionary algorithm in subpopulation tables that uses a data structure named Node-Depth Encoding. For evaluating the relative performance of proposed method, simulations were performed in small distribution systems and the performance was compared with the performance a Mathematical Programing method from literature. New experiments were performed a Mathematical Programing method from literature. New experiments were performed in several fault situations in the real and large-scale distribution system of Londrina-PR and adjacent cities. The solutions provided were appropriated to the treatment of such contingency situations. The same occurs with the switching sequences provided, which were able to prioritize the restoration of higher priority customers. Additional studies evaluated the variation of the running time with the size of grids and with the values adopted for the maximum number of generations of the evolutionary algorithm (which is an input parameter). The results expressed the running time of the proposed method is suitable to the problem needs. Therefore, it could be proved the proposed method achieved the specified objectives, in special, the treatment of practical aspects of the problem. Besides the proposed method, some contributions of this research are proposition of a new multi-objective evolutionary algorithm in subpopulation tables and a new reproduction operator to manipulate graph forests computationally represented by Node-Depth Encoding.

No contexto da operação de sistemas de distribuição, um dos problemas com os quais os operadores lidam frequentemente é o de restabelecimento de energia. Este problema surge na ocorrência de uma falta permanente e pode ser tratado por meio de manobras em chaves presentes na rede primária. Uma vez que tais redes operam com topologia radial, a ocorrência de uma falta pode resultar no desligamento de consumidores saudáveis. Desta maneira, o problema consiste em definir, num curto intervalo de tempo, um número mínimo de chaves que devem ser operadas a fim de isolar a falta e restaurar o máximo de consumidores saudáveis desligados. Os esforços para a obtenção de ferramentas computacionais para fornecimento de soluções para o problema de restabelecimento têm sido intensificados nos últimos anos. Isto ocorre, em especial, devido aos enormes prejuízos causados pela falta de energia às companhias de eletricidade e a toda a sociedade. Neste sentido, o objetivo deste trabalho é a obtenção de um método para auxiliar o trabalho dos operadores através do fornecimento de planos adequados de restabelecimento em curtos intervalos de tempo. Os diferenciais deste método proposto são a sua capacidade de: lidar, em especial, com redes reais de grande porte com reduzido esforço computacional; considerar a existência de vários níveis de prioridade de atendimento entre os consumidores (note, por exemplo, que um hospital ou um centro de segurança pública devem ter maior prioridade de atendimento que um grande supermercado ou unidades residenciais) e priorizar o atendimento deles de acordo a sua prioridade; fornecer uma sequência por meio da qual as chaves possam ser operadas a fim de isolar os setores em falta e reconectar o maior número de consumidores saudáveis desligados executando-se o mínimo de manobras em chaves e priorizando os consumidores com maior prioridade; ser capaz de selecionar cargas menos prioritárias para permaneceram desligadas nas situações em que não é possível obter uma solução que restaure todas as cargas saudáveis fora de serviço; e, adicionalmente, priorizar a operação de chaves controladas remotamente, que, diferentemente das chaves controladas manualmente, podem ser operadas com menores custos e de maneira mais rápida. O método proposto consiste, de maneira sintética, na união de uma busca exaustiva aplicada localmente a um novo algoritmo evolutivo multi-objetivo em tabelas de subpopulação que faz uso de uma estrutura de dados eficiente denominada Representação Nó-Profundidade. Para avaliar a performance relativa do método proposto, simulações foram realizadas num sistema de distribuição de pequeno porte e os resultados foram comparados com os obtidos por um método de Programação Matemática. Na sequência, novos experimentos foram realizadas em diversos casos de falta na rede de distribuição da cidade de Londrina-PR e cidades adjacentes. As soluções fornecidas mostraram-se adequadas ao tratamento dos casos de falta, assim como as sequências de chaveamento associadas a elas, as quais foram capazes de priorizar o restabelecimento dos consumidores prioritários seguindo seus níveis de prioridade. Adicionalmente, estudos avaliaram a variação do tempo de processamento computacional do método proposto com a dimensão das redes de distribuições e também com o número de gerações realizadas pelo algoritmo evolutivo multi-objetivo proposto e os resultados mostraram-se satisfatórios às necessidades do problema Portanto, pode-se comprovar que o método proposto atingiu os objetivos especificados, em especial, o tratamento de aspectos práticos do problema. Além do próprio método proposto, algumas contribuições desta pesquisa são a proposição um novo algoritmo evolutivo multiobjetivo em tabelas de subpopulação e de um novo operador para manipulação de florestas de grafo armazenadas pela Representação Nó-Profundidade e voltado ao problema de restabelecimento. / In the context of distribution systems operation, service restoration is one of the problems with which operators constantly deal. It arises when a permanent fault occurs and is treated trough operations in switches at primary grid. Since distribution systems are usually radial, fault occurrence turns-off healthy customers. Thereby, the service restoration problem consists in defining, in a short processing time, the minimum amount of switches that must be operated for the isolation of the fault and reconnection of the maximum amount of healthy out-of-service customers. The efforts of developing computational tools for getting solution to this problems has increased in the last years. It is, in special, due to enormous losses caused to the utilities and to the whole society. In this sense, the main objective of this research is getting a method able to help the distribution system operator\'s work through providing service restoration plans quickly. The differentials of this research are its ability to: deal, in special, with large scale grids whit a reduced computational effort; consider costumers of several priority levels (note, for instance, a hospital has a higher supply priority in relation to a big supermarket) and prioritize the higher priority customers; provide a switching sequence able to isolate and reconnect the maximum amount of healthy out-of-service customer by the minimum amount of switching actions; select lower priority customers to keep out-of-service in order to reconnect higher priority customers when a it is not possible to restore all customers; and, additionally, prioritize switching operation in remotely controlled switches, whose operation is faster and cheapest than the operation of manually controlled switches. The proposed method mixes a local exhaustive search and a new multi-objective evolutionary algorithm in subpopulation tables that uses a data structure named Node-Depth Encoding. For evaluating the relative performance of proposed method, simulations were performed in small distribution systems and the performance was compared with the performance a Mathematical Programing method from literature. New experiments were performed a Mathematical Programing method from literature. New experiments were performed in several fault situations in the real and large-scale distribution system of Londrina-PR and adjacent cities. The solutions provided were appropriated to the treatment of such contingency situations. The same occurs with the switching sequences provided, which were able to prioritize the restoration of higher priority customers. Additional studies evaluated the variation of the running time with the size of grids and with the values adopted for the maximum number of generations of the evolutionary algorithm (which is an input parameter). The results expressed the running time of the proposed method is suitable to the problem needs. Therefore, it could be proved the proposed method achieved the specified objectives, in special, the treatment of practical aspects of the problem. Besides the proposed method, some contributions of this research are proposition of a new multi-objective evolutionary algorithm in subpopulation tables and a new reproduction operator to manipulate graph forests computationally represented by Node-Depth Encoding.