Todo início de período letivo, gestores de instituições de ensino se deparam com um típico problema: montar as grades horárias das turmas, segundo as demandas de aulas de suas disciplinas e considerando as restrições de disponibilidade horária de todos os envolvidos. Conhecido na literatura como School Timetabling Problem (STP), este típico problema de otimização combinatória é reconhecidamente complexo por conta do seu elevado número de variáveis e restrições. Devido à dependência das regras do sistema educacional de cada país, o STP pode ter inúmeras variantes, cada uma com o seu próprio conjunto de particularidades. Este trabalho se propõe a oferecer um modelo para o STP considerando o sistema educacional brasileiro, visando alocar não apenas professores, mas também determinando que disciplina cada professor deve ministrar e alocando os locais de aula. O modelo proposto, baseado na meta-heurística simulated annealing, foi concebido para que cada instituição de ensino usuária tenha liberdade para definir a penalidade de cada tipo possível de inconformidade ou restrição, de modo que o algoritmo empregado possa encontrar uma solução com o menor custo possível. / Every beginning of term, educational institution managers face a typical problem: planning the classes' timetable, according to their lesson demands for each subject, considering, furthermore, the schedule constrains of all actors. Known as school timetabling problem (STP), this typical combinatorial optimization problem is remarkably complex due to the high number of variables and constraints. Owing to the rules of each country's educational system, STP can have uncountable variants, each one with their own set of features. This dissertation searches to offer a model to STP considering the Brazilian Educational System, focusing on allocating not only the teachers but also determining which subject each teacher should teach and allocating classrooms, laboratories and the like. The propesed model, based on the metaheuristic simulated annealing, was conceived so that each educational institution using this model has the freedom to define which penalty will be applied to each possible kind of noncomformity and constraint, in order for the applied algorithm to find a solution at the lowest cost as possible.

Orientador: Vinícius Amaral Armentano / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-16T07:40:14Z (GMT). No. of bitstreams: 1 Sacchi_LuisHenrique_D.pdf: 1448719 bytes, checksum: f89915d271683e250283d8ec86b25839 (MD5) Previous issue date: 2010 / Resumo: Este trabalho apresenta um estudo computacional da busca tabu paramétrica para resolver problemas de programação inteira mista (PIM) com variáveis binárias. Trata-se de uma heurística genérica para problemas PIM gerais que resolve uma série de problemas de programação linear ao incorporar inequações de ramificação de variáveis inteiras como termos ponderados na função objetivo. O procedimento central do método é baseado em memória de curto prazo da busca tabu, enquanto fases de intensificação e diversificação são induzidas pela memória de longo prazo baseada em freqüência e idéias derivadas de scatter search. Novas estratégias são propostas para encontrar soluções de alta qualidade e extensivos testes computacionais são realizados em instâncias da literatura / Abstract: We present a computational study of parametric tabu search for solving 0-1 mixed integer programming (MIP) problems, a generic heuristic for general MIP problems that solves a series of linear programming problems by incorporating branching inequalities as weighted terms in the objective function. The core procedure is founded on short term memory, whereas both intensification and diversification phases are induced by long term memory based on frequency and ideas derived from scatter search. New strategies are proposed for uncovering feasible and high-quality solutions and extensive computational tests are performed on instances from the literature / Doutorado / Automação / Doutor em Engenharia Elétrica

Orientador: Arnaldo Vieira Moura / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-06T15:19:37Z (GMT). No. of bitstreams: 1 Pereira_RomuloAlbuquerque_M.pdf: 1452483 bytes, checksum: 19f11b532a512f1e86efa79195a4e8ce (MD5) Previous issue date: 2005 / Resumo: Este trabalho de mestrado procurou estudar e resolver um problema real de escalonamento das atividades de desenvolvimento de poços de petróleo em alto mar. Uma versão mais simples deste mesmo problema foi provada ser NP- difícil. Nosso estudo se concentrou no problema real enfrentado pela Petrobrás, com todas suas características e nuances. Antes que locais promissores de bacias petrolíferas sejam efetivamente desenvolvidos em poços de petróleo produtivos, é necessário realizar diversas atividades de perfuração, completarão e interligação nesses locais. O escalonamento dessas atividades deve satisfazer várias restrições conflitantes e buscar a maximização da produção de petróleo em um dado horizonte de tempo. O problema foi atacado em duas etapas: uma sem considerar o deslocamento de recursos e outra considerando-os. Para tal, adotamos a estratégia Greedy Randomized Adaptive Search Procedure (GRASP) e incorporamos várias técnicas específicas para obter melhor desempenho e qualidade da solução final. Os resultados são comparados com outros produzidos por uma ferramenta computacional baseada em Programação por Restrições (PR). Esta última, já em uso e bem aceita na empresa, foi desenvolvida pela Petrobrás. Resultados comparativos realizados em instâncias reais indicam que a implementação GRASP supera a ferramenta de PR produzindo soluções com expressivos aumentos de produção / Abstract: This dissertation aimed at studying and solving a real world scheduling problem. We deal with the scheduling of offshore oil well development activities. A simpler version of this same problem was proved to be in NP-hard. Our approach treats this problem as faced by Petrobras, with all its characteristics and details. Before promising locations at petroliferous basins become productive oil wells, it is often necessary to complete activities of drilling, completion and interconnection at these locations. The scheduling of such activities must satisfy several conflicting constraints and aim at the maximization of oil production. The problem was solved in two parts: one without considering resource displacements and other taking into account such displacements. For such, we used a Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic and used several techniques and variants in order to obtain more efficiency and produce better solutions. The results are compared with schedules produced by a well-accepted constraint programming implementation. Computational experience on real instances indicates that the GRASP implementation is competitive, outperforming the constraint programming implementation / Mestrado / Otimização Combinatoria / Mestre em Ciência da Computação

Orientador: Vinicius Amaral Armentano / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-08T10:15:19Z (GMT). No. of bitstreams: 1 Araujo_OlintoCesarBasside_D.pdf: 1592360 bytes, checksum: 71dd5f2565cd93013aa027127157c442 (MD5) Previous issue date: 2006 / Resumo: A adoção de contêineres em grande escala tornou possível o desenvolvimento do transporte multimodal. Atualmente, carregamento de caixas em contêineres é uma importante atividade em empresas que têm no transporte de carga um fator logístico de alto custo. Este trabalho apresenta o desenvolvimento e aplicação de metaheurísticas com memória adaptativa para a resolução de problemas de corte e empacotamento tridimensional, bem como a integração destes com o problema de roteamento de veículos. Mais especificamente, são tratados os problemas de carregamento de contêiner, bin packing tridimensional e roteamento de veículos capacitados com restrições de empacotamento tridimensional. Uma nova abordagem, baseada em cubóides de tamanho variável, é utilizada para calcular os padrões de carregamento tridimensional em todos os métodos propostos. Restrições de orientação, estabilidade, centro de gravidade, projeção da base de apoio e múltiplos destinos são consideradas. Extensivos testes computacionais são realizados para demonstrar o desempenho das abordagenspropostas / Abstract: The wide-scale adoption of the containers made the development of the multimodal transport possible. Nowadays, shipment of boxes in containers is an important activity for companies that have in the load transport a logistic factor of high cost. This work presents the development and the application of metaheuristics with adaptive memory in order to solve three-dimensional cutting and packing problems, as well as their integration with the vehicle routing problem. In particular, problems of container loading, three-dimensional bin packing and vehicle routing with three-dimensional packing constraints are considered. Furthermore, a new approach based on maximal cuboids that fit in given empty spaces is used to calculate the packing patterns in the proposed methods. Constrains on orientation, stability, center of gravity, overhang and multiple destination are considered. Extensive computational experiments are carried out to demonstrate the performance of the proposed approaches / Doutorado / Automação / Doutor em Engenharia Elétrica

Orientador: Paulo Morelato França / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-09T05:57:31Z (GMT). No. of bitstreams: 1 Usberti_FabioLuiz_M.pdf: 37565259 bytes, checksum: cddb8b852bd82318a8c784f1f223a076 (MD5) Previous issue date: 2007 / Resumo: Esse trabalho se dedicou ao estudo dos algoritmos para roteamento de leituristas, incluindo propostas de alteração que resultem na melhoria da qualidade dos resultados. A motivação é proveniente da alta demanda por soluções computacionais para esse problema, ainda pouco estudado devido às peculiaridades que lhe são inerentes. Encontram-se na literatura duas heurísticas, de estratégias distintas e antagônicas para esse problema. Uma das heurísticas procura construir a rota ignorando a restrição de capacidade, para posterior particionamento dessa rota em subrotas, cada qual destinada a um leiturista (¿route first, cluster second¿). A outra heurística, em uma abordagem inversa, primeiramente subdivide a região de trabalho dos leituristas, para posterior roteamento dessas partições (¿cluster first, route second¿). Essas duas heurísticas foram testadas exaustivamente, tornando possível localizar aspectos sujeitos à melhoria, dando origem a duas novas heurísticas. Foi gerada uma base de testes contendo 144 instâncias que simulam as condições reais de trabalho dos leituristas, classificadas de acordo com o tamanho e dificuldade. A partir das soluções provenientes dos quatro algoritmos foi possível analisá-los comparativamente, avaliando o melhor em um âmbito geral (envolvendo todos os algoritmos) e específico (algoritmos de mesmo tipo, ¿route first cluster second¿ ou ¿cluster first route second¿), segundo critérios de qualidade pré-definidos: número de rotas, tempo de percurso, violação da carga horária e tempo computacional. Os resultados revelam que os novos algoritmos foram melhores tanto na comparação específica quanto na comparação geral / Abstract: This work¿s main study object consists on algorithms for routing meter readers, from which proposals towards solution¿s improvement are made. The demand for computational results concerning this problem, added to literature little attention due to its inherited peculiarities, has been the outmost motivation. Two preexisting heuristics from literature, with distinct and antagonic strategies, are pointed out. One of these heuristics atempt to create a single route, dismissing the capacity restriction, and then partitionates this route into subroutes, each of them destinated to one meter reader (route first, cluster second). The other heuristic, in an inverse approach, first splits the meter reader¿s working area, and only then routes each of these partitions (cluster first, route second). The two heuristics were tested to exaustion, allowing enumeration of weak aspects subject to improvement. Therefore, two new heuristics were developed, based upon the originals, however adapted in order to outperform solution¿s quality. A testing base containing 144 instances was generated, simulating meter readers realistic labor¿s conditions, classified by size and difficulty. Through solutions provided by the four algorithms, comparison analyses have taken place, evaluating in a general (involving all algorithms) and specific manner (same kind algorithms, i.e., route first, cluster second or cluster first, route second), considering four predefined quality criteria: number of routes, deadheading time, violation of shiftwork time and computational time. Results revealed that the new algorithms achieved better solutions on specific and general comparisons / Mestrado / Automação / Mestre em Engenharia Elétrica

Orientadores: Fernando Jose Von Zuben, Leandro Nunes de Castro / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-14T19:14:33Z (GMT). No. of bitstreams: 1 Franca_FabricioOlivettide_M.pdf: 2824607 bytes, checksum: 3de6277fbb2c8c3460d62b4d81d14f73 (MD5) Previous issue date: 2005 / Resumo: Esta dissertação propõe algoritmos bio-inspirados para a solução de problemas de otimização dinâmica, ou seja, problemas em que a superfície de otimização no espaço de busca sofre variações diversas ao longo do tempo. Com a variação, no tempo, de número, posição e qualidade dos ótimos locais, as técnicas de programação matemática tendem a apresentar uma acentuada degradação de desempenho, pois geralmente foram concebidas para tratar do caso estático. Algoritmos populacionais, controle dinâmico do número de indivíduos na população, estratégias de busca local e uso eficaz de memória são requisitos desejados para o sucesso da otimização dinâmica, sendo contemplados nas propostas de solução implementadas nesta dissertação. Os algoritmos a serem apresentados e comparados com alternativas competitivas presentes na literatura são baseados em funcionalidades e estruturas de processamento de sistemas imunológicos e de colônias de formigas. Pelo fato de considerarem todos os requisitos para uma busca eficaz em ambientes dinâmicos, o desempenho dos algoritmos imuno-inspirados se mostrou superior em todos os critérios considerados para comparação dos resultados dos experimentos. / Abstract: This dissertation proposes bio-inspired algorithms to solve dynamic optimization problems, i.e., problems for which the optimization surface on the search space suffers several changes over time. With such variation of number, position and quality of local optima, mathematical programming techniques may present degradation of performance, because they were usually conceived to deal with static problems. Population-based algorithms, dynamic control of the population size, local search strategies and an efficient memory usage are desirable requirements to a proper treatment of dynamic optimization problems, thus being incorporated into the solution strategies implemented here. The algorithms to be presented, and compared with competitive alternatives available in the literature, are based on functionalities and processing structures of immune systems and ant colonies. Due to the capability of incorporating all the requirements for an efficient search on dynamic environments, the immune-inspired approaches overcome the others in all the performance criteria adopted to evaluate the experimental results. / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica

Orientadores: Raul Vinhas Ribeiro, Antonio Carlos Moretti / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-15T22:13:26Z (GMT). No. of bitstreams: 1 Quinzani_CeciliaMorais_M.pdf: 890601 bytes, checksum: 304bbc7988e7df635b107fc3346436b3 (MD5) Previous issue date: 2010 / Resumo: O desenvolvimento das áreas tradicionais da engenharia tem sido caracterizado pelo crescente emprego de modelos de otimização como paradigmas para problemas de tomada de decisão. Quando estes modelos possuem mais de um objetivo são chamados de Problemas de Otimização Multiobjetivo (POM) e uma alternativa apropriada na resolução deste tipo de problema é a utilização de Algoritmos Evolutivos. Os Algoritmos Evolutivos (AE) simulam o processo de evolução natural. Simplificadamente, o conjunto de soluções candidatas (população) sobre o qual operam as metodologias é modificado utilizando dois princípios básicos de evolução: seleção e variação. O objetivo principal desta dissertação consiste na análise da aplicação de Algoritmos Evolutivos na otimização multiobjetivo de portfólios onde o importante é obter uma correlação ótima entre retorno e risco. Diversos algoritmos evolutivos foram analisados na dissertação, sendo também analisadas versões híbridas dos mesmos. A principal contribuição da dissertação é a proposta de um procedimento de refinamento das soluções que se baseia no comportamento da série histórica para gerar uma população inicial mais adequada. Uma comparação do desempenho dos diferentes algoritmos híbridos com e sem este refinamento da solução foi realizada e o algoritmo com melhor desempenho foi identificado / Abstract: The development of traditional areas of engineering has been characterized by the increasing use of optimization models as paradigms for decision making problems. when these models have more than one objective, they are called multi-objective optimiation problems (POMs), and are a suitable alternative in solving this kind of problem is the usage of Evolutionary Algorithms (EAs). The EAs simulate the process of natural evolution. Briefly, the set of candidate solutions (population) in which the methodologies operate is modified using two basic principles of evolution: selection and variation. The main objective of this dissertation is to review the application of Evolutionary Algorithms in Multiobjective optimization of portfolios in which it is important to obtain an optimal correlation between return and risk . Several evolutionary algorithms have been analyzed in the dissertation, and also analyzed hybrid versions of the same. The main contribution of the dissertation is to propose a procedure for the refinement of solutions based on the behavior of the series to generate a better initial population. A comparison of the performance of different algorithms hybrids with and without this refinement of the solution was performed and the algorithm with best performance was identified / Mestrado / Automação / Mestre em Engenharia Elétrica

Orientador: Akebo Yamakami / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-10T17:03:55Z (GMT). No. of bitstreams: 1 FreitasFilho_LeonardoJoseRamos_M.pdf: 1138592 bytes, checksum: 76882e62668bfba4188afce0f7b35d62 (MD5) Previous issue date: 2008 / Resumo: Um dos problemas mais comuns em planejamento de processos é o escalonamento. Este se resume na alocação de tarefas a serem executadas utilizando determinados recursos, sujeitas a uma ordem de prioridades, restrição de tempo e disponibilidade. O Job Shop é um dos sistemas mais conhecidos e estudados, pois reúne características de outras classes de sistemas de planejamento, além de ser necessária a elaboração de métodos de resolução mais sofisticados devido sua alta complexidade (NP-difícil). A computação natural é constituída por novas abordagens de computação caracterizadas por uma maior proximidade com a natureza. A aplicação de métodos inspirados em sistemas imunológicos demonstra, nos últimos anos, ser promissor em diversas áreas de aplicação e pesquisa, como por exemplo, otimização. Tendo em vista este cenário, é feita aqui uma abordagem imuno-inspirada para elaboração de um sistema de otimização, através de resolução do escalonamento de um Job Shop, provendo soluções diversificas e de alta qualidade / Abstract: Scheduling problems are jobs allocation using distinct sources ordered by sequence constraint and time constraint. Job Shop is one the most studied problem because it is possible to find different scheduling features. Also this problem needs sophisticated solving methods by complexity characteristics (NP-Hard). Natural Computing uses a new computation approach representing natural systems. Immune system methods approaches shows, in the last years, good results in many applications and several researches, for example, optimization. In this scenario we developed an artificial immune system to solve Job Shop system. We will show hight diversity and quality solutions / Mestrado / Telecomunicações e Telemática / Mestre em Engenharia Elétrica

Submitted by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-06-19T15:48:40Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação _ Karen M.R. Silva.pdf: 1498619 bytes, checksum: d635f54be65f67af0ab0e765f8be7cc7 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-06-19T15:48:51Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação _ Karen M.R. Silva.pdf: 1498619 bytes, checksum: d635f54be65f67af0ab0e765f8be7cc7 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-06-19T15:49:21Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação _ Karen M.R. Silva.pdf: 1498619 bytes, checksum: d635f54be65f67af0ab0e765f8be7cc7 (MD5) / Made available in DSpace on 2017-06-19T15:49:21Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação _ Karen M.R. Silva.pdf: 1498619 bytes, checksum: d635f54be65f67af0ab0e765f8be7cc7 (MD5) Previous issue date: 2016-12-05 / The college drop-out in Brazilian private universities constitutes problem both for students and for the institution; in the other side, representing the end of aspiration on the future income stream; and on the other, the waste of resources and opportunity costs of unfilled vacancies. Thus, this work presents the study of the pedagogical factors that influence evasion with students first period in engineering courses in a Higher Education Private Institution during 2013, under the approach of the Markov chain. The approach of this study is quantitative with descriptive method, where the data were collected through desk research and interview technique among students. The population is all students of a private institution engineering courses and the sample refers to 64 students dropping out in the year 2013. According to the preliminary results identified that the highest dropout rate happens in the first half course. The biggest cause of this dropout is influenced by financial problems followed by pedagogical reasons. The course which shows greater evasion is the course of Environmental Engineering. Therefore, so far, this study indicates a significant roadmap, when the courses in this study showed us an average dropout at 49% when the national average shows 22%, these data that refer to higher education. The results of this field study allowed that the proposed model showed results with data validated in a period of time, resulting information for decision making. / A evasão nas universidades privadas brasileiras constitui-se problema tanto para os estudantes quanto para a instituição; por um lado, representando o fim de aspirações sobre o fluxo futuro de renda; e por outro, pelo desperdício dos recursos e custos de oportunidade das vagas ociosas. Neste sentido, este trabalho objetiva aplicar a Cadeia de Markov para estudar os fatores pedagógicos influenciadores da evasão de alunos de primeiro período, matriculados em cursos de Engenharia de uma instituição privada de ensino durante o ano de 2013. A abordagem da pesquisa realizada é quantitativa, com delineamento descritivo, onde os dados foram coletados por meio da técnica de pesquisa documental e entrevista entre os alunos. A população da pesquisa são todos os estudantes dos cursos de Engenharia de uma instituição privada e a amostra refere-se a 64 alunos evadidos no ano de 2013. De acordo com os resultados preliminarmente obtidos, foi identificado que a maior frequência de evasão acontece no primeiro semestre do curso. A principal causa de evasão é influenciada por motivos financeiros, seguido dos motivos pedagógicos. No universo analisado, curso de Engenharia Ambiental que evidenciou a maior evasão. Portanto, até o momento este estudo demonstra um panorama relevante, sendo que os cursos analisados apresentam uma evasão média de 49%, em que a média nacional aponta 22%, dados estes que se referem à educação do ensino superior. Os resultados desta pesquisa demonstraram que o modelo proposto apresentou resultados com dados validados em um período de tempo, resultando assim em informações gerenciais à tomada de decisão

Submitted by Cássia Santos (cassia.bcufg@gmail.com) on 2017-06-19T13:06:19Z No. of bitstreams: 2 Dissertação - Fernando Henrique Fernandes de Camargo - 2017.pdf: 1478139 bytes, checksum: 1a8dae23d70a76b9e72b96aae929d85e (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-07-10T12:28:25Z (GMT) No. of bitstreams: 2 Dissertação - Fernando Henrique Fernandes de Camargo - 2017.pdf: 1478139 bytes, checksum: 1a8dae23d70a76b9e72b96aae929d85e (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-07-10T12:28:25Z (GMT). No. of bitstreams: 2 Dissertação - Fernando Henrique Fernandes de Camargo - 2017.pdf: 1478139 bytes, checksum: 1a8dae23d70a76b9e72b96aae929d85e (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-03-20 / Conselho Nacional de Pesquisa e Desenvolvimento Científico e Tecnológico - CNPq / For countries like Brazil, which has hybrid resources as the major source of electricity, the optimization of the operation of the hydroelectric plants is extremely important and it’s being studied recurrently. Adopting a known temporal decomposition model of this optimization problem, this dissertation is proposed to compare the best multiobjective algorithms of the current literature, applying them to the medium term planning of hydroelectric plants. After several experiments, two algorithms are selected as the best options. / Para um país como o Brasil, que tem seus recursos hídricos como maior fonte de geração de energia elétrica, a otimização da operação das usinas hidrelétricas é extremamente importante e vem sendo estudada de maneira recorrente. Adotando um conhecido modelo de decomposição temporal desse problema de otimização, esta dissertação propôe-se a realizar uma comparação entre os melhores algoritmos de otimização multiobjetivo da literatura atual, aplicado-os ao planejamento de médio prazo de usinas hidrelétricas. Após diversos experimentos realizados, dois algoritmos são selecionados como as melhores opções.