Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 201 for “"NP-hard problem"”.
-
Metaheurísticas evolutivas para o problema de roteamento de unidades móveis de pistoneio
… of Technical Vocabulary Building for solving the Problem of Optimizing the Use of Multiple Mobile Units Recovery of Oil (MRO units). Because it is an NP-hard problem, a mathematical model is formulated for the problem, allowing the construction of test instances that are used to validate the …
-
Load volume considerations in the collision free route planning of material handling devices in FMS
… AGVs to avoid collision is known to be an NP-Hard problem. In this research, we address the problem of optimal and efficient routing of AGVs through a guide path network.
-
Contiguous Conflict-free Link Scheduling for Efficient V2X Communication in the Next Generation of Wireless Networks
… scheduler. As an important resource management problem, minimizing the consumed resources by this scheduler in a conflict-free manner is NP-hard. Conflict-free scheduling assigns separate resources to the conflicting links and can enjoy from opportunistic resource reuse. In order to solve this …
-
Algorithms for vehicle routing problem with pickup and delivery
… thesis, we have considered the vehicle routing problem with pickup and delivery which is a generalization of the capacitated vehicle routing problem (CVRP). The vehicle routing problem with pickup and delivery (VRPPD) arises whenever pickup demand and delivery demand is to be satisfied by the …
-
Scheduling jobs on two uniform parallel machines to minimize the makespan
The problem of scheduling n independent jobs on m uniform parallel machines such that the total completion time is minimized is a NP-Hard problem. We propose several heuristic-based online algorithms for machines with different speeds called Q2||Cmax. To show the efficiency of the proposed online …
-
Deep Heuristic: A Heuristic for Message Broadcasting in Arbitrary Networks
… in an arbitrary network has been proved to be an NP-Hard problem. In this thesis, a new heuristic that generates broadcast schemes in arbitrary networks is presented, which has O(|E| + |V | log |V |) time complexity. Based on computer simulations of this heuristic in some commonly used topologies …
-
Approaches for solving some scheduling and routing problems
… for three difficult combinatorial optimisation problems.<br/>The supply ship travelling salesman problem is a simplification of a situation faced by a naval logistics coordinator who must direct a support vessel tasked with resupplying ships in a fleet. It is a generalisation of the travelling …
-
Randomized and Deterministic Parameterized Algorithms and Their Applications in Bioinformatics
Parameterized NP-hard problems are NP-hard problems that are associated with special variables called parameters. One example of the problem is to find simple paths of length k in a graph, where the integer k is the parameter. We call this problem the p-path problem. The p-path problem is the …
-
Crown Reductions and Decompositions: Theoretical Results and Practical Methods
<p>Two kernelization schemes for the vertex cover problem, an NP-hard problem in graph theory, are compared. The first, crown reduction, is based on the identification of a graph structure called a crown and is relatively new while the second, LP-kernelization has been used for some time. A proof …
-
Techniques for Proving Approximation Ratios in Scheduling
The problem of finding a schedule with the lowest makespan in the class of all flowtime-optimal schedules for parallel identical machines is an NP-hard problem. Several approximation algorithms have been suggested for this problem. We focus on algorithms that are fast and easy to implement, rather …
-
Using genetic algorithms for the single allocation hub location problem
Hub location problem is an NP-hard problem that frequently arises in the design of transportation and distribution systems, postal delivery networks, and airline passenger flow. This work focuses on the Single Allocation Hub Location Problem (SAHLP). Genetic Algorithms (GAs) for the capacitated and …
-
Heuristics for Message Broadcasting in Arbitrary Networks
… in an arbitrary network has been proved to be an NP-Hard problem. In this thesis, two new heuristics that generate broadcast schemes in arbitrary networks are presented. Both of them have O(|E|) time complexity. Moreover, in the broadcast schemes generated by the heuristics, each vertex in the …
-
Systematic parameterized complexity analysis in computational phonology
Many computational problems are NP-hard and hence probably do not have fast, i.e., polynomial time, algorithms. Such problems may yet have non-polynomial time algorithms, and the non-polynomial time complexities of these algorithm will be functions of particular aspects of that problem, i.e., the …
-
A STUDY ON QUANTUM ENTANGLEMENT
In this thesis, we focus on the problems of quantum entanglement, which is one of the most important phenomena in quantum physics. In particular, we study the quantum entanglement problem and the quantum distillation problem. Although the quantum entanglement problem is regarded as an NP-hard …
-
A Primal-Dual Framework for Approximation Algorithms using Semidefinite Programming
… design primal-dual approximation algorithms for NP-hard problems. The focus lies on the literature that followed the celebrated Goemans and Williamson approximation algorithm for the maximum cut problem, and thus on the use of semidefinite programming (SDP). We present a primal-dual conic …
-
Solving continuous replenishment inventory routing problems
This research investigates the problem of resupplying points of dispensing (PODs), which will dispense medications to millions of people in case of a bioterrorist attack such as anthrax. After receiving an initial but limited supply of medication, the PODs will operate continuously. Vehicles will …
-
Problem specific heuristics for group scheduling problems in cellular manufacturing
The group scheduling problem commonly arises in cellular manufacturing systems, where parts are grouped into part families. It is characterized by a sequencing task on two levels: on the one hand, a sequence of jobs within each part family has to be identified while, on the other hand, a family …
-
A heuristic for broadcasting in arbitrary networks
… schedule in an arbitrary network is an NP-hard problem. Many papers have been published on the topic of finding an efficient and effective heuristic for broadcasting. In this thesis, a heuristic algorithm for broadcasting in arbitrary networks is presented. This heuristic is first tested …
-
Enhancing FPGA Placement Quality via Machine Learning
… design flow. However, placement is an NP-hard problem and time-consuming, therefore attempting to solve it results in poor solutions. To address these issues, machine learning models were developed and integrated into GPlace3.0, an FPGA placer. A convolutional encoder-decoder model for …
-
Optimization and learning algorithms for orthogonal frequency division multiplexing-based dynamic spectrum access.
… propose two evolutionary algorithms to solve the problem with lower complexity. For systems with frequency reuse, we propose a framework that converts the NP-hard problem into a mixed binary linear programming problem without making any approximations. In the second part of the thesis, learning …
Page 1 of 11