[pt] A alta complexidade do processo logístico de transporte ferroviário de carga, propicia um ambiente favorável para o desenvolvimento de ferramentas de apoio à decisão que possibilitam uma melhor utilização dos recursos envolvidos. Neste trabalho é apresentado um modelo de programação inteira original para o Problema da Alocação ótima de Vagões e Locomotivas no curto prazo (PAVL). Esse problema consiste em determinar a movimentação de vagões (carregados e vazios) e locomotivas na malha de maneira a maximizar o retorno obtido pela demanda atendida no período considerado. Além disso, é apresentada uma extensão para esse modelo onde se permite atrasar ou adiantar trens no primeiro dia do horizonte de planejamento. Esse problema foi resolvido de maneira ótima ou quase ótima em tempo razoável, tanto em termos acadêmicos como para sua utilização prática. São apresentados o problema, a formulação do modelo, as técnicas de pré-processamento utilizadas, assim como resultados computacionais de instâncias reais. / [en] The complexity of the logistic process in railway freight transportation provides a natural environment for the development of decision support tools that allow the companies to make a more efficient use of their resources. In this work we present an original integer programming model for the Cars and Locomotives short-term Allocation Problem. This problem consists in determining the movement of the cars (loaded and empty) and locomotives on the railway network in order to maximize the profit obtained with the requested demand in the given period. We also present an extension of the model in which certain delays and anticipations of trains on the first day of the period are allowed. For all instances tested, this problem was solved to optimality or near-optimality in a reasonable time, either for academic or practical purposes. We present a description of the problem, the mathematical formulation, the preprocessing techniques used, as well as the computational results obtained.

[pt] A indústria das comunicações tem passado nos últimos anos, mundialmente, por profundas transformações. A Internet é a responsável pela maior destas transformações. Com o advento da Internet, existe a necessidade de uma banda de transmissão maior para o tráfego de dados. Para resolver esse problema, surgiu o conceito de redes ópticas e a multiplexação no domínio do comprimento de onda. Entretanto, isso criou um outro problema: o roteamento dos pacotes. A maior parte das redes de comunicação hoje em dia, ainda possui muitos sinais eletrônicos, o que significa que os sinais ópticos precisam ser convertidos em elétricos para serem ampliados, regenerados ou roteados e, depois, reconvertidos para ópticos. Isso acaba gerando atrasos na transmissão dos sinais e um gargalo nas redes ópticas. Para minimizar este problema, vários algoritmos foram criados. Apegando-se a tais fatos, este estudo explora o tema para implementar um algoritmo de enumeração recursiva, que tem como objetivo alocação de comprimentos em redes ópticas, visando minimizar o custo total de transmissão. Esse algoritmo foi testado e comparado com o algoritmo de programação linear, que fornece a solução ótima. / [en] The communication industry was passing in lastest years by great transformations in world. Internet is the mainly responsable for that, because there is the necessity of a large band to data transmission. The optical networks concept and wavelength division multiplexing technology were arised in order to solve this problem. However, this created another problem: the packet routing. The major part of communications networks still has electronics signals. This means that the optical signals have to be converted into electrical signals to be amplified, regenerated and routed and later recovered into optical. This implies in a delay on the data transmission and creates a bottleneck in the optical networks. Some algorithms have been created to minimize this problem. This dissertation has tried to develop an algorithm to solve RWA (routing and wavelength assignment) problems, aiming at the minimum total cost to transmitt datas. This algorithm was tested and compared with the linear program algorithm that gives the optimal solution to RWA problem.

[pt] O objetivo desta dissertação é desenvolver um método de solução baseado em Algoritmos Genéticos (GAs) aliado a um Sistema Baseado em Regras para encontrar e otimizar as soluções geradas para o problema de programação da produção de Óleos Combustíveis e Asfalto na REVAP (Refinaria do Vale do Paraíba). A refinaria é uma planta multiproduto, com dois estágios de máquinas em série - um misturador e um conjunto de tanques, com restrição de recursos e operando em regime contínuo. Foram desenvolvidos neste trabalho dois modelos baseados em algoritmos genéticos que são utilizados para encontrar a seqüência e os tamanhos dos lotes de produção dos produtos finais. O primeiro modelo proposto utiliza uma representação direta da programação da produção em que o horizonte de programação é dividido em intervalos discretos de um hora. O segundo modelo proposto utiliza uma representação indireta que é decodificada para formar a programação da produção. O Sistema Baseado em Regras é utilizado na escolha dos tanques que recebem a produção e os tanques que atendem à demanda dos diversos centros consumidores existentes. Um novo operador de mutação - Mutação por Vizinhança - foi proposto para minimizar o número de trocas operacionais na produção. Uma técnica para agregação de múltiplos objetivos, baseado no Método de Minimização de Energia, também foi incorporado aos Algoritmos Genéticos. Os resultados obtidos confirmam que os Algoritmos Genéticos propostos, associados com o Método de Minimização de Energia e a Mutação por Vizinhança, são capazes de resolver o problema de programação da produção, otimizando os objetivos operacionais da refinaria. / [en] The purpose of this dissertation is to develop a method, based on Genetics Algorithms and Rule Base Systems, to optimize the production scheduling of fuel oil and asphalt area in a petroleum refinery. The refinery is a multi- product plant, with two machine stages - one mixer and a set of tanks - with no setup time and with resource constrains in continuous operation. Two genetic algorithms models were developed to establish the sequence and the lot- size of all production shares. The first model proposed has a direct representation of the production scheduling which the time interval of scheduling is shared in one hour discrete intervals. The second model proposed has a indirect representation that need to be decoded in order to make the real production scheduling. The Rule Base Systems were developed to choice the tanks that receive the production and the tanks that provide the demand of the several consumer centers. A special mutation operator - Neighborhood Mutation - was proposed to minimize the number of changes in the production. A Multi-objective Fitness Evaluation technique, based on a Energy Minimization Method, was also incorporated to the Genetic Algorithm models. The results obtained confirm that the proposed Genetic Algorithm models, associated with the Multi- objective Energy Minimization Method and the Neighborhood Mutation, are able to solve the scheduling problem, optimizing the refinery operational objectives. / [es] El objetivo de esta disertación es desarrollar un método de solución utilizando Algoritmos Genéticos (GAs) aliado a un Sistema Basado en Reglas para encontrar y optimizar las soluciones generadas para el problema de programación de la producción de Aceites Combustibles y Asfalto en la REVAP (Refinería del Valle de Paraíba). La refinería es una planta multiproducto, con dos estados de máquinas en serie - un mezclador y un conjunto de tanques, con restricción de recursos y operando en régimen contínuo. En este trabajo se desarrollaron dos modelos basados en algoritmos genéticos que son utilizados para encontrar la secuencia y los tamaños de los lotes de producción de los productos finales. El primer modelo propuesto utiliza una representación directa de la programación de la producción en la cuál el horizonte de programación se divide en intervalos discretos de un hora. El segundo modelo, utiliza una representación indirecta que es decodificada para formar la programación de la producción. EL Sistema Basado en Reglas se utiliza en la selección de los tanques que reciben la producción y los tanques que atienden a la demanda de los diversos centros consumidores. Un nuevo operador de mutación - Mutación por Vecindad - fue propuesto para minimizar el número de cambios operacionales en la producción. le fue incorporado a los Algoritmos Genéticos una técnica para la agregación de múltiples objetivos, basado en el Método de Minimización de Energía. Los resultados obtenidos confirman que los Algoritmos Genéticos propuestos, asociados al Método de Minimización de Energía y la Mutación por Vecindad, son capazes de resolver el problema de programación de la producción, optimizando los objetivos operacionales de la refinería.

[pt] A década de 90 foi marcante para a indústria de eletricidade, com a introdução de mercados competitivos em que os agentes geradores são livres para tomar suas decisões de produção e investimento, assumindo integralmente os riscos decorrentes de suas estratégias. O despacho e o preço spot neste tipo de mercado são definidos através de leilões diários, onde os agentes fornecem seus lances de preços/quantidades que expressam suas disposições em vender ou comprar energia. Os lances aceitos nos leilões, que estabelecem compromissos de geração, são definidos um dia antes da energia ser fisicamente gerada e injetada na rede. A ocorrência de eventos improváveis, como quebra de máquinas ou alterações nas condições meteorológicas, gera a necessidade de ajustes para compensar os desequilíbrios entre geração e carga, e para isso criaram-se mercados de ajustes. A base experimental do trabalho foi o Nord Pool, o mercado livre de energia dos países nórdicos que possui um mercado de ajustes chamado Elbas. Neste trabalho foi desenvolvido um modelo computacional que otimiza a estratégia de oferta de um agente hidrelétrico price-taker atuando no Nord Pool, que além de representar de forma detalhada as características operativas das usinas, leva em conta as negociações no mercado Elbas e o nível de aversão a risco do agente gerador, através da função objetivo que maximiza uma combinação convexa do valor esperado e do CVaR (Conditional Value at Risk) da renda líquida obtida da venda de energia. Cenários de preços spot e do mercado Elbas foram gerados baseados em modelos de séries temporais ARMA e GARCH, e para reduzir o esforço computacional e viabilizar o uso de um número adequado de cenários foram utilizadas técnicas de decomposição de Benders e Benders Multicut. O modelo desenvolvido possibilitou estudar a atuação dos agentes nos mercados spot e Elbas sob dois pontos de vista distintos: sob a ótica dos geradores, que buscam maximizar suas margens operacionais; e sob a ótica do regulador, cujo foco é investigar se o mercado Elbas cumpre seu papel de equilibrar a oferta e a demanda, e não fazendo com que os geradores especulem através de estratégias conjuntas nos dois mercados. Todos esses efeitos foram estudados e analisados para diferentes perfis de risco dos agentes e diferentes condições de mercado, ou seja, considerando períodos de diferentes volatilidades dos preços praticados no mercado Elbas e diferentes valores (ou custos de oportunidade) da água armazenada nos reservatórios das usinas hidrelétricas. Sob a ótica do agente, o trabalho mostrou que há um incentivo para o agente neutro a tentar usufruir de possíveis preços mais altos no mercado Elbas que os praticados no spot. Sob a ótica do regulador, os resultados mostram que o agente menos avesso a risco, dependendo das condições de mercado, opta por deslocar parte de sua energia do mercado spot para o Elbas, mostrando seu apetite por ganhos maiores independentemente do risco associado às suas decisões. O agente avesso a risco opta por transacionar menos energia no Elbas, principalmente em períodos mais voláteis, evitando com isso os piores cenários. Finalmente, considerando que normalmente empresas de energia são avessas a risco, o modelo de ajustes através do mercado Elbas se mostrou adequado, cumprindo naturalmente seu papel sem a necessidade de interferência do regulador. / [en] The widespread introduction of competitive mechanisms during the 1990s changed the panorama of the electricity industry around the world. Vertically integrated and centrally operated systems were replaced by market environments in which generators became free to make their production and investment decisions and, at the same time, assume the risk of their chosen strategies. Both the dispatch and the energy spot price in such markets result from two-sided auctions in which producing and consuming agents submit their price-quantity bids, expressing how much energy they are willing to buy or sell. The accepted bids, which commit agents to either deliver or consume power, are set a day before the energy delivery. However, since unexpected events may occur - such as changes in weather conditions or breakdowns of generation turbines - some adjustments might have to be done in order to compensate for the unbalances between total generation and load. These adjustments usually take place in the balancing markets. In the present work, we propose an optimization model for a price-taking hydropower producer who trades energy in the Nord Pool – the competitive electricity market encompassing the Nordic countries that comprises a balancing market called Elbas. The proposed model represents in details the operating aspects of the plants and takes into account the possibility of trading energy in the Elbas market. The model represents the level of risk aversion of the agent in its objective function, by maximizing a convex combination of the expected value and the CVaR (Conditional Value at Risk) of the net income obtained. Scenarios of spot and Elbas prices were generated based on time series models ARMA and GARCH and, in order to reduce the computational effort and enable the use of an adequate number of scenarios, Benders decomposition and Benders Multicut methods were applied. The developed model allowed us to study the behavior of agents in the spot and Elbas markets under two different viewpoints: from the perspective of the generators, which aim at maximizing its operating income; and from the viewpoint of the regulator, whose focus is on analyzing whether the Elbas market meets its role of balancing supply and demand, rather than leading generators to speculate through combined strategies in both markets. All these effects were studied and analyzed for different risk-averse profiles of the agents, and for different market conditions, i.e., considering periods of different volatilities of Elbas market prices and different water values (or opportunity costs) stored in the reservoirs of the hydroelectric power plants. From the perspective of the agent, the study showed that there are incentives for the risk- neutral agent to try to take advantage of possible higher prices in the Elbas. From the regulator’s viewpoint, the results show that the risk-neutral agents, depending on market conditions, choose to shift some of its energy generation to the Elbas market, showing their desire for higher incomes regardless of the risk associated with their decisions. The risk-averse agent chooses to trade less energy in Elbas, especially in volatile periods, thereby avoiding the worst scenarios. Finally, considering that energy companies are usually risk-averse, the adjustments made in the Elbas market were shown to be adequate, naturally meeting its role without requiring interventions from the regulator.

[pt] A organização lógica de data centers recai principalmente na questão estratégica de distribuir os serviços nos equipamentos de forma que os custos operacionais sejam os menores possíveis. Além desses custos, devem ser considerados outros aspectos que envolvem a interdependência de seus serviços internos e a distribuição entre suas localidades, visando assim melhorar a qualidade de seu produto aos seus clientes. Este trabalho explora o problema de atribuição de processos a máquinas do desafio ROADEF de 2012 pelos métodos de programação inteira e geração de colunas. Apresenta estratégias para lidar com as dificuldades numéricas encontradas. Na geração de colunas, analisa técnicas para acelerar a convergência, por meio de resolver o mestre restrito após cada variável, geração prévia de colunas e estabilização das variávies duais. Ao final do trabalho, são comparados os resultados obtidos com os melhores resultados oficiais. / [en] A data center logic organization lies mainly by the strategic decision on how distribute services between machines, so the operational costs should be the smallest as possible. Beside those costs, must also consider the interdependence of their own services, the distribution between their localities, to improve the quality of their product to their customers. This work explores the challenge ROADEF 2012 machine assignment problem by the means of integer programming and column generation. Shows strategies to address numeric issues. At column generation, it analyzes techniques to speed up the convergence, by solving after each variable adiction, a previous generation of columns and stabilization of duals variables. At the end of the work, it compares the results obtained are compared with the best official results.

[pt] Os problemas de transporte marítimo são alvo de extensa bibliografia e constituem uma importante área de aplicação da programação matemática. Em particular, o transporte de granéis - entre os quais o petróleo e seus derivados - vem sendo estudado na Petrobrás há mais de duas décadas. Apesar dos esforços despendidos, os escopos das aplicações são ainda algo limitados e os resultados práticos relativamente escassos. O presente trabalho contribui para sistematização da área, definindo uma hierarquia de problemas de transporte marítimo, padronizando conceitos e notação e desenvolvendo modelos para cada classe de aplicação. São discutidos também alguns métodos de solução e propostos procedimentos para incrementar seus desempenhos. Dois destes métodos, designados por modelo de rotas e modelo de recobrimento, são implementados para instâncias de porte real e os resultados obtidos são analisados. / [en] Sea transportation problems have been the object of extensive literature and constitute an important area for the application of mathematical programming techniques. Bulk commodities transportation, particulary of oil and its by-products, has been studied at Petrobras for over two decades. Despite all efforts, the application scopes are still rather limeted and practical results relatively scarce. The present study contributes for a systenatization in the area, defining a hierarchy of sea transportation problems, standardizing concepts and terminology and developing models for each class of application. Some solution methods are also discussed and procedures are proposed to develop their performance. Two of these methods, named Routing model and instances and the results attained are anlysed.

[pt] O uso de multithreading tem se popularizado como forma de separar a execução de tarefas concorrentes e de alcançar maior desempenho aproveitando melhor o tempo das CPUs. No entanto, a programação com threads não é uma tarefa fácil. O uso dos recursos compartilhados deve ser coordenado, pois o acesso concorrente aos mesmos, na maioria dos casos, gera inconsistência na aplicação. O modelo de desenvolvimento orientado a eventos foi apontado por alguns como uma boa alternativa na criação de aplicações. Nesse modelo, a tarefa é realizada por um ou mais eventos, e um loop principal fica responsável por receber e despachar esses eventos. Investigamos, neste trabalho, um modelo em Lua que combina orientação a eventos com preempção sem trazer de volta os problemas de programação concorrente. Investigamos também como características da linguagem podem ser utilizadas para prover mecanismos de coordenação flexíveis. Essas características podem ajudar, por exemplo, a compor novos mecanismos a partir de existentes. / [en] Multithreading has become popular as a way to organize concurrent tasks and achieve better performance from CPUs. However, programming with threads is not an easy task. Usage of shared resources needs to be coordinated because concurrent access to them, in most cases, may create inconsistency in the application. The event-driven model has been pointed as a good alternative to multithreaded programming. In this model, a task is performed by one or more events, where a main loop is responsible for receiving and dispatching these events. In this work, we investigate a model to combine event-driven and preemption in Lua without bringing back all the concurrent programming problems. We also investigate how the language’s characteristics can be used to provide flexible coordination mechanisms. These characteristics can aid, for example, to create new mechanisms based on the ones already existent.

[pt] Este trabalho se propõe a estudar a mídia televisiva a partir de um mecanismo estratégico utilizado pela Rede Globo de Televisão, que pretende criar uma interação permanente entre a audiência e o conteúdo de suas novelas. A pesquisa estuda as relações que, através desse mecanismo, a emissora de televisão pretende estabelecer com seus telespectadores. Além de estudar as repercussões dessa estratégia massiva e permanente nos ambientes culturais da contemporaneidade, esse trabalho desvenda de que forma a mídia de chamadas de programação de uma telenovela é confeccionada, mostrando os instrumentos usados pela Rede Globo para alcançar seu objetivo de agendamento de seus temas junto à audiência. Investiga também, de que maneira essa mídia de chamada de programação pretende incorporar o conteúdo da telenovela nos discursos interpessoais. / [en] This work intends to study television media starting from a strategic mechanism used by Rede Globo de Televisão (Globo TV Network) that pretends to create a permanent interaction between the viewers and the contents of its soapoperas. The research will study the relations pretended to be established by the network with its audience through this mechanism. Aside of studying the repercussions of this massive and permanent strategy in cultural environment, this work will unmask how the commercial break calls media of a soap-opera is made, showing the instruments used by Globo Network to reach the aims of scheduling its themes next to the audience. It will investigate too by which means this media of commercial break calls intends to incorporate the soapopera s content in interpersonal speech.

[pt] Diversas tarefas de Visão Computacional (VC) são formadas por operações aritméticas, replicadas sobre grandes volumes de dados. Esta caracterização descreve também as qualidades desejadas ao considerar uma aplicação qualquer como boa candidata a usufruir do crescente poder de processamento do hardware gráfico. Esta tese formula um conjunto de algoritmos de VC sobre representações do conteúdo visual em baixo nível, para serem processados em GPU. Dando suporte às propostas, são apresentadas uma visão geral das GPUs e de padrões de programação paralelos, os quais oferecem blocos construtores para tarefas de visão. Neste sentido, propomos uma definição formal para o padrão de Redução Múltipla e analisamos seu desempenho segundo diferentes fatores de redução e variações para seus arranjos. Apresentamos duas propostas para extração de informações no espaço da imagem em GPU: a MOCT descreve a localização de objetos identificáveis por suas cores em vídeos naturais, enquanto o operador de Redução Regional Múltipla Paralela (MRR) distribui a computação de operadores definidos sobre diferentes regiões de interesse. Como aplicação do MRR, descrevemos a construção em GPU de um Diagrama Centroidal de Voronoi baseado no algoritmo de Lloyd. Tratamos do conteúdo visual em aglomerados de pixels, mais especificamente, em Quadtrees de regiões. Introduzimos a QuadN4tree, um modelo para representação de quadtrees que permite a navegação através do sistema de vizinhança das folhas e alcança custos ótimos no levantamento do conjunto de vizinhas de uma folha. Em seguida, propomos uma aceleração para aplicações baseadas em minimização de energia via corte de grafo, introduzindo uma etapa de pré-processamento que agrupa pixels similares em folhas de uma quadtree, com o objetivo de reduzir o tamanho do grafo sobre o qual o corte mínimo é encontrado. O método proposto é aplicado ao problema de segmentação de imagens naturais com iluminação ativa. Algumas contribuições desta tese, descrevendo formulações paralelas a dados, foram publicadas nos artigos incluídos nos apêndices. / [en] Arithmetically intensive operations, replicated over huge data sets (usually image pixels or scanned data), are an important part of many Computer Vision (CV) tasks, making them good candidates for taking advantage of the processing power of contemporary graphics processing units (GPUs). This thesis formulates a set of CV algorithms that use low level representations of visual content and are tailored for running on GPUs. A general view of GPUs and parallel programming patterns that offers interesting building blocks for CV tasks provides the necessary background for the algorithms. We also propose a formal definition for the Multiple Reduction pattern and evaluate its efficiency according to different reduction factors and layouts. We present two techniques for extracting data from the image space using the GPU: MOCT, a technique for tracking a set of objects identified by their colors from natural videos, and MRR, a technique for distributing the evaluation of a set of operators defined over different regions of interest within an image. As a MRR application we describe a Centroidal Voronoi Diagram construction based on Lloyds algorithm but entirely computed using GPU resources. We also deal with visual content representations as pixel agglomerations, more specifically, as Regional Quadtrees. We introduce the QuadN4tree: a new model for representing quadtree leaves that allows navigation through their neighborhood systems and achieves an optimal cost for the retrieval of neighbor sets. We also propose modifying the setup for CV applications based on energy minimization via graph cuts, introducing a preprocessing step that groups similar pixels into regional quadtree leaves. This modification aims to reduce the size of the graph for which a minimum cut is to be found. We apply our proposed method to the problem of natural image segmentation by active illumination. Published papers detailing some contributions of this dissertation are included as appendixes. They present data-parallel formulations for the CV tasks we describe.

[pt] Neste trabalho estuda-se a resolução de problemas de otimização e síntese de consultas para recuperação de informações de bancos de dados bibliográficos, através da sua formulação como problemas de programação matemática em variáveis 0-1. Primeiramente é estudado o problema de programação hiperbólica, para o qual foram desenvolvidos algoritmos de complexidade linear. O segundo problema estudado trata de uma extensão do anterior, sendo chamado neste texto de problema de soma hiperbólica. Para este problema são desenvolvidas heurísticas dos tipos simulated annealing e steepest ascent mildest descent (tabu search), além de algoritmos exatos do tipo pesquisa arborescente. Todos os métodos descritos acima foram implementados e são apresentados resultados numéricos. Quanto à otimização de consultas, foram estudados dois problemas básicos: consultas periódicas e síntese de novas, que são formulados como problemas de programação hiperbólica e soma hiperbólica, respectivamente. Foram feitas aplicações considerando-se um banco de dados do Centro de Informações Nucleares da CNEN (Comissão Nacional de Energia Nuclear). / [en] In this work we study the solution of problems arising in the field of queries optimization in information retrieval from classical databases, through their formulation as mathematical problems in 0-1 variables. The first problem studied is the hyperbolic programming problem in 0-1 variables, for which we developed exact linear-time algorithms. The second problem studied is an extension of the former, here named as hyperbolic sum problem. For this problem we developed simulated annealing and steepest ascent-mildest descent (tabu search) heuristics, as well as exact branch-and-bound algorithms. All these methods were implemented and numerical results are presented. Concerning the problem of queries optimization, two basic problems were studied: periodical query and synthesis of new queries, which are formulated respectively as an hyperbolic programming problem and an hyperbolic sum problem. We have also done applications involving these problems, considering real data gathered from a database of Center of Nuclear Information from CNEN (Brazilian National Comission of Nucler Energy)