10th EAI International Conference on Performance Evaluation Methodologies and Tools

Research Article

A Maclaurin-series expansion approach to coupled queues with phase-type distributed service times

  • @INPROCEEDINGS{10.4108/eai.25-10-2016.2266864,
        author={Eline De Cuypere and Koen De Turck and Sabine Wittevrongel and Dieter Fiems},
        title={A Maclaurin-series expansion approach to coupled queues with  phase-type distributed service times},
        proceedings={10th EAI International Conference on Performance Evaluation Methodologies and Tools},
        publisher={ACM},
        proceedings_a={VALUETOOLS},
        year={2017},
        month={5},
        keywords={queueing theory singular perturbation markov process},
        doi={10.4108/eai.25-10-2016.2266864}
    }
    
  • Eline De Cuypere
    Koen De Turck
    Sabine Wittevrongel
    Dieter Fiems
    Year: 2017
    A Maclaurin-series expansion approach to coupled queues with phase-type distributed service times
    VALUETOOLS
    ACM
    DOI: 10.4108/eai.25-10-2016.2266864
Eline De Cuypere1, Koen De Turck2, Sabine Wittevrongel1, Dieter Fiems1,*
  • 1: Ghent University
  • 2: CentraleSupélec
*Contact email: dieter.fiems@ugent.be

Abstract

We propose an efficient numerical scheme for the evaluation of large-scale Markov processes that have a generator matrix that reduces to a triangular matrix when a certain rate is sent to zero. The methodology at hand is motivated by coupled queueing systems. Such systems are a natural abstraction for kitting processes in assembly systems and consist of multiple parallel buffers. The buffers are coupled in the sense that departures from the different buffers are synchronised and that there is no service if any of the buffers is empty. As multiple customer buffers are involved, the Markovian description of the system obviously suffers from the state-space explosion problem. To cope with this problem, a numerical algorithm is presented which calculates the coefficients of the Maclaurin-series expansion of the steady-state probability vector. While the series expansion is a regular perturbation problem for the coupled queueing system with exponential service times, it is a singular perturbation problem if the service times are phase-type distributed. Some numerical examples show that the series expansion technique combined with a simple heuristic provides high numerical accuracy.