• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 64
  • 29
  • 16
  • 10
  • 8
  • 2
  • 2
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • Tagged with
  • 158
  • 158
  • 148
  • 49
  • 29
  • 28
  • 26
  • 23
  • 23
  • 22
  • 20
  • 19
  • 18
  • 18
  • 16
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
121

Introdução aos grafos no ensino médio / Introduction to graphs in high school

Fonte, Carla Cristina, 1990- 12 December 2014 (has links)
Orientador: Pedro José Catuogno / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-26T10:58:39Z (GMT). No. of bitstreams: 1 Fonte_CarlaCristina_M.pdf: 29679078 bytes, checksum: 0009a52938b1cb16c79bdc47af10d323 (MD5) Previous issue date: 2014 / Resumo: Neste trabalho, exploram-se os conceitos iniciais e aplicações importantes da teoria de grafos. Acentuam-se, nas aplicações, alguns problemas clássicos, como o das sete pontes de Königsberg, o do caixeiro viajante e o problema dos casamentos estáveis. Com o intuito de servir como material de apoio para a introdução de grafos ao ensino médio, expõe-se uma sugestão para plano de aula, cuja exploração sinaliza diversas propriedades matemáticas interessantes, além de estimular o raciocínio e o estudo / Abstract: This work focuses on the initial concepts and important applications of the graph theory. Detailing, in the applications, some classic problems such as the seven bridges of Königsberg problem, the travelling salesman problem and the stable marriage problem. In order to provide a supporting material for the introduction to graphs in high school, it is shown a suggestion to the lesson plan, which exploration indicates various interesting mathematical properties beyond stimulating the reasoning and the deep study in the field / Mestrado / Matemática em Rede Nacional / Mestra em Matemática em Rede Nacional
122

Uso de meta-aprendizado na recomendação de meta-heurísticas para o problema do caixeiro viajante / Using meta-learning on the recommendation of meta-heuristics for the traveling salesman problem

Jorge Yoshio Kanda 07 December 2012 (has links)
O problema do caixeiro viajante (PCV) é um problema clássico de otimização que possui diversas variações, aplicações e instâncias. Encontrar a solução ótima para muitas instâncias desse problema é geralmente muito difícil devido o alto custo computacional. Vários métodos de otimização, conhecidos como meta-heurísticas (MHs), são capazes de encontrar boas soluções para o PCV. Muitos algoritmos baseados em diversas MHs têm sido propostos e investigados para diferentes variações do PCV. Como não existe um algoritmo universal que encontre a melhor solução para todas as instâncias de um problema, diferentes MHs podem prover a melhor solução para diferentes instâncias do PCV. Desse modo, a seleção a priori da MH que produza a melhor solução para uma dada instância é uma tarefa difícil. A pesquisa desenvolvida nesta tese investiga o uso de abordagens de meta-aprendizado para selecionar as MHs mais promissoras para novas instâncias de PCV. Essas abordagens induzem meta-modelos preditivos a partir do treinamento das técnicas de aprendizado de máquina em um conjunto de meta-dados. Cada meta-exemplo, em nosso conjunto de meta-dados, representa uma instância de PCV descrita por características (meta-atributos) do PCV e pelo desempenho das MHs (meta-atributo alvo) para essa instância. Os meta-modelos induzidos são usados para indicar os valores do meta-atributo alvo para novas instâncias do PCV. Vários experimentos foram realizados durante a investigação desta pesquisa e resultados importantes foram obtidos / The traveling salesman problem (TSP) is a classical optimization problem that has several variations, applications and instances. To find the optimal solution for many instances of this problem is usually a very hard task due to high computational cost. Various optimization methods, known as metaheuristics (MHs), are capable to generate good solutions for the TSP. Many algorithms based on different MHs have been proposed and investigated for different variations of the TSP. Different MHs can provide the best optimization solution for different TSP instances, since there is no a universal algorithm able to find the best solution for all instances. Thus, a priori selection of the MH that produces the best solution for a given instance is a hard task. The research developed in this thesis investigates the use of meta-learning approaches to select the most promising MHs for new TSP instances. These approaches induce predictive meta-models from the training of machine learning techniques on a set of meta-data. In our meta-data, each meta-example is a TSP instance described by problem characteristics (meta-features) and performance of MHs (target meta-features) for this instance. The induced meta-models are used to indicate the values of the target meta-feature for new TSP instances. During the investigation of this research, several experiments were performed and important results were obtained
123

Objeto de aprendizagem para o ensino de algoritmos solucionadores de problemas de otimização em redes

Lourenço, Wilson Da Silva 26 February 2015 (has links)
Submitted by Nadir Basilio (nadirsb@uninove.br) on 2015-07-17T15:18:49Z No. of bitstreams: 1 Wilson da Silva Lourenco.pdf: 1321079 bytes, checksum: ea090b0df77d0c04ef1dde30e7b41558 (MD5) / Made available in DSpace on 2015-07-17T15:18:49Z (GMT). No. of bitstreams: 1 Wilson da Silva Lourenco.pdf: 1321079 bytes, checksum: ea090b0df77d0c04ef1dde30e7b41558 (MD5) Previous issue date: 2015-02-26 / The network optimization problems (NOP) are common to several areas such as engineering, transport and telecommunications, and have been objects of intense research and studies. Among the classical NOP are the problems of Shortest Path (SPP), Max Flow (MFP) and Traveling Salesman (TSP), which are usually studied in undergraduate and graduate courses such as Industrial Engineering, Computer Science, Information Systems and Logistics, with the use of resources such as chalk and blackboard that hinder the teacher's work, in the sense of showing the functioning of algorithms that solve these problems while maintaining students' motivation for learning. In this context, it is proposed in this research, a computational tool, characterized as a Learning Object (OA) and called TASNOP - Teaching Algorithms for Solving Network Optimization Problems, whose purpose is to contribute to students' understanding about concepts from NOP and, mainly, the functioning of algorithms A*, Greedy Search and Dijkstra used for resolution of SPP, Ford-Fulkerson employed in the resolution of MFP and the Nearest Neighbor to solve the TSP. It is important to highlight that the proposed OA can be accessed through web and also employed in distance learning environments (DLE). Experiments conducted in 2014 with 129 students of Computer Science, from which 51 performed an exercise using the TASNOP and 78 without this tool, confirm that students who used the TASNOP performed better in solving the proposed exercise, corroborating the idea that the OA helped to improve their understanding about the algorithms discussed in this research. In addition, the 51 students who employed the TASNOP answered a questionnaire about it use and, the answers indicated that the TASNOP shows a potential to be used as a learning support tool. / Os problemas de otimização em redes (POR) são comuns a diversas áreas como engenharia, transportes e telecomunicações, e têm sido objetos de intensas pesquisas e estudos. Entre os POR clássicos estão os problemas de Caminho Mínimo (PCM), Fluxo Máximo (PFM) e Caixeiro Viajante (PCV), os quais normalmente são estudados em cursos de graduação e pós-graduação tais como Engenharia de Produção, Ciência da Computação, Sistemas de Informação e Logística, com a utilização de recursos como giz e lousa, o que dificulta o trabalho do professor, no sentido de mostrar o funcionamento dos algoritmos que solucionam esses problemas, mantendo a motivação dos alunos para a aprendizagem. Neste contexto, propõe-se nesta pesquisa, uma ferramenta computacional, caracterizada como um Objeto de Aprendizagem (OA) denominado TASNOP - Teaching Algorithms for Solving Network Optimization Problems, cuja finalidade é contribuir para compreensão dos alunos sobre conceitos de POR e, principalmente, sobre o funcionamento dos algoritmos A*, Busca Gulosa, e Dijkstra, usados para resolução do PCM, Ford-Fulkerson empregado na resolução de PFM e o algoritmo Vizinho mais Próximo para resolução do PCV. É importante ressaltar que o OA proposto pode ser acessado via web e, inclusive, ser acoplado em ambientes de ensino a distância (EaD). Experimentos realizados no ano de 2014 envolvendo 129 alunos do curso de Ciência da Computação, dos quais 51 resolveram um exercício com o uso do TASNOP e 78 sem o seu uso, permitiram verificar que os alunos que utilizaram o TASNOP obtiveram melhor desempenho na resolução do exercício proposto, corroborando a ideia de que o OA contribuiu para melhorar suas compreensões acerca dos algoritmos abordados nesta pesquisa. Em adição, os 51 alunos que usaram o TASNOP responderam a um questionário sobre o seu uso e, com base nessas respostas, ficou evidente o potencial do TASNOP como uma ferramenta de apoio ao ensino.
124

Modelování rizik výrobních procesů / Risk modelling for production processes

Ftáčnik, Peter January 2016 (has links)
The processes and procedures covered the main core of the professional operations in the manufacturing plant. The enterprise should focus on the efficient running of the main processes and risks associated with these procedures. My thesis deals with the risk analysis of selected manufacturing processes particular company from qualitative and quantitative point of view. First, the results are presented from qualitative risk analysis, especially in scope of failures of the machines or in the sequences of production. Second part focus on the problems of optimization sequence batches that the total time required for pre-setting of machines between doses should be minimal. The thesis also takes random waiting period into the consideration and applies wait-and-see approach of stochaistic programming applied in task traveling salesman. Calculations are processed by the GAMS. The results from the GAMS are refered in MS Excel, they are further discussed and interpreted by using descriptive statistics.
125

From Parameter Tuning to Dynamic Heuristic Selection

Semendiak, Yevhenii 18 June 2020 (has links)
The importance of balance between exploration and exploitation plays a crucial role while solving combinatorial optimization problems. This balance is reached by two general techniques: by using an appropriate problem solver and by setting its proper parameters. Both problems were widely studied in the past and the research process continues up until now. The latest studies in the field of automated machine learning propose merging both problems, solving them at design time, and later strengthening the results at runtime. To the best of our knowledge, the generalized approach for solving the parameter setting problem in heuristic solvers has not yet been proposed. Therefore, the concept of merging heuristic selection and parameter control have not been introduced. In this thesis, we propose an approach for generic parameter control in meta-heuristics by means of reinforcement learning (RL). Making a step further, we suggest a technique for merging the heuristic selection and parameter control problems and solving them at runtime using RL-based hyper-heuristic. The evaluation of the proposed parameter control technique on a symmetric traveling salesman problem (TSP) revealed its applicability by reaching the performance of tuned in online and used in isolation underlying meta-heuristic. Our approach provides the results on par with the best underlying heuristics with tuned parameters.:1 Introduction 1 1.1 Motivation 1 1.2 Research objective 2 1.3 Solution overview 2 2 Background and RelatedWork Analysis 3 2.1 Optimization Problems and their Solvers 3 2.2 Heuristic Solvers for Optimization Problems 9 2.3 Setting Algorithm Parameters 19 2.4 Combined Algorithm Selection and Hyper-Parameter Tuning Problem 27 2.5 Conclusion on Background and Related Work Analysis 28 3 Online Selection Hyper-Heuristic with Generic Parameter Control 31 3.1 Combined Parameter Control and Algorithm Selection Problem 31 3.2 Search Space Structure 32 3.3 Parameter Prediction Process 34 3.4 Low-Level Heuristics 35 3.5 Conclusion of Concept 36 4 Implementation Details 37 4.2 Search Space 40 4.3 Prediction Process 43 4.4 Low Level Heuristics 48 4.5 Conclusion 52 5 Evaluation 55 5.1 Optimization Problem 55 5.2 Environment Setup 56 5.3 Meta-heuristics Tuning 56 5.4 Concept Evaluation 60 5.5 Analysis of HH-PC Settings 74 5.6 Conclusion 79 6 Conclusion 81 7 FutureWork 83 7.1 Prediction Process 83 7.2 Search Space 84 7.3 Evaluations and Benchmarks 84 Bibliography 87 A Evaluation Results 99 A.1 Results in Figures 99 A.2 Results in numbers 105
126

Development of Optimization and Simulation Models for the Analysis of Airfield Operations

Baik, Hojong 12 July 2000 (has links)
This research is concerned with the modeling and development of algorithmic approaches for solving airport operational problems that arise in Air Traffic Control (ATC) systems within the terminal area at hub airports. Specifically, the problems addressed include the Aircraft Sequencing Problem (ASP) for runway operations, the Network Assignment Problem (NAP) for taxiway operations, and a simulation model for the evaluation of current or proposed ATC system in detail. For the ASP, we develop a mathematical model and apply the Reformulation-Linearization-Technique (RLT) of Sherali and Adams to construct an enhanced tightened version of the proposed model. Since ASP is NP-Hard and in fact, it is a variation of the well-known Traveling Salesman Problem with time-windows, sub-optimal solutions are usually derived to accommodate the real-time constraints of ATC systems. Nevertheless, we exhibit a significant advancement in this challenging class of problem. Also for the purpose of solving relatively large sized problems in practice, we develop and test suitable heuristic procedures. For the NAP, we propose a quasi-dynamic assignment scheme which is based on the incremental assignment technique. This quasi-dynamic assignment method assumes that the current aircraft route is influenced only by the previous aircraft assigned to the network. This simplified assumption obviates the need for iterative rerouting procedures to reach a pure equilibrium state which might not be achievable in practical taxiway operations. To evaluate the overall system, we develop a microscopic simulation model. The simulation model is designed to have the capability for reproducing not only the dynamic behavior of aircraft, but also incorporates communication activities between controllers and pilots. These activities are critical in ATC operations, and in some instances, might limit the capacity of the facility. Finally, using the developed simulation model named Virginia Tech Airport Simulation Model (VTASM) in concert with ASP and NAP, we compare the overall efficiencies of several control strategies, including that of the existing control system as well as of the proposed advanced control system. / Ph. D.
127

Shop-Scheduling Problems with Transportation

Knust, Sigrid 26 September 2000 (has links)
In this thesis scheduling problems with transportation aspects are studied. Classical scheduling models for problems with multiple operations are the so-called shop-scheduling models. In these models jobs consisting of different operations have to be planned on certain machines in such a way that a given objective function is minimized. Each machine may process at most one operation at a time and operations belonging to the same job cannot be processed simultaneously. We generalize these classical shop-scheduling problems by assuming that the jobs additionally have to be transported between the machines. This transportation has to be done by robots which can handle at most one job at a time. Besides transportation times which occur for the jobs during their transport, also empty moving times are considered which arise when a robot moves empty from one machine to another. Two types of problems are distinguished: on the one hand, problems without transportation conflicts (i.e. each transportation can be performed without delay), and on the other hand, problems where transportation conflicts may arise due to a limited capacity of transport robots. In the first part of this thesis several new complexity results are derived for flow-shop problems with a single robot. Since very special cases of these problems are already NP-hard, in the second part of this thesis some techniques are developed for dealing with these hard problems in practice. We concentrate on the job-shop problem with a single robot and the makespan objective. At first we study the subproblem which arises for the robot when some scheduling decisions for the machines have already been made. The resulting single-machine problem can be regarded as a generalization of the traveling salesman problem with time windows where additionally minimal time-lags between certain jobs have to be respected and the makespan has to be minimized. For this single-machine problem we adapt immediate selection techniques used for other scheduling problems and calculate lower bounds based on linear programming and the technique of column generation. On the other hand, to determine upper bounds for the single-machine problem we develop an efficient local search algorithm which finds good solutions in reasonable time. This algorithm is integrated into a local search algorithm for the job-shop problem with a single robot. Finally, the proposed algorithms are tested on different test data and computational results are presented.
128

Velocity Control of a Mobile Charger in a Wireless Rechargeable Sensor Network / Hastighetsreglering av en Mobil Laddare i ett Trådlöst Laddningsbart Sensornätverk

Haltorp, Emilia January 2023 (has links)
Wireless sensor networks (WSN) are one of the most rapidly evolving technical areas right now. They can be used in a lot of different applications, environmental monitoring and health applications being two examples. The sensors can be placed in hazardous and remote environments since there is no need for cabling or manual maintenance. One of the biggest problems and constraints of today's WSNs is the limited energy capacity of the sensor nodes. Eventually they will be power-depleted, and the network will be dead. A solution to this can be wireless energy transfer technology which makes it possible to recharge sensor nodes with the help of a mobile charger and prolong the lifetime of networks.  This thesis aims to investigate how the charging completion time can be reduced by considering that the charger can charge while moving and by controlling its velocity. The charging completion time is the time from when the charger starts charging the first node until it returns to that starting point.  For this, a two-dimensional WSN was defined that contains sensor nodes and a mobile charger. Anchor nodes, which the charger travels between were defined by choosing the nodes with most neighbors within a defined charging radius. The traveling salesman problem were used to find a path that the charger travels along. A simulation environment was developed in Python to execute tests.  The results show that the charging while moving approach with controlled velocity could reduce the charging completion time with up to 20%. It was also ascertained that this approach works better in dense networks than in sparse. / Trådlösa sensornätverk är ett av de snabbast växande tekniska områdena just nu. De har många olika användningsområden, miljöövervakning och olika hälsotillämpningar är två exempel. Sensorerna kan placeras i farliga och avlägsna miljöer eftersom det inte finns något behov av kablar eller manuellt underhåll. Ett av de största problemen och begränsningarna på dagens trådlösa nätverk är den begränsade energikapaciteten hos sensornoderna. Slutligen kommer de att bli tömda på ström och nätverket kommer att dö. En lösning på detta kan vara trådlös strömöverföring vilket gör det möjligt att ladda sensorerna med hjälp av en mobil laddare och därmed förlänga livstiden på nätverket.  Syftet med detta examensarbete är att undersöka hur slutförandetiden för laddningen kan reduceras i betraktande av att laddaren kan ladda när den rör sig samt att reglera laddaren hastighet. Slutförandetiden för laddningen är den tid det tar från att laddaren börjar ladda den första sensor-noden tills att den kommer tillbaka till punkten den startade på.  För att göra detta definierades ett två-dimensionellt trådlöst sensornätverk som bestod av sensornoder och en mobil laddare. Ankarnoder, vilka laddaren rörde sig emellan, definierades genom att hitta de noder med flest antal grannar inom en bestämd laddningsradie. Handelsresandeproblemet användes för att bestämma rutten som laddaren färdas längs. En simuleringsmiljö utvecklades i Python för att utföra testerna i.  Resultaten visar att med laddaren som laddade när den rörde på sig samt hade reglerad hastighet kunde slutförande-tiden för laddning reduceras med upp till 20%. Det kunde även konstateras att detta tillvägagångssätt fungerar bättre i täta nätverk än i glesa.
129

Modeling, Analysis and Solution Approaches for Some Optimization Problems: High Multiplicity Asymmetric Traveling Salesman, Primary Pharmaceutical Manufacturing Scheduling, and Lot Streaming in an Assembly System

Yao, Liming 10 July 2008 (has links)
This dissertation is devoted to the modeling, analysis and development of solution approaches for some optimization-related problems encountered in industrial and manufacturing settings. We begin by introducing a special type of traveling salesman problem called "High Multiplicity Asymmetric Traveling Salesman Problem" (HMATSP). We propose a new formulation for this problem, which embraces a flow-based subtour elimination structure, and establish its validity for this problem. The model is, then, incorporated as a substructure in our formulation for a lot-sizing problem involving parallel machines and sequence-dependent setup costs, also known as the "Chesapeake Problem". Computational results are presented to demonstrate the efficacy of our modeling approach for both the generic HMATSP and its application within the context of the Chesapeake Problem. Next, we investigate an integrated lot-sizing and scheduling problem that is encountered in the primary manufacturing facility of pharmaceutical manufacturing. This problem entails determination of production lot sizes of multiple products and sequence in which to process the products on machines, which can process lots (batches) of a fixed size (due to limited capacity of containers) in the presence of sequence-dependent setup times/costs. We approach this problem via a two-stage optimization procedure. The lot-sizing decision is considered at stage 1 followed by the sequencing of production lots at stage 2. Our aim for the stage 1 problem is to allocate batches of products to time-periods in order to minimize the sum of the inventory and backordering costs subject to the available capacity in each period. The consideration of batches of final products, in addition to those for intermediate products, which comprise a final product, further complicates the lot-sizing problem. The objective for the stage 2 problem is to minimize sequence-dependent setup costs. We present a novel unifying model and a column generation-based optimization approach for this class of lot-sizing and sequencing problems. Computational experience is first provided by using randomly generated data sets to test the performances of several variants of our proposed approach. The efficacy of the best of these variants is further demonstrated by applying it to the real-life data collected with the collaboration of a pharmaceutical manufacturing company. Then, we address a single-lot, lot streaming problem for a two-stage assembly system. This assembly system is different from the traditional flow shop configuration. It consists of m parallel subassembly machines at stage 1, each of which is devoted to the production of a component. A single assembly machine at stage 2, then, assembles products after components (one each from the subassembly machines at the first stage) have been completed. Lot-detached setups are encountered on the machines at the first and second stages. Given a fixed number of transfer batches (or sublots) from each of the subassembly machines at stage 1 to the assembly machine at stage 2, our problem is to find sublot sizes so as to minimize the makespan. We develop optimality conditions to determine sublot sizes for the general problem, and present polynomial-time algorithms to determine optimal sublot sizes for the assembly system with two and three subassembly machines at stage 1. Finally, we extend the above single-lot, lot streaming problem for the two-stage assembly system to multiple lots, but still, for the objective of minimizing the makespan. Due to the presence of multiple lots, we need to address the issue of the sequencing of the lots along with lot-splitting, a fact which adds complexity to the problem. Some results derived for the single-lot version of this problem have successfully been generalized for this case. We develop a branch-and-bound-based methodology for this problem. It relies on effective lower bounds and dominance properties, which are also derived. Finally, we present results of computational experimentation to demonstrate the effectiveness of our branch-and-bound-based methodology. Because of the tightness of our upper and lower bounds, a vast majority of the problems can be solved to optimality at root node itself, while for others, the average gap between the upper and lower bounds computed at node zero is within 0.0001%. For a majority of these problems, our dominance properties, then, effectively truncate the branch-and-bound tree, and obtain optimal solution within 500 seconds. / Ph. D.
130

Land Leveling Using Optimal Earthmoving Vehicle Routing

McInvale, Howard D. 30 April 2002 (has links)
This thesis presents new solution approaches for land leveling, using optimal earthmoving vehicle routing. It addresses the Shortest Route Cut and Fill Problem (SRCFP) developed by Henderson, Vaughan, Wakefield and Jacobson [2000]. The SRCFP is a discrete optimization search problem, proven to be NP-hard. The SRCFP describes the process of reshaping terrain through a series of cuts and fills. This process is commonly done when leveling land for building homes, parking lots, etc. The model used to represent this natural system is a variation of the Traveling Salesman Problem. The model is designed to limit the time needed to operate expensive, earthmoving vehicles. The model finds a vehicle route that minimizes the total time required to travel between cut and fill locations while leveling the site. An optimal route is a route requiring the least amount of travel time for an individual earthmoving vehicle. This research addresses the SRCFP by evaluating minimum function values across an unknown response surface. The result is a cost estimating strategy that provides construction planners a strategy for contouring terrain as cheaply as possible. Other applications of this research include rapid runway repair, and robotic vehicle routing. / Master of Science

Page generated in 0.0954 seconds