Orientador: João Peres Vieira / Resumo: A Programação Linear é usada na Pesquisa Operacional para resolução de problemas cujo objetivo é encontrar a melhor solução para aqueles problemas que tenham seus modelos representados por expressões lineares. A Álgebra Linear vai ser a ferramenta para a Programação Linear, resolvendo problemas de maximização ou minimização. Vamos utilizar o Método Simplex e, no caso de duas variáveis, apresentaremos também o método gráfico. / Abstract: Linear Programming is used in Operational Research to solve problems resolution whose goal is to find the best solution for those problems that have their models represented by linear expressions. Linear Algebra will be the tool for Linear Programming, solving maximization or minimization problems. We will use the Simplex Method and, in the case of two variables, we will also present the graphical method. / Mestre

Electric cars are projected to become the vehicles of the future. A major barrier for their expansion is range anxiety stemming from the limited range a typical EV can travel. EV batteries' performance and capacity are affected by many factors. In particular, the decrease in ambient temperature below a certain threshold will adversely affect the battery's efficiency. This research develops deterministic and two-stage stochastic program model for charging stations' optimal location to facilitate the routing decisions of delivery services that use EVs while considering the variability inherent in climate and customer demand. To evaluate the proposed formulation and solution approach's performance, Fargo city in North Dakota is selected as a tested. For the first chapter, we formulated this problem as a mixed-integer linear programming model that captures the realistic charging behavior of the DCFC's in association with the ambient temperature and their subsequent impact on the EV charging station location and routing decisions. Two innovative heuristics are proposed to solve this challenging model in a realistic test setting, namely, the two-phase Tabu Search-modified Clarke and Wright algorithm and the Sweep-based Iterative Greedy Adaptive Large Neighborhood algorithm. The results clearly indicate that the EV DCFC charging station location decisions are highly sensitive to the ambient temperature, the charging time, and the initial state-of-charge. The results provide numerous managerial insights for decision-makers to efficiently design and manage the DCFC EV logistic network for cities that suffer from high-temperature fluctuations. For the second chapter, a novel solution approach based on the progressive hedging algorithm is presented to solve the resulting mathematical model and to provide high-quality solutions within reasonable running times for problems with many scenarios. We observe that the location-routing decisions are susceptible to the EV logistic's underlying climate, signifying that decision-makers of the DCFC EV logistic network for cities that suffer from high-temperature fluctuations would not overlook the effect of climate to design and manage the respective logistic network efficiently.

Este trabalho tem seu foco no problema de sequenciamento e programação da lavra em mina a céu aberto, com alocação de equipamentos de carregamento. Neste estudo considera-se a existência de uma frota heterogênea de equipamentos de carga e dois tipos de material lavráveis, sendo minério ou estéril. Para a lavra de minério são considerados requisitos de qualidade a serem atingidos pela mistura de minério, um britador, uma capacidade de operação atribuída à usina de beneficiamento e uma pilha de estoque objetivando abastecer a usina quando faltar minério nas frentes de lavra, denominada pilha de ROM. Em uma mina o carregamento pode ser gerido por um plano de lavra que descreve a movimentação e a produção horária de cada equipamento de carga ao longo do tempo. Neste contexto, apresenta-se um modelo matemático apoiado por um algoritmo responsável por mover o horizonte de tempo a cada execução do modelo com intuito de gerar ordens de lavra resolvidas com otimalidade. Juntas, essas ordens descreverão o plano de lavra dos equipamentos de carga. Os experimentos computacionais, realizados utilizando dados de uma jazida de cobre, mostram a efetividade da proposta considerando um horizonte de médio prazo. / This paper focuses on the mining scheduling problem in open pit, considering the allocation of loading equipment. This study considers the existence of a heterogeneous fleet loading equipment and two types of mineable material, namely ore or waste. For the mining of ore are considered quality requirements to be met by the ore blending, a crusher, the capacity of operation of the processing plant and a stockpile which feed the plant when there is lack of ore in mining fronts, called ROM stockpile. In a mine, loading can be managed by a mining plan that describes the movement and the schedule of each load equipment over time. In this context, we present a mathematical model supported by an algorithm that is responsible for moving the time horizon for each model run, with the goal of generating mining orders till resolved to optimality. Together, these orders describe the mining plan of the loading equipment. The computational experiments, conducted using data from a copper deposit, show the effectiveness of the proposal considering a medium-term horizon.

Dans cette thèse nous nous intéressons à plusieurs problèmes de gestion de stocks, à travers des modèles de dimensionnement de lots sur plusieurs niveaux, en tenant compte de capacités de production. Nous étudions tout d’abord un problème de dimensionnement de lots à deux niveaux en série avec des capacités de production identiques et stationnaires aux deux niveaux, pour lequel proposons un algorithme dynamique exact pouvant résoudre le problème en temps polynomial sous certaines hypothèses. Dans le chapitre suivant nous étendons ce résultat dans deux directions : nous considérons le problème de gestion de stocks sur un nombre quelconque de niveaux en série, et nous considérons des livraisons par lots. Nous présentons un algorithme exact de résolution, polynomial et très efficace, basé sur une décomposition originale en composantes connexes induites. Nous considérons ensuite des versions plus générales de ce problème, en établissant des résultats de NP-complétude lorsque chaque niveau à une capacité ou une taille de lot différentes. Nous proposons pour ces problèmes une 2-approximation, basé sur l’encadrement de la fonction objectif par deux fonctions affines. Pour finir nous étudions un problème sur un seul niveau mais dans un système de production composé de machines identiques fonctionnant en parallèle. L’originalité de ce problème est de considérer une limitation de la consommation énergétique. A chaque période, on doit décider combien de machines allumer ou éteindre, et quel volume produire et stocker. Des résultats de complexité sont proposés, montrant que ce problème est NP-difficile même sous des hypothèses fortes, et un algorithme dynamique exact est présenté pour le cas de paramètres d’énergie stationnaires / In this thesis we are interested in several multi-level lot-sizing problems taking into account production capacities. We first study a 2-level in series lot-sizing problem with identical and stationary capacities at both levels, for which we propose an exact dynamic algorithm running in polynomial time under some hypothesis. Next chapter extends this result on two main lines: we consider the multi-level in series lot-sizing problem with batch deliveries and with a number of level which is part of the input. We provide a very efficient exact algorithm for this problem, which is polynomial in the number of levels and in the number of periods, based on an original decomposition into induced connected components. Then, we consider more general versions of this problem, for which we provide NP-hardness results when batch sizes or capacities are level-dependent. We propose 2-approximation algorithms for these problems, based on the sandwiching of the objective function by two affine functions. Finally, we study a single-level lot-sizing problem in a system composed of identical machines working in parallel. The originality of this study is to consider a periodic energy limitation. At each period it must be decided how many machines to switch on or off and the volume to be produced and stored. Complexity results are provided, showing that this problem is NP-hard, even under some restrictive assumptions, and an exact dynamic algorithm running in polynomial time is proposed for the case of stationary energy parameters

Este trabalho tem seu foco no problema de sequenciamento e programação da lavra em mina a céu aberto, com alocação de equipamentos de carregamento. Neste estudo considera-se a existência de uma frota heterogênea de equipamentos de carga e dois tipos de material lavráveis, sendo minério ou estéril. Para a lavra de minério são considerados requisitos de qualidade a serem atingidos pela mistura de minério, um britador, uma capacidade de operação atribuída à usina de beneficiamento e uma pilha de estoque objetivando abastecer a usina quando faltar minério nas frentes de lavra, denominada pilha de ROM. Em uma mina o carregamento pode ser gerido por um plano de lavra que descreve a movimentação e a produção horária de cada equipamento de carga ao longo do tempo. Neste contexto, apresenta-se um modelo matemático apoiado por um algoritmo responsável por mover o horizonte de tempo a cada execução do modelo com intuito de gerar ordens de lavra resolvidas com otimalidade. Juntas, essas ordens descreverão o plano de lavra dos equipamentos de carga. Os experimentos computacionais, realizados utilizando dados de uma jazida de cobre, mostram a efetividade da proposta considerando um horizonte de médio prazo. / This paper focuses on the mining scheduling problem in open pit, considering the allocation of loading equipment. This study considers the existence of a heterogeneous fleet loading equipment and two types of mineable material, namely ore or waste. For the mining of ore are considered quality requirements to be met by the ore blending, a crusher, the capacity of operation of the processing plant and a stockpile which feed the plant when there is lack of ore in mining fronts, called ROM stockpile. In a mine, loading can be managed by a mining plan that describes the movement and the schedule of each load equipment over time. In this context, we present a mathematical model supported by an algorithm that is responsible for moving the time horizon for each model run, with the goal of generating mining orders till resolved to optimality. Together, these orders describe the mining plan of the loading equipment. The computational experiments, conducted using data from a copper deposit, show the effectiveness of the proposal considering a medium-term horizon.

This dissertation studies a framework in support biomass wood pellet supply chain. The worldwide wood pellet market is growing at a phenomenal rate. However, the economic sustainment of this business depends on how well the producers manage the uncertainty associated with biomass yield and quality. In the first part of the dissertation, we propose a two-stage stochastic programming model that optimizes different critical decisions (e.g., harvesting, storage, transportation, quality inspection, and production decisions) of a biomass-to-pellet supply system under biomass yield and quality uncertainty to economically produce pellets while accounting for the different pellet standards set forward by the U.S. and European markets. The study develops a hybrid algorithm that combines Sample Average Approximation with an enhanced Progressive Hedging algorithm. We propose two parallelization schemes to efficiently speed up the convergence of the overall algorithm. We use Mississippi as a testing ground to visualize and validate the algorithms performance. Experimental results indicate that the biomass-to-pellet supply system is sensitive to the biomass quality parameters (e.g., ash and moisture contents). In the second part of the dissertation, we propose a bi-level mixed-integer linear programming model that captures important features such as the hurricane’s degree, quality of damaged timbers, price-related issues, optimizes different critical decisions (e.g., purchasing, storage, and transportation decisions) of a post-hurricane damaged timber management problem. Lack of efficient tools to manage the wood market interactions in the post-hurricane situation increases timber salvage loss drastically. The overall goal is to provide an efficient decision-making tool for planning and recovering damaged timber to maximize its monetary value and mitigate its negative ecological impacts. Due to the complexity associated with solving the proposed model, we developed two exact solution methods, namely, the enhanced Benders decomposition and the Benders-based branch-and-cut algorithms, to efficiently solve the model in a reasonable time-frame. We use 15 coastal counties in southeast Mississippi to visualize and validate the algorithms' performance. Key managerial insights are drawn on the sensitivity of a number of critical parameters, such as selling/purchasing prices offered by the landowners/mills, quality-level, and deterioration rate of the damaged timbers on their economic recovery following a natural catastrophe.

Made available in DSpace on 2015-03-05T14:01:22Z (GMT). No. of bitstreams: 0 Previous issue date: 12 / Bolsa para curso e programa de Pós Graduação / Este trabalho aborda o uso de uma metaheurística populacional para a solução do problema de otimização conhecido, na Pesquisa Operacional, como Programação de Horário de Cursos Baseada em Currículos. O problema de Programação de Horário de Cursos Baseada em Currículos consiste na construção das grades de horário de cursos em instituição de ensino que indicam em quais períodos semanais cada disciplina destes cursos deverá ocorrer, alocando professores e salas e respeitando um conjunto de requisitos organizacionais, pedagógicos e pessoais. Este trabalho apresenta uma formulação matemática para o problema e especifica um algoritmo de solução baseado na técnica metaheurística Busca Dispersa, combinada com o método de Reconexão por Caminhos. Além disso, é apresentado o registro de testes realizados com instâncias de problemas utilizadas na International Timetabling Competition e também em um problema real de uma instituição local de esino superior. / This paper discusses the use of a populational metaheuristic to solve the optimization problem known in Operational Research, as Curriculum Based Timetabling. The Curriculum Based Timetabling problem is the construction of schedule of courses in educational institutions that indicate which weekly times each subject of these courses should occur, allocating rooms and teachers and a respecting a set of organizational, pedagogical and personal requirements. This paper presents a mathematical formulation for the problem and specify a solution algorithm based on the Scatter Search metaheuristic technique, combined with the method Path Relinking. Furthermore, it is present the record of tests with instances of problems used in the International Timetabling Competition and also a real problem of a local institution.

Ο Ακέραιος Προγραμματισμός είναι κλάδος του Γραμμικού Μαθηματικού Προγραμματισμού, και αποτελεί τμήμα της συνδιαστικής βελτιστοποίησης. Στόχος της χρήσης του είναι η βελτιστοποίηση συστημάτων παραγωγής ή διοίκησης. Ο Ακέραιος Προγραμματισμός χρησιμοποιείται για την επίλυση πρακτικών προβλημάτων, όπως: • Χρονοδιαγράμματα (Scheduling) • Σχεδιασμός παραγωγής • Παράλληλη εκτέλεση εργασιών • Τηλεπικοινωνίες Μπορεί να φαίνεται ότι τα προβλήματα ακεραίου προγραμματισμού είναι εύκολο να λυθούν. Παρ’όλ’αυτά, κάτι τέτοιο δεν ισχύει, διότι οι αστρονομικά μεγάλοι ακέραιοι αριθμοί, καθώς επίσης και η στρογγυλοποίηση και αφαίρεση μη ακεραίων λύσεων από ένα πρόβλημα γραμμικού προγραμματισμού οδηγούν σε προβλήματα και λανθασμένα συμπεράσματα. Οι κυριότερες τεχνικές Ακεραίου Προγραμματισμού είναι οι εξής: • Μέθοδος κλάδου και φραγής (Branch and Bound) • Τεχνικές περιορισμού του εφικτού χώρου (Cutting Planes) • Μέθοδοι απαρίθμησης • Διαμεριστικοί αλγόριθμοι • Αλγόριθμοι βασισμένοι στη θεωρία ομάδων (Gomory) Η προπτυχιακή αυτή διπλωματική εργασία έχει στόχο να παρουσιάσει δύο από αυτές τις τεχνικές λεπτομερώς, την μέθοδο κλάδου και φραγής και τεχνικές περιορισμού του εφικτού χώρου, και να κάνει κατανοητή τη χρησιμότητα των αλγορίθμων αυτών μέσα από παραδείγματα που αφορούν προβλήματα ακέραιου προγραμματισμού. / Integer Programming is a branch of Linear Mathematical Programming, and is part of the combinatorial optimization. The purpose of using the system optimization of production or administration. The Integer Programming is used to solve practical problems, such as: • Timelines (Scheduling) • Production Design • Parallel execution of works • Telecommunications It may seem that the integer programming problems are easy to solve. However, this is not true, because the astronomically large integers, as well as rounding and removing non-integer solutions of a linear programming problem lead to problems and false conclusions. The main technical Integer Programming are: • branch and bound method (Branch and Bound) • Technical limitations of feasible region (Cutting Planes) • Methods of enumeration • Diameristikoi algorithms • Algorithms based on the theory of groups (Gomory) Undergraduate this thesis aims to present two of these techniques in detail, the branch and bound method and techniques to reduce the feasible region, and make understandable the usefulness of these algorithms through examples involving integer programming problems.

Avec plus de 345 millions de tonnes de déchets produits en France en 2012, la performance de la chaîne logistique de collecte, transport et traitement de ces produits et matériaux est devenue un enjeu économique et écologique majeur dans notre société. Dans cette thèse, nous nous intéressons à l’optimisation de la chaîne de collecte et transport des déchets sur le plan tactique et opérationnel. Nous modélisons dans un premier temps un nouveau problème tactique d’optimisation de flux de déchets avec sites de transfert et de traitement sur un horizon mono-périodique puis multi-périodique, afin d’exploiter un réseau logistique existant de manière optimale. Nous résolvons différentes variantes de ce problème linéaire mixte à l’aide d’un solveur. Nous étudions dans un second temps la planification opérationnelle de la collecte de conteneurs d’apport volontaire et des tournées de véhicules associées en résolvant un problème riche de tournées avec gestion de stocks et plateformes de vidage intermédiaires. Nous proposons un modèle d’optimisation de ce nouveau problème et le résolvons par un algorithme à voisinages larges (ALNS) dans un cadre déterministe puis stochastique, dans lequel le remplissage des conteneurs est aléatoire et plus conforme à la réalité. Nous obtenons des résultats compétitifs en évaluant notre approche sur des instances de la littérature proches de notre problème riche. En réalisant un logiciel d’optimisation à destination d’une entreprise de collecte et transport de déchets, nous améliorons également de manière significative les tournées de véhicules en application réelle. / With more than 345 million tons produced in France in2012, waste supply chain management is an important economical and ecological issue for our society. In this thesis, we focus on optimizing waste supply chain on both the tactical and operational decision levels. In order to optimize an existing waste logistic network in medium term, we first solve a multimodal flow problem where products are transferred and transformed in sites of various size, in a mono-periodic then multi-periodic horizon. At an operational level, we study the planning and routing of vehicles used for voluntary drop-off waste container collection by solving a complex inventory routing problem with intermediate facilities. We use a large neighborhoods search metaheuristic to solve both the deterministic and stochastic approaches, where waste supply quantity is also subject to uncertainty. We obtain competitive results on instances coming from the literature on classical routing problems close to our rich case. We also develop an optimization software used by a French waste management company and significantly improve routes in a real application.

This thesis deals with the use of operation research methods in sports scheduling. The theoretical part is focused on basic methods of operation research, linear programming and assignment problems are described in greater detail. The thesis presents the principles of sports tournaments and selected optimization softwares in the next part. In the practical part own mathematical models for sport scheduling are introduced. The solution procedure is demonstrated on real life problem of sports scheduling for actual men's basketball season. This example provides the reader with complex concept of solving process of sport scheduling problems.