Theses and Dissertations from UMD
Permanent URI for this communityhttp://hdl.handle.net/1903/2
New submissions to the thesis/dissertation collections are added automatically as they are received from the Graduate School. Currently, the Graduate School deposits all theses and dissertations from a given semester after the official graduation date. This means that there may be up to a 4 month delay in the appearance of a give thesis/dissertation in DRUM
More information is available at Theses and Dissertations at University of Maryland Libraries.
Browse
4 results
Search Results
Item Solving continuous replenishment inventory routing problems(2008-08-22) Fomundam, Samuel; Herrmann, Jeffrey; Mechanical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)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 resupply the PODs continuously from a central depot that has a stockpile of medication. Each vehicle will repeatedly follow the same route and will deliver at each POD enough medication to replace what was consumed since the last visit. Because the number of drivers and trucks may be limited during an emergency, we wish to minimize the number of vehicles used to resupply the PODs. This thesis presents heuristics and a branch-and-bound approach for solving this NP-hard problem and evaluates their performance. We also analyze a special case in which all of the PODs have the same demand.Item STRUCTURAL SYNTHESIS AND ANALYSIS OF PLANAR AND SPATIAL MECHANISMS SATISFYING GRUEBLER'S DEGREES OF FREEDOM EQUATION(2006-11-27) Sunkari, Rajesh Pavan; Schmidt, Linda C; Mechanical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Design of mechanisms is an important branch of the theory of mechanical design. Kinematic structural studies play an important role in the design of mechanisms. These studies consider only the interconnectivity pattern of the individual links and hence, these studies are unaffected by the changes in the geometric properties of the mechanisms. The three classical problems in this area and the focus of this work are: synthesis of all non-isomorphic kinematic mechanisms; detection of all non-isomorphic pairs of mechanisms; and, classification of kinematic mechanisms based on type of mobility. Also, one of the important steps in the synthesis of kinematic mechanisms is the elimination of degenerate or rigid mechanisms. The computational complexity of these problems increases exponentially as the number of links in a mechanism increases. There is a need for efficient algorithms for solving these classical problems. This dissertation illustrates the successful use of techniques from graph theory and combinatorial optimization to solve structural kinematic problems. An efficient algorithm is developed to synthesize all non-isomorphic planar kinematic mechanisms by adapting a McKay-type graph generation algorithm in combination with a degeneracy testing algorithm. This synthesis algorithm is about 13 times faster than the most recent synthesis algorithm reported in the literature. There exist efficient approaches for detection of non-isomorphic mechanisms based on eigenvalues and eigenvectors of the adjacency or related matrices. However these approaches may fail to detect all cases. The reliability of these approaches is established in this work. It is shown, for the first time, that if the number of links is less than 15, the eigenvector approach detects all non-isomorphic mechanisms. A matrix is also proposed whose characteristic polynomial detects non-isomorphic mechanisms with a higher reliability than the adjacency or Laplace matrix. An erroneous assumption often found in structural studies is that the graph of a planar kinematic chain is a planar graph. It is shown that all the existing algorithms for degeneracy testing and mobility type identification, except those by Lee and Yoon, have this error. Further, Lee and Yoon's algorithms are heuristic in nature and were not rigorously proved. Several structural results and implicit assumptions for planar kinematic chains are proved in this work without relying on the erroneous assumption. These new results provide the mathematical justification for Lee and Yoon's algorithms, thereby validating the adoption of the Lee and Yoon's algorithms for practical applications. A polynomial-time algorithm based on combinatorial optimization techniques is proposed for degeneracy testing. This polynomial-time algorithm is the first degeneracy testing algorithm that works for both planar and spatial kinematic mechanisms with different types of joints.Item Resource Allocation in Networked and Distributed Environments(2006-08-30) Parthasarathy, Srinivasan; Srinivasan, Aravind; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)A central challenge in networked and distributed systems is resource management: how can we partition the available resources in the system across competing users, such that individual users are satisfied and certain system-wide objectives of interest are optimized? In this thesis, we deal with many such fundamental and practical resource allocation problems that arise in networked and distributed environments. We invoke two sophisticated paradigms -- linear programming and probabilistic methods -- and develop provably-good approximation algorithms for a diverse collection of applications. Our main contributions are as follows. Assignment problems: An assignment problem involves a collection of objects and locations, and a load value associated with each object-location pair. Our goal is to assign the objects to locations while minimizing various cost functions of the assignment. This setting models many applications in manufacturing, parallel processing, distributed storage, and wireless networks. We present a single algorithm for assignment which generalizes many classical assignment schemes known in the literature. Our scheme is derived through a fusion of linear algebra and randomization. In conjunction with other ideas, it leads to novel guarantees for multi-criteria parallel scheduling, broadcast scheduling, and social network modeling. Precedence constrained scheduling: We consider two precedence constrained scheduling problems, namely sweep scheduling and tree scheduling, which are inspired by emerging applications in high performance computing. Through a careful use of randomization, we devise the first approximation algorithms for these problems with near-optimal performance guarantees. Wireless communication: Wireless networks are prone to interference. This prohibits proximate network nodes from transmitting simultaneously, and introduces fundamental challenges in the design of wireless communication protocols. We develop fresh geometric insights for characterizing wireless interference. We combine our geometric analysis with linear programming and randomization, to derive near-optimal algorithms for latency minimization and throughput capacity estimation in wireless networks. In summary, the innovative use of linear programming and probabilistic techniques for resource allocation, and the novel ways of connecting them with application-specific ideas is the pivotal theme and the focal point of this thesis.Item Modeling and Solving Variants of the Vehicle Routing Problem: Algorithms, Test Problems, and Computational Results(2005-08-30) Li, Feiyue; Golden, Bruce; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In the standard version of the capacitated vehicle routing problem (VRP), a sequence of deliveries is generated for each vehicle in a homogeneous fleet based at a single depot so that all customers are serviced and the total distance traveled by the fleet is minimized. Each vehicle has a fixed capacity and must leave from and return to the depot. Each vehicle might have a route-length restriction that limits the maximum distance it can travel. Each customer has a known demand and is serviced by exactly one visit of a single vehicle. For more than 45 years, the standard VRP has attracted an enormous amount of attention in the operations research literature. There are many practical applications of vehicle routing in the distribution of products such as soft drinks, newspapers, groceries, and milk and in street sweeping, solid waste collection,and mail delivery. In this dissertation, we model and solve variants of the standard VRP. First, we focus on very large VRPs. We develop new, benchmark instances via a problem generator with as many as 1,200 customers along with estimated solutions. We also develop a simple, flexible, fast, and powerful heuristic solution procedure based on the record-to-record travel algorithm and apply our heuristic to the new problems and generate high-quality solutions very quickly. Next, we turn our focus to five interesting variants of the VRP that have received little attention in the literature but have practical application in the real world: (1) the time dependent traveling salesman problem (TDTSP), (2) the noisy traveling salesman problem (NTSP), (3) the heterogeneous vehicle routing problem (HVRP), (4) the open vehicle routing problem (OVRP), and (5) the landfill routing problem (LRP). For each variant, we develop an effective solution procedure and report computational results. In particular,we solve the TDTSP, HVRP, OVRP, and LRP with our record-to-record travel-based heuristic and generate high-quality results. For the NTSP, we develop a new procedure based on quad trees that outperforms existing solution methods. Finally, for the HVRP and the OVRP, we generate new test problems and solve each new problem using our record-to-record travel-based heuristic.