Novos algoritmos para roteamento de circuitos VLSI

Este trabalho apresenta novos algoritmos para o roteamento de circuitos integrados, e discute sua aplicação em sistemas de síntese de leiaute. As interconexões têm grande impacto no desempenho de circuitos em tecnologias recentes, e os algoritmos propostos visam conferir maior controle sobre sua qualidade, e maior convergência na tarefa de encontrar uma solução aceitável. De todos os problemas de roteamento, dois são de especial importância: roteamento de redes uma a uma com algoritmos de pesquisa de caminhos, e o chamado roteamento de área. Para o primeiro, procura-se desenvolver um algoritmo de pesquisa de caminhos bidirecional e heurístico mais eficiente, LCS*, cuja aplicação em roteamento explora situações específicas que ocorrem neste domínio. Demonstra-se que o modelo de custo influencia fortemente o esforço de pesquisa, além de controlar a qualidade das rotas encontradas, e por esta razão um modelo mais preciso é proposto. Para roteamento de área, se estuda o desenvolvimento de uma nova classe de algoritmos sugerida em [JOH 94], denominados LEGAL. A viabilidade e a eficiência de tais algoritmos são demonstradas com três diferentes implementações. Devem ser também estudados mecanismos alternativos para gerenciar espaços e tratar modelos de grade não uniforme, avaliando-se suas vantagens e sua aplicabilidade em outros diferentes contextos.

Otimização de geometrias aerodinâmicas utilizando métodos inversos

O objetivo deste trabalho é a obtenção de uma técnica para a modelagem otimizada de corpos submetidos a fluxos de alta velocidade, como aerofólios em escoamentos transônicos e outras geometrias aerodinâmicas. A técnica é desenvolvida através de expansões em séries de Fourier para um conjunto de equações diferenciais com interrelação com as condições de contorno, sendo uma equação para a parte superior e outra para a parte inferior do aerofólio. O método de integração temporal empregado baseia-se no esquema explícito de Runge-Kutta de 5 estágios para as equações da quantidade de movimento e na relação de estado para a pressão. Para a aproximação espacial adota-se um esquema em volumes finitos no arranjo co-localizado em diferenças centrais. Utiliza-se dissipação artificial para amortecer as frequências de alta ordem do erro na solução das equações linearizadas. A obra apresenta a solução de escoamentos bi e tridimensionais de fluidos compressíveis transônicos em torno de perfis aerodinâmicos. Os testes num´ericos são realizados para as geometrias do NACA 0012 e 0009 e asas tridimensionais usando as equações de Euler, para número de Mach igual a 0.8 e ® = 0o. Os resultados encontrados comparam favoravelmente com os dados experimentais e numéricos disponíveis na literatura.

Otimização do uso de óleos refrigerantes na indústria metal-mecânica

Neste trabalho, foi realizado um estudo de óleos refrigerantes emulsionados utilizados em máquinas de usinagem da indústria metal-mecânica, com o objetivo de minimizar os gastos com reposição de óleo e o volume de resíduos contaminados pelo mesmo. Foram constatados três problemas principais na utilização do óleo refrigerante emulsionado em estudo: a presença de bactérias degradantes do óleo, a reposição da emulsão de maneira indevida e o arraste de óleo pelos cavacos e limalhas provenientes da própria usinagem. Como solução para estes três problemas principais, foi projetado um equipamento de controle e automação. Este protótipo é composto por três partes essenciais: tratamento bacteriológico prévio da água usada para emulsão do óleo, passagem da água de reposição através dos cavacos e limalhas e controle da concentração do óleo na emulsão. O protótipo foi instalado em um máquina de usinagem da Empresa AGCO do Brasil, sede Canoas e os resultados obtidos foram surpreendentes quanto às grandes possibilidades de minimização dos gastos com óleo refrigerante e do volume de resíduos contaminados por óleos.

Operadores aritméticos de baixo consumo para arquiteturas de circuitos DSP

Este trabalho tem como foco a aplicação de técnicas de otimização de potência no alto nível de abstração para circuitos CMOS, e em particular no nível arquitetural e de transferência de registrados (Register Transfer Leve - RTL). Diferentes arquiteturas para projetos especificos de algorítmos de filtros FIR e transformada rápida de Fourier (FFT) são implementadas e comparadas. O objetivo é estabelecer uma metodologia de projeto para baixa potência neste nível de abstração. As técnicas de redução de potência abordadas tem por obetivo a redução da atividade de chaveamento através das técnicas de exploração arquitetural e codificação de dados. Um dos métodos de baixa potência que tem sido largamente utilizado é a codificação de dados para a redução da atividade de chaveamento em barramentos. Em nosso trabalho, é investigado o processo de codificação dos sinais para a obtenção de módulos aritméticos eficientes em termos de potência que operam diretamente com esses códigos. O objetivo não consiste somente na redução da atividade de chavemanto nos barramentos de dados mas também a minimização da complexidade da lógica combinacional dos módulos. Nos algorítmos de filtros FIR e FFT, a representação dos números em complemento de 2 é a forma mais utilizada para codificação de operandos com sinal. Neste trabalho, apresenta-se uma nova arquitetura para operações com sinal que mantém a mesma regularidade um multiplicador array convencional. Essa arquitetura pode operar com números na base 2m, o que permite a redução do número de linhas de produtos parciais, tendo-se desta forma, ganhos significativos em desempenho e redução de potência. A estratégia proposta apresenta resultados significativamente melhores em relação ao estado da arte. A flexibilidade da arquitetura proposta permite a construção de multiplicadores com diferentes valores de m. Dada a natureza dos algoritmos de filtro FIR e FFT, que envolvem o produto de dados por apropriados coeficientes, procura-se explorar o ordenamento ótimo destes coeficientes nos sentido de minimizar o consumo de potência das arquiteturas implementadas.

Proposta metodológica para otimização experimental de formulações : um estudo de caso no setor alimentício

Esta dissertação de mestrado tem por objetivo apresentar uma metodologia para planejamento e análise de experimentos com formulações, em um contexto de múltiplas variáveis de resposta, para aplicação em indústrias alimentícias de pequeno porte que se caracterizam por utilizar métodos empíricos, ou seja, tentativa e erro, no desenvolvimento de seus produtos. A utilização de Projeto de Experimentos com Formulações, como ferramenta estatística de suporte no desenvolvimento de produtos formulados, tem como objetivo otimizar o planejamento, execução e análise dos experimentos, permitindo que a seqüência de ensaios seja estruturada adequadamente, de forma a traduzir os objetivos a serem atingidos. A metodologia proposta neste trabalho apoia-se nessa ferramenta estatística e põe grande ênfase nas fases de identificação do problema e planejamento, fases nas quais a criatividade do investigador tem uma função muito importante. A metodologia proposta é ilustrada através de um estudo de caso. As etapas do estudo de caso envolvem: identificação do problema; planejamento do experimento; execução do experimento; seleção das melhores rodadas experimentais quanto a características de qualidade sensoriais através de uma análise sensorial comparativa com um produto similar líder de mercado (benchmarking); modelagem individual das variáveis de resposta e definição de uma função objetivo e otimização. A aplicação de Projetos de Experimentos fez-se através da utilização de variáveis independentes, tomando o método adaptável a situações onde há algum tipo de restrição. O desenvolvimento do produto, apresentado no estudo de caso, fez-se em um ambiente de Engenharia Simultânea, propiciado pelas características multifuncionais próprias das empresas em questão, reduzindo substancialmente o tempo de desenvolvimento do novo produto, por meio da realização das várias fases do projeto de forma simultânea.

Otimização de equipes de prestação de serviços : um estudo de caso na área de suporte à micro informática

Essa dissertação aborda o tema simulação de serviços. É apresentada abordagem para estudo de empresas prestadoras de serviços a partir da ótica de avaliação e otimização de produtividade, custos operacionais e lead-time. A abordagem proposta foi desenvolvida com base em estudo de caso realizado junto à empresa Scherer Informática, que atua na área de manutenção de computadores. Os cenários gerados e as simulações dos serviços prestados foram realizados com o suporte de software específico para a modelagem de serviços: o Servicemodel. O estudo possibilitou a empresa conhecer: (i) o melhor dimensionamento das equipes de front office e back office, (ii) a melhor distribuição dos funcionários, que conduz a maior produtividade, (iii) a melhor qualificação da equipe, que minimiza custos operacionais, e, (iv) a análise do lead-time, que permitiu identificar as operações críticas e estabelecer um plano de melhorias visando agilizar o atendimento ao cliente. As etapas observadas no estudo de caso constituem uma abordagem para a otimização de serviços, que considera produtividade, custos operacionais e lead-time. Devido à generalidade das etapas propostas, a abordagem pode ser adaptada para o uso em outras empresas, subsidiando decisões relativas à melhoria dos processos de prestação de serviços.

ANAC : uma ferramenta para a automatização da análise da complexidade de algoritmos

A análise de um algoritmo tem por finalidade melhorar, quando possível, seu desempenho e dar condições de poder optar pelo melhor, dentre os algoritmos existentes, para resolver o mesmo problema. O cálculo da complexidade de algoritmos é muito dependente da classe dos algoritmos analisados. O cálculo depende da função tamanho e das operações fundamentais. Alguns aspectos do cálculo da complexidade, entretanto, não dependem do tipo de problema que o algoritmo resolve, mas somente das estruturas que o compõem, podendo, desta maneira, ser generalizados. Com base neste princípio, surgiu um método para o cálculo da complexidade de algoritmos no pior caso. Neste método foi definido que cada estrutura algorítmica possui uma equação de complexidade associada. Esse método propiciou a análise automática da complexidade de algoritmos. A análise automática de algoritmos tem como principal objetivo tornar o processo de cálculo da complexidade mais acessível. A união da metodologia para o pior caso, associada com a idéia da análise automática de programas, serviu de motivação para o desenvolvimento do protótipo de sistema ANAC, que é uma ferramenta para análise automática da complexidade de algoritmos não recursivos. O objetivo deste trabalho é implementar esta metodologia de cálculo de complexidade de algoritmos no pior caso, com a utilização de técnicas de construção de compiladores para que este sistema possa analisar algoritmos gerando como resultado final a complexidade do algoritmo dada em ordens assintóticas.

A otimização de carteiras internacionais : efeitos dos países emergentes e risco cambial

Este trabalho analisa a existência de benefícios, em termos de risco e retorno, na inclusão de mercados emergentes globais e, em especial, dos países latinoamericanos na formação de carteiras internacionais ótimas, segundo o modelo de Markowitz (1952) e considerando o risco cambial. Para isto, o estudo baseia-se na análise das taxas de retornos mensais, desvio-padrão e coeficientes de correlação em termos de moeda local, dólar, iene, marco alemão e euro, dos Índices dos Mercados de Ações (IMAs) de dezenove países, dos Índices de Bolsa de Valores de São Paulo (IBOVESPA), Buenos Aires (MERVAL), México (IPC), Santiago (IPSA), e de Caracas (IBC), para o período compreendido entre janeiro de 1994 e dezembro de 2000. Utilizou-se o aplicativo SOLVER como ferramenta para a seleção de carteiras ótimas encontrando-se uma taxa livre de risco para este período de estudo como elemento para otimizar as diferentes carteiras internacionais, tomando como base o histórico das taxas das letras do tesouro dos EUA. Tem-se, como restrição, que os investidores não podem efetuar vendas a descoberto. Os resultados indicam que ainda existem evidências dos benefícios da diversificação internacional em termos de desempenho para os investidores mas que estes são menores comparados com aqueles encontrados no trabalho de Zanette (1995) ao considerar o fator cambial. Cabe indicar, também, que a inclusão do componente latino-americano nas diferentes carteiras otimizadas, quase não acrescenta benefício algum do desempenho geral destas carteiras, sendo nulo para as carteiras do investidor japonês.

Aquisição e otimização de mapas de navegação usando redes neurais

A capacidade de encontrar e aprender as melhores trajetórias que levam a um determinado objetivo proposto num ambiente e uma característica comum a maioria dos organismos que se movimentam. Dentre outras, essa e uma das capacidades que têm sido bastante estudadas nas ultimas décadas. Uma consequência direta deste estudo e a sua aplicação em sistemas artificiais capazes de se movimentar de maneira inteligente nos mais variados tipos de ambientes. Neste trabalho, realizamos uma abordagem múltipla do problema, onde procuramos estabelecer nexos entre modelos fisiológicos, baseados no conhecimento biológico disponível, e modelos de âmbito mais prático, como aqueles existentes na área da ciência da computação, mais especificamente da robótica. Os modelos estudados foram o aprendizado biológico baseado em células de posição e o método das funções potencias para planejamento de trajetórias. O objetivo nosso era unificar as duas idéias num formalismo de redes neurais. O processo de aprendizado de trajetórias pode ser simplificado e equacionado em um modelo matemático que pode ser utilizado no projeto de sistemas de navegação autônomos. Analisando o modelo de Blum e Abbott para navegação com células de posição, mostramos que o problema pode ser formulado como uma problema de aprendizado não-supervisionado onde a estatística de movimentação no meio passa ser o ingrediente principal. Demonstramos também que a probabilidade de ocupação de um determinado ponto no ambiente pode ser visto como um potencial que tem a propriedade de não apresentar mínimos locais, o que o torna equivalente ao potencial usado em técnicas de robótica como a das funções potencias. Formas de otimização do aprendizado no contexto deste modelo foram investigadas. No âmbito do armazenamento de múltiplos mapas de navegação, mostramos que e possível projetar uma rede neural capaz de armazenar e recuperar mapas navegacionais para diferentes ambientes usando o fato que um mapa de navegação pode ser descrito como o gradiente de uma função harmônica. A grande vantagem desta abordagem e que, apesar do baixo número de sinapses, o desempenho da rede e muito bom. Finalmente, estudamos a forma de um potencial que minimiza o tempo necessário para alcançar um objetivo proposto no ambiente. Para isso propomos o problema de navegação de um robô como sendo uma partícula difundindo em uma superfície potencial com um único ponto de mínimo. O nível de erro deste sistema pode ser modelado como uma temperatura. Os resultados mostram que superfície potencial tem uma estrutura ramificada.

Método de otimização experimental da qualidade e durabilidade de produtos : um estudo de caso em produto fabricado por injeção de plástico

A melhoria de produtos e processos industriais pode ser realizada utilizando-se métodos de otimização experimental. Este trabalho apresenta um método estruturado para otimização envolvendo variáveis relacionadas com qualidade, comumente utilizadas, e variáveis que descrevem a confiabilidade do produto. O interesse em particular, está em sistematizar uma forma apropriada de determinar o prazo de garantia de produtos, baseado em testes de degradação acelerados. Para atingir este propósito utiliza-se projeto de experimentos conjuntamente com técnicas de avaliação sensorial, utilizada para medir o grau de degradação das amostras provindas dos testes de confiabilidade acelerados. O método é ilustrado com um estudo de caso realizado num produto fabricado em injeção de plástico. No exemplo do estudo de caso, deseja-se modelar a garantia de um piso plástico utilizado, na maternidade, para criação de suínos. Até o momento da realização da análise ocorriam reclamações de problemas com o produto dentro do prazo e garantia. O principal problema era a delaminação do produto devida a intensa fucção entre os cascos do animal e o piso. Um número elevado de reclamações durante o prazo de garantia levou ao desenvolvimento de uma nova composição do piso; o método proposto aqui é utilizado para determinar um prazo de garantia apropriado para produtos novos.

Otimização em dois níveis da orientação e da topologia de cascas laminadas

Este trabalho é uma contribuição para o conhecimento de metodologias de projeto de estruturas de material composto, aplicando métodos de otimização estrutural a cascas laminadas e apresentando uma estratégia em dois níveis. No primeiro nível é realizada a minimização da flexibilidade da estrutura, tendo como variável de projeto a orientação de cada lâmina da estrutura. Utiliza-se Programação Linear Seqüencial (SLP) e direção de tensão principal para otimização da orientação. No segundo nível minimiza-se o volume de cada lâmina, usando a flexibilidade total da estrutura como restrição e a densidade relativa como variável de projeto, também através de SLP. Para evitar aparecimento de áreas com densidades intermediárias, utiliza-se um Método de Continuação, dividindo o nível de otimização topológica em duas ou mais etapas. As formulações desenvolvidas permitem a solução de problemas com múltiplos casos de carregamento. Para a solução da equação de equilíbrio de casca laminada, utiliza-se um elemento finito de casca degenerado de oito nós com integração explícita na direção da espessura. A implementação desse elemento é feita de modo a facilitar a obtenção das derivadas da matriz de rigidez, necessárias na linearização das funções objetivo e restrições. Evita-se assim o uso de derivadas numéricas. Resultados para vários tipos de estrutura são apresentados, incluindo comparações entre diferentes carregamentos, condições de contorno, número de lâminas, espessuras, etc. As soluções obtidas, formas de análise e possíveis aplicações são discutidas.

Modelamento paramétrico e geração de malha em superfícies para aplicações em engenharia

Este trabalho apresenta um conjunto de técnicas para a modelagem paramétrica e geração de malhas de superfícies para uso em sistemas de análise e simulações numéricas pelo Método dos Elementos Finitos. Foram desenvolvidos algoritmos para a geração paramétrica de superfícies, para a determinação das curvas de interseções entre superfícies e para a geração de malhas em superfícies curvas e recortadas. Foram implementas linhas e curvas paramétricas básicas, a partir das quais são geradas superfícies paramétricas de vários tipos que proporcionam uma grande flexibilidade de modelamento geométrico. Curvas e superfícies são geradas e manipuladas de forma interativa. São apresentadas técnicas que simplificam a implementação de linhas e superfícies paramétricas. Foi desenvolvido um algoritmo para determinar as curvas de interseção entre superfícies paramétricas, que são utilizadas como linhas de recorte (trimming lines) para obter geometrias complexas e compostas de várias superfícies. O algoritmo desenvolvido emprega técnicas de subdivisão adaptativa, por quadtrees, em função da curvatura local das superfícies. Primeiramente, obtém-se uma aproximação das curvas de interseção no espaço 3D, através da aproximação por triângulos. Os resultados iniciais são refinados e projetados sobre as duas superfícies envolvidas com algoritmos que permitem obter grande precisão. As curvas de interseção finais são mapeadas nos espaços paramétricos das duas superfícies, porém com uma parametrização única, o que facilita a junção com superfícies adjacentes Um algoritmo de geração de malha foi desenvolvido para gerar malhas triangulares de qualidade sobre as superfícies curvas e recortadas. O algoritmo utiliza um processo de subdivisão adaptativa por quadtrees, similar ao utilizado no algoritmo de interseção, para definir tamanhos de elementos em função da curvatura local. Em seguida, aplica-se um algoritmo tipo advancing front para gerar a malha sobre a superfície. Os algoritmos foram implementados e testados em um ambiente gráfico interativo especialmente desenvolvido para este trabalho. São apresentados vários exemplos que comprovam a eficiência das técnicas e algoritmos propostos, incluindo exemplos de matrizes de conformação mecânica para uso com código de análise METAFOR, análise de sensibilidade para otimização de pré-formas e de modelagem de superfícies compostas recortadas com geração de malhas de qualidade, para uso em análise por Elementos Finitos ou como contorno para geração de elementos tridimensionais.

Desenvolvimento de um sistema de apoio à decisão para a otimização de traçados de obras de engenharia civil : o caso do sistema de defesa contra inundações da cidade de Resistencia, Argentina

O traçado de obras com características lineares num espaço geográfico tem, em princípio, um número muito grande de soluções. A seleção de traçados mais convenientes é hoje abordada pela Pesquisa Operacional por meio da Programação Dinâmica tradicional e das técnicas para resolver o problema conhecido como leastcost- path, (caminho de mínimo custo). Por sua vez, o planejamento de espaços geográficos é feito com o auxílio de técnicas de SIG (sistemas de informação geográfica). O estudo algorítmico dos caminhos de mínimo custo não é novidade e até os programas comerciais para SIG mais utilizados têm incorporado comandos que, com certas limitações, resolvem esse problema. Mas, seja qual for a abordagem, sempre é preciso conhecer a priori a funçãoobjetivo (FO), e isto não é tarefa fácil, pois devem ser conjugados objetivos de satisfação de necessidades sociais, políticas, ambientais e econômicas, o que gera um verdadeiro problema de otimização multiobjetivo e multicritério. Este trabalho teve como foco principal elaborar um modelo de decisão para ajudar na formulação da FO, adotando o paradigma multiobjetivo/multicritério, explorando inclusive o relaxamento difuso de pareceres dos decisores. Foram utilizadas apenas ferramentas computacionais (software e hardware) simples, de ampla difusão entre os engenheiros e de baixo custo, como a planilha de cálculo Excel e o programa Idrisi 32, procurando explorar suas aptidões e limitações, sem recorrer à elaboração e/ou utilização de códigos computacionais próprios, sobre os quais muitas pessoas sentem receios até não serem testados suficientemente. Foi obtido um sistema de apoio à decisão eficaz e de fácil utilização e sua possibilidade de aplicação foi testada na definição do traçado ótimo de parte da defesa norte da cidade de Resistencia (Argentina).

Algoritmos adaptativos para o método GMRES(m)

Nesse trabalho apresentamos algoritmos adaptativos do M´etodo do Res´ıduo M´ınimo Generalizado (GMRES) [Saad e Schultz, 1986], um m´etodo iterativo para resolver sistemas de equa¸c˜oes lineares com matrizes n˜ao sim´etricas e esparsas, o qual baseia-se nos m´etodos de proje¸c˜ao ortogonal sobre um subespa¸co de Krylov. O GMRES apresenta uma vers˜ao reinicializada, denotada por GMRES(m), tamb´em proposta por [Saad e Schultz, 1986], com o intuito de permitir a utiliza¸c˜ao do m´etodo para resolver grandes sistemas de n equa¸c˜oes, sendo n a dimens˜ao da matriz dos coeficientes do sistema, j´a que a vers˜ao n˜ao-reinicializada (“Full-GMRES”) apresenta um gasto de mem´oria proporcional a n2 e de n´umero de opera¸c˜oes de ponto-flutuante proporcional a n3, no pior caso. No entanto, escolher um valor apropriado para m ´e dif´ıcil, sendo m a dimens˜ao da base do subespa¸co de Krylov, visto que dependendo do valor do m podemos obter a estagna¸c˜ao ou uma r´apida convergˆencia. Dessa forma, nesse trabalho, acrescentamos ao GMRES(m) e algumas de suas variantes um crit´erio que tem por objetivo escolher, adequadamente, a dimens˜ao, m da base do subespa¸co de Krylov para o problema o qual deseja-se resolver, visando assim uma mais r´apida, e poss´ıvel, convergˆencia. Aproximadamente duas centenas de experimentos foram realizados utilizando as matrizes da Cole¸c˜ao Harwell-Boeing [MCSD/ITL/NIST, 2003], que foram utilizados para mostrar o comportamento dos algoritmos adaptativos. Foram obtidos resultados muito bons; isso poder´a ser constatado atrav´es da an´alise das tabelas e tamb´em da observa ¸c˜ao dos gr´aficos expostos ao longo desse trabalho.

Implantação da metodologia Seis Sigma e aplicação da técnica estatística projeto de experimentos na resolução de problemas e otimização de processos de fabricação

Resumo não disponível.