Made available in DSpace on 2015-05-14T12:09:45Z (GMT). No. of bitstreams: 1 parte1.pdf: 1452000 bytes, checksum: f0d2af7428a4caf8e2af59b42c65d028 (MD5) Previous issue date: 2007-03-26 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / It was aimed in the present study to carry out a method of economical measurement of water supply system, composed by pipes network, including its propulsion system. This method is denominated here as EficientE , which was carried out on search of a minimal cost solution for threshed networks, with branches intended to amplify the existing networks. In order to develop the optimization methodology, techniques of dynamic programming were used here, in association with basic economical concepts. This technique-concept association enabled the development of a mathematical algorithm iteration of convergence, aiming to obtain a minimum cost solution. For estimating the variables of state of the system, it was performed for each iteration a special program associated to software of hydraulic simulation of continuous water flow in threshed networks of water supply. The method proposed here was tested in five situations of water networks with distinct features concerning their design, size, and contour conditions. This method showed to be effective in all situations, resulting in excellent performance, which means that it can be applied to networks of water distribution of any proportion, since no restrictions were detected when simulating its application. / O presente estudo tem o objetivo de elaborar um método de dimensionamento econômico de sistemas de distribuição de água, composto pela rede de tubulações, com seu sistema de impulsão. O método, aqui denominado EficientE , busca alcançar a solução de custo mínimo para redes malhadas, ramificadas e para ampliações de redes já existentes. Para o desenvolvimento da metodologia de otimização, foram utilizadas técnicas de programação dinâmica, aliadas a conceitos econômicos básicos. Esta junção de técnicas e conceitos propiciou o desenvolvimento de um algoritmo matemático iterativo de convergência, para a obtenção da solução de custo mínimo. Para a determinação das variáveis de estado do sistema, a cada iteração, foi desenvolvido e utilizado um programa, associado a um software de simulação hidráulica do escoamento permanente em redes malhadas de distribuição de água. O método proposto foi testado em cinco exemplos de redes com características distintas, quanto ao traçado, tamanho e condições de contorno. Em todas as redes estudadas, o método funcionou perfeitamente e apresentou excelente desempenho. Os resultados alcançados indicam que o método pode ser utilizado em redes de qualquer porte, pois não foram encontradas quaisquer restrições a sua aplicação.

Bancos de dados biológicos utilizados para comparação e alinhamento local de sequências tem crescido de forma exponencial. Isso popularizou programas que realizam buscas nesses bancos. As implementações dos algoritmos de alinhamento de sequências Smith- Waterman e distância Levenshtein demonstraram ser computacionalmente intensivas e, portanto, propícias para aceleração em hardware. Este trabalho descreve arquiteturas em hardware dedicado prototipadas para FPGA e ASIC para acelerar os algoritmos Smith- Waterman e distância Levenshtein mantendo os mesmos resultados obtidos por softwares. Descrevemos uma nova e eficiente unidade de processamento para o cálculo do Smith- Waterman utilizando affine gap. Também projetamos uma arquitetura que permite particionar as sequências de entrada para a distância Levenshtein em um array sistólico de tamanho fixo. Nossa implementação em FPGA para o Smith-Waterman acelera de 275 a 494 vezes o algoritmo em relação a um computador com processador de propósito geral. Ainda é 52 a 113% mais rápida em relação, segundo nosso conhecimento, as mais rápidas arquiteturas recentemente publicadas. / Bioinformatics databases used for sequence comparison and local sequence alignment are growing exponentially. This has popularized programs that carry out database searches. Current implementations of sequence alignment methods based on Smith- Waterman and Levenshtein distance have proven to be computationally intensive and, hence, amenable for hardware acceleration. This Msc. Thesis describes an FPGA and ASIC based hardware implementation designed to accelerate the Smith-Waterman and Levenshtein distance maintaining the same results yielded by general softwares. We describe an new efficient Smith-Waterman affine gap process element and a new architecture to partitioning and maping the Levenshtein distance into fixed size systolic arrays. Our FPGA Smith-Waterman implementation delivers 275 to 494-fold speed-up over a standard desktop computer and is also about 52 to 113% faster, to the best of our knowledge, than the fastest implementation in a most recent family of accelerators.

The requirements on fuel consumption and emissions for passenger cars are getting stricter every year. This has forced the vehicle industry to look for ways to improve the performance of the driveline. With the increasing focus on electrification, a common method is to combine an electrical driveline with a conventional driveline that uses a petrol or diesel engine, thus creating a hybrid electric vehicle. To fully be able to utilise the potential of the driveline in such a vehicle, an efficient energy management strategy is needed. This thesis describes the development of an efficient route-based energy management strategy. Three different optimisation strategies are combined, deterministic dynamic programming, equivalent consumption minimisation strategy and convex optimisation, together with segmentation of the input data. The developed strategy shows a decrease in computational time with up to more than one hundred times compared to a benchmark algorithm. When implemented in Volvo's simulation tool, VSim, substantial fuel savings of up to ten percent is shown compared to a charge-depleting charge-sustain strategy.

Cílem práce byl návrh a implementace řídicích algoritmů pro optimalizaci spotřeby energie elektrického vozidla. Hlavním úkolem byla optimalizace rozložení energie mezi hlavním zdrojem energie (bateriemi) a super-kapacitory v průběhu jízdního cyklu. Jízdní výkonový profil je odhadován a předpovězen na základě 3D geografických souřadnic a matematického modelu vozidla. V první části jsou uvedeny komponenty vozidla a jejich modely. Poté jsou představeny algoritmy na základě klouzavého průměru a dynamického programování. Byly provedeny simulace a analýzy pro demostraci přínosů algoritmů. V poslední části je popsána Java implementace algoritmů a také aplikace pro operační systém Android.

Processos de Decisão Markovianos (Markov Decision Process - MDP) modelam problemas de tomada de decisão sequencial em que as possíveis ações de um agente possuem efeitos probabilísticos sobre os estados sucessores (que podem ser definidas por matrizes de transição de estados). Programação dinâmica em tempo real (Real-time dynamic programming - RTDP), é uma técnica usada para resolver MDPs quando existe informação sobre o estado inicial. Abordagens tradicionais apresentam melhor desempenho em problemas com matrizes esparsas de transição de estados porque podem alcançar eficientemente a convergência para a política ótima, sem ter que visitar todos os estados. Porém essa vantagem pode ser perdida em problemas com matrizes densas de transição, nos quais muitos estados podem ser alcançados em um passo (por exemplo, problemas de controle com eventos exógenos). Uma abordagem para superar essa limitação é explorar regularidades existentes na dinâmica do domínio através de uma representação fatorada, isto é, uma representação baseada em variáveis de estado. Nesse trabalho de mestrado, propomos um novo algoritmo chamado de FactRTDP (RTDP Fatorado), e sua versão aproximada aFactRTDP (RTDP Fatorado e Aproximado), que é a primeira versão eficiente fatorada do algoritmo clássico RTDP. Também propomos outras 2 extensões desses algoritmos, o FactLRTDP e aFactLRTDP, que rotulam estados cuja função valor convergiu para o ótimo. Os resultados experimentais mostram que estes novos algoritmos convergem mais rapidamente quando executados em domínios com matrizes de transição densa e tem bom comportamento online em domínios com matrizes de transição densa com pouca dependência entre as variáveis de estado. / Markov Decision Process (MDP) model problems of sequential decision making, where the possible actions have probabilistic effects on the successor states (defined by state transition matrices). Real-time dynamic programming (RTDP), is a technique for solving MDPs when there exists information about the initial state. Traditional approaches show better performance in problems with sparse state transition matrices, because they can achieve the convergence to optimal policy efficiently, without visiting all states. But, this advantage can be lose in problems with dense state transition matrices, in which several states can be achieved in a step (for example, control problems with exogenous events). An approach to overcome this limitation is to explore regularities existing in the domain dynamics through a factored representation, i.e., a representation based on state variables. In this master thesis, we propose a new algorithm called FactRTDP (Factored RTDP), and its approximate version aFactRTDP (Approximate and Factored RTDP), that are the first factored efficient versions of the classical RTDP algorithm. We also propose two other extensions, FactLRTDP and aFactLRTDP, that label states for which the value function has converged to the optimal. The experimental results show that when these new algorithms are executed in domains with dense transition matrices, they converge faster. And they have a good online performance in domains with dense transition matrices and few dependencies among state variables.

Bancos de dados biológicos utilizados para comparação e alinhamento local de sequências tem crescido de forma exponencial. Isso popularizou programas que realizam buscas nesses bancos. As implementações dos algoritmos de alinhamento de sequências Smith- Waterman e distância Levenshtein demonstraram ser computacionalmente intensivas e, portanto, propícias para aceleração em hardware. Este trabalho descreve arquiteturas em hardware dedicado prototipadas para FPGA e ASIC para acelerar os algoritmos Smith- Waterman e distância Levenshtein mantendo os mesmos resultados obtidos por softwares. Descrevemos uma nova e eficiente unidade de processamento para o cálculo do Smith- Waterman utilizando affine gap. Também projetamos uma arquitetura que permite particionar as sequências de entrada para a distância Levenshtein em um array sistólico de tamanho fixo. Nossa implementação em FPGA para o Smith-Waterman acelera de 275 a 494 vezes o algoritmo em relação a um computador com processador de propósito geral. Ainda é 52 a 113% mais rápida em relação, segundo nosso conhecimento, as mais rápidas arquiteturas recentemente publicadas. / Bioinformatics databases used for sequence comparison and local sequence alignment are growing exponentially. This has popularized programs that carry out database searches. Current implementations of sequence alignment methods based on Smith- Waterman and Levenshtein distance have proven to be computationally intensive and, hence, amenable for hardware acceleration. This Msc. Thesis describes an FPGA and ASIC based hardware implementation designed to accelerate the Smith-Waterman and Levenshtein distance maintaining the same results yielded by general softwares. We describe an new efficient Smith-Waterman affine gap process element and a new architecture to partitioning and maping the Levenshtein distance into fixed size systolic arrays. Our FPGA Smith-Waterman implementation delivers 275 to 494-fold speed-up over a standard desktop computer and is also about 52 to 113% faster, to the best of our knowledge, than the fastest implementation in a most recent family of accelerators.

Orientador: João Bosco Ribeiro do Val / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-14T00:07:24Z (GMT). No. of bitstreams: 1 Calmon_AndreduPin_M.pdf: 862345 bytes, checksum: 122780715dca28ac7fa3199aa0586e7c (MD5) Previous issue date: 2009 / Resumo: Este trabalho apresenta a caracterização teórica e a estratégia de controle para sistemas estocásticos em tempo discreto onde a variação da ação de controle aumenta a incerteza sobre o estado (sistemas VCAI). Este tipo de sistema possui várias aplicações práticas, como em problemas de política monetária, medicina e, de forma geral, em problemas onde um modelo dinâmico completo do sistema é complexo demais para ser conhecido. Utilizando ferramentas da análise de funções não suaves, mostra-se para um sistema VCAI multidimensional que a convexidade é uma invariante da função valor da Programação Dinâmica quando o custo por estágio é convexo. Esta estratégia indica a existência de uma região no espaço de estados onde a ação ótima de controle é de não variação (denominada região de não-variação), estando de acordo com a natureza cautelosa do controle de sistemas subdeterminados. Adicionalmente, estudou-se algoritmos para a obtenção da política ótima de controle para sistemas VCAI, com ênfase no caso mono-entrada avaliado através de uma função custo quadrática. Finalmente, os resultados obtidos foram aplicados no problema da condução da política monetária pelo Banco Central. / Abstract: This dissertation presents a theoretical framework and the control strategy for discrete-time stochastic systems for which the control variations increase state uncertainty (CVIU systems). This type of system model can be useful in many practical situations, such as in monetary policy problems, medicine and biology, and, in general, in problems for which a complete dynamic model is too complex to be feasible. The optimal control strategy for a multidimensional CVIU system associated with a convex cost functional is devised using dynamic programming and tools from nonsmooth analysis. Furthermore, this strategy points to a region in the state space in which the optimal action is of no variation (the region of no variation), as expected from the cautionary nature of controlling underdetermined systems. Numerical strategies for obtaining the optimal policy in CVIU systems were developed, with focus on the single-input input case evaluated through a quadratic cost functional. These results are illustrated through a numerical example in economics. / Mestrado / Automação / Mestre em Engenharia Elétrica

Submitted by Renata Lopes (renatasil82@gmail.com) on 2016-02-12T13:55:12Z No. of bitstreams: 1 glauciafernandes.pdf: 1492649 bytes, checksum: 3497d6f4bd8b07186c17e1376245374d (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2016-02-26T12:15:00Z (GMT) No. of bitstreams: 1 glauciafernandes.pdf: 1492649 bytes, checksum: 3497d6f4bd8b07186c17e1376245374d (MD5) / Made available in DSpace on 2016-02-26T12:15:00Z (GMT). No. of bitstreams: 1 glauciafernandes.pdf: 1492649 bytes, checksum: 3497d6f4bd8b07186c17e1376245374d (MD5) Previous issue date: 2014-01-28 / FAPEMIG - Fundação de Amparo à Pesquisa do Estado de Minas Gerais / Este trabalho tem por objetivo sugerir uma adaptação do modelo de Silva & Santiago (2009) para projetos com market share garantido, aplicando a modelagem para analisar a viabilidade de um projeto de P&D incubado pelo CRITT da UFJF. Além disso, algumas críticas foram apontadas em relação ao modelo dos autores, tais como a inflexibilidade de alguns parâmetros e à insensibilidade dos custos em relação ao tempo e a performance do produto/tecnologia, quando grande parte dos custos das empresas são fixos. A fim de contornar esses problemas alguns testes de sensibilidades foram realizados garantido maior confiabilidade dos resultados: (i) análises da probabilidade de sucesso; (ii) análise dos parâmetros de forma e escala, e; (iii) análise do desvio padrão do tempo. Com respeito ao projeto estudado (o HBDO), este se mostrou mais promissor diante do tratamento múltiplo da incerteza, apresentando um valor superior ao valor calculado pela análise tradicional. Com relação ás análises de sensibilidades sobre o projeto, observou-se que os parâmetros sensibilizados impactaram significativamente o valor do projeto, indicando que uma análise cautelosa deve ser feita em relação aos mesmos. Além disso, uma análise do valor do projeto com o tempo seguindo uma distribuição uniforme também foi realizada, apresentando valores menores que os estimados anteriormente com a distribuição triangular, mas seguindo as mesmas conclusões anteriores sobre a importância de se considerar as incertezas na análise de valoração. Por fim, conclui-se que a análise de valoração de projetos de P&D ainda é um desafio e, por isso, o desenvolvimento e/ou aprimoramento de modelos que captem as incertezas e flexibilidades gerenciais que os gestores enfrentam justifica a escolha dessa unidade de estudo. / This work suggests an adaptation of Silva & Santiago (2009) model for treat projects with guaranteed market share and we intend to apply it to analyze a R&D project, which is incubated by CRITT at UFJF. Moreover, some critics were made about authors' model, such as the inflexibility of some parameters and the insensitivity of costs on time and product/technology performance, when most costs of the companies are fixed. To ride out these problems some sensitivity tests were performed to guarantee higher reliability of the results: (i) analysis of the success probability; (ii) analysis of the parameters of shape and scale; (iii) analysis of the standard deviation of time. With respect to the project that we studied (the HBDO), it was more promising over multiple uncertainties, presenting a value higher than that calculated by traditional analysis. With respect to sensitivity analysis performed, it was observed that the sensitized parameters had a significantly impact on the project value, which indicate that a careful analysis should be done for those. Furthermore, an analysis of the project value with the time following a uniform distribution was performed too and it showed lower values than those estimated previously with triangular distribution. It also showed the same previous conclusions about the importance of considering the uncertainties in the valuation analysis. Finally, we concluded that the analysis of the valuation of R&D projects is still a challenge and, therefore, the development and/or improvement of models that capture the uncertainty and managerial flexibility faced by the managers, justifies the choice of this study.

O planejamento operacional de um sistema de transporte de longa distância implica resolver um problema de otimização de rede dinâmica, visando a efetuar, de forma eficaz e eficiente, o atendimento às demandas de cargas, utilizando a capacidade de transporte disponível. A metodologia de solução proposta utiliza a abordagem de Rede de Filas Logísticas, a qual substitui o processo de otimização global da rede (usualmente utilizando Programação Linear Inteira) por um modelo de Programação Dinâmica Estocástica, Aproximada e Adaptativa, que permite a resolução de uma série de subproblemas delimitados no tempo, reduzindo sensivelmente a quantidade de variáveis envolvidas. Este método permite a utilização de modelos matemáticos mais realistas em horizontes de planejamento mais amplos. O presente trabalho estende os modelos encontrados na Literatura, aplicando o método a problemas de maior complexidade, incluindo a consideração de frotas heterogêneas de veículos, janelas de início de atendimento, utilização de terceiros transportadores e penalidades pelo não atendimento das demandas. São apresentados exemplos de problemas experimentais submetidos com sucesso à técnica desenvolvida. O trabalho inclui ainda o delineamento de um Sistema de Apoio à Decisão incorporando a metodologia proposta. / Operational planning of a long haul transportation system implies to solve a dynamic network optimization problem, aiming to perform the freight movements in an efficient and effective way, while utilizing the available transportation capacity. The proposed solution methodology utilizes the Logistic Queueing Network approach, replacing the network global optimization process through Integer Linear Programming by a model of Stochastic, Approximate and Adaptive Dynamic Programming, which allows the resolution of a sequence of sub- problems delimited in time, strongly reducing the quantity of variables involved. This method allows the utilization of more realistic mathematical models in a broader planning horizon. The research extends models found in the literature to solve more complex problems, including the consideration of heterogeneous fleet of vehicles, time windows, third party vehicles and penalties for not attendance of demands. Experimental problems solved successfully with the developed technique are presented. The work also presents the delineation of a Decision Support System incorporating the proposed methodology.

Neste trabalho, estudamos o problema de corte bidimensional multiperíodo com sobras aproveitáveis, que consiste em cortar objetos grandes visando a produção de um conjunto de itens menores. Supomos um horizonte de planejamento finito com uma quantidade finita de períodos entre os tempos inicial e final. Primeiramente consideramos uma versão determinística em que conhecemos, à priori, os itens solicitados em uma ordem de trabalho e o custo dos objetos a cada período. Algumas das sobras geradas durante o processo de corte dos itens solicitados em um período podem ser utilizadas como objetos no futuro. As sobras que podem ser usadas no futuro são denominadas sobras aproveitáveis. De forma geral, uma sobra é considerada aproveitável se possui dimensões iguais ou superiores as de algum item de uma lista pré-definida para o período. O objetivo é minimizar o custo total dos objetos utilizados para satisfazer a ordem de trabalho dos itens solicitados de todo o horizonte considerado. Havendo soluções com o mesmo custo, desejamos encontrar aquela que, no fim do horizonte de tempo considerado, maximize o valor das sobras aproveitáveis remanescentes. Apresentamos uma modelagem matemática do problema usando uma formulação em dois níveis, que é transformada em um modelo de programação linear inteira mista, devido às características do problema. Considerando a dificuldade em resolver o modelo desenvolvido, apresentamos uma proposta de uma abordagem heurística baseada em Programação Dinâmica Aproximada (PDA) para lidar com o problema proposto. Outras opções baseadas em estratégias do tipo horizonte rolante e relax-and-fix também são consideradas. Consideramos também o cenário onde não conhecemos de antemão os itens da ordem de trabalho e o custo dos objetos, mas temos informações das distribuições de probabilidade de ambos. Nesse caso, apresentamos uma abordagem baseada em programação dinâmica aproximada para estimar a melhor estratégia a ser seguida em cada período. Comparamos os resultados obtidos pela PDA com os resultados encontrados por um método guloso. Em cenários adequados, os resultados mostram que a PDA consegue soluções superiores ao método guloso. / In this research, we study the multi-period two-dimensional cutting problem with usable leftover, which consists of cutting objects to produce a set of items. We assume a finite planning horizon with a finite amount of periods between the initial and final times. First we consider a deterministic version in which we know, a priori, the set of ordered items and the cost of the objects at each period. Some of the leftovers generated during the cutting process of the ordered items in a period may be used as objects in the future. The leftovers that can be used in the future are called usable leftovers. In general, a leftover is considered usable if it has dimensions equal to or greater than that of some item from a predefined list for the period. The goal is to minimize the total cost of the objects used to cut the set of ordered items of the entire considered horizon. If there are solutions with the same cost, we wish to find one that, at the end of the considered time horizon, maximizes the value of the remaining usable leftovers. We present a mathematical model of the problem using a bilevel formulation, which is transformed into a mixed integer linear programming model, due to the characteristics of the problem. Considering the difficulty in solving the developed model, we propose a heuristic approach based on approximate dynamic programming (ADP) to deal with the proposed problem. Other options based on the rolling horizon and relax-and-fix strategies are also considered. We also consider the scenario where we do not know in advance the set of ordered items and the cost of the objects, but we have information about the probability distributions of both. In this case, we present an approach based on approximate dynamic programming to estimate the best strategy to be followed at each period. We compared the results obtained by the ADP with the results found by a greedy method. In suitable scenarios, the results show that the ADP achieves superior solutions to the greedy method.