Institute for Systems Research
Permanent URI for this communityhttp://hdl.handle.net/1903/4375
Browse
6 results
Search Results
Item Threshold Reliability of Networks with Small Failure Sets(1993) Ball, Michael O.; Hagstrom, Jane N.; Provan, J. Scott; ISRThis paper addresses two classes of reliability analysis models: a network flow model and a project scheduling model. For the network flow model we are given a capacitated source/sink graph in which arcs fail randomly. The system is defined as operating whenever the max-flow value is greater than a threshold. For the project scheduling model we are given a directed acyclic source/sink graph in which each arc has two lengths. Each arc randomly takes on one of two states. In the "operating" state it takes on its smaller length and in its "failed" state it takes on it larger length. The system is defined as operating whenever the length of the longest path is less than a threshold. We address a special case of the threshold flow problem in which all arcs have the same capacity and a special case of the project scheduling model in which the difference between the lower and higher arc lengths is constant. For these special cases we show that if the underlying systems are 1-critical, namely, all arcs are in some cutset of size two, then the threshold flow problem can be solved in polynomial time and planar project scheduling problem can be solved in polynomial time. Both solutions are obtained by reducing the problems to the problem of determining the probability that the failed arcs in a directed acyclic graph lie on a single path. We also show how the basic approach can be used to generate bounds for systems that are "almost critical".Item Reliability, Covering and Balanced Matrices(1993) Ball, Michael O.; Lin, Feng L.; ISRThe paper addresses a certain generalized covering integer program. The original application that motivated the study of this problem was an emergency services vehicle location problem. In this paper, we show that the same model can be applied to a general system reliability optimization problem. The main contribution of this paper is the definition and analysis of a reformulation strategy. Specifically, we show how the original generalized covering problem can be reformulated as a set covering problem. We then show that for a particular special case the associated constraint matrix is balanced. This in turn implies that the integer program can be efficiently solved using linear programming techniques. This result together with the good computational results reported in a previous paper constitute substantial evidence as to the overall effectiveness of the reformulation strategy. Furthermore, they indicate that the generalized covering model addressed can be effectively solved in a fairly wide range of cases.Item Building Decision Support Systems That Use Operations Research Models as Database Applications(1992) Ball, Michael O.; Datta, Anindya; Dahl, Roy; ISRIn 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.Item MANDATE: MAnaging Networks using DAtabase TEchnology(1992) Haritsa, Jayant R.; Ball, Michael O.; Roussopoulos, N.; Datta, Anindya; ISRIn a recent opinion poll of telecommunications executives, enterprise network management was identified to be the top technological issue of the future. At present, however, there do not exist any viable solutions to this critical problem. Therefore, considerable research efforts are being focused on the development of effective network management tools. A management information database is the heart of a network management system - it provides the interface between all functions of the network management system, and therefore has to provide sophisticated functionality allied with high performance. In this paper, we describe MANDATE (MAnaging Networks using DAtabase TEchnology), a database system that is designed to effectively support the management of large networks of the future. MANDATE uses special characteristics of network management data and transactions, together with recent advances in database technology, to efficiently derive its functionality.Item A Reliability Model Applied to Emergency Service Vehicle Location(1992) Ball, Michael O.; Lin, Feng L.; ISRThis 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.Item Bounding a Probability Measure over a Polymatroid with an Application to Transportation Problems(1992) Ball, Michael O.; Shanthikumar, J.G.; ISRWe are given a set of supply nodes, a set of demand nodes and a set of arcs between certain supply/demand pairs, which indicate if the supply node can serve as a source for the demand node. The level of the supply available at each supply node and the amount demanded by each demand node are independent random variables. We derive an upper bound on the probability that the random demand can be met by the random supply under the assumption that the supply levels have new better than used (NBU) distribution functions. The functional form of the bound is the product of the probabilities that each demand node, viewed independently, can be feasibly satisfied. In order to prove this result we first prove another result concerning polymatroids. This result gives a lower bound on the probability that a random vector is the member of the polymatroid.