Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto. / Submitted by Maurílio Figueiredo (maurilioafigueiredo@yahoo.com.br) on 2014-10-31T18:05:58Z No. of bitstreams: 2 license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) DISSERTAÇÃO_AboragemHíbridaResolver.pdf: 1641214 bytes, checksum: 218f649d0f24be89b2fada8ab32118bf (MD5) / Approved for entry into archive by Gracilene Carvalho (gracilene@sisbin.ufop.br) on 2014-11-19T16:06:22Z (GMT) No. of bitstreams: 2 license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) DISSERTAÇÃO_AboragemHíbridaResolver.pdf: 1641214 bytes, checksum: 218f649d0f24be89b2fada8ab32118bf (MD5) / Made available in DSpace on 2014-11-19T16:06:22Z (GMT). No. of bitstreams: 2 license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) DISSERTAÇÃO_AboragemHíbridaResolver.pdf: 1641214 bytes, checksum: 218f649d0f24be89b2fada8ab32118bf (MD5) Previous issue date: 2014 / A alocação da tripulação (motoristas e cobradores) é uma etapa muito importante no planejamento operacional do Sistema de Transporte Público visto que custo operacional representado pelas escalas de trabalho compõe uma parcela significativa nos custos totais de uma empresa de transporte público. A redução dos custos das escalas de trabalho afetam não são as empresas operadoras, mas também os usuários deste serviço, pois com esta redução há a possibilidade de um maior investimento na qualidade do transporte público e a redução dos preços dos bilhetes. Estes custos, estão estritamente relacionados as normas operacionais impostas pelas empresas e legislações trabalhistas que se retém na definição das jornadas de trabalho dos motoristas e cobradores. Esse trabalho tem a finalidade de propor um novo método computacional capaz de auxiliar o processo da programação da tripulação em empresas de transporte público de ônibus urbano. Os métodos apresentados nesta pesquisa são baseados no uso de um modelo de programação linear inteira, ainda inédito na literatura, se diferindo dos demais pelo fato de que cada jornada e gerada diretamente a partir das tarefas a serem alocadas. Uma metaheurística Late Acceptance Hill Climbing (LAHC) também foi utilizada com o objetivo de resolver problemas de maiores dimensões. Um método híbrido, utilizando o método exato e a metaheurística LAHC, é proposto com o objetivo de obter um refinamento das soluções obtidas pela metaheurística, de modo a reduzir os custos das jornadas geradas. Para avaliar as abordagens apresentadas foram utilizadas instâncias geradas a partir de dados reais de uma empresa do setor de transporte público da cidade de Belo Horizonte/MG. Os modelos computacionais propostos apresentaram resultados satisfatórios, sendo que os custos finais foram reduzidos para a maioria dos testes realizados. Por outro lado, há a necessidade de novos estudos sobre os métodos apresentados, afim de que os mesmos se tornem mais eficientes. __________________________________________________________________________________________ / ABSTRACT: The allocation of crew (drivers and collectors) is a quite important stage of operational planning of Public Transit System once the operational cost represented by the work schedules consist in a significant portion of total costs in a public transit company. Cost reduction of work schedules afects not only the operating company but also the users of this service since there is chance of higher investments in transit quality and reduction of ticket prices because of this cost-cutting. These costs are strictly related to the operational rules established by companies and work laws which refects themselves in the transit drivers and collectors work schedule definition. The goal of this work is to propose a new computational method able to assist the crew planning process in urban bus public transit companies. The methods presented in this work are based on use of an integer linear programming method even unpublished in literature, being diferent from others due the fact that each schedule is created directly from tasks to be allocated. A metaheuristic Late Acceptance Hill Climbing (LAHC) was also utilized with the purpose of solving bigger problems. A hybrid method using the exact method and the metaheuristic LAHC is proposed with the goal of refining solutions gotten through metaheuristic, reducing created schedule costs. To evaluate the presented approaches, problems generated from real data from a public transit company from Belo Horizonte/MG city were used. The proposed computational methods presented satisfactory results and final costs were reduced for most tests performed. On the other hand, other researches about the presented methods are necessary in order that they become more eficient.

Made available in DSpace on 2016-08-29T15:33:21Z (GMT). No. of bitstreams: 1 tese_8728_Diss_final_Joao_Carlos.pdf: 461426 bytes, checksum: 8779aab5fa73bdbf2bdcc5785ea56a4b (MD5) Previous issue date: 2015-03-16 / Em países em desenvolvimento, perdas não-técnicas são consideradas pelas companhias de distribuição de energia como algumas das maiores causas de prejuízos. No Brasil, parte dessas perdas pode ser repassada ao consumidor nas tarifas, entretanto o valor máximo deste repasse é limitado pela agência reguladora, como forma de incentivar melhorias por parte das distribuidoras. Este limite é definido na forma de metas de redução de perdas. O problema de otimização abordado neste trabalho trata da redução de perdas do ponto de vista da distribuidora. Para atingir as metas estabelecidas pela agência reguladora, as distribuidoras possuem várias ações de redução de perdas, que devem ser alocadas em planos multianuais. Estes planos tentam atingir a meta estabelecida, respeitando alguns orçamentos disponíveis, e objetivando sempre obter o maior lucro possível com a alocação das ações. Este trabalho aborda o problema como uma generalização do Problema da Mochila. Uma modelagem formal é definida e a dificuldade da mesma é analisada através de testes computacionais, utilizando um resolvedor genérico aplicado a uma variedade de instâncias para obter a solução exata. Duas heurísticas são então propostas, a primeira baseada em uma abordagem gulosa e a segunda na metaheurística Busca Tabu, e aplicadas ao problema. Finalmente, as técnicas são comparadas considerando a qualidade das soluções encontradas.

La idea central de esta tesis consiste en aprovechar las técnicas metaheurísticas para resolver problemas reales asociados al transporte. Por ende, en esta investigación hemos incluido el desarrollo de algoritmos metaheurísticos, su diseño, aplicación y testeo del software. Los problemas de transporte se caracterizan por su difícil tratamiento, con respecto a su modelado. En particular, en Argentina, la calidad del servicio de transporte público ha sido considerada históricamente como inadecuada, encontrándose típicamente asociada a un reclamo continuo por parte de la sociedad. Por lo tanto, la principal línea de investigación aquí tratada se relaciona con el transporte público de pasajeros, particularmente concentrándose en las localizaciones de las paradas de colectivos y en el establecimiento de las rutas que servirán para prestar un mejor servicio, minimizando los costos globales. Como última parte de nuestras investigaciones, creamos una hiperheurística eficiente basada en el análisis de desempeño de distintas metaheurísticas, cuyos algoritmos individuales desarrollamos y testeamos en primera instancia. Se consideraron las siguientes metaheurísticas: Algoritmos Genéticos, Recocido Simulado y Optimización por Colonia de Hormigas. Como resultado hemos obtenido una técnica hiperheurística que resuelve exitosamente el problema de localización y ruteo para el transporte público. El algoritmo propuesto selecciona y aplica la metaheurística apropiada para cada momento, a fin de obtener un proceso de búsqueda exitoso. Comparaciones con procedimientos bien establecidos reflejan el impacto de un procedimiento hiperheurístico sobre la optimización completa. Las principales contribuciones de esta tesis se pueden resumir como sigue: * Nuevas propuestas para el tratamiento de un problema que aqueja a gran parte de la población mundial como lo es el transporte público. * Aplicación exitosa del enfoque en problemas de transporte no relacionado a las personas, tal como la localización de cañerías. * Técnicas que reducen el número de evaluaciones improductivas mediante la implementación de una memoria interna. * Novedosa selección de vecinos que acelera el proceso de búsqueda. * La capacidad de enlazar nuestra propuesta con software externo. * Estrategia paralela que ofrece notables mejoras en cuanto al tiempo de cómputo a la vez que optimiza los recursos disponibles / The thesis statement concerns taking advantage of metaheuristic techniques as a means to solve realistic problems associated to transport. Then, in this research we have included the development of metaheuristic algorithms, their design, application and software testing. Transport problems are characterized by their difficult treatment, as regards their modeling. In particular, in Argentina, the quality of public transport service has historically been deemed inadequate, being typically marked by continual social demands. Therefore, the main points that this research covered is related to public transport of passengers, particularly concentrating on bus-stop locations and bus-route design so as to offer a better service while minimizing global costs. As the last part of our research work, an efficient hyper-heuristics was created on the basis of the performance analysis of various meta-heuristics, whose individual algorithms were firstly developed and tested. The following meta-heuristics were considered: Genetic Algorithms, Simulated Annealing and Ant Colony Optimization. As a result, we have obtained a hyperheuristic technique that succeeds in solving the location and routing problem for the public transport. The proposed algorithm chooses and applies the most adequate metaheuristic at any time instance, in order to obtain a successful search process. The comparisons with the well-established procedures reflect the impact of a hyperheuristic procedure on the optimization as a whole. The main contributions of this thesis can be summarized as follows: * New proposals for the treatment of a problem that concerns a wide amount of the world population, like the public transport. * Successful application of this approach to transport problems unrelated to persons, like pipeline routing. * Techniques that reduce the number of unproductive evaluations by means of an internal memory implementation. * Novel neighbour choice that speeds up the search process. * The capacity to link our proposal with external software. * Parallel strategy that offers noteworthy improvements as regards computing times, while optimizing the available resources

O crescimento expressivo de dispositivos móveis e serviços associados, aliado a busca constante pela informação, seja ela pessoal ou empresarial cria um novo paradigma, a Internet Móvel. Dispositivos móveis como tablets e celulares, obtiveram crescimento de 300% na participação de acessos à Internet brasileira entre maio de 2011 e maio de 2012. Este percentual atingiu cerca de 2,4% do tráfego total de dados no Brasil. É importante observar a oportunidade e tendência de crescimento desta proporção para os próximos anos, pois países como Estados Unidos e Reino Unido já ultrapassaram a barreira dos 10%, atingindo 10,9% e 13% respectivamente. Já a infraestrutura empregada nas tecnologias de comunicação está em constante evolução. Assim, para se tirar proveito de todas essas facilidades oferecidas pelos dispositivos móveis e portáteis é necessário que a maioria dos locais possua cobertura de sinal. Baseado nesta premissa e nos dados apresentados, este trabalho objetiva desenvolver um modelo matemático capaz de calcular a área de cobertura do sinal das antenas omnidirecionais. Para os experimentos utiliza-se a metaheurística Simulated Annealing com o objetivo de validar o modelo matemático proposto. A metodologia de avaliação desta metaheurística foi adaptada para ser executada no modo clássico e também no modo guloso (Greedy). Foram elaboradas três estratégias de perturbação nominadas de simples, livre e baseadas em Unit Disk Graph (UDG). O modelo desenvolvido permite que a metaheurística atue com antenas de diferentes alcances. Desenvolveu-se uma ferramenta computacional em Linguagem C++ que incorporou todos os cenários das simulações, métodos de avaliação Greedy e Clássico, estratégias de perturbação e interface gráfica. Os resultados experimentais mostram que o modelo de cobertura de sinal proposto auxilia na convergência da metaheurística em ambas as metodologias, SA Clássica e Greedy. / 95 f.

En lo últimos años se han producido numerosos avances en la industria química en áreas tales como: monitoreo de procesos, control basado en modelos, control estadístico multivariable, optimización en tiempo real, diagnóstico de fallas, etc. Sin embargo, existen aún varios tópicos claves que deben resolverse, entre ellos, el diseño de la red de instrumentación de una planta química. Ésta proporciona un conocimiento integral del estado actual de proceso que resulta indispensable para la toma de decisiones. En este contexto aparece la necesidad de desarrollar estrategias sistemáticas que permitan determinar para cada variable de proceso si será medida, y en tal caso, indicar cuántos sensores la medirán y cuáles serán sus características, a la vez que se optimiza un criterio de desempeño preestablecido. Este problema se conoce como Problema de Diseño de Redes de Sensores, PDRS. Frecuentemente es necesario satisfacer restricciones en la calidad de las estimaciones sólo para un conjunto de variables claves. En este caso, se diseña una red de sensores llamada General, sin conocer a priori la cardinalidad del conjunto óptimo de instrumentos. Si bien se han utilizado diferentes modelos de selección óptima de sensores, siempre resulta un problema de optimización combinatorial sujeto a restricciones. En esta tesis se han desarrollado e implementado metodologías de resolución del PDRS para plantas de proceso cuya operación se representa mediante sistemas linealizados de ecuaciones algebraicas. Las estrategias propuestas emplean motores de optimización híbridos con el fin de explotar las ventajas de los algoritmos estocásticos de búsqueda global y local. Dichas metodologías, si bien no garantizan optimalidad, ofrecen buenas soluciones en tiempos que no crecen exponencialmente con el tamaño de la entrada. Además son lo suficientemente flexibles como para ser adaptadas a otras formulaciones del PDRS. Inicialmente se investiga la resolución del diseño empleando nuevos algoritmos de búsqueda local inspirados en la heurística Búsqueda Tabú (BT). Los resultados alcanzados indican que éstos son menos robustos cuando la complejidad de las restricciones aumenta. También se estudia el comportamiento de un algoritmo ad-hoc híbrido basado en Búsqueda Dispersa, que combina una búsqueda global con técnicas de inspección por entornos diferentes a las empleadas en la BT, obteniéndose una mejor reproducibilidad de los resultados. Además se analiza la aplicabilidad de los Algoritmos de Estimación de Distribuciones (AEDs), de orden creciente, para la resolución del PDRS. Si bien todos son capaces de hallar buenas soluciones, la complejidad adicional que implica considerar un modelo gráfico probabilístico de mayor orden no produce una mejora importante en la calidad y repetitividad de las mejores soluciones. Por último se desarrolla una nueva metodología, denominada pPBIL-OS (Parallel Population Based Incremental Learning – Strategic Oscillations). Ésta consiste en un esquema de resolución híbrido que combina las ventajas del algoritmo poblacional PBIL, de orden uno, con la técnica de búsqueda local Oscilaciones Estratégicas, que trabaja en el marco de la BT. El procedimiento emplea un cierto número de subpoblaciones que evolucionan de manera independiente, pudiendo intercambiar información entre ellas con cierta probabilidad. Su desempeño, medido en función de: la calidad y reproducibilidad de las soluciones, la capacidad de resolver problemas de tamaño incremental y los requerimientos de cómputo, resulta muy satisfactorio. / In recent years many improvements have occurred in chemical industries in areas such as: process monitoring, model predictive control, statistical process control, real time optimization, etc. However there exist many key topics which should be solved, e.g., the design of the instrumentation network of a chemical plant. It provides a comprehensive knowledge about the current process state that is very important for the decision making process. In this context, the development of systematic strategies which determine if a process variable will be measured, and indicating this case the quantity of sensors and their features, and also satisfying a performance criterion, is essential. This problem is known as the Sensor Network Design Problem, PDRS. Frequently it is necessary to fulfill some restrictions on the estimation quality of a set of key variables. In this case, a General Sensor Network is designed without knowing in advance the cardinality of the optimum set. Even though different models are used for the optimal selection of instruments, a combinatorial optimization problem subject to constraints always arises. In this thesis, resolution methodologies of the PDRS are developed and implemented for process plants whose operation is represented by a linearized system of algebraic equations. The proposed strategies use hybrid optimization engines that take advantage of the combined use of global and local search stochastic algorithms. Even though these methodologies do not guarantee optimality, they provide good solutions using computation times that do not exponentially depend on the problem size. Furthermore they are flexible enough to be adopted for other formulations of the PDRS. At first the research addresses the design problem using new local search algorithms which are inspired on the Tabu Search (BT). Results indicate that their robustness decreases when the restrictions complexity increases. Furthermore the behaviour of an ad-hoc hybrid algorithm based on Scatter Search is studied. It combines a global search with local search techniques which are different from the ones used by BT. A better solution reproducibility is achieved. Also the applicability of Estimation of Distribution Algorithms (AEDs) of incremental order for the resolution of the PDRS is analyzed. Although they are capable to obtain good solutions, the additional complexity involved in considering a graphical probabilistic model of high order does not improve the solutions quality and reproducibility. At last, a new methodology, called pPBIL-OS (Parallel Population Based Incremental Learning – Strategic Oscillations), is developed. It is a hybrid solving scheme than combines the advantages of the global search algorithm PBIL, of order one, with the local search technique Strategic Oscillations. It works in the framework of the BT. The procedure employs a certain number of subpopulations, which evolve independiently and exchange information among them with a given probability. The strategy performance, which is evaluated in terms of the solutions quality and reproducibility, the capability to solve problems of incremental size and the computation time requirements, is very satisfactory.

Tese de mestrado integrado. Engenharia Industrial e Gestão. Faculdade de Engenharia. Universidade do Porto. 2008

Submitted by Amauri Alves (amauri.alves@ufv.br) on 2015-11-12T16:30:16Z No. of bitstreams: 1 texto completo.pdf: 2506377 bytes, checksum: 20e4041dc3e7d817743c7994b1883fa9 (MD5) / Made available in DSpace on 2015-11-12T16:30:16Z (GMT). No. of bitstreams: 1 texto completo.pdf: 2506377 bytes, checksum: 20e4041dc3e7d817743c7994b1883fa9 (MD5) Previous issue date: 2015-02-25 / Este trabalho aborda o problema Assembly flowshop de três estágios, onde existem m máquinas paralelas no primeiro estágio, uma máquina de transporte no segundo estágio e uma máquina de montagem no terceiro estágio. No primeiro estágio, diferentes partes do produto são fabricadas de forma independente nas máquinas paralelas. No segundo estágio, as peças fabricadas são coletadas e transferidas para o próximo estágio. No terceiro estágio as peças são montadas obtendo o produto final. Este problema possui muitas aplicações em indústrias de manufatura e pertence a classe de problemas de otimização combinatória NP-difícil. Para resolução deste problema é realizada uma abordagem mono-objetivo e uma multi-objetivo, onde a primeira visa encontrar uma sequência de n tarefas que minimize o atraso total, enquanto a segunda busca encontrar uma sequência de n tarefas para minimização simultânea do tempo total de fluxo e do atraso total. Para abordagem mono-objetivo são propostos quatro diferentes algoritmos baseados nas metaheurísticas: o GRASP-RVND, que corresponde a aplicação conjunta das metaheurísticas GRASP (Greedy Randomized Adaptive Search Procedure) e RVND (Random Variable Neighborhood Descent), o ILS (Iterated Local Search), o IG (Iterated Greedy) e o ILS-IG (que corresponde a aplicação conjunta das metaheurísticas ILS e IG). Foram realizados experimentos computacionais para comparar a eficiência dos algoritmos e os resultados obtidos são comparados com os resultados de um algoritmo PSA (Simulated Annealing Híbrido) da literatura. Nos experimentos foram usadas instâncias de pequeno e grande porte. Os resultados dos algoritmos também foram comparados com os resultados obtidos por um modelo de Programação Linear Inteira (MILP) para instâncias de pequeno porte. Os resultados foram analisados estatisticamente e os testes mostram que os algoritmos propostos foram superiores ao PSA em todas as classes de instâncias. Para a abordagem multiobjetivo são propostos dois algoritmos genéticos híbridos, obtidos a partir da aplicação combinada das metaheurísticas NSGA-II (Non-dominated Sorting Genetic Algorithm-II) e IG, sendo que, um deles utiliza uma busca local para melhorar as soluções dominantes. Os algoritmos foram comparados com o algoritmo tradicional NSGA-II. A análise estatística aplicada sobre os resultados obtidos mostra que houve grande melhoria em relação aos resultados gerados pelo NSGA-II. / This paper addresses the Assembly flowshop problem with three stages, where there are m parallel machines in the first stage, a transport machine in the second period and an assembly machine in the third stage. In the first stage, different parts of the product are produced independently in parallel machines. In the second stage, the manufactured parts are collected and transferred to the next stage. In the third stage the parts are assembled to give the final product. This problem has many applications in manufacturing industries and belongs to the class of combinatorial optimization problems NP-hard. In order to solvie this problem, mono- objective and multi-objective approach are proposed, where the first aims to find a n task sequence that minimizes the total tardiness, while the second attempts to find a sequence for simultaneous minimization of the total flow time and the total tardiness. For the mono-objective approach is proposed four different algorithms are proposed based on metaheuristics: GRASP- RVND, which is the combined application of metaheuristics GRASP (Greedy Randomized Adaptive Search Procedure) and RVND (Random Variable Neighborhood Descent), the ILS (Iterated Local Search ), IG (Iterated Greedy) and the ILS-IG (which corresponds to the combined application of the metaheuristics ILS and IG). We performed computational experiments to compare the efficiency of the proposed algorithms, and the obtained results are compared with the results of a PSA (Simulated Annealing Hybrid) literature algorithm. In our experiments we use small and large instances. The results of the algorithms were also compared with the results obtained by an Integer Linear Programming Model (MILP) for small instances. The results were analyzed statistically and the tests show that the proposed algorithms are superior to PSA in all classes of instances. For a multi-objective approach, we propose two hybrid genetic algorithms, obtained from the combined application of the metaheuristics NSGA-II (Non-dominated Sorting Genetic Algorithm-II) and IG. One of these algorithms uses a local search for improve the dominant solutions. The algorithms were compared with the traditional algorithm NSGA-II. The statistical analysis applied to the obtained results shows that there was a great improvement with relation to the results generated by the NSGA-II.

La mayoría de los yacimientos petroleros y gasíferos en el mundo están dispersos y ubicados en zonas remotas, alejadas de los centros de consumo y procesamiento. Por lo tanto, una logística que optimice la ubicación de las líneas de transporte, centros de almacenamiento y plantas de procesamiento del producto final es esencial para maximizar la rentabilidad de la actividad. La factibilidad del potencial uso de la gasolina natural como materia prima petroquímica incentivó nuestro análisis de la logística de distribución de líneas de transporte que permita alcanzar volúmenes de producción adecuados para su posterior transformación en productos de mayor valor. El objetivo central de esta tesis consiste en aprovechar herramientas computacionales modernas para la optimización del diseño de redes de cañerías. Por consiguiente, en esta investigación hemos incluido el desarrollo de técnicas metaheurísticas, su diseño, aplicación y cuidadosas comparaciones. Las principales contribuciones de esta tesis son: Desarrollo de un modelo general para el problema de logística de redes de transporte de gasolina natural. El modelo desarrollado es muy relevante en el plano nacional dado que una región elegida como caso de estudio corresponde a la Provincia de Santa Cruz (Argentina) donde existen yacimientos dispersos, los cuales presentan una importante producción de gasolina natural. Análisis comparativo de varias técnicas metaheurísticas de optimización para resolver el problema de diseño óptimo de redes de cañerías. Implementación de nuevas técnicas metaheurísticas para el desarrollo de modelos de optimización. Se adoptó un enfoque estratégico basado en la hibridación de un algoritmo metaheurístico. Simulated Annealing fue implementado y enlazado con el conocido paquete de software GAMS. De esta forma, se obtuvo el algoritmo híbrido que denominamos SAG (sigla proveniente de: Simulated Annealing with GAMS). El propósito de SAG es encontrar una óptima distribución de la red. Elaboración de un paquete general de software cuyo objetivo es minimizar el costo total de una red de cañerías e identificar la localización estratégica de los nodos concentradores, en los cuales el producto extraído de yacimientos dispersos puede ser almacenado para ser finalmente transportado a plantas de procesamiento. Este diseño también tiene en cuenta las características geográficas de la zona en estudio. El análisis y comparación de desempeño entre los algoritmos Simulated Annealing y Algoritmos Genéticos. Estos algoritmos brindaron buenos resultados con excelentes tiempos de cómputo. Análisis de las respuestas dinámicas de la producción de los yacimientos. En general, la producción de hidrocarburos es afectada por diversas causas, por ejemplo por la explotación de nuevos pozos o por el agotamiento de pozos existentes. Diseño de un sistema de control óptimo del volumen de gasolina natural en el nodo concentrador mediante Algoritmos Genéticos. El objetivo perseguido fue contemplar la dinámica de los pozos y garantizar el suministro a la planta de procesamiento. Empleo de una estrategia paralela que ofrece notables mejoras en cuanto al tiempo de cómputo. / Most oil and gas fields are scattered all over the world, being located in remote areas far away from the consumption or processing centers. Therefore, an optimized logistic system for the transport lines, storage centers and product processing plants is essential to maximize industrial profitability. The feasibility of the potential employment of natural gasoline as a petrochemical raw material encouraged our analysis of the logistics of transportation lines that allows reaching suitable production volumes for their further processing into more valuable products. The main goal of this thesis is to take advantage of modern computing tools to optimize the design of pipeline networks. Therefore, in our research the development of metaheuristic techniques, their design, application and judicious comparison have been included. The main contributions of this thesis are the following: The development of a general model for the network problem associated to the logistics for natural gasoline transport. This model is particularly relevant at national level since the area that was chosen as a case of study is Santa Cruz province (Argentina) where there are scattered fields in which there is an important production of natural gasoline. The comparison of several metaheuristic techniques for the optimization of pipeline-network design problems. The implementation of new metaheuristic techniques for the development of optimization models. A tactic approach was adopted, which is based on the hybridization of a metaheuristic algorithm. Simulated Annealing was implemented and linked with the well-known GAMS software. Thus, the hybrid algorithm, which we called SAG (Simulated Annealing with GAMS), was obtained aiming at getting an efficient distribution of pipeline networks for the transportation of liquid hydrocarbons. The preparation of a general software package in order to minimize the total piping costs and to identify strategic locations for the concentrating nodes, where the product extracted from scattered fields can be stored prior to being transported to processing plants. Geographical features of the related region were taken into account in the design. The performance analysis and the algorithmic comparison between Simulated Annealing and Genetic Algorithm were carried out. These algorithms yielded good results with excellent computing times. The analysis of the dynamic responses of field production. Generally, hydrocarbon production is affected by varied causes, for instance by the exploiting of new wells or the exhaustion of existing ones. The design of an optimal control system for the volume of natural gasoline in the concentrating node by means of Genetic Algorithms. The control objective was to contemplate well dynamics in order to ensure the supply to the processing plant. The use of a parallel strategy that offers significant improvements in terms of computing times. Paola Patricia Oteiza Técnicas Metaheurísticas

Made available in DSpace on 2014-07-29T14:57:48Z (GMT). No. of bitstreams: 1 Dissertacao Carine Rodrigues da Costa.pdf: 991478 bytes, checksum: 516faf301aac129df1d69068892a5ea9 (MD5) Previous issue date: 2011-03-30 / The necessity of solving optimization problems in a reasonable computational time limit makes the development of heuristics be a large research area. Usually, developed heuristics for optimization problems are empirically evaluated by its application to a set of specific instances, comparing to quality solution and computational efforts. Besides, when presenting a new heuristic, the contributions should be scientifically evaluated and reported in an objective way. The quality of a computational experiment report may become evident the difficulty to reproduce the experiment or compare the results with those of other experiments. Part of the origin of these issues comes from the fact that there is no standard for reporting experiments in Computer Science. Therefore, the focus of this work is to investigate methods of conducting experimental research with heuristics, to examine what methods are more favorable and consistent in evaluating these. Thus, the investigation resulted in a compilation with contribution of several authors, which consisted in identifying a set of recommendations, including the formulation of a checklist representing the summary form of all the items that were seen in this study. The results of this review served as the basis for definitining the research and leading a sample study, which consisted in analysis of articles that deal with the Quadratic Assignment Problem (QAP), by checking the necessary items for understanding, reproduction and comparison of the performed experiments. / A necessidade de resolver problemas de otimização em um limite razoável de tempo computacional faz com que o desenvolvimento de heurísticas seja uma grande área de pesquisa. Usualmente, heurísticas desenvolvidas para problemas de otimização são avaliadas empiricamente, pela sua aplicação a um conjunto de instâncias específicas, comparando qualidade da solução e esforços computacionais. Além disso, ao se apresentar uma nova heurística, as contribuições devem ser avaliadas cientificamente e relatadas de uma maneira objetiva. Ao descrever um experimento computacional e relatar os resultados obtidos do mesmo, pode ficar evidente a dificuldade de reproduzir o experimento ou comparar os resultados obtidos com os de outros experimentos. Parte da origem dessas questões vem do fato de que não há padrão para o relato de experimentos na área de Computação. Portanto, o foco deste trabalho é investigar métodos de condução de pesquisa experimental com heurísticas, para analisar quais são os mais favoráveis e consistentes na avaliação destas. Desta forma, a investigação resultou em uma compilação com a contribuição de diversos autores, em que consistiu na identificação de um conjunto de recomendações, com a elaboração de um checklist, representando de forma sumarizada todos os itens vistos nesta pesquisa. Os resultados dessa revisão serviram como base para a definição da pesquisa e condução de um estudo exemplo, que consistiu na análise de artigos que tratam do Problema de Atribuição Quadrática (PAQ), com a verificação dos itens necessários para compreensão, reprodução e comparação dos experimentos realizados.

Neste trabalho é apresentado o projeto de uma fonte de tensão de referência, um circuito capaz de prover uma tensão invariante com a temperatura, a tensão de alimentação e o processo de fabricação. São apresentadas: as equações de funcionamento, os passos para a elaboração da uma topologia final, o dimensionamento dos parâmetros de projeto com o uso de algoritmos metaheurísticos, o desenho do layout e os resultados e análises finais. O projeto emprega a tecnologia CMOS de 0,35 &#956m com quatro camadas de metal da Austria Micro Systems, em que os VTH0\'s dos transistores NMOS e PMOS, modelo típico, são, respectivamente, 0,5 V e -0,7 V. O circuito de fonte de referência é do tipo bandgap e faz a soma ponderada de correntes proporcionais a temperatura para atingir uma tensão de referência. Obteve-se um circuito típico com 0,5 V de tensão de referência, coeficiente de temperatura de 15 ppm/ºC em intervalo de temperatura de -10 a 90ºC em 1,0 V de tensão de alimentação, regulação de linha de 263 ppm/V em um intervalo de variação de 1,0 V a 2,5 V em 27ºC, 2,7 &#956A de corrente consumida e área de 0,11 mm². A introdução de um bloco de ajuste de coeficiente de temperatura, com ajuste digital, permite que mais que 90% dos circuitos produzidos tenham um coeficiente de temperatura de até 30 ppm/ºC. As medidas realizadas no trabalho são provenientes de simulações elétricas realizadas com o ELDO e modelos BSIM3v3. / In this work is presented a design of a reference voltage source, circuits capable to provide an invariant voltage regardless of the temperature, power supply and fabrication process. It\'s presented: the operation equations, the steps to elaborate a final topology, the project parameter sizing using a metaheuristic algorithm, the drawing of the layout, and the final results and its analysis. The design employs an AMS-CMOS 0.35 &#956m technology with four metal levels, whose NMOS and PMOS VTH0\'s for a typical circuit is 0.5 V and -0.7 V. The reference voltage circuit is bandgap and performs a weighted summation of proportional temperature currents to achieve the voltage reference. A typical circuit was obtained with 0.5 V reference voltage, 15 ppm/ºC temperature coefficient in the temperature range of -10 to 90ºC under 1.0 V power supply, 263 ppm/V line regulation in the range of 1.0 V to 2.5 V under 27ºC, 2.7 &#956A power consumption in a 0.11 mm² area. For a projected circuit its also possible to ensure a temperate coefficient under 30 ppm/ºC, for more than 95% of the produced circuits, employing an adjustment block which ought to be digitally calibrated for each circuit.