Research Article
A matrix analytical method for the discrete time Lindley equation using the generalized Schur decomposition
@INPROCEEDINGS{10.1145/1190366.1190377, author={Nail Akar}, title={A matrix analytical method for the discrete time Lindley equation using the generalized Schur decomposition}, proceedings={1st International ICST Workshop on Tools for solving Structured Markov Chains}, publisher={ACM}, proceedings_a={SMCTOOLS}, year={2012}, month={4}, keywords={Lindley equation discrete-time queues matrix geometric distribution generalized ordered Schur decomposition}, doi={10.1145/1190366.1190377} }- Nail Akar
Year: 2012
A matrix analytical method for the discrete time Lindley equation using the generalized Schur decomposition
SMCTOOLS
ACM
DOI: 10.1145/1190366.1190377
Abstract
In this paper, we study the discrete time Lindley equation governing an infinite size GI/GI/1 queue. In this queuing system, the arrivals and services are independent and identically distributed but they obey a discrete time matrix geometric distribution not necessarily with finite support. Our GI/GI/1 model allows geometric batch arrivals and also treats late, early, and hybrid arrival models in a unified manner. We reduce the problem of finding the steady state probabilities for the Lindley equation to finding the generalized ordered Schur form of a matrix pair (E, A) where the size of these matrices are the sum, not the product, of the orders of individual arrival and service distributions. The approach taken in this paper is purely matrix analytical and we obtain a matrix geometric representation for the related quantities (queue lengths or waiting times) for the discrete time GI/GI/1 queue using this approach.
