The present thesis shows the manner of distributing workers on shifts with regular work load but uneven work schedules. It is generally known as the covering or set-covering problem. The present paper describes a way to solve it with mathematical modelling and programs for possible planning of workers on shifts. The issue is documented on a case of an existing company.

At the basic there is a connection between operation research and automotive logistics. The supply chain in this type of industry is hard to coordinate and flexibility is considered as a main key indicator. Companies increase their competitiveness through the optimization of supply chain and try to take control of every flow or a process. This idea goes throughout the departments. The main concept, which is about a connection of whole supply chain with information flow means, that there isn't need of stock and every input is highly available on time and in requested quantity and quality. This thesis describes inbound logistics and introduces some of the methods used for planning vehicle routes. In our situation which is based on car maker data set was chosen a group of a suppliers for the analysis. We used vehicle routing problem with some modifications, heuristics based on the covering problem. Founded solution was compared with the present state.

No description available.

This thesis applies classical optimization problems such as assignment or set-covering problem on logical puzzles or brainteasers. Listed in the first part are mathematical model, description and typical example of each optimization problem used in this thesis. The second part contains these models applied to the particular brainteasers for example Sudoku or Einstein's Puzzle. Exercises are divided into simpler and more complex ones. There is specification, source and a described method of solution stated for each of them. The calculation examples use Lingo or MS Excel or both. The aim is to show the possibility to address logical puzzles and brainteasers with the use of optimization problems, and thus confirm the wide possibilities of using these models. These examples can clarify and diversify the curriculum.

<p>This thesis is devoted to introducing new problem formulations and exact solution methods for a class of continuous covering location models. The manuscript includes three self-contained studies which are organized as in the following. </p> <p> In the first study, we introduce the planar expropriation problem with non-rigid rectangular facilities which has many applications in regional planning and undesirable facility location domains. This model is proposed for determining the locations and formations of two-dimensional rectangular facilities. Based on the geometric properties of such facilities, we developed a new formulation which does not require employing distance measures. The resulting model is a mixed integer nonlinear program. For solving this new model, we derived a continuous branch-and-bound framework utilizing linear approximations for the tradeoff curve associated with the facility formation alternatives. Further, we developed new problem generation and bounding strategies suitable for this particular branch-and-bound procedure. We designed a computational study where we compared this algorithm with two well-known mixed integer nonlinear programming solvers. Computational experience showed that the branch-and-bound procedure we developed performs better than BARON and SBB both in terms of processing time and size of the branching tree.</p> <p> The second study is referred to as the planar maximal covering problem with single convex polygonal shapes and it has ample applications in transmitter location, inspection of geometric shapes and directional antenna location. In this study, we investigated maximal point containment by any convex polygonal shape in the Euclidean plane. Using a fundamental separation property of convex sets, we derived a mixed integer linear formulation for this problem. We were able to identify two types of special cuts based on the geometric properties of the shapes under study, which were later employed for developing a branch-and-cut procedure for solving this particular location model. We also evaluated the resultant bound quality after employing the afore-mentioned cuts. </p> <p> In the third study, we discuss the dynamic planar expropriation problem with single convex polygonal shapes. We showed how the basic problem formulations discussed in the first two studies extend to their diametric opposites, and further to models in higher dimensions. Subsequently, we allowed a dynamic setting where the shape under study is expected to function over a finite planning horizon and the system parameters such as the fixed point locations and expropriation costs are subject to change. The shape was permitted to relocate at the beginning of each time period according to particular relocation costs. We showed that this dynamic problem structure can be decomposed into a set of static problems under a particular vector of relocations. We discussed the solution of this model by two enumeration procedures. Subsequently, we derived an incomplete dynamic programming procedure which is suitable for this distinct problem structure. In this method, there is no need to evaluate all the branches of the branching tree and one proceeds with keeping the minimum stage cost. The evaluation of a branch is postponed until relocation takes place in the lower-level problems. With this postponing structure, the procedure turned out to be superior to the two enumeration procedures in terms of tree size. </p> / Thesis / Doctor of Philosophy (PhD)

Submitted by JOSIANE SANTOS DE OLIVEIRA (josianeso) on 2018-04-12T13:49:50Z No. of bitstreams: 1 Deborah Luisa Detânico Vieira_.pdf: 1504339 bytes, checksum: 49a2adc770aff79d216c818e22dea099 (MD5) / Made available in DSpace on 2018-04-12T13:49:50Z (GMT). No. of bitstreams: 1 Deborah Luisa Detânico Vieira_.pdf: 1504339 bytes, checksum: 49a2adc770aff79d216c818e22dea099 (MD5) Previous issue date: 2017-05-17 / Nenhuma / Com a crescente demanda de serviços de voz e, principalmente, dados móveis se fez necessário o desenvolvimento das tecnologias de quarta geração (4G). O padrão Long Term Evolution (LTE), desenvolvido pela Third Generation Partnership Project (3GPP), foi escolhido pela International Telecommunications Union (ITU) como tecnologia para atender os requisitos da quarta geração de serviços móveis. Para as operadoras inserirem esta nova tecnologia em suas redes existentes, se faz necessário um estudo meticuloso de planejamento, muito embora, na prática, este planejamento seja desenvolvido de forma empírica. O problema de planejamento de redes é conhecido e bem estudado no ramo da computação, conhecido como problema de recobrimento de conjuntos e classificado, pela sua complexidade, como NP-difícil. Dadas as características diferenciadas da arquitetura da rede do LTE, este trabalho busca resolver o problema de planejamento de redes de quarta geração (4G), utilizando uma modelagem matemática aplicada a uma metaheurística híbrida, composta de Algoritmo Genético e Busca Tabu. Almejase resolver o problema de cobertura de uma determinada região, cobrindo a maior área possível com o menor número possível de Base Stations (BS), visando ao planejamento com maior assertividade e redução do custo de implantação da rede 4G. / With the constantly demand of voice services and mostly in mobile data, there was the need the development of the mobile services of fourth generation (4G). The pattern Long Term Evolution, developed by the Third Generation Partnership Project (3GPP) was chosen by the International Telecommunications Union (ITU) as technology to attend the requirements of the fourth generation of mobile services. For the mobile operators introduce and apply this new generation in their own existing networks, they need to do an extensive research and planning, even if, in practical means, it is applied using the empirical way. The network planning problem is widely known and studied in computing area as set-covering problem ans classified as NPhard. Due the unique characteristics of network architecture of LTE, this work aims to solve the mobile’s fourth generation planning problem using a mathematics modelling apply to a hybrid metaheuristics, composed with Genetic Algorithm and Tabu Search. It aims solve the coverage problem of a specific region, covering the largest area possible with the fewest number of Base Sations (BS) possible, seeking the best compliance and cost reduction of the LTE network deployment.

Submitted by Silvana Teresinha Dornelles Studzinski (sstudzinski) on 2015-06-19T15:40:42Z No. of bitstreams: 1 Eduardo Augusto Martins.pdf: 5700123 bytes, checksum: 4789112a51c3fa9b5a888aa5987298e9 (MD5) / Made available in DSpace on 2015-06-19T15:40:42Z (GMT). No. of bitstreams: 1 Eduardo Augusto Martins.pdf: 5700123 bytes, checksum: 4789112a51c3fa9b5a888aa5987298e9 (MD5) Previous issue date: 2013 / Nenhuma / Sistemas centralizados de medição de energia são atualmente uma escolha para automatizar redes e garantir o funcionamento do complexo sistema de distribuidoras de energia elétrica. Atualmente, estes sistemas compõem as chamadas smart grids, redes inteligentes de geração, transmissão e distribuição de energia, dotadas de dispositivos de comunicação de dados, possibilitando a aplicação de sistemas distribuídos, com base na troca de informações entre equipamentos, formando uma nova rede, também de alta complexidade, para interligação e controle de dados. No Brasil, um trabalho inédito vem sendo desenvolvido na criação deste tipo de rede: a utilização de uma infraestrutura avançada de medição, baseada em sistemas de medição centralizada, alocadas em áreas de grandes concentrações urbanas, com objetivos de diminuição, ou até mesmo eliminação de perdas comerciais de distribuição de energia, emerge como novidade na aplicação de redes inteligentes de distribuição de energia elétrica no país. Este trabalho tem por objetivo a descrição do desenvolvimento de uma solução computacional, baseada em um método de busca metaheurística conhecido como Simulated Annealing para apoio à formulação de projetos de redes otimizadas de infraestrutura avançada de medição que utilizam equipamentos de sistemas de medição centralizados em uma rede de distribuição de energia elétrica, garantindo máxima cobertura da rede, atendimento a todos os clientes geograficamente localizados na região de projeto, minimizando custos de instalação dos sistemas. Na busca deste objetivo, este trabalho apresenta a redução do problema de otimização para o Problema do Recobrimento, a construção do modelo matemático, a implementação computacional e as aplicações na forma de simulações e resultados. A metodologia proposta, aplicada ao sistema computacional como forma de simulação, permite uma análise muito rápida e dinâmica de topologias de rede a serem projetadas para utilização em projetos de redes de comunicações, onde se utilizam sistemas de medição centralizados. O sistema computacional permite a alteração das características de simulação e das características das redes, dependendo das restrições impostas pela área geográfica em estudo. A estratégia apresenta bons resultados na formação de topologias de redes de comunicação para sistemas de medição centralizada, bem como otimização na utilização de equipamentos, reduzindo custos de instalação na rede. / Centralized systems of energy measurement are actually a choice for automating networks and ensure the operation of the complex system of electricity distribution. Currently, these systems comprise the so-called smart grid generation, transmission and distribution of energy, equipped with data communication devices, enabling the implementation of distributed systems, based on the exchange of information between devices, forming a new network, of high complexity, and for interconnection data control. In Brazil, a new work is being developed for creating this type of network: the use of an advanced infrastructure for measurement, centralized measurement systems allocation in areas of large urban concentrations, with goals of reducing, or even eliminating, commercial losses of power distribution, that emerges as a novelty in applying smart grid distribution of electricity in the country. This work aims at describing the development of a computational solution, based on a metaheuristic search method known as Simulated Annealing to support the design of optimized network for advanced metering infrastructure using equipment measurement systems on a centralized network of power distribution, ensuring maximum coverage, service to all customers geographically located in the area and minimizing installation costs of the systems. In pursuit of this goal, the work presents the reduction of the optimization problem to the covering problem, the mathematical model construction, computational implementation and application in the form of simulations and results. The methodology applied to the computing system like a simulation, allows an very fast and dynamic analysis of the network topologies to be designed for use in projects where communication networks are used in centralized measurement systems. The computing system allows modification of simulation features and characteristics of networks, depending on the constraints imposed by the geographical area under consideration. The strategy presents good results in the formation of network topologies communication systems for centralized measurement and optimizing the use of equipment, reducing installation costs in the network.

Στην παρούσα μεταπτυχιακή εργασία περιγράφεται η διαδικασία συνδυασμού προβλημάτων Επιχειρησιακής Έρευνας με την μεθοδολογία εύρεσης συγκριτικής αποδοτικότητας (DEA). Αρχικά, παρουσιάζεται μια γενική περιγραφή της μεθόδου DEA και μια συνοπτική επισκόπηση της σχετικής βιβλιογραφίας. Παρουσιάζεται ο τρόπος συνδυασμού της μεθόδου DEA και δύο κλασσικών μοντέλων χωροθέτησης εγκαταστάσεων, του μοντέλου με περιορισμό και του αντίστοιχου μοντέλου χωρίς περιορισμό στην χωρητικότητα. Για την επίτευξη αυτού του στόχου γίνονται οι απαραίτητοι χειρισμοί στην μέθοδο DEA ούτως ώστε να μπορεί να υπολογίζεται η αποδοτικότητα για όλες τις μονάδες λήψης απόφασης ταυτόχρονα – μέθοδος ταυτόχρονης DEA (Simultaneous DEA), εφόσον το κλασσικό μοντέλο βρίσκει την αποδοτικότητα μιας μονάδας λύνοντας μια φορά το γραμμικό πρόβλημα με τους συντελεστές βαρύτητας αυτής της μονάδας. Η λύση του πολυκριτήριου προβλήματος αναδεικνύει την αλληλεπίδραση μεταξύ κόστους και αποδοτικότητας, για τη λήψη απόφασης ανάλογα με τις ανάγκες που μπορεί ενυπάρχουν σε ένα αντίστοιχο πραγματικό πρόβλημα. Στην συνέχεια αναπτύσσεται για πρώτη φορά στη διεθνή βιβλιογραφία μια μεθοδολογία για το συνδυασμό δύο άλλων βασικών προβλημάτων, της κάλυψης και της σύμπτυξης συνόλου, αντίστοιχα, με την μεθοδολογία DEA. Στόχος είναι να μορφοποιηθεί ένα μοντέλο γραμμικού προγραμματισμού έτσι ώστε εκτός από το μέτρο απόφασης του κόστους για την κάλυψη ή σύμπτυξη ενός συνόλου-στόχου, από διαθέσιμα υποσύνολα να ληφθεί υπόψη και η αποδοτικότητα του εκάστοτε υποσυνόλου, η οποία εν τέλει θα επηρεάσει και την συνολική αποδοτικότητα του συνόλου-στόχου. Γίνεται ο συνδυασμός των μεθοδολογιών και αναπτύσσονται μεθοδολογίες πολυκριτήριας ανάλυσης που μπορούν να χρησιμοποιηθούν για την λήψη αποφάσεων που αφορούν την αποδοτική και οικονομική κάλυψη ή σύμπτυξη ενός συνόλου. Για την πιστοποίηση και τη διαπίστωση της λειτουργικότητας των προτεινόμενων μεθοδολογιών αναπτύσσονται παραδείγματα προβλημάτων, τα οποία και επιλύονται επιτυχώς. / In the present thesis, the combination of Operation Research Problems with the Data Envelopment Analysis (DEA) is performed in order to make optimal and efficient decisions. Firstly, a general description of DEA and a breath literature review is presented. Then, we show and test location modeling formulations that utilize data envelopment analysis (DEA) efficiency measures to find optimal and efficient facility location/allocation patterns. In addition, to the authors’ best knowledge, the combinations of DEA with the Set Covering Problem as well as Set Packing Problem are formulated as multiobjective problems, for first time in the literature. The main aim of the proposed models is to make cost-effective and efficient decisions regarding the Set Covering and Packing Problem, respectively. Numerical examples are developed in order to validate and test the novel models. The numerical results of multiobjective analysis demonstrate that the proposed methods are able to successfully find optimal and efficient solutions for real set covering, packing and partitioning problems.

We meet with solving of optimization problems every day, when we try to do our tasks in the best way. An Ant Colony Optimization is an algorithm inspired by behavior of ants seeking a source of food. The Ant Colony Optimization is successfuly using on optimization tasks, on which is not possible to use a classical optimization methods. A Genetic Algorithm is inspired by transmision of a genetic information during crossover. The Genetic Algorithm is used for solving optimization tasks like the ACO algorithm. The result of my master's thesis is created simulator for solving choosen optimization tasks by the ACO algorithm and the Genetic Algorithm and a comparison of gained results on implemented tasks.