Institute for Systems Research

Permanent URI for this communityhttp://hdl.handle.net/1903/4375

Browse

Author: search.filters.author.Ball, Michael O.

Search Results

Now showing 1 - 10 of 29
  • Thumbnail Image
    Item
    Optimization-Based Available-To-Promise with Multi-Stage Resource Availability
    (2005) Zhao, Zhenying; Ball, Michael O.; Ball, Michael O.; ISR
    Increasingly, customer service, rapid response to customer requirements, and flexibility to handle uncertainties in both demand and supply are becoming strategic differentiators in the marketplace. Organizations that want to achieve these benchmarks require sophisticated approaches to conduct order promising and fulfillment, especially in today's highmix low-volume production environment. Motivated by these challenges, the Available-to-Promise (ATP) function has migrated from a set of availability records in a Master Production Schedule (MPS) toward an advanced real-time decision support system to enhance decision responsiveness and quality in Assembly To Order (ATO) or Configuration To Order (CTO) environment. Advanced ATP models and systems must directly link customer orders with various forms of available resources, including both material and production capacity. In this paper, we describe a set of enhancements carried out to adapt previously published mixed integer- programming (MIP) models to the specific requirements posed by an electronic product supply chain within Toshiba Corporation. This model can provide individual order delivery quantities and due dates, together with production schedules, for a batch of customer orders that arrive within a predefined batching interval. The model considers multi-resource availability including manufacturing orders, production capability and production capacity. In addition, the model also takes into account a variety of realistic order promising issues such as order splitting, model decomposition and resource expediting and de-expediting. We conclude this paper with comparison of our model execution results vs. actual historical performance of systems currently in place.
  • Thumbnail Image
    Item
    The Rate Control Index for Traffic Flow
    (2001) Hoffman, Robert L.; Ball, Michael O.; ISR; NEXTOR
    The objective of Air Traffic Flow Management is to maintain safe andefficient use of airspace and airports by regulating the flow oftraffic. In this paper,we introduce a single-valued metric for post-operatively rating theperformance ofachieved traffic flow against targeted traffic flow. We providevariations on themetric, one of which factors out stochastic conditions upon which a planis formu-lated, and show how these improve on current traffic control analysistechniques.The core of the metric is intuitive and simple, yet leads to aninteresting optimiza-tion problem that can be efficiently solved via dynamic programming.Numericalresults of the metric are given as well as a sample of the type ofanalysis that shouldfollow a low rating by the metric. Although this metric was originallydevelopedto rate the performance of Ground Delay Programs, it is equallyapplicable to anysetting in which the flow of discrete objects such as vehicles iscontrolled and laterevaluated.
  • Thumbnail Image
    Item
    Bicriteria Product Design Optimization
    (2001) Raghavan, S.; Ball, Michael O.; Trichur, Vinai S.; ISR
    Competitive imperatives are causing manufacturing firms toconsider multiple criteria when designing products. However,current methods to deal with multiple criteria in product designare ad hoc in nature. In this paper we present a systematicprocedure to efficiently solve bicriteria product designoptimization problems.

    We first present a modeling framework, theAND/OR tree, that permits a simplified representation of productdesign optimization problems. We then show how product designoptimization problems on AND/OR trees can be framed as networkdesign problems on a special graph---a directed series-parallelgraph.

    We develop a solution algorithm for the bicriteria problemthat requires as a subroutine the solution of the parametricshortest path problem. Although this problem is hard on generalgraphs, we show that it is polynomially solvable on theseries-parallel graph. As a result we develop an efficientsolution algorithm for the product design optimization problemthat does not require the use of complex and expensivelinear/integer programming solvers.

    As a byproduct of thesolution algorithm, sensitivity analysis for product designoptimization is also efficiently performed under this framework.We illustrate our model and solution algorithm on a complexdesign problem at a FORTUNE 100 company.

  • Thumbnail Image
    Item
    Measuring Ground Delay Program Effectiveness Using the Rate Control Index
    (2000) Ball, Michael O.; Hoffman, Robert L.; Ball, Michael O.; ISR; NEXTOR
    The objective of Air Traffic Flow Management is to maintain safe and efficient use of airspace and airports by regulating the flow of traffic. In this paper, we introduce a single-valued metric for post-operatively rating the performance of achieved traffic flow against targeted traffic flow. We provide variations on the metric, one of which factors out stochastic conditions upon which a plan is formulated, and show how these improve on current traffic control analysis techniques. The core of the metric is intuitive and simple, yet leads to an interesting optimization problem that can be efficiently solved via dynamic programming. Numerical results of the metric are given as well as a sample of the type of analysis that should follow a low rating by the metric. Although this metric was originally developed to rate the performance of Ground Delay Programs, it is equally applicable to any setting in which the flow of discrete objects such as vehicles is controlled and later evaluated.
  • Thumbnail Image
    Item
    Collaborative Decision Making in Air Traffic Management: Current and Future Research Directions
    (2000) Ball, Michael O.; Hoffman, Robert L.; Chen, Chien-Yu; Vossen, Thomas; ISR; NEXTOR
    Collaborative Decision Making (CDM) embodies a new philosophy for managing air traffic. The initial implementation of CDM in the US has been aimed at Ground Delay Program Enhancements (GDP-E). However, the underlying concepts of CDM have the potential for much broader applicability.

    This paper reviews on-going and proposed CDM research streams. The topic areas discussed include: ground delay program enhancements; collaborative routing; performance monitoring and analysis; collaborative resource allocation mechanisms; game theory models for analyzing CDM procedures and information exchange; collaborative information collection and distribution.

  • Thumbnail Image
    Item
    The Rate Control Index for Traffic Flow
    (2000) Ball, Michael O.; Hoffman, Robert L.; Ball, Michael O.; ISR; NEXTOR
    The objective of Air Traffic Flow Management is to maintain safe and efficient use of airspace and airports by regulating theflow of traffic. In this paper, we introduce a single-valued metric for post-operatively rating the performance ofachieved traffic flow against targeted traffic flow. We provide variations on the metric, one of which factors out stochastic conditions upon which a plan is formulated, and show how those improve on current traffic control analysis techniques.

    The core of the metric is intuitive and simple, yet leads to an interesting optimization problem that can be efficiently solved via dynamic programming. Numerical results of the metric are given as well as a sample of the type of analysis that should follow a low rating by the metric.

    Although this metric was originally developed to rate the performance of GroundDelay Programs, it is equally applicable to any setting in which the flow of discrete objects such as vehicles is controlled and later evaluated.

  • Thumbnail Image
    Item
    Next Generation Satellite Systems for Aeronautical Communications
    (2000) Ercetin, Ozgur; Ball, Michael O.; Tassiulas, Leandros; Tassiulas, Leandros; ISR; NEXTOR
    The US airspace is reaching its capacity with the current Air Traffic Control system and a number of flights that is constantly rising, and estimated to be over 54 million per year by 2002. The FAA has undertaken several projects to modernize the National Airspace System (NAS) to ensure the safety of the increasing number of flights. Of special importance is the modernization of the Air-Ground (A/G) Communications infrastructure, which is the heart of the air traffic control (ATC).

    The current plan in the modernization of the A/G communications is to migrate from analog voice only system to integrated digital voice and data system. The next generation satellite systems can be an alternative to the terrestrial A/G systems by their low propagation and transmission delays, global coverage, high capacity, and free flight suitable characteristics. In this paper, we give an overview of the current and the future ATC architectures, describe the systems and the communications issues in these systems, and develop a framework in which LEO/MEO next generation satellite systems can be integrated to the future ATC systems.

  • Thumbnail Image
    Item
    The Static Stochastic Ground Holding Problem with Aggregate Demands
    (1999) Ball, Michael O.; Hoffman, Robert L.; Odoni, A.; Rifkin, R.; Ball, Michael O.; ISR; NEXTOR
    The ground delay program is a mechanism used to decrease the rate of incoming flights into an airport when it is projected that arrival demand into the airport will exceed capacity. In this paper, we present an integer programming model for plannning ground delay programs. The model considers a stochastic capacity profile which is represented by a set of airport capacity scenarios and their probabilities. Both the demand on the airport and the output of the model are represented at an aggregate level in terms of number of flights per unit time. This allows the model to be used in conjunction with arbitrarily complex preprocesses for allocating individual flights to slots. It was specifically designed to be used in the Collaborative Decision Making setting where individual flight assignments result from an iterative process involving both the airlines and traffic flow managers. We show that the linear programming dual of the model can be transformed into a network flow problem. This implies that the integer program can be solved efficiently using linear programming or network flow models.
  • Thumbnail Image
    Item
    On the Use of Integer Programming Models in AI Planning
    (1999) Vossen, Thomas; Ball, Michael O.; Lotem, Amnon; Nau, Dana; ISR
    Recent research has shown the promise of using propositional reasoning and search to solve AI planning problems. In this paper, we further explore this area by applying Integer Programming to solve AI planning problems. The application of Integer Programming to AI planning has a potentially significant advantage, as it allows quite naturally for the incorporation of numerical constraints and objectives into the planning domain. Moreover, the application of Integer Programming to AI planning addresses one of the challenges in propositional reasoning posed by Kautz and Selman, who conjectured that the principal technique used to solve Integer Programs---the linear programming (LP) relaxation---is not useful when applied to propositional search. We discuss various IP formulations for the class of planning problems based on the STRIPS paradigm. Our main objective is to show that a carefully chosen IP formulation significantly improves the "strength" of the LP relaxation, and that the resultant LPs are useful in solving the IP and the associated planning problems. Our results clearly show the importance of choosing the "right" representation, and more generally the promise of using Integer Programming techniques in the AI planning domain.
  • Thumbnail Image
    Item
    A Comparison of Formulations for the Single-Airport Ground Holding Problem with Banking Constraints
    (1998) Hoffman, Robert L.; Ball, Michael O.; ISR; NEXTOR
    Both the single-airport ground-holding problem (GH) and the multi-airport ground-holding problem can be extended by the addition of banking constraints to accommodate the hubbing operations of major airlines. These constraints enforce the desire of airlines to land certain groups of flights, called banks, within fixed time windows, thus preventing the propagation of delays throughout their entire operation. GH can be formulated as a transportation problem and readily solved. But in the presence of banking constraints, GH becomes a difficult integer programming problem. In this paper, we construct five different models of the single-airport ground holding problem with banking constraints (GHB). The models are evaluated both computationally and analytically. For two of the models, we show that the banking constraints induce facets of the convex hull of the set of integer solutions. In addition, we explore a linear transformation of variables and a branching technique.