Institute for Systems Research Technical Reports

Permanent URI for this collectionhttp://hdl.handle.net/1903/4376

This archive contains a collection of reports generated by the faculty and students of the Institute for Systems Research (ISR), a permanent, interdisciplinary research unit in the A. James Clark School of Engineering at the University of Maryland. ISR-based projects are conducted through partnerships with industry and government, bringing together faculty and students from multiple academic departments and colleges across the university.

Browse

Author: search.filters.author.Ball, Michael O.Subject: search.filters.subject.algorithms

Search Results

Now showing 1 - 7 of 7
  • Thumbnail Image
    Item
    Integrating Tradeoff Analysis and Plan-Based Evaluation of Designs for Microwave Modules
    (1996) Trichur, Vinai S.; Ball, Michael O.; Baras, John S.; Hebbar, Kiran; Minis, Ioannis; Nau, Dana S.; Smith, Stephen J.J.; ISR
    Previously, we have described two systems, EDAPS and EXTRA, which support design and process planning for the manufacture of microwave modules, complex devices with both electrical and mechanical attributes. EDAPS integrates electrical design, mechanical design, and process planning for both mechanical and electrical domains. EXTRA accesses various component and process databases to help the user define design and process options. It then supports the user in choosing among these options with an optimization bases tradeoff analysis module.

    In this paper, we describe our current work towards the integration and enhancement of the capabilities of EDAPS and EXTRA. We integrate EXTRA's functionality with the initial design step of EDAPS. in the resultant system, the user, supported by an enhanced tradeoff analysis capability, can select and describe a promising preliminary design and process plan based on the analysis of a variety of alternatives from both an electrical and mechanical perspective. This preliminary design is then subjected top further analysis and refinement using existing EDAPS capabilities. In addition to the integration of these two systems, specific new functions have been developed, including tradeoff analysis over a much broader set of criteria, and the ability of the tradeoff module to query the process planner to determine costs of individual options.

  • Thumbnail Image
    Item
    Two-Path Subsets: Efficient Counting and Applications to Performability Analysis
    (1996) Ball, Michael O.; Hagstrom, Jane N.; Provan, J. Scott; ISR
    The problem of computing preformability probabilities in stochastic PERT and flow networks is studied when the networks is ﲭinimally designed to withstand any two component failures. Polynomial-time algorithms to compute preformability when the network is planar -- the nonplanar versions being NP-hard -- solve related ﲴwo-path subset problems. Given an acyclic graph with weights on the arcs, the algorithms compute the total weight of all subsets of arcs that are contained in (1) two source-sink paths or (2) two arc-disjoint source-sink paths. A polynomial algorithm is given for (1), and for (2) in the case where the graph is a source-sink planar k-flow graph, that is edge-minimal with respect to supporting k units of flow.
  • Thumbnail Image
    Item
    Call Rerouting in an ATM Environment
    (1995) Ball, Michael O.; Vakhutinsky, A.; ISR; CSHCN
    ATM networks must handle multiclass traffic with diverse quality of service requirements. We consider a multiclass routing model in which routes are calculated in a distributed fashion by the call origination nodes. Within this general context, we address the problem of rerouting a set of previously routed calls to avoid a failed link. Under the approach we propose, a single node executes an aggregate global rerouting of all affected calls and then converts the set of aggregate routes into an allocation of bandwidth on each link to call origination nodes for the purpose of rerouting. The bandwidth allocation is distributed to each origination node, which in turn then calculates routes for the individual calls. The problem faced by each call origination node is a variant of the so-called bandwidth packing problem. We develop and analyze an approximate algorithm for solving the problem in the specific context that arises in our setting.
  • Thumbnail Image
    Item
    On the Selection of Parts and Processes during Design of Printed Circuit Board Assemblies
    (1995) Ball, Michael O.; Baras, John S.; Bashyam, Sridhar; Karne, Ramesh K.; Trichur, Vinai S.; ISR
    We consider a multiobjective optimization model that determines components and processes for given conceptual designs of printed circuit board assemblies. Specifically, out model outputs a set of solutions that are Pareto optimal with respect to a cost and a quality metric. The discussion here broadly outlines an integer programming based solution strategy, and represents in-progress work being carried out in collaboration with a manufacturing firm.
  • Thumbnail Image
    Item
    Building Decision Support Systems That Use Operations Research Models as Database Applications
    (1992) Ball, Michael O.; Datta, Anindya; Dahl, Roy; ISR
    In this paper we address the problem of building decision support systems that make use of multiple operations research models as database application. The motivation for developing applications in a database environment is that, by doing so, the development effort can be substantially reduced, while, at the same time, the application inherits valuable database features. the paper contains two main contributions. First, we present a set of modeling constructs that should aid developers in structuring such applications and in carrying out the development process. Included in this material is a fairly comprehensive model for handling versions. Second, we discuss certain design alternatives and evaluate performance tradeoffs associated with hem. In addition, to evaluating the differences among competing database designs, we provide evidence that properly designed database applications, show little performance degradation over file based applications.
  • Thumbnail Image
    Item
    Network Reliability
    (1992) Ball, Michael O.; Colbourn, Charles J.; Provan, J.S.; ISR
    This paper provides a detailed review of the state of the art in the field of network reliability analysis. The primary model treated is a stochastic network in which arcs fail randomly and independently with known failure probabilities. The inputs to the basic network reliability analysis problem consist of the network and a failure probability for each are in the network. The output is some measure of the reliability of the network. The reliability measures treated most extensively in this paper are: the two terminal measure, the probability that there exists a path between two specified nodes; the all-terminal measure the probability that the network is connected and the k-terminal measure, the probability that a specified node subset, K, is connected. In all cases the results concerning each problem's computational complexity, exact algorithms, analytic bounds and Monte Carlo methods are covered. The paper also treats more complex reliability measures including performability measures and stochastic shortest path, max flow and PERT problems. A discussion is provided on applications and using the techniques covered in practice.
  • Thumbnail Image
    Item
    A Reliability Model Applied to Emergency Service Vehicle Location
    (1992) Ball, Michael O.; Lin, Feng L.; ISR
    This article proposes a reliability model for the emergency service vehicle location problem. Emergency services planners must solve the strategic problem of where to locate emergency services stations and the tatical problem of the number of vehicles to place in each station. We view the problem as one of optimizing the reliability of a system, where system failure is interpreted as the inability of a vehicle to respond to a demand call within an acceptable amount of time. Our model handles the stochastic problem aspects in a more explicit way than previous models in the literature. Based on a reliability bound on the probability of system failure, we derive a 0-1 integer programming (IP) optimization model. To solve it, we propose valid inequalities as a preprocessing technique to augment the IP and solve the IP using a branch-and-bound-procedure. Our computational results show that the preprocessing techniques and highly effective. We feel that the reliability model should have applications beyond this context and hope that it till lead to ideas for similar optimization models for designing other systems.