O principal objetivo dos veículos híbridos é diminuir o consumo de combustível em relação a veículos convencionais. Para isso, existe a necessidade de realizar a integração dos diferentes sistemas do trem-de-força e coordenar o seu funcionamento através de estratégias de controle. Tais estratégias são desenvolvidas e simuladas em conjunto com um modelo computacional da planta do veículo antes de serem aplicadas em uma unidade de controle eletrônica. O presente estudo tem como objetivo analisar o gerenciamento de energia em um veículo híbrido elétrico não-plugin do tipo série-paralelo visando à diminuição de consumo de combustível. O método de otimização global é utilizado para encontrar as variáveis de controle que resultam no mínimo consumo de combustível em um determinado ciclo de condução. Na primeira etapa, um modelo computacional da planta do veículo e da estratégia de controle não-ótima são criados. Os resultados obtidos da simulação são então comparados com dados experimentais do veículo operando em dinamômetro de chassis. A seguir, o método de otimização global é aplicado ao modelo computacional utilizando programação dinâmica e tendo como objetivo a minimização do consumo de combustível total ao final do ciclo. Os resultados mostram considerável redução do consumo de combustível utilizando otimização global e tendo como variável de controle não só a razão de distribuição de torque mas também os pontos de operação do motor de combustão. Os modelos computacionais criados nesse trabalho são disponibilizados e podem ser usados para o estudo de diferentes estratégias de controle para veículos híbridos. / The main goal of hybrid electric vehicles is to decrease engine emission and fuel consumption levels. In order to realize this, one must perform the powertrain system integration and coordinate its operation through supervisory control strategies. These control strategies are developed in a simulation environment containing the plant model of the powertrain before they can be implemented in a real-time control unit. The goal of this work is to analyze the energy management strategy which minimizes the fuel consumption in a series-parallel non-plugin hybrid electric vehicle. Global optimization is used for finding the control variables that result in the minimum fuel consumption for a specific driving cycle. In a first stage, a computational model of vehicle plant and non-optimal control strategy are created. The results from the simulation are compared against experimental data from chassis dynamometer tests. Next, a global optimization strategy is applied using dynamic programming in order to minimize total fuel consumption at the end of the driving cycle. The results from the optimization show a considerable fuel consumption reduction having as control variables not only the torque-split strategy but also the engine operating points. As contribution from this work, the computational models are made available and can be used for analyzing different control strategies for hybrid vehicles.

O problema de controle de estoques com demanda não estacionária e lead-time positivo tem se tornado cada vez mais relevante em virtude da crescente tendência de redução do ciclo de vida dos produtos e internacionalização das cadeias de suprimentos. Embora haja uma solução exata para a minimização do custo esperado da política de estoques para este cenário, baseado no método de programação dinâmica, o custo computacional deste método ainda é considerado elevado. Este trabalho detalha e avalia através de simulação o método exato e duas aproximações para a minimização do custo esperado da política de estoques, em termos do desempenho em custo e eficiência computacional. Os resultados experimentais permitem a análise dos métodos disponíveis. Enquanto a abordagem heurística de Bollapragada e Morton, que utiliza o nivelamento da demanda não estacionária, perde desempenho de custo com o aumento do lead-time, a nova heurística proposta, que aproxima os parâmetros da política ótima por valores limitantes, produz resultados sucessivamente melhores com o aumento do lead-time. / The inventory control problem with nonstationary demand and positive lead-time has become increasingly important due to the growing trend of reduction in product life cycle and internationalization of the supply chain. Although there is an exact solution to the minimization of the expected cost of inventory policy on this environment, through the method of dynamic programming, the computational cost of this method is still considered high. This work details and evaluates through simulation the exact method and two heuristic solutions for the minimization of expected cost of inventory policy, in terms of cost performance and computational efficiency. The experimental results allow the analysis of the available methods. While the Bollapragada and Morton heuristic approach, which levels the non-stationary demand, decreases the cost performance when lead-time is increased, the new heuristic proposed, that approximates the optimal policy parameters by limiting values, successively produces better results with increasing lead-times.

O planejamento da operação energética em sistemas hidrotérmicos de potência com um único reservatório tem como objetivo determinar a participação de usinas hidrelétricas e térmicas de forma a garantir o suprimento de energia demandada ao menor custo operacional possível, dentro de restrições físicas e técnicas do modelo. Alguns fatores tornam a solução deste problema bastante complexa destacando a não linearidade e a não separabilidade temporal aditiva. O objetivo deste trabalho é apresentar uma nova abordagem com tratamento agregado das afluências, descrevendo uma nova caracterização das distribuições de probabilidades e um novo modelo para a programação dinâmica estocástica markoviana. Nesse novo modelo da programação dinâmica estocástica markoviana, agregações plurimensais de vazões são utilizadas como entrada em um modelo de programação dinâmica estocástica markoviana modificado para discretizações temporais plurimensais. A nova abordagem proposta foi simulada em diferentes usinas hidrelétricas brasileiras localizadas em diferentes regiões geográficas e sob diferentes regimes hidrológicos. Os resultados das simulações feitas com a utilização deste novo modelo são apresentados e comparados ao modelo de programação dinâmica estocástica markoviana mensal, atualmente utilizado no setor elétrico brasileiro, com economia de custos relativas superiores a 10% em alguns casos. / The energetic operation planning on hydrothermal power systems with a single reservoir aims to determine the participation of hydroelectric power plants and thermal power plants to guaranty supply of energy demanded with the smallest possible cost, under physical and technical model boundaries. Some points became the solution of this problem complex, highlighting the non linearity and the additive non time separability. The objective of this paper is show the new approach with aggregated inflows, describing a new probability distributions featuring and a new model for the markovian stochastic dynamic programming. On this new model of markovian stochastic dynamic programming, multi monthly inflow aggregations are used as input in a model of markovian stochastic dynamic programming modified for multi months discretizations. The new approach proposed was simulated on differents Brazilian hydroelectric power plants located on different regions and under different hydrologic regime. The results of simulations using this new model are presented and compared to the model of monthly markovian dynamic programming, nowadays used on the Brazilian electrical sector, with relatives economic savings up to 10% in some cases.

[pt] Uma maneira de localizar uma informação em uma base de dados grande e caótica como a Internet é utilizar um índice hierárquico que respeita alguma maneira de categorizar os dados. Exemplos desta hierarquia são os serviços de diretório, comuns em sites de busca. Porém, esta abordagem pode apresentar algumas desvantagens, como a necessidade de percorrer muitas páginas até chegar em uma informação muito acessada. Uma maneira de tratar este problema é o uso de hotlinks, hyperlinks adicionais que servem como atalho em uma busca. Estudamos algoritmos eficientes para atribuir hotlinks em um diretório web, de modo a reduzir o número máximo ou o número médio de acessos em uma busca. Fornecemos para o problema de minimização do número máximo de acessos um algoritmo (14/3)-aproximado e um algoritmo polinomial exato baseado em programação dinâmica. Por outro lado, para o problema de minimizar o número médio de acessos, adaptamos o algoritmo exato do problema anterior. Entretanto, este algoritmo adaptado é polinomial apenas para sites representados por árvores com altura O(log n). Por isso, introduzimos um parâmetro que permite ao usuário reduzir o tempo de execução em detrimento da qualidade da solução. Para este problema de minimizar o número médio de acessos, realizamos também experimentos comparando nosso algoritmo, um modelo em programação inteira, e alguns algoritmos propostos por outros autores. Introduzimos modificações práticas que melhoraram a performance do nosso algoritmo. / [en] An approach to search an information in a large and chaotic data base like the Internet is to use a hierarquical index regarding some categorization of the data. As an example, we have the web directories, usually found in search engines. However, this approach may have problems, as the need of visiting too many web pages to find a very accessed information. A way to address this problem is the use of hotlinks, which are hyperlinks added to the web site and used as shortcuts in a search. We studied efficient algorithms to assign hotlinks in web directories, in such a way to minimize the maximum or the average number of accesses to find an information. For the problem of minimizing the maximum number of accesses, we provide an (14/3)-approximation algorithm and an exact polinomial time algorithm based on dynamic programming. On the other hand, for the problem of minimizing the expected number of accesses, we adapted the previous exact algorithm. However, this adapted algorithm is polinomial only for web sites represented by trees with height O(log n). So, we introduce a parameter that allows the user to reduce the execution time under the cost of reducing the solution quality. For this problem of minimizing the expected number of accesses, we also made experiments comparing our algorithm, an integer programming model, and some algorithms proposed by other authors. We introduce pratical changes that improved the performance of our algorithm.

This study considers a vehicle routing problem with time windows, accessibility restrictions on customers and a fleet that is heterogeneous with regard to capacity, average speed and cost. A vehicle can perform multiple routes per day, all starting and ending at a single depot, and it is assigned to a single driver, whose total work hours are limited. The available fleet is divided into an owned fleet, for which a variable cost is incurred, and a chartered fleet, for which only a fixed cost is incurred for each vehicle used. A column generation algorithm embedded in a branch-and-bound framework is proposed. The column generation pricing subproblem required a specific elementary shortest path problem with resource constraints algorithm to address the possibility for each vehicle performing multiple routes per day and to address the need to determine the workdays start time within the planning horizon. To make the algorithm efficient, a constructive heuristic and a learning metaheuristic algorithm based on tabu search were also developed. Both were used on branch-and-bound tree nodes to generate a good initial solution to the linear restricted master problem; particularly, to find a good initial primal bound to the branch-and-bound tree. / Este estudo aborda um problema de roteirização de veículos com janelas de tempo, restrições de acessibilidade nos clientes e uma frota que é heterogênea em relação à capacidade de carga, velocidade média de deslocamento e custo. Um veículo pode percorrer múltiplas rotas por dia, todas começando e terminando em um mesmo depósito, e está designado a um único motorista, cujo total de horas trabalhadas no dia está limitado a um valor máximo. A frota disponível é dividida em uma frota própria, para a qual um custo variável é incorrido, e uma frota de freteiros, para a qual apenas um custo fixo é incorrido para cada veículo utilizado. Um algoritmo baseado em geração de colunas, integrado a um procedimento de branch-and-bound, é proposto neste estudo. O subproblema de precificação da geração de colunas requereu um algoritmo específico para o problema do caminho mínimo elementar com restrições sobre recursos capaz de lidar com a possibilidade de cada veículo percorrer múltiplas rotas por dia e capaz de lidar com a necessidade de determinar o instante de início do dia de trabalho do motorista dentro do horizonte de planejamento. Para tornar o algoritmo eficiente, uma heurística construtiva e uma heurística de melhoria baseada em busca tabu também foram desenvolvidos. Ambos são utilizados nos nós da árvore de branch-and-bound para gerar boas soluções iniciais para o problema mestre restrito da geração de colunas; particularmente, para encontrar um bom limitante primal inicial para a árvore de branch-and-bound.

Leung Ka-Kit. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2002. / Includes bibliographical references (leaves 129-131). / Abstracts in English and Chinese. / Abstract --- p.1 / Chapter CHAPTER 1. --- introduction --- p.14 / Chapter 1.1 --- Preamble --- p.14 / Chapter 1.2 --- Biological background --- p.14 / Chapter CHAPTER 2. --- previous related work --- p.18 / Chapter 2.1 --- Protein functionality analysis --- p.18 / Chapter 2.1.1 --- Analysis from primary structure --- p.18 / Chapter 2.1.2 --- Analysis from tertiary structure --- p.20 / Chapter 2.2 --- Secondary structure prediction --- p.21 / Chapter 2.3 --- Motivation - Challenges from protein complexity --- p.22 / Chapter CHAPTER 3. --- mathematical representations for protein properties and sequence alignment --- p.24 / Chapter 3.1 --- Secondary structure sequence model --- p.24 / Chapter 3.2 --- Substitution matrix --- p.26 / Chapter 3.3 --- Gap --- p.26 / Chapter 3.4 --- Similarity measurement --- p.27 / Chapter 3.5 --- Geometric Model for Protein --- p.28 / Chapter CHAPTER 4. --- overall system design --- p.30 / Chapter 4.1 --- System architecture and design --- p.30 / Chapter 4.2 --- System environment --- p.32 / Chapter 4.3 --- Experimental data --- p.32 / Chapter CHAPTER 5. --- adaptive dynamic programming (adp)- general global alignment consideration --- p.35 / Chapter 5.1 --- t-triangles cutting --- p.35 / Chapter 5.1.1 --- Theoretical time and memory requirements of ADP with z-triangles cutting --- p.43 / Chapter 5.1.1.1 --- Study of parameters affecting h in case 1 --- p.44 / Chapter 5.1.1.2 --- Study of parameters affecting h in case 2 --- p.45 / Chapter 5.1.2 --- Experimental results of ADP with z-triangles cutting --- p.46 / Chapter 5.2 --- Constructing the path matrix by expansion --- p.51 / Chapter 5.2.1 --- Time and memory requirements of EXPAND --- p.57 / Chapter 5.2.2 --- Experimental results and discussions --- p.58 / Chapter CHAPTER 6. --- adp - global alignment of sequences with consecutive repeated characters --- p.65 / Chapter 6.1 --- Estimation of similarity upper bound (Ba) --- p.65 / Chapter 6.1.1 --- Sequence composition (SC) consideration --- p.65 / Chapter 6.1.2 --- Implementation of SC --- p.67 / Chapter 6.1.3 --- Experimental results --- p.69 / Chapter 6.1.4 --- Overall trend of change of structures (OTCS) --- p.74 / Chapter 6.1.5 --- Uninformed search --- p.76 / Chapter 6.2 --- Short-cut --- p.80 / Chapter 6.2.1 --- Time and memory requirements --- p.86 / Chapter 6.2.2 --- Experimental results and discussions --- p.86 / Chapter CHAPTER 7. --- ga based topology discovery --- p.87 / Chapter 7.1 --- Chromosome encoding --- p.87 / Chapter 7.2 --- Non-sequential order penalty --- p.88 / Chapter 7.3 --- Fitness function --- p.88 / Chapter 7.4 --- Genetic operators --- p.88 / Chapter 7.4.1 --- Hop operator --- p.89 / Chapter 7.4.2 --- Inverse operator --- p.89 / Chapter 7.4.3 --- Shift operator --- p.90 / Chapter 7.4.4 --- Selection pressure --- p.90 / Chapter 7.5 --- Selection of progeny --- p.91 / Chapter 7.6 --- Implementation --- p.91 / Chapter 7.6.1 --- Size of population and generation --- p.91 / Chapter 7.6.2 --- Parallelization --- p.91 / Chapter 7.6.3 --- Crowding Handling --- p.92 / Chapter 7.6.4 --- Selection of progeny --- p.92 / Chapter 7.7 --- Results of alignment with GA exploration on topological order --- p.93 / Chapter CHAPTER 8. --- FILTERING OF FALSE POSITIVES --- p.103 / Chapter 8.1 --- Alignment Segments to Gap Ratio (ASGR) --- p.103 / Chapter 8.2 --- Tolerance --- p.104 / Chapter 8.3 --- Overall trend of change of structures (OTCS) --- p.104 / Chapter 8.4 --- Results and discussions --- p.105 / Chapter CHAPTER 9. --- SECONDARY STRUCTURE PREDICTION --- p.111 / Chapter 9.1 --- 3-STATE SECONDARY STRUCTURE PREDICTION IMPROVEMENT --- p.111 / Chapter 9.2 --- 8-state secondary structure prediction --- p.117 / Chapter 9.3 --- Iterative Subordinate Voting (IS V) --- p.117 / Chapter 9.4 --- ISV Results and discussion --- p.119 / Chapter CHAPTER 10. --- CONCLUSIONS --- p.123 / Chapter 10.1 --- Contributions --- p.123 / Chapter 10.2 --- Future Work --- p.126 / Chapter 10.2.1 --- Using database indexing --- p.126 / Chapter 10.2.2 --- 3-state secondary structure prediction improvement --- p.127 / appendix --- p.128 / Chapter ´Ø --- Interpretation on the dp一filter results --- p.128

Bibliography : leaves 196-200. / Thesis (Ph. D.)--Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science, 1977. / Microfiche copy available in the Institute Archives and Barker Engineering Library. / by Loren Kerry Platzman. / Ph.D.

Uma das tarefas mais básicas em bioinformática é a comparação de seqüências feita por algoritmos de alinhamento, que modelam as alterações evolutivas nas seqüências biológicas através de mutações como inserção, remoção e substituição de símbolos. Este trabalho trata de generalizações nos algoritmos de alinhamento que levam em consideração outras mutações conhecidas como rearranjos, mais especificamente, inversões, duplicações em tandem e duplicações por transposição. Alinhamento com inversões não tem um algoritmo polinomial conhecido e uma simplificação para o problema que considera somente inversões não sobrepostas foi proposta em 1992 por Schöniger e Waterman. Em 2003, dois trabalhos independentes propuseram algoritmos com tempo O(n^4) para alinhar duas seqüências com inversões não sobrepostas. Desenvolvemos dois algoritmos que resolvem este mesmo problema: um com tempo de execução O(n^3 logn) e outro que, sob algumas condições no sistema de pontuação, tem tempo de execução O(n^3), ambos em memória O(n^2). Em 1997, Benson propôs um modelo de alinhamento que reconhecesse as duplicações em tandem além das inserções, remoções e substituições. Ele propôs dois algoritmos exatos para alinhar duas seqüências com duplicações em tandem: um em tempo O(n^5) e memória O(n^2), e outro em tempo O(n^4) e memória O(n^3). Propomos um algoritmo para alinhar duas seqüências com duplicações em tandem em tempo O(n^3) e memória O(n^2). Propomos também um algoritmo para alinhar duas seqüências com transposons (um tipo mais geral que a duplicação em tandem), em tempo O(n^3) e memória O(n^2). / Sequence comparison done by alignment algorithms is one of the most fundamental tasks in bioinformatics. The evolutive mutations considered in these alignments are insertions, deletions and substitutions of nucleotides. This work treats of generalizations introduced in alignment algorithms in such a way that other mutations known as rearrangements are also considered, more specifically, we consider inversions, duplications in tandem and duplications by transpositions. Alignment with inversions does not have a known polynomial algorithm and a simplification to the problem that considers only non-overlapping inversions were proposed by Schöniger and Waterman in 1992. In 2003, two independent works proposed algorithms with O(n^4) time to align two sequences with non-overlapping inversions. We developed two algorithms to solve this problem: one in O(n^3 log n) time and other, considering some conditions in the scoring system, in O(n^3) time, both in O(n^2) memory. In 1997, Benson proposed a model of alignment that recognized tandem duplication, insertion, deletion and substitution. He proposed two exact algorithms to align two sequences with tandem duplication: one in O(n^5) time and O(n^2) memory, and other in O(n^4) time and O(n^3) memory. We propose one algorithm to align two sequences with tandem duplication in O(n^3) time and O(n^2) memory. We also propose one algorithm to align two sequences with transposons (a type of duplication more general than tandem duplication), in O(n^3) time and O(n^2) memory.

Esta dissertação aborda o problema de redução do consumo de combustível para veículos. Com esse objetivo, realiza-se o levantamento de um modelo estocástico e de seus parâmetros, o desenvolvimento de um controlador para o veículo, e análise dos resultados. O problema considera a interação com o trânsito de outros veículos, que limita a aplicação de resultados antes disponíveis. Para isto, propõe-se modelar a dinâmica do problema de maneira aproximada, usando sistemas com saltos markovianos, e levantar as probabilidades de transição dos estados da cadeia através de um modelo mais completo para o trânsito no percurso. / This dissertation deals with control of vehicles aiming at the fuel consumption optimization, taking into account the interference of traffic. Stochastic interferences like this and other real world phenomena prevents us from directly applying available results. We propose to employ a relatively simple system with Markov jumping parameters as a model for the vehicle subject to traffic interference, and to obtain the transition probabilities from a separate model for the traffic. This dissertation presents the model identification, the solution of the new problem using dynamic programming, and simulation of the obtained control.

Neste trabalho, apresenta-se um método para o Planejamento de Redes de Distribuição Secundária. O modelo básico desenvolvido baseia-se em técnica de programação dinâmica a fim de selecionar a política de evolução de trocas de transformadores de distribuição e rede secundária, com mínimo custo operacional dentro de limites de qualidade de serviço, para o atendimento de carga crescente no tempo em uma área de estudo restrita. Inicialmente, apresenta-se a filosofia básica do método, incluindo-se os dados necessários, critérios de planejamento e metodologia para o cálculo elétrico de redes secundárias. Em sequência, são apresentados três modelos para a solução do problema; tais modelos são diferenciados pela eliminação progressiva de hipóteses simplificativas. Nos dois primeiros modelos, a carga e seu crescimento são supostos uniformemente distribuídos ao longo dos trechos da rede secundária. No terceiro modelo, a distribuição da carga dos pontos presentes na rede secundária, durante o período de estudo, é estabelecida por procedimento randômico, com o único vínculo de serem mantidos os mercados globais de demanda e número de consumidores na área em estudo. Posteriormente, estabelece-se um exemplo de aplicação que permite proceder à comparação entre os três modelos desenvolvidos. Finalizando o trabalho, são estabelecidas as conclusões, possibilidades de aplicação do método em diversos estudos do sistema de Distribuição Secundária e são tecidos comentários sobre tópicos para ulterior desenvolvimento. / This work focuses on a method for the Planning of Secondary Distribution Systems. The basic model deals with dynamic programming in order to get an optimized design - Distribution Transformer and Secondaries - which presents the lowest operation cost within service quality limits in order to supply growing load on a restricted area. Initially the basic concepts of the method are presented, including the establishment of the data base, planning criteria and methodology in order to get operating conditions at secondary networks. Concerning this method, three computational models were established. These models differ form each other as far as some of the simplified hypothesis are eliminated. The first two models consider a uniform distribution of loads along the secondary system. The third model establishes a randomic distribution of loads on the restricted studying area. Following an application example, comparison is proceeded among the developed models. Eventually the conclusions, some possible applications of the method on Distribution system studies and research topics for further developments are settled.