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

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.