[pt] O objetivo do planejamento da operação hidrotérmica de médio e longo prazo é definir as metas para geração de cada hidroelétrica e termelétrica, a fim de atender à carga ao menor custo esperado de operação e respeitando as restrições operacionais. Algoritmos de Programação Dinâmica Estocástica (PDE) e de Programação Dinâmica Dual Estocástica (PDDE) têm sido amplamente aplicados para determinar uma política operativa ideal o despacho hidrotérmico. Em ambas as abordagens a estocasticidade das afluências é comumente produzida por modelos periódicos autoregressivos de lag p - PAR(p), cuja estimativa dos parâmetros é baseada nos dados históricos disponíveis. Como os estimadores são funções de fenômenos aleatórios, além da incerteza sobre as vazões, também há incerteza sobre os parâmetros estatísticos, o que não é capturado no modelo PAR (p) padrão. A existência de incerteza nos parâmetros significa que há um risco de que a política da operação hidrotérmica planejada não será a ótima. O objetivo desta tese é apresentar uma metodologia para incorporar a incerteza dos parâmetros do modelo PAR (p) no problema de programação estocástica hidrotérmica. São apresentados estudos de caso ilustrando o impacto da incerteza dos parâmetros nos custos operativos do sistema e como uma política operativa que incorpore esta incerteza pode reduzir este impacto. / [en] The objective of the medium and long-term hydrothermal scheduling problem is to define operational target for each power plant in order to meet the load at the lowest expected cost and respecting the operational constraints. Stochastic Dynamic Programming (SDP) and Stochastic Dual Dynamic Programming (SDDP) algorithms have been widely applied to determine the optimal operating policy for the hydrothermal dispatch. In both approaches, the stochasticity of the inflows is usually produced by periodic auto-regressive models - PAR (p), whose parameters are estimated based on available historical data. As the estimators are a function of random phenomena, besides the inflows uncertainty there is statistical parameter uncertainty, which is not captured in the standard PAR (p) model. The existence of uncertainty in the parameters means that there is a risk that the hydrothermal operating policy will not be optimal. This thesis presents a methodology to incorporate the PAR(p) parameter uncertainty into stochastic hydrothermal scheduling and to assess the resulting impact on the computation of a hydro operations policy. Case studies are presented illustrating the impact of parameter uncertainty in the system operating costs and how an operating policy that incorporates this uncertainty can reduce this impact.

[pt] No planejamento da operação hidrotérmica brasileiro, assim como em outros países hidro dependentes, a Programação Dinâmica Dual Estocástica (PDDE) é utilizada para calcular uma política ótima avessa a risco que, muitas vezes, considera modelos autorregressivos para modelagem das afluências às hidrelétricas. Em aplicações práticas, estes modelos podem induzir a uma variabilidade indesejável de variáveis primais (geração térmica) e duais (custo marginal e preço spot), que são altamente sensíveis a mudanças nas condições iniciais das vazões. Neste trabalho, são propostas duas abordagens diferentes para estabilizar as soluções da PDDE no problema de planejamento da operação energética: a primeira abordagem visa regularizar variáveis primais considerando uma penalidade adicional sobre as mudanças no despacho térmico ao longo do tempo. A segunda abordagem reduz indiretamente a variabilidade da geração térmica e do custo marginal ao ignorar informações de afluências passadas na função de custo futuro e compensando-a com um aumento na aversão ao risco. Para fins de comparação, a qualidade solução foi avaliada com um conjunto de índices propostos que resumem cada aspecto importante de uma política de planejamento hidrotérmico. Em conclusão, mostramos que é possível obter soluções com boa qualidade em comparação com benchmarks atuais e com uma redução significativa variabilidade. / [en] In the hydrothermal energy operation planning of Brazil and other hydro-dependent countries, Stochastic Dual Dynamic Programming (SDDP) computes a risk-averse optimal policy that often considers river-inflow autoregressive models. In practical applications, these models induce an undesirable variability of primal (thermal generation) and dual (marginal cost and spot price) solutions, which are highly sensitive to changes in current inflow conditions. In this work, we propose two differing approaches to stabilize SDDP solutions to the energy operation planning problem: the first approach aims at regularizing primal variables by considering an additional penalty on thermal dispatch revisions over time. The second approach indirectly reduces thermal generation and marginal cost variability by disregarding past inflow information in the cost-to-go function and compensating it with an increase in risk aversion. For comparison purposes, we assess solution quality with a set of proposed indexes summarizing each important aspect of a hydrothermal operation planning policy. In conclusion, we show it is possible to obtain high- quality solutions in comparison to current benchmarks and with significantly reduced variability.

[pt] A programação de máquinas é um processo de tomada de decisão que desempenha um importante papel na maioria das indústrias de manufatura e serviços. Esta dissertação aborda o problema de programação de máquinas paralelas idênticas sem preempção, considerando características da programação de data de liberação e data limite para execução do início das tarefas, restrição de precedência entre pares de tarefas, elegibilidade e disponibilidade de máquinas. Para resolver este problema, uma formulação de programação linear inteira mista é proposta. O novo modelo, chamado de bucket-indexed (BI), particiona o horizonte de planejamento em períodos de tempos de mesmo tamanho (buckets). O tamanho dos buckets é um par âmetro que varia de acordo com a instância e influencia o porte do modelo, podendo assumir valores entre 1 e o menor tempo de processamento das tarefas. Quanto maior o tamanho do bucket, menor é o número de buckets criados e, consequentemente, menor o porte do modelo. A formulação proposta é testada em instâncias reais referentes ao problema de programação de sondas para construção de poços de petróleo de uma indústria brasileira de óleo e gás. A fim de avaliar os resultados obtidos pela formulação BI, a formulação clássica time-indexed (TI) foi também implementada para comparação dos tempos computacionais e qualidade da solução. Os resultados da formulação proposta apontam um melhor desempenho nas instâncias testadas, reduzindo o tempo computacional em todos os casos e resolvendo instâncias de grande porte não resolvidas pela formulação TI. / [en] Machine scheduling is a decision-making process that plays an important role in most manufacturing and service industries. This dissertation tackles a nonpreemptive identical parallel machine scheduling problem, considering release dates, deadlines, precedences, eligibility, and machine availability constraints. To solve this problem, a mixed-integer linear programming formulation is proposed. The new model, called bucketindexed, partitions the planning horizon in periods of equal length (buckets). The bucket size is a parameter which varies according to instances and influences the model size, assuming values between 1 and the shortest processing time of jobs. The larger the bucket size, the smaller is the number of buckets created and, consequently, the smaller the model size. The proposed formulation is tested in real instances of the rig scheduling problem for a Brazilian oil and gas industry. To evaluate the results obtained by the BI formulation, the classical time-indexed (TI) formulation was also implemented for comparison of computational times and solution quality. The results of the proposed formulation highlight a better performance in all the tested instances, reducing computational time in all cases and solving large instances unsolvable by the TI formulation.

[pt] A indústria do petróleo é uma das mais importantes e dinâmicas do Brasil. Em uma indústria naturalmente integrada como a petrolífera, é necessário um adequado planejamento estratégico da cadeia integrada de petróleo que contemple todos os seus processos, como a produção de petróleo, refino, distribuição e comercialização de derivados. Além disso, a indústria de petróleo está suscetível a diversas incertezas relacionadas a preço de petróleo e derivados, oferta de óleo bruto e demanda de produtos. Em face destas oportunidades e desafios, foi desenvolvido no âmbito desta dissertação um modelo de programação estocástica para o planejamento estratégico da cadeia de petróleo brasileira. O modelo contempla as refinarias e suas unidades de processos, as propriedades dos petróleos e derivados, a logística nacional e decisões de comercialização de petróleo e derivados, incluindo incertezas associadas a preço de mercado, produção de petróleo nacional e demanda interna de derivados. A partir do modelo estocástico foram formulados um modelo robusto e um modelo MinMax no intuito de comparar o desempenho e a qualidade da solução estocástica. Os modelos propostos foram aplicados a um exemplo real, com 17 refinarias e 3 centrais petroquímicas que processam 50 produtos intermediários, destinados a produção de 10 derivados associados à demanda nacional, 8 campos de exploração de petróleo, 14 produtores gás natural, 1 produtor de óleo vegetal, 13 terminais, 4 bases de distribuição e 278 arcos de transporte. Na análise de resultados foram utilizadas medidas como Valor Esperado da Informação Perfeita (EVPI) e Valor da Solução Estocástica (VSS). / [en] The oil industry is one of the most important and dynamic in Brazil. As the oil industry naturally integrated, we need an appropriate strategic planning to the oil supply chain that consider all its processes, such as oil production, refining, distribution and refined products marketing. Moreover, the oil industry is susceptible to various uncertainties regarding the oil and products price, crude oil supply and products demand. In light of these opportunities and challenges, it was developed in this dissertation a stochastic programming model for the strategic planning of the Brazilian oil supply chain. The model includes refineries and process units, oils and their products properties, logistics and national marketing decisions of oil and products, including uncertainties associated with market price, oil domestic production and refined products domestic demand. Based on the stochastic model a robust model and a MinMax model were formulated in order to compare the performance and quality of the stochastic solution. The proposed models were applied to a real example, with 17 refineries and 3 petrochemical power plants that process 50 intermediate products, intended to production of 10 final products associated to national demand, 8 oil fields, 14 natural gas producers, 1 vegetal oil producer, 13 terminals, 4 delivery points and 278 arches of transport. In the results analysis was used as measures the Expected Value of Perfect Information (EVPI) and the Value of the Stochastic Solution (VSS).

[pt] Na visualização de campos escalares de dados volumétricos, o uso de seções de corte é uma técnica eficaz para se inspecionar a variação do campo no interior do domínio. A técnica de visualização consiste em mapear sobre a superfície da seção de corte um mapa de cores, o qual representa a variação do campo escalar na interseção da superfície com o volume. Este trabalho propõe um método eficiente para o mapeamento de campos escalares de malhas não estruturadas em seções de corte arbitrárias. Trata-se de um método de renderização direta (a interseção da superfície com o modelo não é extraída) que usa a GPU para garantir bom desempenho. A idéia básica do método proposto é utilizar o rasterizador da placa gráfica para gerar os fragmentos da superfície de corte e calcular a interseção de cada fragmento com o modelo em GPU. Para isso, é necessário testar a localização de cada fragmento na malha não estruturada de maneira eficiente. Como estrutura de aceleração, foram testadas três variações de grades regulares para armazenar os elementos (células) da malha, e cada elemento é representado pela lista de planos de suas faces, facilitando o teste de pertinência fragmento-elemento. Uma vez determinado o elemento que contém o fragmento, são aplicados procedimentos para interpolar o campo escalar e para identificar se o fragmento está próximo à fronteira do elemento, a fim de representar o aramado (wireframe) da malha na superfície de corte. Resultados obtidos demonstram a eficácia e a eficiência do método proposto. / [en] For the visualization of scalar fields in volume data, the use of cross sections is an effective technique to inspect the field variation inside the domain. The technique consists in mapping, on the cross section surfaces, a colormap that represents the scalar field on the surfasse-volume intersection. In this work, we propose an efficient method for mapping scalar fields of unstructured meshes on arbitrary cross sections. It is a direct-rendering method (the intersection of the surface and the model is not extracted) that uses GPU to ensure efficiency. The basic idea is to use the graphics rasterizer to generate the fragments of the cross-section surface and to compute the intersection of each fragment with the model. For this, it is necessary to test the location of each fragment with respect to the unstructured mesh in an efficient way. As acceleration data structure, we tested three variations of regular grids to store the elements (cells) of the mesh, and each elemento is represented by the list of face planes, easing the in-out test between fragments and elements. Once the element that contains the fragment is determined, it is applied procedures to interpolate the scalar field and to check if the fragment is close to the element boundary, to reveal the mesh wireframe on the surface. Achieved results demonstrate the effectiveness and the efficiency of the proposed method.

[pt] O primeiro estágio na linha de produção de um sistema de geração procedural de cidades é, tipicamente, a geração da malha rodoviária. Este trabalho apresenta um algoritmo para a geração de malhas rodoviárias em paralelo na GPU usando um modelo de execução baseado em filas de trabalho. Esse algoritmo recebe parâmetros declarativos, juntamente com mapas geográficos e sócio estatísticos, e produz uma representação em alto nível de uma malha rodoviária urbana. / [en] The first stage in the pipeline of a procedural city generation system is typically the generation of the road network. This work presents a parallel algorithm for road networks generation on the GPU, using a work-queue based execution model. This algorithm receives declarative parameters along with geographic and socio-statistical maps and produces a high level representation of an urban road network.

[pt] A importância do planejamento em logística ferroviária cresce a cada dia devido ao alto custo dos investimentos para o aumento da sua capacidade. Entretanto, planejar é uma atividade que exige uma representação suficientemente precisa da realidade estudada. Neste contexto, os modelos de programação matemática apresentam-se cada vez mais adequados. Isto decorre dos recentes avanços nos algoritmos e computadores disponíveis para sua resolução. Esta dissertação apresenta modelos e algoritmos para o planejamento ferroviário tático e estratégico, isto é feito estudando o Problema de Planejamento de Atendimento (PPA). Primeiramente este problema é considerado assumindo que toda a estrutura ferroviária está definida: a malha, a tração e os vagões disponíveis, os pátios para carga, descarga e transbordo, suas respectivas taxas de carga e descarga e as demandas previstas. Em seguida, a questão adicional de determinar os pátios onde paradas podem ser efetuadas é considerada. Finalmente, em uma terceira etapa, introduz-se a capacidade de se analisar os efeitos do congestionamento de trechos da malha e seu impacto nos tempos de circulação e na capacidade da estrutura logística. Modelos são apresentados para cada um dos níveis de complexidade do PPA. Algoritmos exatos e heurísticos e técnicas de pré- processamento, foram desenvolvidos para os tratamentos dos casos obtidos. Em todos os casos, foi possível resolver de maneira ótima ou quase ótima em tempo razoável, tanto em termos acadêmicos, como para a utilização prática. Resultados computacionais sobre um amplo conjunto de instâncias reais são apresentados. / [en] Planning in Railway Logistic is an activity with growing importance. This is due to the high costs of investment to increase the railway capacity. Nevertheless, planning in this context is a cumbersome task, since a precise representation is necessary to consider most relevant points in this activity. Mathematical programming is becoming one of the best ways derive precise representations and to solve them. This is due to the recent advances on algorithms and computers used in the resolution of mathematical programming problems. This dissertation presents models and algorithms for tactical and strategical railway planning what is done by studying a demand planning problem (PPA). First, this problem is considered assuming that all the railway structure is defined: the network, the locomotives and wagons available, the yards for loading and unloading with their respective rates, and the forecast of demands. Next, the question of deciding the yards to stop is considered. Finally, in a third step, the effect of congestion in parts of the network is introduced to the models. This allows analyzing the variation in the travel times and its consequence in the logistic structure capacity. Models are presented for all cases of the PPA. Exact and heuristic algorithms, as well as pre-processing techniques, are described for the problem resolution. In all cases, the resulting approach allowed to solve the problems optimally or quasioptimally in a reasonable computing time. Computational results are presented on a wide set of real world instances.

[pt] Os desenvolvedores de sistemas cliente-servidor constantemente se deparam com questões de desempenho e escalabilidade, muitas vezes o número de clientes simultâneos de um servidor pode crescer de forma significativa. Além disso, se esses sistemas podem executar códigos de terceiros, passa a existir a preocupação com a questão de segurança da execução destes trechos de códigos. O objetivo desse trabalho é testar o desempenho de diversas combinações de modelos de concorrência e sandboxes. Como exemplo de sistema sujeito a solicitações concorrentes que precisa permitir a execução de programas de terceiros, temos os servidores web. O Xavante é um servidor web desenvolvido na linguagem de programação Lua que originalmente utiliza um modelo de programação concorrente baseado em co-rotinas. Esse servidor já possuía a flexibilidade de mapear tipos de requisição a tratadores diferentes. Alguns desses tratadores de requisi ção permitem a utilização de código de terceiros em tempo de execução e, por isso, já fazem uso de sandboxes a fim de oferecer um ambiente de execução protegido. Nesse trabalho testamos o uso dessas sandboxes nativas ao Xavante além de outros tipos de sandboxes. Também aumentamos as possibilidades de extensão do servidor, flexibilizando a arquitetura de modo a permitir diferentes estratégias de concorrência. Utilizando a nova arquitetura testamos o desempenho das diversas combinações de sandboxes e modelos de programação concorrente, permitindo a comparação dos modelos não só do ponto de vista qualitativo mas também medindo o impacto de desempenho do seu uso. / [en] Client-server developers constantly have to deal with questions concerning performance and scalability, since the number of simultaneous clients can grow significantly. Moreover, if these systems can execute third-party code, there is also the concern of secure execution of these pieces of code. This work goal is to benchmark several combinations of concurrency and sandboxes models. As an example of a system exposed to several concurrent requests that must be able to execute third-party code, we have the web servers. Xavante is a web server developed in the Lua programming language that originally uses an concurrency programming model based on coroutines. This server offers the flexibility to map request types to different handlers. Some of these request handlers dynamically allow the use of third-party code, therefore they make use of sandboxes in order to offer a protected running environment. In this work we test the use of Xavante´s native sandboxes and other types of sandboxes.We also improve the extensibility of the server, using a different architecture in order to allow different concurrency strategies. Using the new architecture we tested the performance of several combinations of sandboxes and concurrency programming models, allowing the model comparison not only in a qualitative point of view but also measuring the related performance impacts.

[pt] No projeto de estruturas de engenharia há, freqüentemente, incertezas associadas µas propriedades dos materiais, nas propriedades geométricas e aos carregamentos. A maneira mais comum e tradicional para se levar em conta estas incertezas é através da definição dos valores de projeto como o resultado do produto do valor característico das variáveis aleatórias por um fator parcial de segurança. Esta solução, no entanto, falha ao não permitir a quantificação da confiabilidade do projeto ótimo uma vez que um fator grande de segurança pode não significar uma confiabilidade mais alta. Para se considerar a natureza probabilística de quantidades como propriedades dos materiais, carregamentos, etc., tem-se que identificar e definir estas quantidades como variáveis aleatórias no modelo de análise. Desta maneira, a probabilidade de falha (ou a confiabilidade) de uma estrutura sujeita a uma restrição de desempenho na forma de uma função de estado limite pode, então, ser calculada e formulada como uma restrição num problema de otimização. Neste trabalho, restrição probabilísticas são incorporadas ao esquema tradicional de otimização estrutural. A formulação e os métodos numéricos para este processo, comumente chamado de otimização baseada em confiabilidade, são descritos. O objetivo principal é apresentar um sistema computacional capaz de resolver problemas de otimização de forma e de dimensões de treliças espaciais baseado em confiabilidade. Podem ser consideradas como variáveis, determinísticas ou aleatórias, as seções transversais, as coordenadas nodais, as propriedades dos materiais (módulo de elasticidade e tensão de escoamento) e os carregamentos. De maneira a tratar os problemas de instabilidade global são considerados os efeitos da não-linearidade geométrica no comportamento da estrutura e uma restrição formulada para uma função de estado limite associada na carga de colapso é incluída. Funções de estado limite referentes aos deslocamentos e nas tensões também são consideradas. A flambagem global das barras é considerada por meio da carga crítica de Euler / [en] Uncertainties associated with random variables, such as, the material proprieties and loads, are inherent to the design of structures. These uncertainties are traditionally taken into account in the project before the design by defining design values for the random variables. The design values of the random variables are obtained from statistical properties of the random variables and from partial safety factors. Once these values are defined the variables are treated as deterministic variables in the design process. This approach has been followed in the conventional design optimization and in many design codes such as the Brazilian code for the design of steel and concrete structures. This simple approach, however, does not allow an estimate of the structural reliability of the resulting project which may have a low (unsafe structure) or a very high (expensive structure) reliability. To overcome this problem a reliability analysis must be incorporated into the traditional design optimization. Design optimization, incorporating reliability analyses, has been denoted Reliability-Based Design Optimization (RBDO). In RBDO, the constraints are defined in terms of the probabilities of failure associated with some prescribed failure functions and therefore, it requires, as in the reliability analysis, the definition of the random variables and information about their statistical properties. In this work, RBDO is applied to the shape and sizing optimization of spatial trusses considering geometric nonlinearities. The constraints considered in the RBDO problem are related to the following failure mechanisms: to the global collapse (limit load), to local buckling and yield stress and to serviceability conditions (displacement bounds). The algorithms used for solving the optimization problem and for performing the reliability analysis are described.

[pt] Diversos problemas em engenharia, aprendizado de máquina e economia podem ser resolvidos através de Programação Semidefinida (SDP). Potenciais aplicações podem ser encontradas em telecomunicações, fluxo de potência e teoria dos jogos. Além disso, como SDP é uma subclasse de otimização convexa, temos uma série de propriedades e garantias que fazem da SDP uma tecnologia muito poderosa. Entretanto, dentre as diferentes subclasses de otimização convexa, SDP ainda permanece como uma das mais desafiadoras. Instancias de larga escala ainda não podem ser resolvidas pelos atuais softwares disponíveis. Nesse sentido, esta tese porpõe um novo algoritmo para resolver problemas de SDP. A principal contribuição deste novo algoritmo é explorar a propriedade de posto baixo presente em diversas instancias. A convergência desta nova metodologia é provada ao mostrar que o algoritmo proposto é um caso particular do Approximate Proximal Point Algorithm. Adicionalmente, as variáveis ótimas duais são disponibilizadas como uma consequência do algoritmo proposto. Além disso, disponibilizamos um software para resolver problemas de SDP, chamado ProxSDP. Três estudos de caso são utilizados para avaliar a performance do algoritmo proposto. / [en] Many problems of interest can be solved by means of Semidefinite Programming (SDP). The potential applications range from telecommunications, electrical power systems, game theory and many more fields. Additionally, the fact that SDP is a subclass of convex optimization brings a set of theoretical guarantees that makes SDP very appealing. However, among all sub-classes of convex optimization, SDP remains one of the most challenging in practice. State-of-the-art semidefinite programming solvers still do not efficiently solve large scale instances. In this regard, this thesis proposes a novel algorithm for solving SDP problems. The main contribution of this novel algorithm is to achieve a substantial speedup by exploiting the low-rank property inherent to several SDP problems. The convergence of the new methodology is proved by showing that the novel algorithm reduces to a particular case of the Approximated Proximal Point Algorithm. Along with the theoretical contributions, an open source numerical solver, called ProxSDP, is made available with this work. The performance of ProxSDP in comparison to state-of-the-art SDP solvers is evaluated on three case studies.