Made available in DSpace on 2015-03-04T18:51:05Z (GMT). No. of bitstreams: 1 Dissert_MSc_JaquelineAngelo.pdf: 926474 bytes, checksum: da4b07a3aac6c41fe497e0351128bde1 (MD5) Previous issue date: 2008-07-24 / Coordenacao de Aperfeicoamento de Pessoal de Nivel Superior / This dissertation presents the BicriterionAnt, MACS and MONACO Ant Colony algorithms, available in literature, to solve the Multi-Objective Traveling Salesman Problem (MOTSP). The characteristics of the problem and of each algorithm used are presented. Those algorithms were tested in six bi-objective instances of MOTSP. Changes in the original algorithms were implemented to try to produce better results than the original ones. To validate the results and to measure the quality of the solutions, metrics of performance were used which help to identify the best non-dominated solution sets. / Esta dissertação apresenta os algoritmos BicriterionAnt, MACS e MONACO, disponíveis na literatura, baseados em colônia de formigas, para resolução do Problema do Caixeiro Viajante Multiobjetivo (PCVMO). São apresentadas as características do problema e de cada algoritmo utilizado. Estes algoritmos foram testados em seis instâncias bi-objetivo do PCVMO. Foram implementadas algumas alterações na estrutura original dos algoritmos na tentativa de produzir resultados melhores do que os algoritmos originais. Para a avaliação dos resultados e medição da qualidade das soluções, foram utilizadas métricas de desempenho que auxiliam na identificação dos melhores conjuntos de soluções não-dominadas.

Scheduling concerns the allocation of limited resources to tasks over time. In manufacturing systems, scheduling is nothing but assigning the jobs to the available processors over a period of time. Our research focuses on scheduling in systems of parallel processors which is challenging both from the theoretical and practical perspectives. The system of parallel processors is a common occurrence in different types of modern manufacturing systems such as job shop, batch shop and mass production. A variety of important and challenging problems with realistic settings in a system of parallel processors are considered. We consider two types of processors comprising discrete and batch processors. The processor which produces one job at a time is called a discrete processor. Batch processor is a processor that can produce several jobs simultaneously by keeping jobs in a batch form which is commonly seen in semiconductor manufacturing, heat treatment operations and also in chemical processing industries. Our aim is to develop efficient solution methodologies (heuristics/metaheuristics) for three different problems in the thesis. The first two problems consider the objective of minimizing total weighted tardiness in cases of discrete and batch processors where customer delivery time performance is critical. The third problem deals with the objective of minimizing the total weighted completion time in the case of batch processors to reduce work-in-process inventory. Specifically, the first problem deals with the scheduling of parallel identical discrete processors to minimize total weighted tardiness. We develop a metaheuristic based on Ant Colony Optimization(ACO) approach to solve the problem and compare it with the available best heuristics in the literature such as apparent tardiness cost and modified due date rules. An extensive experimentation is conducted to evaluate the performance of the ACO approach on different problem sizes with varied tardiness factors. Our experimentation shows that the proposed ant conony optimization algorithm yields promising results as compared to the best of the available heuristics. The second problem concerns with the scheduling of jobs to parallel identical batch processors for minimizing the total weighted tardiness. It is assumed that the jobs are incompatible in respect of job families indicating that jobs from different families cannot be processed together. We decompose the problem into two stages including batch formation and batch scheduling as in the literature. Ant colony optimization based heuristics are developed in which ACO is used to solve the batch scheduling problem. Our computational experimentation shows that the proposed five ACO based heuristics perform better than the available best traditional dispatching rule called ATC-BATC rule. The third scheduling problem is to minimize the total weighted completion time in a system of parallel identical batch processors. In the real world manufacturing system, jobs to be scheduled come in lots with different job volumes(i.e number of jobs) and priorities. The real settings of lots and high batch capacity are considered in this problem. This scheduling problem is formulated as a mixed integer non-linear program. We develop a solution framework based on the decomposition approach for this problem. Two heuristics are proposed based on the proposed decomposition approach and the performance of these heuristics is evaluated in the cases of two and three batch processors by comparing with the solution of LINGO solver.

The development of a shape optimization solver using the existing Computational Fluid Dynamics (CFD) codes is taken up as topic of research in this thesis. A shape optimizer was initially developed based on Genetic Algorithm (GA) coupled with a CFD solver in an earlier work. The existing CFD solver is based on Kinetic Flux Vector Splitting and uses least squares discretization. This solver requires a cloud of points and their connectivity set, hence this CFD solver is a meshless solver. The advantage of a meshless solver is utilised in avoiding re-gridding (only connectivity regeneration is required) after each shape change by the shape optimizer. The CFD solver is within the optimization loop, hence evaluation of CFD solver after each shape change is mandatory. Although the earlier shape optimizer developed was found to be robust, but it was taking enoromous amount of time to converge to the optimum solution (details in Appendix). Hence a new evolving method, Ant Colony Optimization (ACO), is implemented to replace GA. A shape optimizer is developed coupling ACO and the meshless CFD solver. To the best of the knowledge of the present author, this is the first time when ACO is implemented for aerodynamic shape optimization problems. Hence, an exhaustive validation has become mandatory. Various test cases such as regeneration problems of (1) subsonic - supersonic nozzle with a shock in quasi - one dimensional flow (2) subsonic - supersonic nozzle in a 2-dimensional flow field (3) NACA 0012 airfoil in 2-dimensional flow and (4) NACA 4412 airfoil in 2-dimensional flow have been successfully demonstrated. A comparative study between GA and ACO at algorithm level is performed using the travelling salesman problem (TSP). A comparative study between the two shape optimizers developed, i.e., GA-CFD and ACO-CFD is carried out using regeneration test case of NACA 4412 airfoil in 2-dimensional flow. GA-CFD performs better in the initial phase of optimization and ACO-CFD performs better in the later stage. We have combined both the approaches to develop a hybrid GA-ACO-CFD solver such that the advantages of both GA-CFD and ACO-CFD are retained with the hybrid method. This hybrid approach has 2 stages, namely, (Stage 1) initial optimum search by GA-CFD (coarse search), the best members from the optimized solution from GA-CFD are segregated to form the input for the fine search by ACO-CFD and (Stage 2) final optimum search by ACO-CFD (fine search). It is observed that this hybrid method performs better than either GA-CFD or ACO- CFD, i.e., hybrid method attains better optimum in less number of CFD calls. This hybrid method is applied to the following test cases: (1) regeneration of subsonic-supersonic nozzle with shock in quasi 1-D flow and (2) regeneration of NACA 4412 airfoil in 2-dimensional flow. Two applications on shape optimization, namely, (1) shape optimization of a body in strongly rotating viscous flow and (2) shape optimization of a body in supersonic flow such that it enhances separation of binary species, have been successfully demonstrated using the hybrid GA-ACO-CFD method. A KFVS based binary diffusion solver was developed and validated for this purpose. This hybrid method is now in a state where industrial shape optimization applications can be handled confidently.

Large-scale virtualized data centers require cloud providers to implement scalable, autonomic, and energy-efficient cloud management systems. To address these challenges this thesis provides four main contributions. The first one proposes Snooze, a novel Infrastructure-as-a-Service (IaaS) cloud management system, which is designed to scale across many thousands of servers and virtual machines (VMs) while being easy to configure, highly available, and energy efficient. For scalability, Snooze performs distributed VM management based on a hierarchical architecture. To support ease of configuration and high availability Snooze implements self-configuring and self-healing features. Finally, for energy efficiency, Snooze integrates a holistic energy management approach via VM resource (i.e. CPU, memory, network) utilization monitoring, underload/overload detection and mitigation, VM consolidation (by implementing a modified version of the Sercon algorithm), and power management to transition idle servers into a power saving mode. A highly modular Snooze prototype was developed and extensively evaluated on the Grid'5000 testbed using realistic applications. Results show that: (i) distributed VM management does not impact submission time; (ii) fault tolerance mechanisms do not impact application performance and (iii) the system scales well with an increasing number of resources thus making it suitable for managing large-scale data centers. We also show that the system is able to dynamically scale the data center energy consumption with its utilization thus allowing it to conserve substantial power amounts with only limited impact on application performance. Snooze is an open-source software under the GPLv2 license. The second contribution is a novel VM placement algorithm based on the Ant Colony Optimization (ACO) meta-heuristic. ACO is interesting for VM placement due to its polynomial worst-case time complexity, close to optimal solutions and ease of parallelization. Simulation results show that while the scalability of the current algorithm implementation is limited to a smaller number of servers and VMs, the algorithm outperforms the evaluated First-Fit Decreasing greedy approach in terms of the number of required servers and computes close to optimal solutions. In order to enable scalable VM consolidation, this thesis makes two further contributions: (i) an ACO-based consolidation algorithm; (ii) a fully decentralized consolidation system based on an unstructured peer-to-peer network. The key idea is to apply consolidation only in small, randomly formed neighbourhoods of servers. We evaluated our approach by emulation on the Grid'5000 testbed using two state-of-the-art consolidation algorithms (i.e. Sercon and V-MAN) and our ACO-based consolidation algorithm. Results show our system to be scalable as well as to achieve a data center utilization close to the one obtained by executing a centralized consolidation algorithm.

The building automation industry lacks an affordable, simple, solution for autonomous PID controller tuning when overhead variables fluctuate. In this project, requested by Jitea AB, a solution was developed, utilising step response process modelling, numerical integration of first order differential equations, and Ant Colony Optimization (ACO). The solution was applied to two control schemes; simulated outlet flow from a virtual water tank, and the physical air pressure in the ventilation system of a preschool in Sweden. An open-loop step response provided the transfer function in each case, which, after some manipulation, could be employed to predict the performance of any given set of PID parameters, based on a weighted cost function. This prediction model was used in ACO to find optimal settings. The program was constructed in both Structured Control Language and Structured Text and documented in an approachable way. The results showed that the program was, in both cases, able to eliminate overshoot and retain the settling time (with a slightly raised rise time) achieved with settings tuned per the current methods of Jitea AB. Noise and oscillations present in the physical system did not appear to have any major negative influence on the tuning process. The program performed above Jitea AB’s expectation, and will be tested in more scenarios, as it showed promise. Autonomous implementation could be of societal benefit through increased efficiency and sustainability in a range of processes. In future studies, focus should be on improving the prediction model, and further optimising the ACO variables. / Byggnadsautomationsbranschen saknar en kostnadseffektiv lösning för att autonomt trimma in PID-regulatorer när överordnade variabler fluktuerar. I detta (av Jitea AB beställda) arbete, utvecklades en lösning baserad på stegsvarsmodellering, numerisk integration av första gradens ordinära differentialekvationer och myrkolonisoptimering (ACO). Lösningen applicerades i två regleringsfall; en simulerad utloppsventil från en virtuell vattentank, och det fysiska lufttrycket i ventilationssystemet på en förskola i Sverige. Ett stegsvar med öppen slinga gav en överföringsfunktion i respektive fall, som efter viss manipulering kunde nyttjas för att förutspå prestandan för en uppsättning PID-parametrar baserat på en samlad, viktad kostnadsfunktion. Predikteringsmodellen implementerades i ACO för att finna optimala parametrar. Programmet konstruerades i Structured Control Language och Structured Text, och dokumenterades på ett pedagogiskt sätt. Resultaten visade att programmet (i båda fallen) klarade att eliminera översläng med bibehållen stabiliseringstid (och något förskjuten stigningstid) jämfört med Jitea AB:s existerande trimningsmetod. Signalbrus och oscillationer i det fysiska systemet verkade inte ha någon avsevärd negativ inverkan på trimningsprocessen. Programmet presterade över Jitea AB:s förväntan, och kommer (med tanke på de lovande resultaten) fortsatt att testas i fler scenarion. Implementation av en autonom version skulle kunna innebära flera samhälleliga förmåner i form av ökad verkningsgrad och hållbarhet i en rad processer. I framtida studier bör fokus läggas på att ytterligare förbättra prediktionsmodellen, samt att vidare utforska de optimala myrkolonisvariablerna.

Atualmente existem diferentes ferramentas computacionais para auxílio nos estudos de coordenação da proteção, que permitem traçar as curvas dos relés, de acordo com os parâmetros escolhidos pelos projetistas. Entretanto, o processo de escolha das curvas consideradas aceitáveis, com um elevado número de possibilidades e variáveis envolvidas, além de complexo, requer simplificações e iterações do tipo tentativa e erro. Neste processo, são fatores fundamentais tanto a experiência e o conhecimento do especialista, quanto um árduo trabalho, sendo que a coordenação da proteção é qualificada pela IEEE Std. 242 como sendo mais uma arte do que uma ciência. Este trabalho apresenta o desenvolvimento de um algoritmo genético e de um algoritmo inspirado em otimização por colônia de formigas, para automatizar e otimizar a coordenação da função de sobrecorrente de fase de relés digitais microprocessados (IEDs), em subestações industriais. Seis estudos de caso, obtidos a partir de um modelo de banco de dados, baseado em um sistema elétrico industrial real, são avaliados. Os algoritmos desenvolvidos geraram, em todos os estudos de caso, curvas coordenadas, atendendo a todas as restrições previamente estabelecidas e as diferenças temporais de atuação dos relés, no valor de corrente de curto circuito trifásica, apresentaram-se muito próximas do estabelecido como ótimo. As ferramentas desenvolvidas demonstraram potencialidade quando aplicadas nos estudos de coordenação da proteção, tendo resultados positivos na melhoria da segurança das instalações, das pessoas, da continuidade do processo e do impedimento de emissões prejudiciais ao meio ambiente. / Nowadays there are several computational tools applied to the protection coordination studies, which allow observe the curves of the relays, according to the parameters chosen by the designers. However, the process of choosing the curves considered acceptable, with a great number of possibilities and variables involved, is difficult and, moreover, requires simplifications and some trial and error iterations. In this process, the key factors are the expert experience and knowledge as well as a hard work. The protection coordination is described by IEEE Std. 242 as more of an art than a science. This paper presents the development of a genetic algorithm and an algorithm based on an ant colony optimization to automate and optimize the coordination of overcurrent curves using intelligent electronic devices (IEDs) in industrial substations. Six case studies, obtained from a database model based on an actual industrial electrical system, were evaluated. The developed algorithms generated, in all case studies, coordinated curves, complying with all previous established restrictions. The temporal differences of the curves, at three-phase short circuit current values, were very close to the set as optimal. The developed tools are a valuable contribution to the protection coordination studies, improving the safety of the equipment and the people, the process reliability and the prevention of harmful emissions to the environment.

Made available in DSpace on 2016-06-02T19:05:47Z (GMT). No. of bitstreams: 1 3340.pdf: 982188 bytes, checksum: 49ba39146aa7542a1670dd3d90507739 (MD5) Previous issue date: 2010-06-28 / Financiadora de Estudos e Projetos / In the context of automated manufacturing systems, combinatorial optimization problems, such as determining the production schedule, have been focused in many studies due to the high degree of complexity to their resolution. Several studies point to use of metaheuristics for the problem dealt, where different approaches perspectives have been proposed in order to find good solutions in a short time. In this paper, we propose an approach based on Ant Colony Optimization metaheuristic (ACO) for the reactive production scheduling problem in an FMS aiming the combination of problem characteristics with metaheuristic characteristics. For this, the problem is addressed from two perspectives, based on modeling and the search method. The problem representation is characterized by a description of the problem at the operations level, since the production schedule is included in this context. On the model is applied a constructive search method based on ACO that using the collaboration principle, establishing a relationship between operations so that it lead the search for promising regions of the solution space. The goal of this work is to obtain a reactive programming in acceptable response time in order to minimize the makespan values. Experimental results showed an improvement of the results obtained so far by other approaches. / No contexto de Sistemas Automatizados de Manufatura, problemas de otimização combinatória, como determinar a programação da produção, têm sido foco de estudo em muitas pesquisas devido ao alto grau de complexidade para sua resolução. Diversos trabalhos apontam para o uso de metaheurísticas para o tratamento do problema, onde diferentes perspectivas de abordagens têm sido propostas visando encontrar soluções de qualidade em um curto espaço de tempo. Neste trabalho, é proposta uma abordagem baseada na metaheurística Otimização por Colônia de Formigas (Ant Colony Optimization ACO) para o problema de programação reativa da produção em um FMS, com o objetivo de conciliar as características do problema com as características da metaheurística. Para isso, o problema é tratado em duas perspectivas, com base na modelagem e no método de busca. A modelagem do problema é caracterizada por uma descrição do problema em nível de operações, uma vez que a programação da produção está incluída neste contexto. Sobre o modelo é aplicado um método de busca construtiva baseado em ACO que usando o princípio de colaboração, estabelece uma relação entre as operações de forma que esta direcione a busca para regiões promissoras do espaço de soluções. O Objetivo deste trabalho é obter uma programação reativa em tempo de resposta aceitável, visando minimizar o valor de makespan. Resultados experimentais mostraram uma melhoria dos resultados até então obtidos por outras abordagens.

Made available in DSpace on 2016-12-12T17:38:37Z (GMT). No. of bitstreams: 1 ALEXANDRE ITTNER.pdf: 1538757 bytes, checksum: f2722c8cdafb578a75d3a153751fa3a1 (MD5) Previous issue date: 2010-08-24 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This dissertation presents a research work on the Cable Routing Problem in Electrical Panels and its resolution by computational means. Strictly, this work shows a formal definition for the problem, elaborates on the available computational approaches, and suggests several algorithms for its resolution. At last, an application developed using the proposed algorithms is described, yielding good results for the problem instances typically found in the industry. / Esta dissertação apresenta um estudo sobre as características do Problema do Roteamento de Cabos em Painéis Elétricos e sua solução por meios computacionais. Especificamente, este trabalho apresenta uma definição formal para o problema, descreve as abordagens computacionais disponíveis e propõe uma série de algoritmos para sua solução. Por fim, descreve-se um aplicativo desenvolvido empregando os algoritmos propostos que permite a obtenção de bons resultados para as instâncias deste problema tipicamente encontradas na indústria.

Made available in DSpace on 2015-03-03T15:47:46Z (GMT). No. of bitstreams: 1 LeonardoCTB_DISSERT.pdf: 2119704 bytes, checksum: 5bdd21de8bfa668bba821593cdd5289f (MD5) Previous issue date: 2011-02-07 / Conselho Nacional de Desenvolvimento Cient?fico e Tecnol?gico / Multi-objective combinatorial optimization problems have peculiar characteristics that require optimization methods to adapt for this context. Since many of these problems are NP-Hard, the use of metaheuristics has grown over the last years. Particularly, many different approaches using Ant Colony Optimization (ACO) have been proposed. In this work, an ACO is proposed for the Multi-objective Shortest Path Problem, and is compared to two other optimizers found in the literature. A set of 18 instances from two distinct types of graphs are used, as well as a specific multiobjective performance assessment methodology. Initial experiments showed that the proposed algorithm is able to generate better approximation sets than the other optimizers for all instances. In the second part of this work, an experimental analysis is conducted, using several different multiobjective ACO proposals recently published and the same instances used in the first part. Results show each type of instance benefits a particular type of instance benefits a particular algorithmic approach. A new metaphor for the development of multiobjective ACOs is, then, proposed. Usually, ants share the same characteristics and only few works address multi-species approaches. This works proposes an approach where multi-species ants compete for food resources. Each specie has its own search strategy and different species do not access pheromone information of each other. As in nature, the successful ant populations are allowed to grow, whereas unsuccessful ones shrink. The approach introduced here shows to be able to inherit the behavior of strategies that are successful for different types of problems. Results of computational experiments are reported and show that the proposed approach is able to produce significantly better approximation sets than other methods / Problemas de otimiza??o combinat?ria multiobjetivo apresentam caracter?sticas peculiares que exigem que t?cnicas de otimiza??o se adaptem a esse contexto. Como muitos desses problemas s?o NP-?rduos, o uso de metaheur?sticas tem crescido nos ?ltimos anos. Particularmente, muitas abordagens que utilizam a Otimiza??o por Col?nias de Formigas t?m sido propostas. Neste trabalho, prop?e-se um algoritmo baseado em col?nias de formigas para o Problema do Caminho mais Curto Multiobjetivo, e compara-se o algoritmo proposto com dois otimizadores encontrados na literatura. Um conjunto de 18 inst?ncias oriundas de dois tipos de grafos ? utilizado, al?m de uma metodologia espec?fica para a avalia??o de otimizadores multiobjetivo. Os experimentos iniciais mostram que o algoritmo proposto consegue gerar conjuntos de aproxima??o melhores que os demais otimizadores para todas as inst?ncias. Na segunda parte do trabalho, uma an?lise experimental de diferentes abordagens publicadas para col?nias de formigas multiobjetivo ? realizada, usando as mesmas inst?ncias. Os experimentos mostram que cada tipo de inst?ncia privilegia uma abordagem algor?tmica diferente. Uma nova met?fora para o desenvolvimento deste tipo de metaheur?stica ? ent?o proposta. Geralmente, formigas possuem caracter?sticas comuns e poucos artigos abordam o uso de m?ltiplas esp?cies. Neste trabalho, uma abordagem com m?ltiplas esp?cies competindo por fontes de comida ? proposta. Cada esp?cie possui sua pr?pria estrat?gia de busca e diferentes esp?cies n?o tem acesso ? informa??o dada pelo ferom?nio das outras. Como na natureza, as popula??es de formigas bem sucedidas tem a chance de crescer, enquanto as demais se reduzem. A abordagem apresentada aqui mostra-se capaz de herdar o comportamento de estrat?gias bem-sucedidas em diferentes tipos de inst?ncias. Resultados de experimentos computacionais s?o relatados e mostram que a abordagem proposta produz conjuntos de aproxima??o significativamente melhores que os outros m?todos

Atualmente existem diferentes ferramentas computacionais para auxílio nos estudos de coordenação da proteção, que permitem traçar as curvas dos relés, de acordo com os parâmetros escolhidos pelos projetistas. Entretanto, o processo de escolha das curvas consideradas aceitáveis, com um elevado número de possibilidades e variáveis envolvidas, além de complexo, requer simplificações e iterações do tipo tentativa e erro. Neste processo, são fatores fundamentais tanto a experiência e o conhecimento do especialista, quanto um árduo trabalho, sendo que a coordenação da proteção é qualificada pela IEEE Std. 242 como sendo mais uma arte do que uma ciência. Este trabalho apresenta o desenvolvimento de um algoritmo genético e de um algoritmo inspirado em otimização por colônia de formigas, para automatizar e otimizar a coordenação da função de sobrecorrente de fase de relés digitais microprocessados (IEDs), em subestações industriais. Seis estudos de caso, obtidos a partir de um modelo de banco de dados, baseado em um sistema elétrico industrial real, são avaliados. Os algoritmos desenvolvidos geraram, em todos os estudos de caso, curvas coordenadas, atendendo a todas as restrições previamente estabelecidas e as diferenças temporais de atuação dos relés, no valor de corrente de curto circuito trifásica, apresentaram-se muito próximas do estabelecido como ótimo. As ferramentas desenvolvidas demonstraram potencialidade quando aplicadas nos estudos de coordenação da proteção, tendo resultados positivos na melhoria da segurança das instalações, das pessoas, da continuidade do processo e do impedimento de emissões prejudiciais ao meio ambiente. / Nowadays there are several computational tools applied to the protection coordination studies, which allow observe the curves of the relays, according to the parameters chosen by the designers. However, the process of choosing the curves considered acceptable, with a great number of possibilities and variables involved, is difficult and, moreover, requires simplifications and some trial and error iterations. In this process, the key factors are the expert experience and knowledge as well as a hard work. The protection coordination is described by IEEE Std. 242 as more of an art than a science. This paper presents the development of a genetic algorithm and an algorithm based on an ant colony optimization to automate and optimize the coordination of overcurrent curves using intelligent electronic devices (IEDs) in industrial substations. Six case studies, obtained from a database model based on an actual industrial electrical system, were evaluated. The developed algorithms generated, in all case studies, coordinated curves, complying with all previous established restrictions. The temporal differences of the curves, at three-phase short circuit current values, were very close to the set as optimal. The developed tools are a valuable contribution to the protection coordination studies, improving the safety of the equipment and the people, the process reliability and the prevention of harmful emissions to the environment.