[pt] Este trabalho está relacionado ao problema da utilização eficiente da órbita de satélite geoestacionários. Neste problema, os satélites devem ser alocados adequadamente na órbita, obedecendo a limites de interferência máxima, de modo a satisfazer os requisitos de desempenho dos sistemas. Algumas técnicas para a determinação das posições orbitais de satélites existentes e planejados são mencionadas. Um novo modelo matemático para a otimização das posições orbitais dos satélites, baseado na minimização de uma função objetivo associada à interferência total que afeta cada um dos sistemas, é proposto. Finalmente, alguns resultados obtidos através da aplicação deste modelo são analisados e comparados a outros resultados disponíveis. / [en] This work is related to the problem of efficiently using the geoestationary satellite orbit in an interference limited environment. Some techniques to determine the orbital positions of existing and planned satellites are mentioned. A new mathematical model for optimizing satellite orbital positions based on the minimization of an objective function associated to the total interference affecting each system is proposed. Finally, results obtained through the application of this model are analysed and compared to other available results.

[pt] Problemas de Programação de Horários (PPHs) tem sido amplamente estudados, dada a sua importância prática e teórica. A maioria das variações do problema pertence µa classe NP-Difícil. Em geral, trata-se da alocação de recursos materiais e humanos no espaço e no tempo, visando a otimização de um conjunto de objetivos definidos. Na Programação de Horários de Cursos Universitários, por exemplo, o objetivo pode ser a satisfação do corpo docente e o desempenho acadêmico dos alunos. Nos últimos anos, as formulações de PPHs propostas pela International Timetabling Competition (ITC) tem sido bastante utilizadas, sendo notável a predominância de métodos baseados em busca local e metaeurísticas entre as abordagens propostas recentemente. Este trabalho tem como objetivo propor algoritmos para o Problema de Programação de Horários Pós-Matrícula da ITC, focando principalmente em métodos heurísticos baseados em Programação Matemática. Entre os modelos de Programação Linear Inteira Mista que propomos para este problema, destaca-se o modelo baseado na Formulação de Representantes Assimétricos para o Problema de Coloração de Grafos. Abordamos a aplicação da heurística de Local Branching e propomos um esquema de resolução por Geração de Colunas, como forma de viabilizar o tratamento dos modelos propostos, uma vez que a complexidade de tais modelos representa um desafio para os resolvedores de Programação Linear Inteira Mista atualmente disponíveis. / [en] Timetabling Problems have been widely studied, given its practical and theorical relevance. Most of its variations belong to the NP-Hard class of problems. In general, it is about allocation of material and human resources in time and space, aiming to optimize some set of defined objetives. In University Course Timetabling, for example, the objective might be the satisfaction of professors and the academic performance of students. In the last years, the formulations for timetabling problems proposed by the In- ternational Timetabling Competition (ITC) have been widely adopted. The predominance of meta-heuristics and local search-based methods is remark- able among the recently proposed approaches. The objetive of this thesis is to propose algorithms for the Post Enrolment-based Course Timetabling Problem of the ITC, focusing on Mathematical Programming-based heuris- tic methods. Among the Mixed Integer Linear Programming models that we propose for this problem, we highlight the one based on the Asymetric Representatives Formulation for the Graph Coloring Problem. We explore the application of the Local Branching heuristic and we propose a Column Generation solution procedure, as an attempt to handle the proposed models, given that the complexity of such models poses a challenge for currently available Mixed Integer Linear Programming solvers.

[pt] Esta dissertação investiga o uso de Algoritmos Genéticos e de Co-Evolução Cooperativa na otimização de problemas de planejamento com restrições de precedência. Neste tipo de problema algumas ou todas as tarefas têm restrições que implicam na necessidade de planejá-las ou executá-las antes ou depois de outras. Por esta razão, o uso de modelos evolucionários convencionais como, por exemplo, os baseados em ordem pode gerar soluções inválidas, não penalizáveis, que precisam ser descartadas, comprometendo assim o desempenho do algoritmo. O objetivo do trabalho foi, portanto, estudar formas de representação de soluções para este tipo de problema capazes de gerar somente soluções válidas, bem como avaliar o desempenho dos modelos propostos. O trabalho consistiu de 3 etapas principais: um estudo sobre problemas de otimização de planejamento com algoritmos genéticos; a definição de novos modelos usando algoritmos genéticos e co-evolução cooperativa para otimização de problemas de planejamento com restrições de precedência e a implementação de uma ferramenta para estudo de caso. O estudo sobre os problemas de otimização de planejamentos com algoritmos genéticos envolveu o levantamento de representações, dificuldades e características deste tipo de problema e, mais especificamente, de representações baseadas em ordem. A modelagem do algoritmo genético consistiu fundamentalmente na definição de uma representação dos cromossomas e da função da avaliação que levasse em conta a existência de restrições de precedência (tarefas que devem ser planejadas/executadas antes de outras). A construção do modelo co-evolucionário por sua vez consistiu em definir uma nova população, com uma outra representação, que se responsabilizasse pela distribuição dos recursos para execução das tarefas, responsabilidade esta que, no modelo com algoritmos genéticos convencionais, era tratada de forma simples por um conjunto de heurísticas. Finalmente, desenvolveu-se uma ferramenta para implementar estes modelos e tratar de um estudo de caso complexo que oferecesse as características necessárias para testar a qualidade das representações e avaliar os resultados. O estudo de caso escolhido foi a otimização do planejamento da descarga, armazenamento e embarque de minério de ferro de modo a minimizar o tempo de estadia dos navios em um porto fictício. Foram realizados vários testes que demonstraram a capacidade dos modelos desenvolvidos em gerar soluções viáveis, sem a necessidade de heurísticas de correção, e os resultados obtidos foram comparados com os de um processo de busca aleatória. Em todos os casos, os resultados obtidos pelos modelos foram sempre superiores aos obtidos pela busca aleatória. No caso do modelo de representação com uma única população obteve-se resultados até 41% melhores do que com os obtidos por uma busca aleatória. No caso do modelo de representação com co-evolução o resultado ficou 33% melhor que a busca aleatória com tratamento de solução idêntico ao da solução co-evolucionária. Os resultados da co-evolução comparados com o algoritmo genético com uma única espécie foram 29% melhores. / [en] This work investigates the use of Genetic Algorithms and Cooperative Co-Evolution in optimization of scheduling problems with precedence constraints. In this kind of problem some or all tasks have constraints that imply planning or executing them before or after others. For this reason, the use of order-based conventional evolutionary models may generate invalid solutions, which cannot be penalized, needing to be discarded and therefore compromising the algorithm performance. The main goal was therefore to study models for this kind of problem that are capable of generating only valid solutions. The work was divided in 3 main steps: a survey on scheduling optimization problems using genetic algorithms; definition of two models based on genetic algorithms and cooperative co-evolution for optimizing scheduling problems with precedence constraints; and the implementation of a tool for a case study. The study on scheduling optimization problems with genetic algorithms consisted in gathering information about representations and characteristics of this kind of problem and, more specifically, about order-based representations. The genetic algorithm modeling consisted basically in defining a chromosome representation and an evaluation function that took into account the existence of precedence constraints (tasks that must be scheduled or executed before others). The co-evolutionary model consisted in defining a new population, with another representation scheme, which was responsible for distributing resources for tasks execution. On the conventional genetic algorithm model, this role was played by a simple set of heuristics. Finally, a tool was developed for implementing those models and treating a complex case study which offered the needed characteristics for testing representation performance and evaluating results. The chosen case study was the optimization of iron ore dumping, stocking and ship loading on a fictitious harbor, targeting minimization of ships waiting time. Tests were done in order to demonstrate the ability of the developed models in generating viable solutions without the need of corrective heuristics and the results were compared to the results obtained through exhaustive search. In all cases, the models` results were better than the exhaustive search ones. In the case where the representation used a single population the results obtained were up to 41% better than the ones with the exhaustive search. The co- evolutionary results outperformed the co-evolutionary search with the same solution representation by 33%. Compared to the single specie genetic algorithm, the co- evolutionary model outperformed it by 29%.

[pt] Com base em alguns conceitos de planejamento, que buscam utilizar recursos materiais e humanos de forma racional e eficiente, e na Lei Nacional das Licitações, Lei 8.666/93, que normatiza as contratações feitas pelas empresas públicas, este trabalho estuda os procedimentos adotados em um processo de licitação e apresenta uma proposta para otimizar esses processos e suas consequentes contratações. Discute-se a metodologia de planejamento adaptativo, o processo de Gestão de Conhecimento e a estratégia empresarial de aperfeiçoamento de processos de modo a compor uma base teórica para dar suporte ao projeto de melhoria de desempenho e otimização dos processos licitatórios. Este trabalho analisa também as condições de aplicação da Lei 8.666/93, os procedimentos que devem ser adotados para realização de licitações e descreve os processos licitatórios de contratação de serviços, obras e fornecimento de bens da Companhia Brasileira de Trens Urbanos - CBTU, regidos pelas diretrizes da Lei 8.666/93. A partir de uma análise crítica desses processos e da Lei Nacional de Licitações, apresenta-se uma proposta para otimização desses processos. / [en] Based in some planning concepts which take advantage of human and material resources rationally and efficiently as much as on Bidding Brazilian Law, which regulates the public contracts, this work studies the procedures used in bidding processes and presents a proposition to optimize then and their contracts. This work also considers the adaptive planning methodology, the knowledge management process improvement, so that to compose a theorical base to support the performance progress and optimization of bidding processes. Finally, this work realizes a critical analysis of bidding national law and CBTU bidding processes presenting a optimization for such processes.

[pt] Métodos que combinam estratégias normalmente encontradas em algoritmos metaeurísticos com técnicas para resolver problemas de programação inteira mista (MIP) têm apresentado ótimos resultados nos últimos anos. Este trabalho propõe dois novos algoritmos nessa linha: um algoritmo que faz pós-processamento nas soluções encontradas pelo resolvedor MIP. Os dois algoritmos utilizam um novo tipo de vizinhança, chamada de vizinhança elipsoidal, que possui fortes semelhanças com as técnicas de relinking de algoritmos PR e que neste trabalho é generalizada e extendida para múltiplas soluções. O problema generalizado de alocação (GAP) é usado para os experimentos. São testados também um resolvedor MIP puro (ILOG CPLEX versão 11) e um algoritmo branch and price que utiliza as heurísticas RINS e guided dives. Os algoritmos testados são comparados entre e com heurísticas específicas para o GAP. Os resultados são satisfatórios e indicam que as vizinhanças elipsoidais conseguem frequentemente melhorar as soluções encontradas pelo resolvedor MIP, encontrando a melhor solução para algumas instâncias. / [en] Methods that mix strategies usually found in metaheristic algorithms with techniques to solve mixed integer programming problems (MIPs) have had great results over the past few years. This wprk proposes two new algorithms in this philosophy: one is based on the Path Relink (PR) metaheuristc, while the other one is a simple algorithm that does post-processing in the solutions found by the MIP solver. Both algorithms use a new neighborhood structure, called ellipsoidal neighborhood, that has strong resemblances with the relinking step from PR algorithms and that, in this work, is generalized and extended for multiple solutions. The generalized assignment problem (GAP) is used for the computational experiments. Also tested are MIP solver (ILOG CPLEX version 11) and a branch and price algorithm that uses the RINS and guides dives heuristics. The tested algorithms are compared among themselves and with GAP-specific heuristics. The results are satisfactory and show that the ellipsoidal neighborhood can frequently improve the solutions found by the MIP solver, even finding the best result for some instances.

[pt] O método dos elementos discretos (MED), desenvolvido na década de 70, tem despertado, com o aumento da capacidade de processamento e o desenvolvimento de técnicas de computação de alto desempenho, crescente interesse de diversos pesquisadores como ferramenta de estudo de problemas de engenharia. Um campo de estudo de grande apelo é a modelagem de fenômenos associados a materiais granulares, dentre eles a compacta ção de pacotes granulares - como por exemplo em pós metálicos na indústria siderúrgica - , a produção de areia e a produção de material de sustenta ção de fraturas estimuladas hidraulicamente na indústria do petróleo, motivação deste trabalho. A aplicação do método requer em sua primeira etapa a geração da configuração inicial das partículas ou o preenchimento de domínios com as mesmas. Alguns estudos têm se voltado para o desenvolvimento de algoritmos de geração de arranjos densos de partículas. Neste trabalho apresenta-se um algoritmo geométrico de geração de arranjos densos de partículas que correspondam a uma dada curva granulométrica e estejam de acordo com outros parâmetros definidos para o pacote granular. No presente trabalho é dada atenção especial a geração de arranjos bidimensionais de discos para modelar o fenômeno de preenchimento de fraturas em poços estimulados por fraturamento hidráulico. O refluxo desse material com o bombeamento de óleo é uma das principais causas de declínio de produção de petróleo em poços fraturados, além de causar danos ao equipamento. O algoritmo proposto foi implementado em linguagem Java e a otimização dos arranjos segundo a porosidade foi realizada através da aplicação de algoritmos genéticos. Aplicações do algoritmo a alguns arranjos de partículas e ao problema de preenchimento de fraturas são apresentados. / [en] The Discrete Element Method (DEM), developed in the 70’s, has become more a attractive with the increasing computer processing capacity and the development of high-performance computational techniques. This scenario induced growing interest of many researchers as a tool to study engineering problems. A very appealling field of study is the modeling of phenomena associated with granular materials, including the compaction of granular packages, such as metal powders in the steel industry, sand production and proppant flowback in the petroleum industry, which is motivation to this work. The application of the method in its first step requires the generation of the particles’ initial configuration or the filling of domains with them. Some studies have focused on the development of algorithms to generate dense packing of particles. This work presents an algorithm to generate random dense packing of particles that correspond to a given granulometric curve and are consistent with other parameters set for the granular package. In the present work special attention is given to generation of two-dimensional packings of disks to model the phenomenon of fractures filling in wells stimulated by hydraulic fracturing. The proppant flowbak generated by the oil pumping is a leading cause of production decline in fractured wells, besides causing damage to the production equipment. The proposed algorithm was implemented in Java language and the optimization of packings was performed according to the porosity using genetic algorithms. Applications of the algorithm to some packings of particles and the problem of filling of fractures are presented.

[pt] O problema de minimizar o custo de avaliar uma função discreta lendo sequencialmente as suas variáveis é um problema que surge em diversas aplicações, entre elas sistemas de diagnóstico automático e aprendizado ativo. Neste problema, cada variável da função está associada a um custo, que se deve pagar para checar o seu valor. Além disso, pode existir uma distribuição de probabilidades associadas aos pontos onde a função está definida. A maioria dos trabalhos nesta área se concentra ou na minimização do custo máximo ou na minimização do custo esperado gasto para avaliar a função. Nesta dissertação, mostramos como obter uma Ômicron logaritmo de N aproximação em relação à minimização do pior custo (a melhor aproximação possível assumindo que P é diferente de NP). Nós também mostramos um procedimento polinomial para avaliar uma função otimizando simultaneamente o pior custo e o custo esperado. / [en] The problem of minimizing the cost of evaluating a discrete function by sequentially reading its variables is a problem that arises in several applications, among them automatic diagnosis design and active learning. In this problem, each variable of the function is associated with a cost, that we have to pay in order to check its value. In addition, there may exist a probability distribution associated with the points where the function is defined. Most of the work in the area has focussed either on the minimization of the maximum cost or on the minimization of the expected cost spent to evaluate the function. In this dissertation, we show how to obtain an Ômicron logarithm of N approximation with respect to the worst case minimization (the best possible approximation under the assumption that P is different from NP). We also show a polynomial time procedure for evaluate a function that simultaneously optimizes both the worst and the expected costs.

[pt] Este trabalho apresenta uma formulação puramente baseada em plasticidade para ser aplicada à otimização topológica. A principal ideia da otimização topológica em mecânica dos sólidos é encontrar a distribuição de material dentro do domínio de forma a otimizar uma medida de performance e satisfazer um conjunto de restrições. Uma possibilidade é minimizar a flexibilidade da estrutura satisfazendo que o volume seja menor do que um determinado valor. Essa é a formulação clássica da otimização topológica, que é vastamente utilizada na literatura. Não obstante fornecer resultados interessantes, condições adicionais devem ser levadas em consideração para viabilizar sua aplicação prática. O projeto estrutural aborda dois aspectos principais: (i) a estrutura não deve colapsar, suportando os carregamentos aplicados (critério de segurança); e (ii) deverá se sujeitar a um valor máximo aceitável de deformação (critério de aceitabilidade). Consequentemente, a otimização topológica clássica deve ser modificada de forma a encontrar a distribuição de material correspondente ao menor volume possível tal que o critério de segurança seja verificado. O referido critério de segurança pode ser definido como limitar as tensões elásticas ao critério de plastificação em todo o domínio. Esta definição resultou em um novo ramo de pesquisa: a otimização topológica com restrições de tensões. Por outro lado, entende-se que o projeto estrutural plástico é preferível quando um projeto ótimo é almejado, uma vez que permite um maior aproveitamento da resistência do material. Dessa forma, este trabalho aborda a incorporação do projeto estrutural plástico à otimização topológica como método mais vantajoso do que a otimização topológica clássica e a com restrições de tensões. A formulação proposta é uma extensão da análise limite, que fornece uma estimativa da carga de colapso de uma estrutura diretamente por meio da programação matemática, assegurando a eficiência computacional da metodologia proposta. De forma a verificar a otimização topológica plástica e comparar a topologia final com as obtidas através da otimização topológica clássica e da com restrição de tensões, são apresentados exemplos numéricos. / [en] This work presents a full plastic formulation to be applied within topology optimization. The main idea of topology optimization in solid mechanics is to find the material distribution within the domain so that it optimizes a performance measure and satisfies a set of constraints. One might seek to minimize the compliance satisfying that the volume is less than a given value. The aforementioned formulation is the standard topology optimization which has been used widely in literature. Although it provides interesting results, additional requirements must be taken into account when practical application is concerned. Structures are designed considering two main aspects: (i) the structure must not collapse, supporting the applied loads (safety criterion); and (ii) its displacements must be lower than a prescribed bound (serviceability criterion). Consequently, the standard formulation shall be modified, finding the material distribution corresponding to the minimum volume such that the safety criterion is met. Said safety criterion may be defined as restraining the elastic stresses to the yield criterion in the entire domain. This definition has resulted in a new branch in this research field: the stress constrained topology optimization. On the other hand, it is understood that the plastic design criterion is preferable when optimization is intended, since it fully exploits the material strength. Therefore, this work addresses the incorporation of the plastic design criterion into topology optimization as a more advantageous method than standard and stress constrained topology optimization methods. The proposed formulation is an extension of limit analysis, which provides an estimative of the collapse load of a structure directly through mathematical programming, ensuring computational efficiency to the proposed methodology. Lastly, numerical examples are shown to verify plastic topology optimization and the final topology is compared with those provided by standard and stress constrained topology optimization methods.

[pt] Este trabalho tem por objetivo apresentar uma proposta de aplicação, para alunos do Ensino Médio, de otimização de funções lineares usando o modelo de resolução gráfica. Para melhor visualização do modelo é sugerido o uso de ferramentas tecnológicas como softwares gráficos – neste trabalho foi utilizado o software livre GeoGebra. A ideia principal do trabalho é mostrar a importância da Matemática como ferramenta para interpretar, compreender e tomar decisões nas mais diversas situações do cotidiano, em especial, neste trabalho situações de alocação de recursos para otimização do lucro de uma produção. / [en] This project aims to present an application proposal, for high school students, to optimize linear functions using the graphic resolution model. In order to achieve a better view of the model, the use of technological tools such as graphic softwares is suggested — in this project we used a free software named GeoGebra. The project main idea is to show the importance of Mathematics as a tool to interpret, understand and make decisions in relation to the most varied daylife situations, specifically here, in this project, in situations of resources allocation to optimize the profits of a production.

[pt] A metodologia da superfície de resposta desempenha um papel importante no desenvolvimento, melhoria e otimização de processos e produtos mediante a aplicação de um conjunto de técnicas estatísticas e matemáticas. O foco principal desta pesquisa é a última etapa da metodologia que está relacionada ao estudo da superfície de resposta na região de interesse. Assim, a presente dissertação tem como objetivo apresentar de forma sintetizada a metodologia para realizar a Análise de Cumeeira nos modelos ajustados de superfícies de resposta de segunda ordem que têm como ponto estacionário um ponto de sela ou um ponto fora da região experimental. Nesta análise procuram-se as condições ótimas de processos e produtos através de experimentos planejados. A análise de cumeeira é particularmente importante quando for difícil visualizar a superfície de resposta devido à existência de quatro ou mais dimensões. Apresentam-se alguns exemplos oriundos da literatura e também é realizada a análise de um caso prático real. / [en] The response surface methodology plays an important role in the developing, improving and optimizing processes and products through the application of a collection of statistical and mathematical techniques. The main focus of this research is the last step of the methodology that is related to the study of the response surface in the region of interest. Thus, this dissertation aims to present a summarized methodology for ridge analysis in the fitted models of the second-order response surfaces that have a saddle point or a point out of the experimental region as a stationary point. This analysis looks for the optimum process and product conditions through planned experiments. Ridge analysis is particularly important when it is difficult to visualize the response surface due to the existence of four or more dimensions. In this work there are some examples that derive from literature, and an analysis of a real case study is also performed.