Modularity Density Maximization is a graph clustering problem which avoids the resolution limit degeneracy of the Modularity Maximization problem. This thesis aims at solving larger instances than current Modularity Density heuristics do, and show how close the obtained solutions are to the expected clustering. Three main contributions arise from this objective. The first one is about the theoretical contributions about properties of Modularity Density based prioritizers. The second one is the development of eight Modularity Density Maximization heuristics. Our heuristics are compared with optimal results from the literature, and with GAOD, iMeme-Net, HAIN, BMD- heuristics. Our results are also compared with CNM and Louvain which are heuristics for Modularity Maximization that solve instances with thousands of nodes. The tests were carried out by using graphs from the “Stanford Large Network Dataset Collection”. The experiments have shown that our eight heuristics found solutions for graphs with hundreds of thousands of nodes. Our results have also shown that five of our heuristics surpassed the current state-of-the-art Modularity Density Maximization heuristic solvers for large graphs. A third contribution is the proposal of six column generation methods. These methods use exact and heuristic auxiliary solvers and an initial variable generator. Comparisons among our proposed column generations and state-of-the-art algorithms were also carried out. The results showed that: (i) two of our methods surpassed the state-of-the-art algorithms in terms of time, and (ii) our methods proved the optimal value for larger instances than current approaches can tackle. Our results suggest clear improvements to the state-of-the-art results for the Modularity Density Maximization problem.

Amostras de DNA são encontradas em fragmentos, obtidos em vestígios de uma cena de crime, ou coletados de amostras de cabelo ou sangue, para testes genéticos ou de paternidade. Para identificar se esse fragmento pertence ou não a uma sequência de DNA, é necessário compará-los com uma sequência determinada, que pode estar armazenada em um banco de dados para, por exemplo, apontar um suspeito. Para tal, é preciso uma ferramenta eficiente para realizar o alinhamento da sequência de DNA encontrada com a armazenada no banco de dados. O alinhamento de sequências de DNA, em inglês DNA matching, é o campo da bioinformática que tenta entender a relação entre as sequências genéticas e suas relações funcionais e parentais. Essa tarefa é frequentemente realizada através de softwares que varrem clusters de base de dados, demandando alto poder computacional, o que encarece o custo de um projeto de alinhamento de sequências de DNA. Esta dissertação apresenta uma arquitetura de hardware paralela, para o algoritmo BLAST, que permite o alinhamento de um par de sequências de DNA. O algoritmo BLAST é um método heurístico e atualmente é o mais rápido. A estratégia do BLAST é dividir as sequências originais em subsequências menores de tamanho w. Após realizar as comparações nessas pequenas subsequências, as etapas do BLAST analisam apenas as subsequências que forem idênticas. Com isso, o algoritmo diminui o número de testes e combinações necessárias para realizar o alinhamento. Para cada sequência idêntica há três etapas, a serem realizadas pelo algoritmo: semeadura, extensão e avaliação. A solução proposta se inspira nas características do algoritmo para implementar um hardware totalmente paralelo e com pipeline entre as etapas básicas do BLAST. A arquitetura de hardware proposta foi implementada em FPGA e os resultados obtidos mostram a comparação entre área ocupada, número de ciclos e máxima frequência de operação permitida, em função dos parâmetros de alinhamento. O resultado é uma arquitetura de hardware em lógica reconfigurável, escalável, eficiente e de baixo custo, capaz de alinhar pares de sequências utilizando o algoritmo BLAST. / DNA samples are found in fragments, obtained in traces of a crime scene, collected from hair or blood samples, for genetic or paternity tests. To identify whether this fragment belongs or not to a given DNA sequence it is necessary to compare it with a determined sequence which usually come from a database, for instance, to point a suspect. To this end, we need an efficient tool to perform the alignment of the DNA sequence found with the ones stored in the database. The alignment of DNA sequences, which is a field of bioinformatics that helps to understand the relationship between genetic sequences and their functional relationships and parenting. This task is often performed by software that scan clusters of databases, which requires high computing effort, thus increasing the cost of DNA sequences alignment projects. This work presents a parallel hardware architecture, for BLAST algorithm, to DNA pairwise alignment. This is the original version of the BLAST algorithm, that resulted in several other versions. The BLAST algorithm is a heuristic method and is the fastest algorithm for sequence alignment. The strategy of BLAST is to divide the sequences into smaller subsequences of size w. After making comparisons in these subsequences, algorithm steps analyzes only the subsequences that are identical. Thus, reducing the number of tests and combinations needed to perform the alignment. For each identical sequence found, three steps are followed by the algorithm: seeding, extension and evaluation. The proposed hardware architecture is based on the characteristics of the algorithm to implement a fully parallel hardware, where the basic steps of BLAST are pipelined. The proposed architecture was implemented in FPGA and the results show a comparison between the area occupied, number of cycles and maximum frequency of operation permitted, as a function of alignment parameters. The result is a hardware architecture in reconfigurable logic, scalable, efficient and with low cost, capable of aligning the pairs of sequences using BLAST algorithm.

Orientadora: Profa. Dra. Juliana Cristina Braga / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2016. / Objetos de Aprendizagem (OAs) são recursos educacionais digitais ou não que possibilitam apoiar o processo educativo, tendo como sua característica principal, a reusabilidade. Eles podem ser encontrados em Repositórios de Objetos de Aprendizagem (ROAs), definidos como bibliotecas digitais aonde são armazenados, catalogados e disponibilizados. Problemas de usabilidade nestes repositórios, podem ser empecilhos que inviabilizam a possibilidade de reúso dos OAs por parte dos usuários finais docentes. Um desses problemas, está relacionado ao design de interface de usuário de alguns ROAs, ser pouco intuitivo. Este trabalho apresenta 3 métodos que viabilizam a detecção de problemas de usabilidade e como propor baseando-se em alguns resultados, um protótipo Lo-fi de interface de usuário intuitiva e amigável. A Revisão Sistemática (Método 1) foi realizada com o objetivo de identificar os problemas de usabilidade em diversos ROAs. O Método 2, Avaliação Heurística, foi realizada com especialistas de IHC em busca de observar os problemas e dificuldades na interação com 3 ROAs: Ariadne, BIOE e MERLOT. O Método 3, consiste em aplicar métodos da área de Design para propor o visual estético de um protótipo Lo-fi, sendo esta, a etapa final. Foram identificados durante e após a Revisão Sistemática, que muitos problemas de usabilidade são relacionados ao design da interface do usuário e também com os sistemas implementados nesses ROAs. Os resultados obtidos na Revisão Sistemática Avaliação Heurística foram importantes para obter dados que agregassem informações relevantes em relação à usabilidade dos ROAs escolhidos para análise, além de ser possível propor checklists de usabilidade para ROAs. Foram aplicados métodos da área do Design para a concepção do protótipo Lo-fi, entitulado de OAS PARA VOCÊ. Sugere-se realizar posteriormente, a validação das checklists de usabilidade para ROAs e a implementação do OAS PARA VOCÊ. / Learning Objects (LOs), are digital or non digital educational resources which can support the educational process, presenting as a main characteristic, its reusability. The can be found in Learning Object Repositories (LORs), which can be defined as digital libraries where stores, catalogs and makes them available. Usability issues in these repositories may be possible obstacles which can make the possibility of reuse, very difficult for the end users, the teachers. One of these issues, is related to the fact that some user interface design presented in some LORs, aren¿t intuitive. This work presents three methods which enable the usability issues detection and how to propose result based, an intuitive and user-friendy Lo-fi prototype. The Systematic Review (Method 1) was performed aiming to identify usability issues in several LORs. Method 2, Heuristic Evaluation, was held with HCI experts, trying to observe issues and difficulties while interacting with 3 LORs: Ariadne, BIOE and MERLOT. Method 3, consists in applying methods from the Design¿s field aiming to propose visual aesthetics of Lo-fi prototype, this is the work¿s final step. Were identified during and after the Systematic Review, that many usability issues were related to user¿s interfaces and also within the systems implementation in these LORs. The results obtained in the Systematic Review and Heuristic Evaluation were important to get data which could add up relevant information related to the usability in those chosen LORs for analysis, in addition, was possible to propose usability checklists for LORs. For the Lo-fi prototype¿s (entitled OAS PARA VOCÊ) conception, were applied methods from the Design¿s field. It is suggested to put into practice in the future, the validation or the usability heuristics for LORs and the implementation of the OAS PARA VOCÊ.

Submitted by MARCO ALONSO MENESES ORIONDO (mameneseso@gmail.com) on 2016-04-29T17:33:57Z No. of bitstreams: 1 Meneses - Dissertação.pdf: 4087822 bytes, checksum: dc161c85a2ac9500af836619b1f9d6f3 (MD5) / Approved for entry into archive by Felipe Augusto Arakaki (arakaki@reitoria.unesp.br) on 2016-05-02T18:55:33Z (GMT) No. of bitstreams: 1 oriondo_mam_me_ilha.pdf: 4087822 bytes, checksum: dc161c85a2ac9500af836619b1f9d6f3 (MD5) / Made available in DSpace on 2016-05-02T18:55:33Z (GMT). No. of bitstreams: 1 oriondo_mam_me_ilha.pdf: 4087822 bytes, checksum: dc161c85a2ac9500af836619b1f9d6f3 (MD5) Previous issue date: 2016-03-10 / Neste trabalho apresenta-se uma versão especializada da meta-heurística Algoritmo dos Fogos de Artifício de Busca Dinâmica com Mutação de Covariância (AFABDMC) para resolver o problema de Fluxo de Potência Ótimo (FPO) em sistemas de transmissão. No algoritmo proposto consideram-se como variáveis contínuas de controle a magnitude da tensão e a geração de potência ativa nas barras de geração e como variáveis de controle discretas o estado de operação dos shunts e a posição do comutador de taps em transformadores. Assim, o modelo para o problema é de Programação Não-Linear Inteira Mista (PNLIM). A estratégia de resolução adotada consiste em controlar, em cada iteração, os valores das variáveis de controle discretas utilizando-se a meta-heurística AFABDMC e a partir desses valores escolhidos pela meta-heurística, resolver um problema de Programação Não-Linear (PNL) que fornece os valores das variáveis de controle contínuas junto com o estado de operação do sistema. A meta-heurística AFABDMC foi escrita em linguagem MATLAB e o modelo do problema em AMPL. Os subproblemas de PNL foram resolvidos utilizando-se o solver KNITRO, sendo que a interface entre o MATLAB e o AMPL foi feita utilizando-se o AMPL API. Foram realizados testes com os sistemas IEEE de 14, 30, 57 e 118 barras e os resultados indicam que a metodologia proposta é capaz de encontrar soluções de muito boa qualidade para o problema. / In this work, a new specialized metaheuristic based on the Dynamic Search Fireworks Algorithm with Covariance Mutation (DSFWACM) is applied on the Optimal Power Flow (OPF) problem in transmission systems. In the proposed method, generator bus voltage magnitudes and active power generation are considered as continuous variables and the operating state of the shunts and transformer taps settings are considered as discrete variables. Thus, the model is a Mixed-Integer Nonlinear Programming (MINLP) problem. The adopted resolution strategy is to control, in each iteration, the value of the discrete control variables using the DSFWACM metaheuristic and from the metaheuristic’s chosen values, solve the Nonlinear Programming (NLP) problem that provides the values of the continuous control variables along with the system’s operation state. The DSFWACM metaheuristic was written in MATLAB and the problem model in AMPL. The NLP sub-problems were solved using the KNITRO solver, and the interface between MATLAB and AMPL was implemented using the AMPL API. Tests were conducted with the IEEE 14, 30, 57 and 118-bus systems and the results show that the proposed method is able to find high quality solutions to the problem. / CNPq: 132374/2011-0

Existem vários problemas clássicos na área de pesquisa operacional que trabalham com o tema vinculado à designação de veículos em um sistema logístico, entre eles o Problema de Escalonamento de Veículos com Múltiplas Garagens (MDVSP). Esses modelos são largamente utilizados e representam uma das etapas essenciais para o planejamento de trânsito em massa (HAGHANI e BANIHASHEMI, 2002). Tratando-se de sistemas logísticos reais, dificilmente encontra-se um ambiente onde os veículos devem partir e chegar a uma única garagem, por isso torna-se necessário o planejamento das seqüências de viagens de modo a reduzir os custos de deslocamentos com o aproveitamento das múltiplas garagens distribuídas geograficamente. Infelizmente, considerando a complexidade exponencial do MDVSP, muitas vezes sua aplicação torna-se inviável na solução de problemas reais. Por essa razão, poucos trabalhos abordam o MDVSP de modo a conseguir solucionar o problema para uma grande quantidade de viagens e garagens. A maioria das pesquisas trabalha com instâncias inferiores a 500 viagens e quatro garagens, mostrando-se pouco aplicáveis. Esse estudo refere-se a um trabalho de pesquisa operacional que aborda soluções de problemas de escalonamento de veículos com múltiplas garagens (MDVSP) considerando sua aplicabilidade em sistemas reais. Tendo em vista a complexidade exponencial do MDVSP, nesse estudo optou-se por tratar o problema através de uma abordagem baseada na redução do espaço de estados e na utilização de heurísticas. Durante essa pesquisa três procedimentos de redução do espaço de estados foram adotados. Os resultados apontam que é possível reduzir em até 98% o número de variáveis nesses problemas sem comprometer uma solução satisfatória ou ótima. Além dos procedimentos de redução do espaço de estados, foi desenvolvido um procedimento de buscar a solução do MDVSP. Através desse último procedimento foi possível resolver o MDVSP com até 3000 viagens e oito garagens. Sendo assim, nesse estudo desenvolveram-se modelos que servem para o planejamento de um sistema logístico através da aplicação de cenários, com vistas a permitir a geração e análise de alternativas de escalonamento. Objetivou-se com isso, fornecer ao sistema logístico um modelo amplo que permita a escolha da ação mais conveniente e eficiente a ser tomada em modelos compostos por diversas garagens. / There are many classics problems in operations research concerning optimal assignment vehicles in logistical system. The multiple depot vehicle scheduling problem (MDVSP) is one of them. This problem is largely used to represent and solve mass transit planning (HAGHANI e BANIHASHEMI, 2002). Considering a real logistical system, it is very difficult to find out a situation where the vehicles must leave and come to only one depot. In general, the shipping company has several depots located at different sites in a network. In this way, it is strongly necessary to reduce cost through the planning of sequence trips taking into account multiple depots geographically distributed. Unfortunately, the exponential complexity of the MDVSP reduces, in the most cases, the applicability of this problem in the real world. For this reason, few researchers address the MDVSP to solve real world problems considering a large number of trips and depots. The majority of the research dealing with the MDVSP works with instances lower than 500 trips and four depots, what can be considered a major constraint for its practical use. The main objective of this work is to solve the MDVSP for very large instances. A state space reduction approach combined with heuristic procedures are developed to obtain a realistic way of solving this complex problem. In this research, three state space reduction procedures were developed. The results appointed that is possible to reduce until 98% of variables in the MDVSP without jeopardizing an optimal solution. Furthermore, heuristic procedures were developed to obtain solutions without relaxing any realworld constraint of the problem. The solution procedure developed was compared with wellknown available instances. The method is able to solve the MDVSP with 3000 trips and eight depots in less than 11 minutes. Although the solution process does not obtain the best solution in all tested instances, it is by far the quickest.

O ensino de heurísticas e metaheurísticas é disperso na estrutura educacional superior brasileira em disciplinas da graduação e pós-graduação. De acordo com o plano de ensino do professor e sua concepção pedagógica, estas disciplinas podem ser centradas em aspectos práticos, com exemplos reais, ou focalizar as estruturas matemáticas que dão suporte à teoria e concepção dos modelos que são debatidos na literatura. No decorrer desta tese, é apresentada uma metodologia dialógica-problematizadora que, através da concepção, desenvolvimento e teste de duas ferramentas tecnológicas (o ambiente virtual de aprendizagem AMEM – Ambiente Multimídia para Educação Mediada por Computador e o objeto de aprendizagem LOBO – Learning Object Based on Optimization), busca uma forma inovadora de discutir os algoritmos heurísticos e metaheurísticos em torno de um problema comum, através de práticas baseadas no diálogo e instigando os alunos a buscar as respostas para os problemas que são apresentados aos mesmos. Concebida como uma proposta para dinamizar o ensino superior de heurísticas e metaheurísticas, esta tese apresenta a metodologia pedagógica, o ferramental tecnológico desenvolvido e, em sua última parte, uma aplicação real destas em uma disciplina de graduação. Considerando as questões de pesquisa previamente definidas na Matriz Dialógica-Problematizadora, é possível concluir que há muito trabalho ainda a percorrer para romper o ciclo positivista que pode agir como um inibidor de novas práticas, servindo como um ponto de apoio aos alunos que, acostumados ao ato de ouvir em uma sala de aula, não se sentem à vontade em agir. A utilização de ferramentas que permitam criar um espaço dialógico e questionador, como o AMEM e o LOBO, pode contribuir para quebrar este estigma. / The education of heuristics and metaheuristics is dispersed in the Brazilian higher educational structure in disciplines of the graduation and posgraduation. The discipline can be centered in practical aspects, with real examples, or to focus the mathematical structures which support the theory and conception of the literature models. The professor, considering his education plan and his pedagogical conceptions, can choose one of them. In this thesis, the dialogical-problem methodology is presented, through the conception, development and test of two technological tools (the virtual environment of learning AMEM - Multimedia Educational Environment Mediated for Computer and the learning object LOBO - Learning Object Based on Optimization). The tools and the methodological approach produce an innovative way to the heuristics and metaheuristics educational, based in a common problem, through a practical focused in the dialogue and instigating the students to seek their owner answers. Conceived as a new proposal to the heuristics and metaheuristics higher education, this thesis presents the pedagogical methodology, the technological developed tool and a real application of these in one graduation discipline. Considering the questions of research previously defined in the Dialogical-Problem Matrix, the conclusions of the thesis appoints to a great effort needed to break the pedagogical traditional methodology, especially in the students’ behavior. The use of tool to create a dialogical space, as AMEM and the LOBO, can contribute to break this stigma.

Orientador: Rubén Augusto Romero Lázaro / Resumo: The purpose of this research is to develop a tool for optimization in power system distribution that uses meta-heuristic based on a multi-start methodology to reconfigure and allocate fixed and switched capacitor banks to obtain the radial topology that presents the lowest operating cost. To find initial radial topologies for system reconfiguration, the Prim algorithm was applied and to the current solution an improvement process called “neighborhood search” was performed. The improved system is subjected to a capacitor allocation algorithm showing that it is possible to get a radial topology that presents more economic cost of operation. As a proposal of the multi-start methodology, the procedure is repeated until a desired stop criterion, then several solutions are generated and the best one can be the solution of the problem. All programs were written in C ++ and applied to systems of 69 nodes, 84 nodes and 135 nodes. / Mestre

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. / 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.

Um tema pouco estudado na literatura, mas frequentemente encontrado por empresas prestadoras de serviço, é o Problema de Escalonamento de Técnicos de Campos (Field Technician Scheduling Problem). O problema consiste em associar um número de tarefas - em diversos locais, com diferentes prioridades e com janelas de tempo - a uma quantidade de técnicos - com diferentes horários de expediente e com habilidades distintas - que saem no início do horário de trabalho da sede da empresa, para onde devem retornar antes do fim do expediente. Cada tarefa é atendida por um único técnico. Esse problema é estudado neste trabalho. A primeira parte do trabalho apresenta um modelo de programação linear inteira mista (PLIM) e, dada a complexidade do problema, heurísticas construtivas e meta-heurísticas foram desenvolvidas. Na função objetivo, procura-se principalmente maximizar o número ponderado de tarefas executadas em um dia de trabalho, de acordo com as suas prioridades. Em linhas gerais, as heurísticas construtivas ordenam as tarefas de acordo com um critério pré-estabelecido e, em seguida, designam cada uma a um dos técnicos capazes de realiza-la sem violar as restrições do problema. Tendo em conta o bom desempenho obtido em outros problemas semelhantes, foi adotado um Algoritmo Genético denominado Biased Random-Key Genetic Algorithms (BRKGA), que utiliza chaves aleatórias para codificar e decodificar as soluções. Codificadores e decodificadores adaptados ao problema foram desenvolvidos e testes computacionais são apresentados. As soluções obtidas em problemas de pequenas dimensões são comparadas com as soluções ótimas conhecidas e, para aprimorar a avaliação do desempenho nas instâncias médias e grandes, quatro procedimentos para obter limitantes superiores foram propostos. Testes computacionais foram realizados em 1040 instâncias. O BRKGA encontrou 99% das 238 soluções ótimas conhecidas e, nas 720 instâncias de dimensões médias e grandes, ficou em média a 3,8% dos limitantes superiores. As heurísticas construtivas superaram uma heurística construtiva da literatura em 90% das instâncias. A segunda parte do trabalho apresenta uma nova abordagem para o Problema de Escalonamento de Técnicos de Campo: um modelo biobjetivo, onde uma segunda função objetivo buscará que as tarefas prioritárias sejam realizadas o mais cedo possível. Uma versão multiobjectivo do BRKGA foi desenvolvida, considerando diversas estratégias para classificar a população do algoritmo e escolher as melhores soluções (estratégias de elitismo). Codificadores e decodificadores foram criados para o problema multiobjectivo. Os resultados computacionais obtidos são comparados com os resultados de um Algoritmo Genético conhecido na literatura, o Nondominated Sorting Genetic Algorithm II (NSGA II). Para instâncias de pequenas dimensões, os resultados da meta-heurística proposta também são comparados com a fronteira ótima de Pareto de 234 instâncias, obtidas por enumeração completa. Em média, o BRKGA multiobjectivo encontrou 94% das soluções da fronteira ótima de Pareto e, nas instâncias médias e grandes, superou o desempenho do NSGA-II nas medidas de avaliação adotadas (porcentagem de soluções eficientes, hipervolume, indicador epsílon e cobertura). / An important topic in service companies, but little studied until now, is the field technician scheduling problem. In this problem, technicians have to execute a set of jobs or service tasks. Technicians have different skills and working hours. Tasks are in different locations within a city, with different time windows, priorities, and processing times. Each task is executed by only one technician. This problem is addressed in this thesis. The first part of the research presents the mixed integer linear programming model (MILP) and, due to the complexity of this problem, constructive heuristics and metaheuristics were proposed. The objective function is to maximize the sum of the weighted performed tasks in a day, based on the priority of tasks. In general terms, in the proposed constructive heuristics, jobs are ordered according to a criterion and, after that, tasks are assigned to technicians without violating constraints. A Genetic Algorithm (the Biases Randon Key Genetic Algorithm - -RKGA) is applied to the problem, based on its success in similar problems; the BRKGA uses random keys and a decoder transforms each chromosome of the Genetic Algorithm into a feasible solution of the problem. Decoders and encoders adapted to the problem were developed and computational tests are presented. A comparison between the solutions of the heuristic methods and optimal solutions values was also conducted for small instances and, to analyze medium and large instances, four upper bound models were proposed. Computational experiments with 1040 instances were carried out. The BRKGA reached 99% of the 238 optimal solutions and, for 720 medium and large instances, the average upper bound gap was 3,8%. Constructive heuristics overcame a heuristic of the literature in 90% of the instances. The second part of this research presents a new approach of the Field Technician Scheduling Problem: a multiobjective model, with a second objective function to execute the priority tasks as soon as possible. A multiobjective BRKGA was developed, with different strategies to classify the Genetic Algorithm population and to select the elite solutions (elite strategies). Decoders and encoders were developed for the multiobjective problem too. The results were compared with a known Genetic Algorithm, the Nondominated Sorting Genetic Algorithm II (NSGA II). For 234 small instances, the results were compared with the Pareto optimal solutions, obtained by complete enumeration. On average, the BRKGA found 94% of the Pareto optimal solutions and, for 720 medium and large instances, outperformed the NSGA-II by means of the measures adopted (percentage of efficient solutions, hypervolume, epsilon and coverage).

Made available in DSpace on 2016-06-02T19:05:23Z (GMT). No. of bitstreams: 1 DissEGRM.pdf: 5921557 bytes, checksum: 89005165cd9d839d8283e0713abe1fb8 (MD5) Previous issue date: 2005-05-30 / Financiadora de Estudos e Projetos / The Petri Net based Search has been shown as a promising way to solve Flexible manufacturing Systems (FMS) Scheduling Problem. However, the response time is critical since it s a system with high computational complexity. Focusing the reduction of response time, this work proposes a heuristic for Petri Net based Search to solve FMS Scheduling problem of makespan minimization. Experiments showed improvements on response time reduction comparing with prior works / Abordagens de Busca baseadas em Rede de Petri (PN) têm sido mostradas como uma forma promissora de resolver o problema da Programação da Produção de Sistemas Flexíveis de Manufatura (FMS). Entretanto, o tempo de resposta é crítico, uma vez que se trata de um sistema de alta complexidade computacional. Focando a redução do tempo de resposta do sistema, este trabalho propõe uma heurística para busca baseada em Rede de Petri para resolver o problema de programação de FMS na minimização do makespan. Experimentos mostraram um avanço na melhoria do tempo de resposta em relação a trabalhos anteriores