Hundreds of steel products need to be scheduled on a single or parallel machine in a steel plant every week. A good feasible schedule may save the company millions of dollars compared to a bad one. Single and parallel machine scheduling are also encountered often in many other industries, making it a crucial research topic for both the process system engineering and operations research communities. Single or parallel machine scheduling can be a challenging combinatorial optimization problem when a large number of jobs are to be scheduled. Each job has unique job characteristics, resulting in different setup times/costs depending on the processing sequence. They also have specific release dates to follow and due dates to meet. This work presents both an exact method using mixed-integer quadratic programming, and an approximate method with metaheuristics to solve real-world large-scale single/parallel machine scheduling problems faced in a steel plant. More than 1000 or 350 jobs are to be scheduled within a one-hour time limit in the single or parallel machine problem, respectively. The objective of the single machine scheduling is to minimize a combined total changeover, total earliness, and total tardiness cost, whereas the objective of the parallel machine scheduling is to minimize an objective function comprising the gaps between jobs before a critical time in a schedule, the total changeover cost, and the total tardiness cost. The exact method is developed to benchmark computation time for a small-scale single machine problem, but is not practical for solving the actual large-scale problem. A metaheuristic algorithm centered on variable neighborhood descent is developed to address the large-scale single machine scheduling with a sliding-window decomposition strategy. The algorithm is extended and modified to solve the large-scale parallel machine problem. Statistical tests, including Student's t-test and ANOVA, are conducted to determine efficient solution strategies and good parameters to be used in the metaheuristics. / Thesis / Master of Applied Science (MASc)

Yes / An Improved Discrete Cuckoo Search (IDCS) is proposed in this paper to solve resource-constrained project scheduling problems (RCPSPs). The original Cuckoo Search (CS) was inspired by the breeding behaviour of some cuckoo species and was designed specifically for application in continuous optimisation problems, in which the algorithm had been demonstrated to be effective. The proposed IDCS aims to improve the original CS for solving discrete scheduling problems by reinterpreting its key elements: solution representation scheme, Lévy flight and solution improvement operators. An event list solution representation scheme has been used to present projects and a novel event movement and an event recombination operator has been developed to ensure better quality of received results and improve the efficiency of the algorithm. Numerical results have demonstrated that the proposed IDCS can achieve a competitive level of performance compared to other state-of-the-art metaheuristics in solving a set of benchmark instances from a well-known PSPLIB library, especially in solving complex benchmark instances. / Partially funded by the Innovate UK project HARNET – Harmonised Antennas, Radios and Networks under contract no. 100004607.

Thesis (PhD (Logistics))--University of Stellenbosch, 2011. / ENGLISH ABSTRACT: The design of a water distribution system (WDS) involves finding an acceptable trade-off between cost minimisation and the maximisation of numerous system benefits, such as hydraulic reliability and surplus capacity. The primary design problem involves cost-effective specifica- tion of a pipe network layout and pipe sizes (which are typically available in a discrete set of commercial diameters) in order to satisfy expected consumer water demands within required pressure limits. The problem may be extended to consider the design of additional WDS com- ponents, such as reservoirs, tanks, pumps and valves. Practical designs must also cater for the uncertainty of demand, the requirement of surplus capacity for future growth, and the hydraulic reliability of the system under different demand and potential failure conditions. A detailed literature review of exact and approximate approaches towards single-objective (minimum cost) WDS design optimisation is provided. Essential topics which have to be included in any modern WDS design paradigm (such as demand estimation, reliability quantification, tank design and pipe layout) are discussed. A number of formative concepts in multi-objective evo- lutionary optimisation are also reviewed (including a generic problem formulation, performance evaluation measures, comparative testing strategies, and suitable classes of metaheuristics). The two central themes of this dissertation are conducting multi-objective WDS design optimi- sation using metaheuristics, and a critical examination of surrogate measures used to quantify WDS reliability. The aim in the first theme is to compare numerous modern metaheuristics, in- cluding several multi-objective evolutionary algorithms, an estimation of distribution algorithm and a recent hyperheuristic named AMALGAM (an evolutionary framework for the simulta- neous incorporation of multiple metaheuristics applied here for the first time to a real-world problem), in order to determine which approach is most capable with respect to WDS design optimisation. Several novel metaheuristics are developed, as well as a number of new variants of existing algorithms, so that a total of twenty-three algorithms were compared. Testing with respect to eight small-to-large-sized WDS benchmarks from the literature reveals that the four top-performing algorithms are mutually non-dominated with respect to the vari- ous performance metrics. These algorithms are NSGA-II, TAMALGAMJndu, TAMALGAMndu and AMALGAMSndp (the last three being novel variants of AMALGAM). However, when these four algorithms are applied to the design of a very large real-world benchmark, the AMALGAM paradigm outperforms NSGA-II convincingly, with AMALGAMSndp exhibiting the best perfor- mance overall. As part of this study, a novel multi-objective greedy algorithm is developed by combining several heuristic design methods from the literature in order to mimic the design strategy of a human engineer. This algorithm functions as a powerful local search. However, it is shown that such an algorithm cannot compete with modern metaheuristics, which employ advanced strategies in order to uncover better solutions with less computational effort. The second central theme involves the comparison of several popular WDS reliability surro- gate measures (namely the Resilience Index, Network Resilience, Flow Entropy, and a novel mixed surrogate measure) in terms of their ability to produce designs that are robust against pipe failure and water demand variation. This is the first systematic study on a number of WDS benchmarks in which regression analysis is used to compare reliability surrogate measures with probabilistic reliability typically derived via simulation, and failure reliability calculated by considering all single-pipe failure events, with both reliability types quantified by means of average demand satisfaction. Although no single measure consistently outperforms the others, it is shown that using the Resilience Index and Network Resilience yields designs that achieve a better positive correlation with both probabilistic and failure reliability, and while the Mixed Surrogate measure shows some promise, using Flow Entropy on its own as a quantifier of re- liability should be avoided. Network Resilience is identified as being a superior predictor of failure reliability, and also having the desirable property of supplying designs with fewer and less severe size discontinuities between adjacent pipes. For this reason, it is recommended as the surrogate measure of choice for practical application towards design in the WDS industry. AMALGAMSndp is also applied to the design of a real South African WDS design case study in Gauteng Province, achieving savings of millions of Rands as well as significant reliability improvements on a preliminary engineered design by a consulting engineering firm. / AFRIKAANSE OPSOMMING: Die ontwerp van waterverspreidingsnetwerke (WVNe) behels die soeke na ’n aanvaarbare afruiling tussen koste-minimering en die maksimering van ’n aantal netwerkvoordele, soos hidroliese betroubaarheid en surpluskapasiteit. Die primere ontwerpsprobleem behels ’n koste-doeltreffende spesifikasie van ’n netwerkuitleg en pypgroottes (wat tipies in ’n diskrete aantal kommersiele deursnedes beskikbaar is) wat aan gebruikersaanvraag binne sekere drukspesifikasies voldoen. Die probleem kan uitgebrei word om die ontwerp van verdere WVN-komponente, soos op- gaardamme, opgaartenks, pompe en kleppe in ag te neem. Praktiese WVN-ontwerpe moet ook voorsiening maak vir onsekerheid van aanvraag, genoegsame surpluskapsiteit vir toekom- stige netwerkuitbreidings en die hidroliese betroubaarheid van die netwerk onder verskillende aanvraag- en potensiele falingsvoorwaardes. ’n Omvattende literatuurstudie word oor eksakte en benaderde oplossingsbenaderings tot enkel- doelwit (minimum koste) WVN-ontwerpsoptimering gedoen. Sentrale temas wat by heden- daagse WVN-ontwerpsparadigmas ingesluit behoort te word (soos aanvraagvooruitskatting, die kwantifisering van betroubaarheid, tenkontwerp en netwerkuitleg), word uitgelig. ’n Aantal basiese konsepte in meerdoelige evolusionˆere optimering (soos ’n generiese probleemformulering, werkverrigtingsmaatstawwe, vergelykende toetsingstrategie¨e, en sinvolle klasse metaheuristieke vir WVN-ontwerp) word ook aangeraak. Die twee sentrale temas in hierdie proefskrif is meerdoelige WVN-ontwerpsoptimering deur mid- del van metaheuristieke, en ’n kritiese evaluering van verskeie surrogaatmaatstawwe vir die kwantifisering van netwerkbetroubaarheid. Die doel in die eerste tema is om ’n aantal moderne metaheuristieke, insluitend verskeie meerdoelige evolusionere algoritmes en die onlangse hiper- heuristiek AMALGAM (’n evolusionere raamwerk vir die gelyktydige insluiting van ’n aantal metaheuristieke wat hier vir die eerste keer op ’n praktiese probleem toegepas word), met mekaar te vergelyk om sodoende ’n ideale benadering tot WVN-ontwerpoptimering te identi- fiseer. Verskeie nuwe metaheuristieke sowel as ’n aantal nuwe variasies op bestaande algoritmes word ontwikkel, sodat drie en twintig algoritmes in totaal met mekaar vergelyk word. Toetse aan die hand van agt klein- tot mediumgrootteWVN-toetsprobleme uit die literatuur dui daarop dat die vier top algoritmes mekaar onderling ten opsigte van verskeie werkverrigtings- maatstawwe domineer. Hierdie algoritmes is NSGA-II, TAMALGAMJndu, TAMALGAMndu en AMALGAMSndp, waarvan laasgenoemde drie nuwe variasies op AMALGAM is. Wanneer hierdie vier algoritmes egter vir die ontwerp van ’n groot WVN-toetsprobleem ingespan word, oortref die AMALGAM-paradigma die NSGA-II oortui-gend, en lewer AMALGAMSndp die beste resultate. As deel van hierdie studie is ’n nuwe meerdoelige gulsige algoritme ontwerp wat verskeie heuristiese ontwerpsmetodologiee uit die literatuur kombineer om sodoende die on- twerpstrategie van ’n ingenieur na te boots. Hierdie algoritme funksioneer as ’n kragtige lokale soekprosedure, maar daar word aangetoon dat die algoritme nie met moderne metaheuristieke, wat gevorderde soekstrategie¨e inspan om beter oplossings met minder berekeningsmoeite daar te stel, kan meeding nie. Die tweede sentrale tema behels die vergelyking van ’n aantal gewilde surrogaatmaatstawwe vir die kwantifisering van WVN-betroubaarheid (naamlik die elastisiteitsindeks, netwerkelastisiteit, vloei-entropie en ’n gemengde surrogaatmaatstaf ) in terme van die mate waartoe hul gebruik kan word om WVNe te identifiseer wat robuust is ten opsigte van pypfaling en variasie in aanvraag. Hierdie proefskrif bevat die eerste sistematiese vergelyking deur middel van regressie-analise van ’n aantal surrogaatmaatstawwe vir die kwantifisering van WVN-betroubaarheid en stogastiese betroubaarheid (wat tipies via simulasie bepaal word) in terme van ’n aantal toetsprobleme in die literatuur. Alhoewel geen enkele maatstaf as die beste na vore tree nie, word daar getoon dat gebruik van die elastisiteitsindeks en netwerkelastisiteit lei na WNV-ontwerpe met ’n groter positiewe korrelasie ten opsigte van beide stogastiese betroubaarheid en falingsbetroubaarheid. Verder toon die gebruik van die gemengde surrogaatmaatstaf potensiaal, maar die gebruik van vloei-entropie op sy eie as kwantifiseerder van betroubaarheid behoort vermy te word. Netwerkelastisiteit word as ’n hoe-gehalte indikator van falingsbetroubaarheid geidentifiseer en het ook die eienskap dat dit daartoe instaat is om ontwerpe met ’n kleiner aantal diskontinuiteite sowel as van ’n minder ekstreme graad van diskontinuiteite tussen deursnedes van aangrensende pype daar te stel. Om hierdie rede word netwerkelastisiteit as die surogaatmaatstaf van voorkeur aanbeveel vir toepassings van WVN-ontwerpe in die praktyk. AMALGAM word ook ten opsigte van ’n werklike Suid-Afrikaanse WVN-ontwerp gevallestudie in Gauteng toegepas. Hierdie toepassing lei na die besparing van miljoene rande asook noe- menswaardige verbeterings in terme van netwerkbetroubaarheid in vergeleke met ’n aanvanklike ingenieursontwerp deur ’n konsultasiefirma.

La résolution satisfaisante d'un problème d'optimisation difficile, qui comporte un grand nombre de solutions sous-optimales, justifie souvent le recours à une métaheuristique puissante. La majorité des algorithmes utilisés pour résoudre ces problèmes d'optimisation sont les métaheuristiques à population. Parmi celles-ci, nous intéressons à l'Optimisation par Essaim Particulaire (OEP, ou PSO en anglais) qui est apparue en 1995. PSO s'inspire de la dynamique d'animaux se déplaçant en groupes compacts (essaims d'abeilles, vols groupés d'oiseaux, bancs de poissons). Les particules d'un même essaim communiquent entre elles tout au long de la recherche pour construire une solution au problème posé, et ce en s'appuyant sur leur expérience collective. L'algorithme PSO, qui est simple à comprendre, à programmer et à utiliser, se révèle particulièrement efficace pour les problèmes d'optimisation à variables continues. Cependant, comme toutes les métaheuristiques, PSO possède des inconvénients, qui rebutent encore certains utilisateurs. Le problème de convergence prématurée, qui peut conduire les algorithmes de ce type à stagner dans un optimum local, est un de ces inconvénients. L'objectif de cette thèse est de proposer des mécanismes, incorporables à PSO, qui permettent de remédier à cet inconvénient et d'améliorer les performances et l'efficacité de PSO. Nous proposons dans cette thèse deux algorithmes, nommés PSO-2S et DEPSO-2S, pour remédier au problème de la convergence prématurée. Ces algorithmes utilisent des idées innovantes et se caractérisent par de nouvelles stratégies d'initialisation dans plusieurs zones, afin d'assurer une bonne couverture de l'espace de recherche par les particules. Toujours dans le cadre de l'amélioration de PSO, nous avons élaboré une nouvelle topologie de voisinage, nommée Dcluster, qui organise le réseau de communication entre les particules. Les résultats obtenus sur un jeu de fonctions de test montrent l'efficacité des stratégies mises en oeuvre par les différents algorithmes proposés. Enfin, PSO-2S est appliqué à des problèmes pratiques, en segmentation d'images et en électronique / The successful resolution of a difficult optimization problem, comprising a large number of sub optimal solutions, often justifies the use of powerful metaheuristics. A wide range of algorithms used to solve these combinatorial problems belong to the class of population metaheuristics. Among them, Particle Swarm Optimization (PSO), appeared in 1995, is inspired by the movement of individuals in a swarm, like a bee swarm, a bird flock or a fish school. The particles of the same swarm communicate with each other to build a solution to the given problem. This is done by relying on their collective experience. This algorithm, which is easy to understand and implement, is particularly effective for optimization problems with continuous variables. However, like several metaheuristics, PSO shows some drawbacks that make some users avoid it. The premature convergence problem, where the algorithm converges to some local optima and does not progress anymore in order to find better solutions, is one of them. This thesis aims at proposing alternative methods, that can be incorporated in PSO to overcome these problems, and to improve the performance and the efficiency of PSO. We propose two algorithms, called PSO-2S and DEPSO-2S, to cope with the premature convergence problem. Both algorithms use innovative ideas and are characterized by new initialization strategies in several areas to ensure good coverage of the search space by particles. To improve the PSO algorithm, we have also developed a new neighborhood topology, called Dcluster, which can be seen as the communication network between the particles. The obtained experimental results for some benchmark cases show the effectiveness of the strategies implemented in the proposed algorithms. Finally, PSO-2S is applied to real world problems in both image segmentation and electronics fields

Dans la pratique, beaucoup de problèmes d'optimisation sont dynamiques : leur fonction objectif (ou fonction de coût) évolue au cours du temps. L'approche principalement adoptée dans la littérature consiste à adapter des algorithmes d'optimisation statique à l'optimisation dynamique, en compensant leurs défauts intrinsèques. Plutôt que d'emprunter cette voie, déjà largement explorée, l'objectif principal de cette thèse est d'élaborer un algorithme entièrement pensé pour l'optimisation dynamique. La première partie de cette thèse est ainsi consacrée à la mise au point d'un algorithme, qui doit non seulement se démarquer des algorithmes concurrents par son originalité, mais également être plus performant. Dans ce contexte, il s'agit de développer une métaheuristique d'optimisation dynamique. Deux algorithmes à base d'agents, MADO (MultiAgent algorithm for Dynamic Optimization) et MLSDO (Multiple Local Search algorithm for Dynamic Optimization), sont proposés et validés sur les deux principaux jeux de tests existant dans la littérature en optimisation dynamique : MPB (Moving Peaks Benchmark) et GDBG (Generalized Dynamic Benchmark Generator). Les résultats obtenus sur ces jeux de tests montrent l'efficacité des stratégies mises en oeuvre par ces algorithmes, en particulier : MLSDO est classé premier sur sept algorithmes évalués sur GDBG, et deuxième sur seize algorithmes évalués sur MPB. Ensuite, ces algorithmes sont appliqués à des problèmes pratiques en traitement de séquences d'images médicales (segmentation et recalage de séquences ciné-IRM cérébrales). A notre connaissance, ce travail est innovant, en ce sens que l'approche de l'optimisation dynamique n'avait jamais été explorée pour ces problèmes. Les gains de performance obtenus montrent l'intérêt d'utiliser les algorithmes d'optimisation dynamique proposés pour ce type d'applications / Many real-world problems are dynamic, i.e. their objective function (or cost function) changes over time. The main approach used in the literature is to adapt static optimization algorithms to dynamic optimization, compensating for their intrinsic defects. Rather than adopting this approach, already widely investigated, the main goal of this thesis is to develop an algorithm completely designed for dynamic optimization. The first part of this thesis is then devoted to the design of an algorithm, that should not only stand out from competing algorithms for its originality, but also perform better. In this context, our goal is to develop a dynamic optimization metaheuristic. Two agent-based algorithms, MADO (MultiAgent algorithm for Dynamic Optimization) and MLSDO (Multiple Local Search algorithm for Dynamic Optimization), are proposed and validated using the two main benchmarks available in dynamic environments : MPB (Moving Peaks Benchmark) and GDBG (Generalized Dynamic Benchmark Generator). The benchmark results obtained show the efficiency of the proposed algorithms, particularly : MLSDO is ranked at the first place among seven algorithms tested using GDBG, and at the second place among sixteen algorithms tested using MPB. Then, these algorithms are applied to real-world problems in medical image sequence processing (segmentation and registration of brain cine-MRI sequences). To our knowledge, this work is innovative in that the dynamic optimization approach had never been investigated for these problems. The performance gains obtained show the relevance of using the proposed dynamic optimization algorithms for this kind of applications

The research is a study of the efficiency and robustness of genetic algorithm to instances of both discrete and continuous global optimization problems. We developed genetic algorithm based heuristics to find the global minimum to problem instances considered. In the discrete category, we considered two instances of real-world space allocation problems that arose from an academic environment in a developing country. These are the university timetabling problem and hostel space allocation problem. University timetabling represents a difficult optimization problem and finding a high quality solution is a challenging task. Many approaches, based on instances from developed countries, have been reported in the literature. However, most developing countries are yet to appreciate the deployment of heuristics and metaheuristics in handling the timetabling problem. We therefore worked on an instance from a university in Nigeria to show the feasibility and efficiency of heuristic method to the timetabling problem. We adopt a simplified bottom up approach in which timetable are build around departments. Thus a small portion of real data was used for experimental testing purposes. As with similar baseline studies in literature, we employ genetic algorithm to solve this instance and show that efficient solutions that meet stated constraints can be obtained with the metaheuristics. This thesis further focuses on an instance of university space allocation problem, namely the hostel space allocation problem. This is a new instance of the space allocation problems that has not been studied by metaheuristic researchers to the best of our knowledge. The problem aims at the allocation of categories of students into available hostel space. This must be done without violating any hard constraints but satisfying as many soft constraints as possible and ensuring optimum space utilization. We identified some issues in the problem that helped to adapt metaheuristic approach to solve it. The problem is multi-stage and highly constrained. We first highlight an initial investigation based on genetic algorithm adapted to find a good solution within the search space of the hostel space allocation problem. Some ideas are introduced to increase the overall performance of initial results based on instance of the problem from our case study. Computational results obtained are reported to demonstrate the effectiveness of the solution approaches employed. Sensitivity analysis was conducted on the genetic algorithm for the two SAPs considered to determine the best parameter values that consistently give good solutions. We noted that the genetic algorithms perform well specially, when repair strategies are incorporated. This thesis pioneers the application of metaheuristics to solve the hostel space allocation problem. It provides a baseline study of the problem based on genetic algorithms with associated test data sets. We report the best known results for the test instances. It is a known fact that many real-life problems are formulated as global optimization problems with continuous variables. On the continuous global optimization category therefore, we focus on improving the efficiency and reliability of real coded genetic algorithm for solving unconstrained global optimization, mainly through hybridization with exploratory features. Hybridization has widely been recognized as one of the most attractive approach to solving unconstrained global optimization. Literatures have shown that hybridization helps component heuristics to taking advantage of their individual strengths while avoiding their weaknesses. We therefore derived three modified forms of real coded genetic algorithm by hybridizing the standard real-coded genetic algorithm with pattern search and vector projection. These are combined to form three new algorithms namely, RCGA-PS, RCGA-P, and RCGA-PS-P. The hybridization strategy used and results obtained are reported and compared with the standard real-coded genetic algorithm. Experimental studies show that all the modified algorithms perform better than the original algorithm.

Uma hiper-heurística é uma heurística que pode ser utilizada para lidar com qualquer problema de otimização, desde que a ela sejam fornecidos alguns parâmetros, como estruturas e abstrações, relacionados ao problema considerado. As hiper-heurísticas têm sido aplicadas a alguns problemas práticos e apresentadas como métodos de grande potencial, no que diz respeito à capacidade de possibilitar o desenvolvimento, em tempo bastante reduzido, de algoritmos capazes de lidar satisfatoriamente, do ponto de vista prático, com problemas de otimização complexos e pouco conhecidos. No entanto, é difícil situar as hiper-heurísticas em algum nível de qualidade e avaliar a robustez dessas abordagens caso não as apliquemos a problemas para os quais existam diversas instâncias disponíveis publicamente e já experimentadas por algoritmos relevantes. Este trabalho procura dar alguns passos importantes rumo a essas avaliações, além de ampliar o conjunto das hiper-heurísticas, compreender o impacto de algumas alternativas naturais de desenvolvimento e estabelecer comparações entre os resultados obtidos por diferentes métodos, o que ainda nos permite confrontar as duas diferentes classes de hiper-heurísticas que identificamos. Com essas finalidades em mente, desenvolvemos 3 novas hiper-heurísticas e implementamos 2 das hiper-heurísticas mais importantes criadas por outros autores. Para estas últimas, experimentamos ainda algumas extensões e modificações. Os dois métodos hiper-heurísticos selecionados podem ser vistos como respectivos representantes de duas classes distintas, que aparentemente englobam todas as hiper-heurísticas já desenvolvidas e nos permitem denominar cada um desses métodos como \"hiper-heurística de busca direta por entornos\" ou como \"hiper-heurística evolutiva indireta\". Implementamos cada hiper-heurística como uma biblioteca (em linguagem C), de forma a evidenciar e estimular a independência entre o nível em que se encontra a hiper-heurística e aquele onde se apresentam as estruturas e abstrações diretamente relacionadas ao problema considerado. Naturalmente, essa separação é de ingente importância para possibilitar a reutilização imediata das hiper-heurísticas e garantir que nelas haja total ausência de informações relativas a um problema de otimização específico. / A hyperheuristic is a heuristic that can be used to handle any optimization problem, provided that the algorithm is fed with some parameters, as structures and abstractions, related to the problem at hand. Hyperheuristics have been applied to some practical problems and presented as methods with great potential to allow the quick development of algorithms that are able to successfully deal, from a practical standpoint, with complex ill-known optimization problems. However, it\'s difficult to position hyperheuristics at some quality level and evaluate their robustness without applying them to problems for which there are many instances available in the public domain and already attacked by worthy algorithms. This work aims to give some important steps towards that process of evaluation, additionally increasing the number of available hyperheuristics, studying the impact of some natural development alternatives and comparing the results obtained by different methods, what also enables us to confront the two classes of hyperheuristics that we have identified. With those purposes in mind, we have developed 3 original hyperheuristics and implemented 2 of the most important hyperheuristics created by other authors. For those latter two approaches, we have also experimented with some modifications and extensions. The two methods we have chosen for implementation may be seen as respectively representing two distinct classes, which seem to contain all hyperheuristics developed so far and that allow us to classify any of these methods as either being a \"direct neighbourhood search hyperheuristic\" or an \"indirect evolutive hyperheuristic\". We have implemented each hyperheuristic as a library (in the C language), so as to clearly show and estimulate the independence between the level where the hyperheuristic is and that to which the structures and abstractions directly related to the problem at hand belong. Obviously, this separation of concerns is extremely important to make the immediate reuse of hyperheuristics possible and enforce in them the complete absence of information from a specific optimization problem.

Submitted by Maria Cristina (library@lncc.br) on 2015-07-27T15:05:42Z No. of bitstreams: 1 thesis.pdf: 1867062 bytes, checksum: 8cffd5298d9eeaf5fe03a2244a4578f9 (MD5) / Approved for entry into archive by Maria Cristina (library@lncc.br) on 2015-07-27T18:14:30Z (GMT) No. of bitstreams: 1 thesis.pdf: 1867062 bytes, checksum: 8cffd5298d9eeaf5fe03a2244a4578f9 (MD5) / Made available in DSpace on 2015-07-27T18:26:47Z (GMT). No. of bitstreams: 1 thesis.pdf: 1867062 bytes, checksum: 8cffd5298d9eeaf5fe03a2244a4578f9 (MD5) Previous issue date: 2014-09-29 / Conselho Nacional de Desenvolvimento Científico e Tecnológico - CNPq / This work aims at the development and implementation of robust and efficient computational algorithms to treat multilevel optimization problems, particularly bilevel problems. Those problems are characterized by an optimization problem within the constraints of another optimization problem, and are considered more difficult to treat than classical optimization problems, since, in general, they are non-convex nor differentiable, even when the functions involved are all linear. To solve those problems, different techniques were developed which are based on Ant Colony Optimization and Differential Evolution metaheuristics. Beside those, a surrogate model (metamodel) was also developed, based on the Nearest Neighbors Method, in an attempt to reduce the computational cost of one of the proposed methods. A variety of bilevel problems were addressed to validate the proposed algorithms, including: (i) optimization problems in continuous space with and without constraints; (ii) an application in Operational Research involving the production and distribution planning problem; and (iii) bilevel problems containing multiple followers in the lower level. The analysis of the applicability and the performance of the proposed methodologies showed that they were able to successfully solve all problems, in which competitive results were obtained concerning the applications addressed. / Este trabalho visa o desenvolvimento e implementação computacional de algoritmos robustos e eficientes para tratar problemas de otimização multinível, particularmente os de dois níveis. Problemas desta natureza são caracterizados por possuírem um problema de otimização dentro das restrições de outro problema de otimização, e são considerados mais difíceis de serem tratados do que os problemas clássicos de otimização, pois, em geral, não são convexos e nem diferenciáveis, mesmo quando as funções envolvidas são todas lineares. Para resolver tais problemas, diferentes técnicas de otimização foram desenvolvidas, utilizando como base as metaheurísticas de Otimização por Colônia de Formigas e Evolução Diferencial. Além destas, propôs-se um modelo de substituição (metamodelo), baseado no Método dos Vizinhos mais Próximos, na tentativa de reduzir o custo computacional em um dos métodos proposto. Uma diversidade de problemas em dois níveis foi utilizada para validar os algoritmos desenvolvidos, incluindo: (i) problemas de otimização no espaço contínuo, restritos e irrestritos; (ii) uma aplicação em Pesquisa Operacional envolvendo o problema de planejamento de produção e distribuição; e (iii) problemas envolvendo múltiplos seguidores no nível inferior. A análise da aplicabilidade e do desempenho das metodologias propostas mostraram que estas foram capazes de resolver com sucesso todos os problemas, onde resultados competitivos foram obtidos na linha dos problemas abordados.

O presente trabalho visa a investigação e o desenvolvimento de estratégias de otimização contínua e discreta para problemas de Fluxo de Potência Ótimo com Restrições de Segurança (FPORS) Multiobjetivo, incorporando variáveis de controle associadas a taps de transformadores em fase, chaveamentos de bancos de capacitores e reatores shunt. Um modelo Problema de Otimização Multiobjetivo (POM) é formulado segundo a soma ponderada, cujos objetivos são a minimização de perdas ativas nas linhas de transmissão e de um termo adicional que proporciona uma maior margem de reativos ao sistema. Investiga-se a incorporação de controles associados a taps e shunts como grandezas fixas, ou variáveis contínuas e discretas, sendo neste último caso aplicadas funções auxiliares do tipo polinomial e senoidal, para fins de discretização. O problema completo é resolvido via meta-heurísticas Evolutionary Particle Swarm Optimization (EPSO) e Differential Evolutionary Particle Swarm Optimization (DEEPSO). Os algoritmos foram desenvolvidos utilizando o software MatLab R2013a, sendo a metodologia aplicada aos sistemas IEEE de 14, 30, 57, 118 e 300 barras e validada sob os prismas diversidade e qualidade das soluções geradas e complexidade computacional. Os resultados obtidos demonstram o potencial do modelo e estratégias de resolução propostas como ferramentas auxiliares ao processo de tomada de decisão em Análise de Segurança de redes elétricas, maximizando as possibilidades de ação visando a redução de emergências pós-contingência. / The goal of the present work is to investigate and develop continuous and discrete optimization strategies for SCOPF problems, also taking into account control variables related to in-phase transformers, capacitor banks and shunt reactors. Multiobjective optimization model is formulated under a weighted sum criteria whose objectives are the minimization of active power losses and an additional term that yields a greater reactive support to the system. Controls associated with taps and shunts are modeled either as fixed quantities, or continuous and discrete variables, in which case auxiliary functions of polynomial and sinusoidal types are applied for discretization purposes. The complete model is solved via EPSO and DEEPSO metaheuristics. Routines coded in Matlab were applied to the IEEE 14,30, 57, 118 and 300-bus test systems, where the method was validated in terms of diversity and quality of solutions and computational complexity. The results demonstrate the robustness of the model and solution approaches and uphold it as an effective support tool for the decision-making process in Power Systems Security Analysis, maximizing preventive actions in order to avoid insecure operating conditions.

Submitted by JOSIANE SANTOS DE OLIVEIRA (josianeso) on 2017-11-29T16:00:55Z No. of bitstreams: 1 André da Silva Davi_.pdf: 2370087 bytes, checksum: dcaf9c82247a500748da7c104102054b (MD5) / Made available in DSpace on 2017-11-29T16:00:55Z (GMT). No. of bitstreams: 1 André da Silva Davi_.pdf: 2370087 bytes, checksum: dcaf9c82247a500748da7c104102054b (MD5) Previous issue date: 2017-09-12 / Nenhuma / Neste trabalho foi desenvolvido um modelo computacional para a otimização de layout de um Armazém. Além da abordagem do Problema de Layout de Armazém, também é abordado o Problema de Família de Partes. Para o desenvolvimento do modelo foi aplicada a metaheurística Algoritmo Genético. O objetivo do estudo é projetar a configuração de um armazém que otimize a alocação de mercadorias nas prateleiras tal que proporcione a minimização da movimentação das mesmas durante a seleção de pedidos, pois a operação e a gerência são partes essenciais das operações e serviços realizados. Para isto, as variáveis de decisão são: a distância absoluta da localização da mercadoria e o número de pedidos por dia. O resultado deste trabalho é a geração de um layout capaz de comportar as mercadorias de acordo com as necessidades de alocação, realizando uma otimização de aproximadamente 15%. / In this work a computational model was developed for a warehouse layout optimization. In addition to the Warehouse Layout Problem approach, the Part Family Problem is also addressed. For the development of the model was applied the metaheuristic Genetic Algorithm. The objective of the study is to design the configuration of a warehouse that optimizes an allocation of goods on the shelves that provides a minimization of the warehouse's movement during order selection, operation and management with essential uses of the operations and services performed. The decision variables are: the absolute distance of the location of the merchandise and the number of requests per day. The result is a set of new layouts, according to the conditions of service and the realization of an optimization of approximately 15%.