Numerical Methods for Solving Discrete Event Systems: With Applications to Queueing Systems

✍ Scribed by Winfried Grassmann, Javad Tavakoli

• Publisher: Springer
• Year: 2022
• Tongue: English
• Leaves: 370
• Series: CMS/CAIMS Books in Mathematics, 5
• Category: Library

✦ Synopsis

This graduate textbook provides an alternative to discrete event simulation.  It describes how to formulate discrete event systems, how to convert them into Markov chains, and how to calculate their transient and equilibrium probabilities. The most appropriate methods for finding these probabilities are described in some detail, and templates for efficient algorithms are provided. These algorithms can be executed on any laptop, even in cases where the Markov chain has hundreds of thousands of states. This book features the probabilistic interpretation of Gaussian elimination, a concept that unifies many of the topics covered, such as embedded Markov chains and matrix analytic methods.

The material provided should aid practitioners significantly to solve their problems. This book also provides an interesting approach to teaching courses of stochastic processes.

 

✦ Table of Contents

Preface
Contents
1 Basic Concepts and Definitions
1.1 The Definition of a Discrete Event System
1.1.1 State Variables
1.1.2 Events
1.2 Markov Chains
1.2.1 Discrete-time Markov Chains (DTMCs)
1.2.2 Continuous-time Markov Chains (CTMCs)
1.3 Random Variables and Their Distributions
1.3.1 Expectation and Variance
1.3.2 Sums of Random Variables
1.3.3 Some Distributions
1.3.4 Generating Functions
1.4 The Kendall Notation
1.5 Little's Law
1.6 Sets and Sums
Problems
2 Systems with Events Generated by Poisson or by Binomial Processes
2.1 The Binomial and the Poisson Process
2.2 Specification of Poisson Event Systems
2.3 Basic Principles for Generating Transition Matrices
2.4 One-dimensional Discrete Event Systems
2.4.1 Types of One-dimensional Discrete Event Systems
2.4.2 The M/M/1/N Queue
2.4.3 Birth–Death Processes, with Extensions
2.4.4 A Simple Inventory Problem
2.5 Multidimensional Poisson Event Systems
2.5.1 Types of Multidimensional Systems
2.5.2 First Example: A Repair Problem
2.5.3 Second Example: Modification of the Repair Problem
2.6 Immediate Events
2.6.1 An Example Requiring Immediate Events
2.6.2 A Second Example with Immediate Events: A Three-way Stop
2.7 Event-based Formulations of the Equilibrium Equations
2.8 Binomial Event Systems
2.8.1 The Geom/Geom/1/N Queue
2.8.2 Compound Events and Their Probabilities
2.8.3 The Geometric Tandem Queue
Problems
3 Generating the Transition Matrix
3.1 The Lexicographic Code
3.2 The Transition Matrix for Systems with Cartesian State Spaces
3.3 The Lexicographic Code Used for Non-Cartesian State Spaces
3.4 Dividing the State Space into Subspaces
3.5 Alternative Enumeration Methods
3.6 The Reachability Method
Problems
4 Systems with Events Created by Renewal Processes
4.1 The Renewal Process
4.1.1 Remaining Lifetimes
4.1.2 The Age Process
4.1.3 The Number of Renewals
4.2 Renewal Event Systems
4.2.1 Description of Renewal Event Systems
4.2.2 The Dynamics of Renewal Event Systems
4.3 Generating the Transition Matrix
4.3.1 The Enumeration of States in Renewal Event Systems
4.3.2 Ages Used as Supplementary State Variables
4.3.3 Remaining Lifetimes used as Supplementary State Variables
4.3.4 Using both Age and Remaining Life as Supplementary State Variables
Problems
5 Systems with Events Created by Phase-type Processes
5.1 Phase-type (PH) Distributions
5.1.1 Phase-type Distributions based on Sums, and the Erlang Distribution
5.1.2 Phase-type Distributions Based on Mixtures, and the Hyper-exponential Distribution
5.1.3 Coxian Distributions
5.1.4 Renewal Processes of Phase type
5.1.5 Discrete Distributions as PH Distributions
5.2 The Markovian Arrival Process (MAP)
5.3 PH Event Systems
5.3.1 Immediate Events in PH Event Systems
5.3.2 Two Examples
5.4 Generating the Transition Matrix with Immediate Events
Problems
6 Execution Times, Space Requirements, and Accuracy of Algorithms
6.1 Asymptotic Expressions
6.2 Space Complexity
6.2.1 The Sparsity of Transition Matrices
6.2.2 Storing only the Non-zero Elements of a Matrix
6.2.3 Storage of Banded Matrices
6.3 Time Complexity
6.4 Errors due to Inaccurate Data, Rounding, and Truncation
6.4.1 Data Errors
6.4.2 Rounding Errors
6.4.3 Truncation Errors
Problems
7 Transient Solutions of Markov Chains
7.1 Extracting Information from Data Provided by Transient Solutions
7.2 Transient Solutions for DTMCs
7.3 Transient Solutions for CTMCs
7.4 Programming Considerations
7.5 An Example: A Three-Station Queueing System
7.6 Waiting Times
7.6.1 Waiting Times in the M/M/1 Queue under Different Queuing Disciplines
7.6.2 Comparison of the Queueing Disciplines
7.7 Conclusions
Problems
8 Moving toward the Statistical Equilibrium
8.1 Structure of the Transition Matrix and Convergence toward Equilibrium
8.1.1 Paths and Their Effect on the Rate of Convergence
8.1.2 Communicating Classes
8.1.3 Periodic DTMCs
8.2 Transient Solutions using Eigenvalues
8.2.1 Basic Theorems
8.2.2 Matrix Power and Matrix Exponential
8.2.3 An Example of a Transient Solution using Eigenvalues
8.2.4 The Theorem of Perron-Frobenious
8.2.5 Perron–Frobenius and Non-Negative Matrices
8.2.6 Characterization of Transient Solutions
8.2.7 Eigenvalues with Multiplicities Greater than One
8.2.8 Coxian Distributions Characterized by Eigenvalues
8.2.9 Further Insights about PH Distributions Gained through Eigenvalues
8.2.10 Eigenvalues of Zero
8.2.11 Eigensolutions of Tridiagonal Transition Matrices
8.3 Conclusions
Problems
9 Equilibrium Solutions of Markov Chains and Related Topics
9.1 Direct Methods
9.1.1 The State Elimination Method
9.1.2 Banded Matrices
9.1.3 Gaussian Elimination as Censoring
9.1.4 A Two Server Queue
9.1.5 Block-structured Matrices
9.1.6 The Crout Method
9.2 The Expected Time Spent in a Transient State
9.2.1 The Fundamental Matrix
9.2.2 Moments of the Time to Absorption
9.2.3 Finding Expectation and Variance for M/M/1 Waiting Times
9.3 Iterative Methods
9.3.1 Equilibrium Probabilities Found as Limits of Transient Probabilities
9.3.2 Methods based on Successive Improvements
9.3.3 Convergence Issues
9.3.4 Periodic Iteration Matrices
9.3.5 Examples
9.4 Conclusions
Problems
10 Reducing the Supplementary State Space Through Embedding
10.1 The Semi-Markov Process (SMP)
10.1.1 Using Age as the Supplementary Variable
10.1.2 Using the Remaining Lifetime as Supplementary Variable
10.2 Embedding at Changes of the Physical State
10.2.1 Creating the Supplementary State Space
10.2.2 The Physical States of Embedded Markov Chains can Form Semi-Markov Processes
10.2.3 Numerical Experiments
10.3 Embedding at Specific Event Types
10.3.1 The Main Formulas
10.3.2 An Example where the Embedding Event is Never Disabled
10.3.3 An Example where the Embedding Event can be Disabled
10.3.4 The Embedded Markov Chains of M/G/1/N and GI/M/1/N Queues
10.3.5 Finding Random Time Distributions from Embedding Point Distributions
Problem
11 Systems with Independent or Almost Independent Components
11.1 Complexity Issues when using Subsystems
11.2 Mathematical Tools for Combining Independent Subsystems
11.2.1 Combining DTMCs via Kronecker Products
11.2.2 CTMCs and Kronecker Sums
11.2.3 Using Kronecker Products in Almost Independent Subsystems
11.3 Jackson Networks
11.3.1 Simple Tandem Queues
11.3.2 General Jackson Networks
11.3.3 Closed Queueing Networks
11.4 Conclusions
Problems
12 Infinite-state Markov Chains and Matrix Analytic Methods (MAM)
12.1 Properties Specific to Infinite-state Markov Chains
12.1.1 Diverging and Converging Markov Chains
12.1.2 Stochastic and Substochastic Solutions of Infinite-state Markov Chains
12.1.3 Convergence to the Desired Solution
12.2 Markov Chains with Repeating Rows, Scalar Case
12.2.1 Recurrent and Transient Markov Chains
12.2.2 The Extrapolating Crout Method
12.2.3 Using Generating Functions for Norming the Probabilities
12.2.4 The Waiting-time Distribution of the GI/G/1 Queue
12.2.5 The Line Length Distribution in a GI/G/1 Queue Obtained from its Waiting-Time Distribution
12.2.6 The M/D/c Queue
12.2.7 Increase of X limited to 1, and Decrease of X limited to 1
12.3 Matrices with Repeating Rows of Matrix Blocks
12.3.1 Recurrent and Transient GI/G/1 Type processes
12.3.2 The GI/G/1 Paradigm
12.3.3 Generating Functions
12.3.4 The QBD Process
12.3.5 The Classical MAM Paradigms
12.4 Solutions using Characteristic Roots and Eigenvalues
12.4.1 Solutions based on Characteristic Roots
12.4.2 Using Eigenvalues for Block-Structured Matrices with Repeating Rows
12.4.3 Application of the Generalized Eigenvalue Problem for Finding Equilibrium Solutions
12.4.4 Eigenvalue Solutions Requiring only one Eigenvalue
12.5 Conclusions
Problems
A Language Conventions for Algorithms
Appendix References
Index