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

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