Submitted by Irvana Coutinho (irvana@ufpa.br) on 2013-01-28T13:46:14Z No. of bitstreams: 2 license_rdf: 23898 bytes, checksum: e363e809996cf46ada20da1accfcd9c7 (MD5) Tese_AlgoritmosCulturaisAbordagem.pdf: 1360669 bytes, checksum: 17fb217e7255ede1a2f4ac1767703825 (MD5) / Approved for entry into archive by Ana Rosa Silva(arosa@ufpa.br) on 2013-01-28T17:07:35Z (GMT) No. of bitstreams: 2 license_rdf: 23898 bytes, checksum: e363e809996cf46ada20da1accfcd9c7 (MD5) Tese_AlgoritmosCulturaisAbordagem.pdf: 1360669 bytes, checksum: 17fb217e7255ede1a2f4ac1767703825 (MD5) / Made available in DSpace on 2013-01-28T17:07:35Z (GMT). No. of bitstreams: 2 license_rdf: 23898 bytes, checksum: e363e809996cf46ada20da1accfcd9c7 (MD5) Tese_AlgoritmosCulturaisAbordagem.pdf: 1360669 bytes, checksum: 17fb217e7255ede1a2f4ac1767703825 (MD5) Previous issue date: 2012 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / FAPESPA - Fundação Amazônia de Amparo a Estudos e Pesquisas / Em muitos problemas de otimização há dificuldades em alcançar um resultado ótimo ou mesmo um resultado próximo ao valor ótimo em um tempo viável, principalmente quando se trabalha em grande escala. Por isso muitos desses problemas são abordados por heurísticas ou metaheurísticas que executam buscas por melhores soluções dentro do espaço de busca definido. Dentro da computação natural estão os Algoritmos Culturais e os Algoritmos Genéticos, que são considerados metaheurísticas evolutivas que se complementam devido ao mecanismo dual de herança cultura/genética. A proposta do presente trabalho é estudar e utilizar tais mecanismos acrescentando tanto heurísticas de busca local como multipopulações aplicados em problemas de otimização combinatória (caixeiro viajante e mochila), funções multimodais e em problemas restritos. Serão executados alguns experimentos para efetuar uma avaliação em relação ao desempenho desses mecanismos híbridos e multipopulacionais com outros mecanismos dispostos na literatura de acordo com cada problema de otimização aqui abordado. / In many optimization problems is hard to reach a good result or a result close to the optimum value in a feasible time, especially when working on large scale. So, many of these problems are addressed by heuristics or metaheuristics running search for better solutions within the defined search space. Within the natural computing algorithms there are the cultural and genetic algorithms. These are evolutionary metaheuristics complement each other due to the dual mechanism of cultural heritage/genetic. The purpose of this paper is to study and use such mechanisms adding local search heuristics and multipopulation applied to combinatorial optimization problems (knapsack and travel salesman problems), constrained problems and multimodal functions. Some experiments have been conducted to assess the performance of the proposed combination of meta-heuristisc and heuristics mechanisms against approaches found in literature as applied to problem addressed here.

Submitted by Fabielle Cheuczuk (fabielle.cheuczuk@unioeste.br) on 2017-11-30T13:22:04Z No. of bitstreams: 2 liro s. w. 2017.pdf: 2354107 bytes, checksum: 3a3d7bd6afbbedf2b5055cb60c32b347 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-11-30T13:22:05Z (GMT). No. of bitstreams: 2 liro s. w. 2017.pdf: 2354107 bytes, checksum: 3a3d7bd6afbbedf2b5055cb60c32b347 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-08-18 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work seeks to identify and to analyze the agricultural activities which optimize income in a rural family property using linear programming, called software Lindo, considering limits or restrictions of size, labor and financial resources. The methodology included the IBGE data analysis, among other official data sources to define the main agricultural activities of the region, including forest production or reforestation activities, fruits and vegetables, characterized as optimization model. Six scenarios were considered in the model, varying the amount of labor, as a restriction in each scenario. The results showed that, regardless of the amount of labor used, garlic is the main activity of the model, being cultivated in all scenarios, with demand of approximately 70% of all labor. Another clear point of the result in the optimization model is that in the scenarios with greater availability of labor the model opt for more intensive activities, this happens in the scenarios 04, 05 and 06, from the use of four people or above , during the year, with peach and strawberry cultivation. In contrast, with less labor availability, as in scenarios 01, 02 and 03, it opts for the use of most of the area with less labor-intensive activities, such as soybeans with maize (crop and mini crop) and soybean (crop and mini crop). Although the size of the property is a limiting factor, with the use of a larger number of people, that is, of labor, income generation is possible and feasible, respecting the choice of activities that compensate for its use. / Este trabalho procura identificar e analisar as atividades agrícolas que otimizam a renda em uma propriedade familiar rural utilizando-se da programação linear, por meio do software Lindo, considerando limites ou restrições de tamanho, mão de obra e recursos financeiros. A metodologia incluiu a análise de dados do IBGE, dentre outras fontes de dados oficiais para definição das principais atividades agrícolas da região, incluindo atividades de produção florestal ou reflorestamento, frutas e verduras, caracterizadas como modelo de otimização. Foram considerados seis cenários no modelo, variando a quantidade de mão de obra, como restrição em cada cenário. Os resultados apontaram que independentemente da quantidade de mão de obra utilizada, o alho é a principal atividade do modelo, sendo cultivada em todos os cenários, com demanda de aproximadamente 70% de toda a mão de obra. Outro apontamento claro do resultado do modelo de otimização, é que nos cenários com maior disponibilidade de mão de obra o modelo opta por atividades mais intensivas por esta, isto acontece nos cenários 04, 05 e 06, a partir do uso de quatro pessoas ou acima, durante o ano, com cultivo também de pêssego e morango. De modo contrário com menor disponibilidade de mão de obra, como nos cenários 01, 02 e 03, opta pelo uso da maior parte da área com atividades menos intensivas em mão de obra, como soja com milho (safra e safrinha) e soja (safra e safrinha). Apesar do tamanho da propriedade ser um fator limitante, com o uso de um maior número de pessoas, ou seja, de mão de obra, a geração de renda é possível e viável , respeitando-se a escolha de atividades que compensem a sua utilização.

A geração hidrelétrica é dependente da afluência, no entanto, é possível minimizar a variação da energia natural afluente por meio dos reservatórios. Por sua vez, a geração eólica tem como desvantagem a volatilidade devido a sua dependência em relação ao vento. Nesse sentido, uma carteira otimizada de projetos eólicos possibilita a redução da volatidade da energia gerada pelo conjunto, na medida em que aproveita as complementariedades do vento. No Brasil, os Estados da Bahia, Rio Grande do Norte, Ceará, Rio Grande do Sul e Piauí concentram 90% da capacidade instalada das usinas eólicas em operação, em construção ou contratada, com uma previsão da fonte atingir 11,6% de participação na matriz elétrica. A pesquisa tem como objetivo desenvolver uma metodologia de apoio baseada na teoria de portifólio de Markowitz que poderá ser utilizada pelo órgão de planejamento energético brasileiro para a definição da quantidade de energia a ser contratada por fonte e local, por meio de leilões de energia regionais e por fonte, com o objetivo de se obter uma carteira otimizada de empreendimentos, que reduza a volatilidade. O método também pode servir de apoio ao investidor para se obter um portfólio de usinas que minimize o risco de exposição financeira no mercado de curto prazo. Nenhum estudo aplicando a teoria de portifólio de Markowitz em usinas eólicas do Brasil foi encontrado na literatura. Os resultados obtidos demonstram que a carteira formada pelas usinas eólicas existentes não está na fronteira eficiente e poderia ser otimizada com aumento da expectativa de geração ou redução do risco. No mesmo sentido, a otimização da carteira também reduziu o risco de exposição ao mercado de curto prazo. / Even though the hydroelectric generation is highly dependent on the river flows, it is possible to minimize the volatility of the energy generation in a given period using the storage capacity of the reservoirs. In contrast, to minimize the volatility of the wind generation is burdensome due to its dependency on wind. Accordingly, an optimized portfolio of wind projects all together allows the reduction of the volatility of the energy generation for the complementarity of wind from different locations. In Brazil, the states of Bahia, Rio Grande do Norte, Ceara, Rio Grande do Sul and Piauí concentrate 90% of the installed capacity of wind power plants in operation, under construction or contracted with a font forecast to reach 11.6% share the electric matrix. The Thesis aims to develop a support methodology based in portfolio theory of Markowitz that can be used by the Brazilian-planning agency in future, to define the amount of energy to be contracted by source and location, through regional and source energy auctions, to obtain an optimized portfolio projects, with reduced volatility. The methodology can also serve to support the investor to obtain a portfolio of plants that minimize the risk of financial exposure to short-term market. No study applying Markowitz\'s portfolio theory in wind farms of Brazil was found in the literature. The results show that the portfolio of the existing wind farms is not on the efficient frontier and could be optimized with increased expectation of generating or reducing the risk. Similarly, the optimization of the portfolio also reduced the risk of exposure to short-term market.

Submitted by Maria Aparecida (cidazen@gmail.com) on 2017-08-24T14:39:48Z No. of bitstreams: 1 José Artur.pdf: 1071380 bytes, checksum: e1992e06fe45627db90b9f36e8a88d84 (MD5) / Made available in DSpace on 2017-08-24T14:39:48Z (GMT). No. of bitstreams: 1 José Artur.pdf: 1071380 bytes, checksum: e1992e06fe45627db90b9f36e8a88d84 (MD5) Previous issue date: 2012-09-21 / This master dissertation presents a optimization mathematical programming model derived from the classical problem of transport, which aims to scale, with global optimization, the fleet of a system of road passenger transport, describing possible routes between each source/target to meet the constraints of cost (profitability) and quality of service. It covers classic methods of solution of linear programming models considered streaming networks and proposes improvements to the canonical model of the transport problem from the perspective of transit planning, and analyze the use of dynamic programming, evolutionary methods and heuristics for solving the problem of minimization of the model. / Neste trabalho é apresentado um modelo de otimização derivado do problema clássico de transporte, que tem a finalidade de dar suporte ao planejamento de transporte de passageiros , com otimização global, dimensionando a frota de veículos de transporte rodoviário, qualificando as rotas possíveis entre cada origem/destino para satisfazer as restrições de custo (rentabilidade) e qualidade de serviço. Abrange métodos clássicos de solução de modelos de programação linear considerados de fluxo contínuo de redes e propõe melhorias no modelo canônico do problema de transporte a partir da perspectiva do planejamento operacional, além de analisar o uso de métodos de programação dinâmica, métodos evolutivos e heurísticos para a solução do problema de minimização.

A geração hidrelétrica é dependente da afluência, no entanto, é possível minimizar a variação da energia natural afluente por meio dos reservatórios. Por sua vez, a geração eólica tem como desvantagem a volatilidade devido a sua dependência em relação ao vento. Nesse sentido, uma carteira otimizada de projetos eólicos possibilita a redução da volatidade da energia gerada pelo conjunto, na medida em que aproveita as complementariedades do vento. No Brasil, os Estados da Bahia, Rio Grande do Norte, Ceará, Rio Grande do Sul e Piauí concentram 90% da capacidade instalada das usinas eólicas em operação, em construção ou contratada, com uma previsão da fonte atingir 11,6% de participação na matriz elétrica. A pesquisa tem como objetivo desenvolver uma metodologia de apoio baseada na teoria de portifólio de Markowitz que poderá ser utilizada pelo órgão de planejamento energético brasileiro para a definição da quantidade de energia a ser contratada por fonte e local, por meio de leilões de energia regionais e por fonte, com o objetivo de se obter uma carteira otimizada de empreendimentos, que reduza a volatilidade. O método também pode servir de apoio ao investidor para se obter um portfólio de usinas que minimize o risco de exposição financeira no mercado de curto prazo. Nenhum estudo aplicando a teoria de portifólio de Markowitz em usinas eólicas do Brasil foi encontrado na literatura. Os resultados obtidos demonstram que a carteira formada pelas usinas eólicas existentes não está na fronteira eficiente e poderia ser otimizada com aumento da expectativa de geração ou redução do risco. No mesmo sentido, a otimização da carteira também reduziu o risco de exposição ao mercado de curto prazo. / Even though the hydroelectric generation is highly dependent on the river flows, it is possible to minimize the volatility of the energy generation in a given period using the storage capacity of the reservoirs. In contrast, to minimize the volatility of the wind generation is burdensome due to its dependency on wind. Accordingly, an optimized portfolio of wind projects all together allows the reduction of the volatility of the energy generation for the complementarity of wind from different locations. In Brazil, the states of Bahia, Rio Grande do Norte, Ceara, Rio Grande do Sul and Piauí concentrate 90% of the installed capacity of wind power plants in operation, under construction or contracted with a font forecast to reach 11.6% share the electric matrix. The Thesis aims to develop a support methodology based in portfolio theory of Markowitz that can be used by the Brazilian-planning agency in future, to define the amount of energy to be contracted by source and location, through regional and source energy auctions, to obtain an optimized portfolio projects, with reduced volatility. The methodology can also serve to support the investor to obtain a portfolio of plants that minimize the risk of financial exposure to short-term market. No study applying Markowitz\'s portfolio theory in wind farms of Brazil was found in the literature. The results show that the portfolio of the existing wind farms is not on the efficient frontier and could be optimized with increased expectation of generating or reducing the risk. Similarly, the optimization of the portfolio also reduced the risk of exposure to short-term market.

Um dos maiores desafios envolvidos no projeto de grades computacionais é o escalonamento de processos, o qual consiste no mapeamento de processos sobre os computadores disponíveis, a fim de reduzir o tempo de execução de aplicações ou maximizar a utilização de recursos. A literatura na área de Sistemas Distribuídos trata, geralmente, esses dois objetivos separadamente, dando origem às abordagens de escalonamento orientado a aplicações e orientado a recursos, respectivamente. Mais recentemente, uma nova abordagem, denominada escalonamento orientado a sistemas, tem recebido destaque, buscando otimizar ambos objetivos simultaneamente. Seguindo essas abordagens, algoritmos heurísticos e de aproximação têm sido propostos. Os heurísticos buscam por soluções de maneira eficiente sem, contudo, apresentar garantias quanto à qualidade das soluções obtidas. Em contrapartida, os algoritmos de aproximação provêm tais garantias, contudo são mais difíceis de serem projetados, o que justifica o fato de haver apenas versões simplificadas desses algoritmos para cenários de escalonamento de processos. A falta de algoritmos de aproximação adequados para abordar o problema de escalonamento de processos e a necessidade de soluções que atendam o escalonamento orientado a sistemas motivaram esta tese de doutorado que apresenta a proposta do Min Heap-based Scheduling Algorithm (MHSA), um algoritmo de aproximação para o problema de escalonamento de processos orientado a sistemas. Esse algoritmo foi baseado em um modelo de otimização matemática proposto no contexto desta tese. Esse modelo considera os comportamentos de processos e recursos a fim de quantificar a qualidade de soluções de escalonamento. O funcionamento do MHSA envolve a construção de uma árvore min-heap, em que os nós representam computadores e as chaves de ordenação correspondem aos tempos de fila, i.e., ocupação dos computadores. Apesar de esse algoritmo primordialmente reduzir o tempo de execução (ou makespan) de aplicações, essa estrutura em árvore permite que qualquer computador que ocupe o nó raiz receba cargas, o que favorece a ocupação de recursos e, portanto, sua orientação a sistemas. Esse algoritmo tem complexidade assintótica de pior caso igual a O(\'log IND. 2 m\'), em que m corresponde ao número de computadores do sistema. Sua razão de aproximação foi estudada para ambientes distribuídos heterogêneos com e sem a presença de comunicação entre processos, o que permite conhecer, a priori, o nível mínimo de qualidade alcançado por suas soluções. Experimentos foram conduzidos para avaliar o algoritmo proposto e compará-lo a outras propostas. Os resultados confirmam que o MHSA reduz o tempo dispendido na obtenção de boas soluções de escalonamento / One of the most important challenges involved in the design of grid computing systems is process scheduling, which maps applications into the available computers in attempt to reduce the application execution time, or maximize resource utilization. The literature of Distributed Systems usually deals with these two objectives separately, supporting the application-centric and the resourcecentric scheduling, respectively. More recently, a third approach referred to as system-centric scheduling has emerged which attempts to optimize both objectives in conjunction. Heuristic-based and approximation-based algorithms have been proposed to address this third type of scheduling. Heuristics aim to find good solutions at acceptable time constraints, without guaranteeing solution quality. On the other hand, approximation-based algorithms provide optimal solution bounds, however they are more difficult to design what makes them available only to simple scenarios. The need for approximation-based algorithms to support system-centric scheduling has motivated this thesis which presents Min Heap-based Scheduling Algorithm (MHSA). This approximation algorithm is based on a mathematical optimization model, also proposed in this work, which considers process and resource behaviors to measure the quality of scheduling solutions. MHSA builds a min-heap data structure in which tree nodes represent computers and sorting keys correspond to queuing times, i.e., computer workloads. Besides this algorithm primarily reduces application execution times (also referred to as makespan), its data structure allows any computer assume the root node and, consequently, receive workloads, what favors resource utilization. This algorithm has the worst-case time complexity equals to O(\'log IND. 2 m\'), in which m represents the number of system computers. Its approximation ratio was analyzed to heterogeneous distributed systems considering bag-of-tasks and communication-intensive applications. Having this ratio, we know the minimum quality level provided by every scheduling solution. Experiments were performed to compare MHSA to others. Results confirm MHSA reduces the time spent to obtain good quality scheduling solutions

Um dos maiores desafios envolvidos no projeto de grades computacionais é o escalonamento de processos, o qual consiste no mapeamento de processos sobre os computadores disponíveis, a fim de reduzir o tempo de execução de aplicações ou maximizar a utilização de recursos. A literatura na área de Sistemas Distribuídos trata, geralmente, esses dois objetivos separadamente, dando origem às abordagens de escalonamento orientado a aplicações e orientado a recursos, respectivamente. Mais recentemente, uma nova abordagem, denominada escalonamento orientado a sistemas, tem recebido destaque, buscando otimizar ambos objetivos simultaneamente. Seguindo essas abordagens, algoritmos heurísticos e de aproximação têm sido propostos. Os heurísticos buscam por soluções de maneira eficiente sem, contudo, apresentar garantias quanto à qualidade das soluções obtidas. Em contrapartida, os algoritmos de aproximação provêm tais garantias, contudo são mais difíceis de serem projetados, o que justifica o fato de haver apenas versões simplificadas desses algoritmos para cenários de escalonamento de processos. A falta de algoritmos de aproximação adequados para abordar o problema de escalonamento de processos e a necessidade de soluções que atendam o escalonamento orientado a sistemas motivaram esta tese de doutorado que apresenta a proposta do Min Heap-based Scheduling Algorithm (MHSA), um algoritmo de aproximação para o problema de escalonamento de processos orientado a sistemas. Esse algoritmo foi baseado em um modelo de otimização matemática proposto no contexto desta tese. Esse modelo considera os comportamentos de processos e recursos a fim de quantificar a qualidade de soluções de escalonamento. O funcionamento do MHSA envolve a construção de uma árvore min-heap, em que os nós representam computadores e as chaves de ordenação correspondem aos tempos de fila, i.e., ocupação dos computadores. Apesar de esse algoritmo primordialmente reduzir o tempo de execução (ou makespan) de aplicações, essa estrutura em árvore permite que qualquer computador que ocupe o nó raiz receba cargas, o que favorece a ocupação de recursos e, portanto, sua orientação a sistemas. Esse algoritmo tem complexidade assintótica de pior caso igual a O(\'log IND. 2 m\'), em que m corresponde ao número de computadores do sistema. Sua razão de aproximação foi estudada para ambientes distribuídos heterogêneos com e sem a presença de comunicação entre processos, o que permite conhecer, a priori, o nível mínimo de qualidade alcançado por suas soluções. Experimentos foram conduzidos para avaliar o algoritmo proposto e compará-lo a outras propostas. Os resultados confirmam que o MHSA reduz o tempo dispendido na obtenção de boas soluções de escalonamento / One of the most important challenges involved in the design of grid computing systems is process scheduling, which maps applications into the available computers in attempt to reduce the application execution time, or maximize resource utilization. The literature of Distributed Systems usually deals with these two objectives separately, supporting the application-centric and the resourcecentric scheduling, respectively. More recently, a third approach referred to as system-centric scheduling has emerged which attempts to optimize both objectives in conjunction. Heuristic-based and approximation-based algorithms have been proposed to address this third type of scheduling. Heuristics aim to find good solutions at acceptable time constraints, without guaranteeing solution quality. On the other hand, approximation-based algorithms provide optimal solution bounds, however they are more difficult to design what makes them available only to simple scenarios. The need for approximation-based algorithms to support system-centric scheduling has motivated this thesis which presents Min Heap-based Scheduling Algorithm (MHSA). This approximation algorithm is based on a mathematical optimization model, also proposed in this work, which considers process and resource behaviors to measure the quality of scheduling solutions. MHSA builds a min-heap data structure in which tree nodes represent computers and sorting keys correspond to queuing times, i.e., computer workloads. Besides this algorithm primarily reduces application execution times (also referred to as makespan), its data structure allows any computer assume the root node and, consequently, receive workloads, what favors resource utilization. This algorithm has the worst-case time complexity equals to O(\'log IND. 2 m\'), in which m represents the number of system computers. Its approximation ratio was analyzed to heterogeneous distributed systems considering bag-of-tasks and communication-intensive applications. Having this ratio, we know the minimum quality level provided by every scheduling solution. Experiments were performed to compare MHSA to others. Results confirm MHSA reduces the time spent to obtain good quality scheduling solutions