Algorithms for the multi-server queue with phase type service

We consider the multiserver queue with c phase type servers and a renewal input. It is well-known that the stationary joint distribution of the queue length and the number of servers in each phase of service is “modified matrix-geometric”, that is, of the form . Here, the component xv(n1,...,nm) of the vector xv is the probability that a stationary arrival finds v customers in the system and that immediately thereafter n, servers are in phase i of service, 1≤i≤m. The matrix R appears also in the formulas for all interesting queue characteristics and is therefore important. Here we develop efficient schemes to compute the matrix R and the “boundary probabilities” x0,...,xc-1. We also provide a complete proof for the easily implementable formula for the stationary waiting time distribution; this proof was sketched in an earlier paper without much detail.