1st International ICST Workshop on Tools for solving Structured Markov Chains

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
Nail Akar1,*
  • 1: Electrical and Electronics Eng., Bilkent University, Ankara, Turkey.
*Contact email: akar@ee.bilkent.edu.tr

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.