Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2018 | Book

Introduction G(V, E) Read chapter Read first chapter

Introduction to Queueing Networks

Theory ∩ Practice

Author: Prof. J. MacGregor Smith

Publisher: Springer International Publishing

Book Series : Springer Series in Operations Research

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

The book examines the performance and optimization of systems where queueing and congestion are important constructs. Both finite and infinite queueing systems are examined. Many examples and case studies are utilized to indicate the breadth and depth of the queueing systems and their range of applicability. Blocking of these processes is very important and the book shows how to deal with this problem in an effective way and not only compute the performance measures of throughput, cycle times, and WIP but also to optimize the resources within these systems.

The book is aimed at advanced undergraduate, graduate, and professionals and academics interested in network design, queueing performance models and their optimization. It assumes that the audience is fairly sophisticated in their mathematical understanding, although the explanations of the topics within the book are fairly detailed.

Table of Contents

Frontmatter
1. Introduction G(V, E)
Overview
In this first chapter, we give the interested reader an introduction to the basic research issues concerning queueing, blocking, and transportation networks. We discuss queueing and congestion, why, where, when, and how system tools can be best utilized. The key organizing elements of the chapter include but are not limited to the following:
  • I. Representing a system with a queueing network G(V, E),.
  • II. Analyzing a system’s performance with efficient algorithms f[G(V, E)].
  • III. Synthesizing a system with optimization procedures G(V, E)∗.
In order to model a system, we examine some of the fundamental principles of representing systems with queueing networks. Secondly, certain principles, algorithms, and systematic procedures for analyzing these systems are outlined along with a set of examples. Finally, illustrative ways of optimally synthesizing the results so we can improve the system are described.
J. MacGregor Smith
2. Problem Overview
Overview
Finite queueing models and blocking systems and their traffic problems originated with A. K. Erlang and the Danish telephone system in Copenhagen, Denmark, around 1909. In this chapter, we present an introduction to Stochastic Processes together with the notation used in queueing and congestion problems. We will trace the evolution of queue and queueing network models and their optimization for traffic congestion and performance. We also articulate the framework as depicted in Figure 2.1 and outline of topics around which the models in the Volume will be developed.
J. MacGregor Smith
3. Mathematical Models and Properties of Queues G(V)
Overview
This chapter discusses the underlying mathematical models of the most important queues and their properties needed to model both infinite and finite buffer queueing networks. This chapter surveys known methods and tools essential to modeling infinite and finite buffer queueing systems. We will summarize known results or defer to some of the other reference books for further details of specialized queueing models. We will not try and overwhelm the reader with formulae but hopefully inform the reader about the use of these formulae especially for analysis and optimization. We break down the type of queues into four categories which will be used in later chapters regarding algorithms and optimization for queues and queueing networks:
I.
Product-Form Queues that will admit a product-form distribution;
II.
Non-product-Form Queues that will require more general procedures because the probability distributions do not have memoryless properties.
III.
Blocking Queues because they have finite waiting room and will cause interruptions in the stochastic flows of the system, and finally
IV.
Transportation and Loss Queues Special queues for transportation, communication, and many other types of applications.
These categories are designed to be able to work with the performance algorithms that we shall describe in Chapters 5 (Open Networks) and 6 (Closed Networks) and the various optimization problems and methodology described in Chapters 7 (Resource Allocation), 8 (Routing Problems), and 9 (Topological Network Design).
J. MacGregor Smith
4. Transportation and Loss Queues G(E)
Overview
The fundamentals of modeling transportation and material handling systems with finite queues and queueing networks are described in this chapter. This is a critical linking chapter in the book because how to capture congestion in traffic flow processes is central to the topological network design of queueing, blocking, transportation, and loss networks. Starting with a background literature review of transportation and material handling systems and then building upon the basic principles of capturing the throughput volume, speeds, density, and congestion in transportation systems, we develop appropriate queueing models to capture these fundamental traffic flow processes. We focus on the state-dependent M∕G∕c∕c queues and queueing network models as they incorporate the micro and macro aspects of traffic flow simultaneously. Figure 4.1 illustrates a high-rise building with the stairwells which are essential for the pedestrians flowing through the facility. We can generalize these to generalized Erlang and Engset models which provides a computational advantage for us in dealing with large instances of queueing and blocking networks.
J. MacGregor Smith
5. Open Queueing Network Algorithms
Overview
In this chapter, we discuss open queueing network models for topological network design. The topics chosen are closely related to the queue categories (repeated below) we defined in Chapter 3 We emphasize practical algorithms wherever possible along with their computer implementations for performance and optimization.
  • Product-Form (Jackson) Networks
    We discuss their use and illustrate what can be accomplished through several examples including some simple optimization experiments.
  • Non-Product-Form Networks
    We present a parametric decomposition approach for dealing with non-product-form networks. The algorithm is based on the queueing network approximation (QNA) algorithm of Whitt. The performance and optimization with QNA are demonstrated in several examples.
  • Blocking Networks
    These have to be treated with special care in order to account for the interruption of flow processes and non-renewal effects. We discuss the Expansion Method for exponential blocking networks and the generalized expansion method for more general distributions. Some simple tandem, merge, and split topology network examples are discussed.
  • Transportation and Loss Networks
    Transportation networks round out the material in this chapter. Several examples demonstrate the performance of these state-dependent networks.
J. MacGregor Smith
6. Closed Queueing Network Performance Models
Overview
In this chapter, we present closed queueing network models for topological network design. We first give a brief historical perspective of the major developments in closed queueing network models and then discuss some of the important principles in modeling with closed network algorithms, the arrival theorem, aggregation, and Norton’s theorem. These algorithms are presented for their clarity and directness in the performance and optimization of queueing systems. Networks we will discuss include:
  • Product-Form Networks: Starting from the basic exact algorithms developed by Gordon and Newell, we discuss their use and illustrate with several examples and algorithms along with their performance and optimization wherever possible.
  • Non-product-Form Networks: General service time distributions are treated next and we present algorithms and optimizations. Because of the complexity of this problem, the focus is mostly on approximation algorithms.
  • Blocking Networks: As in open network algorithms, blocking in closed networks is extremely complex, and we present a series of approaches for treating blocking in closed networks.
  • Transportation and Loss Networks: Movement of goods from one queue to another in closed networks is of course very important, and we present an approach based upon state-dependent algorithms.
Closed queueing network models are the foundation of many applications and optimization solutions.
J. MacGregor Smith
7. Optimal Resource Allocation Problems (ORAP) G(V ∗) in TND
Overview
Chapter 7 begins the last of three chapters on optimization problems in topological network design (TND). While all the optimization problems are closely intertwined, we separate them due to the complexity and detail involved. We will build upon the open and closed algorithms which regulate the performance of the network and add optimization algorithms to define the best resources within the network.
• Resource Allocation Problems (ORAP)
These are the foremost problems one considers in improving stochastic flow processes as they are the most obvious ones and also some of the most significant.
• Optimal Routing Problems (ORTE)
Routing problems while related to the resource allocation ones in Chapter 7 are normally distinguishable because of certain application requirements. Accessibility and egress are good examples where routing is critical, but in telecommunications and computer network, routing problems are very significant. We will address these in Chapter 8
• Optimal Topology Problems (OTOP)
Optimal topology problems are perhaps the most challenging and complex network design problems because of their frequent integer requirements. Since they often comprise the resource allocation and routing problems, they are also quite significant to applications. We will close this volume in Chapter 9 by examining the OTOP.
J. MacGregor Smith
8. Optimal Routing Problems (ORTE) G(E ∗) in TND
Overview
This is the second chapter in our optimization finale. It concerns routing in queueing networks which is one of the most fundamental problems in topological network design. We illustrate optimal routing optimization in the design of queues, processes, and queueing networks where we examine blocking then transportation and loss networks. Figure 8.1 illustrates a general network topology where optimal routing is critical at many junctions. Access and egress problems are fundamental routing problems in most facilities and urban environments. We have already examined briefly the routing problem in product-form and non-product-form networks with infinite buffers in Chapters 5 and 6 We illustrate the problem with a number of applications and tie together the theory of queues and algorithms for the solution of a number of instances of optimal routing (ORTE) problems.
J. MacGregor Smith
9. Optimal Topology Problems (OTOP) G(V, E)∗ in TND
Overview
We illustrate a number of optimal topological network design problems in queueing networks in this chapter. We conclude our study of this problem with a number of applications and tie together the theory of queues and algorithms for the solution of a number of TND problems. These are probably the most difficult optimization problems we examine in this volume because of the integer and nonlinear programming aspects. We break down the problems into fixed topology problems and spatially generated ones. The fixed topology problems have a given topology that must be evaluated as is. The spatially generated topologies occur when the topology is not fixed, and we use mathematical programming concepts to generate the topologies a priori. They represent fundamental queueing network design problems that are not only challenging but useful in many applications. Figure 9.1 represents all TND optimization problems.
J. MacGregor Smith
10. Final Coda
Overview
In this last chapter, we summarize the volume’s contents, provide a review of the software tools available that were presented in the various chapters, and provide some open questions for future research and development.
  • Chapter 1: Introduction G(V, E)
  • Chapter 2: Problem Overview \(\varOmega {\bigl (G(V,E)\bigr )}\)
  • Chapter 3: Mathematical Models and Properties of Queues G(V )
  • Chapter 4: Transportation and Loss Queues G(E)
  • Chapter 5: Open Queueing Network Algorithms \(f{\bigl (G(V,E)\bigr )}\)
  • Chapter 6: Closed Queueing Network Algorithms \(f{\bigl (G(V,E,N)\bigr )}\)
  • Chapter 7: Optimal Resource Allocation Problems G(V ∗)
  • Chapter 8: Optimal Routing Problems G(E ∗)
  • Chapter 9: Optimal Topology Problems G(V, E)∗
J. MacGregor Smith
Backmatter
Metadata
Title
Introduction to Queueing Networks
Author
Prof. J. MacGregor Smith
Copyright Year
2018
Electronic ISBN
978-3-319-78822-7
Print ISBN
978-3-319-78821-0
DOI
https://doi.org/10.1007/978-3-319-78822-7

Premium Partners

    Image Credits