6th International Conference on Performance Evaluation Methodologies and Tools

Research Article

Algorithmic approach to series expansions around transient Markov chains

Download274 downloads
  • @INPROCEEDINGS{10.4108/valuetools.2012.250292,
        author={Eline De Cuypere and Koen De Turck and Dieter Fiems and Sabine Wittevrongel},
        title={Algorithmic approach to series expansions around transient Markov chains},
        proceedings={6th International Conference on Performance Evaluation Methodologies and Tools},
        publisher={IEEE},
        proceedings_a={VALUETOOLS},
        year={2012},
        month={11},
        keywords={paired queues perturbation series expansion},
        doi={10.4108/valuetools.2012.250292}
    }
    
  • Eline De Cuypere
    Koen De Turck
    Dieter Fiems
    Sabine Wittevrongel
    Year: 2012
    Algorithmic approach to series expansions around transient Markov chains
    VALUETOOLS
    ICST
    DOI: 10.4108/valuetools.2012.250292
Eline De Cuypere1,*, Koen De Turck1, Dieter Fiems1, Sabine Wittevrongel1
  • 1: Ghent University
*Contact email: eline.decuypere@telin.ugent.be

Abstract

We propose an efficient numerical scheme for the evaluation of large-scale Markov chains, under the condition that their generator matrix reduces to a triangular matrix when a certain rate is sent to zero. A numerical algorithm is presented which calculates the first N coefficients of the MacLaurin series expansion of the steady-state probability vector with minimal overhead.

We apply this numerical approach to paired queuing systems, which have a.o. applications in kitting processes in assembly systems. Pairing means that departures from the different buffers are synchronised and that service is interrupted if any of the buffers is empty. We also show a decoupling result that allows for closed-form expressions for lower-order expansions. Finally we illustrate our approach by some numerical examples.