Calculation of the steady state waiting time distribution in GI/PH/c and MAP/PH/c queues

Søren Asmussen and Jakob R. Møller,

Abstract:: We consider the waiting time (delay) $W$ in a FCFS $c$--server queue with arrivals which are either renewal or governed by Neuts' Markovian arrival process, and (possibly heterogeneous) service time distributions of general phase--type $F_i$, with $m_i$ phases for the $i$th server. The distribution of $W$ is then again phase--type, with $m_1\cdots m_c$ phases for the general heterogeneous renewal case and $(m+c-1)!/(c!(m-1)!)$ phases for the homogeneous case $F_i=F$, $m_i=m$. We derive the phase--type representation in a form which is explicit up to the solution of a matrix fixpoint problem; the key new ingredient is a careful study of the not--all--busy period where some or all servers are idle. Numerical examples are presented as well.
Key words:: busy period, heterogenous servers, iteration, Kronecker product, Kronecker sum, many-server queue, Markovian arrival process, matrix-analytic methods, non-linear matrix equation, phase-type distribution, waiting time