Research Article
Algorithmic approach to series expansions around transient Markov chains
@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
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.