Algorithms for the multi-server queue with phase type service

Abstract

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 x_v(n₁,...,n_m) of the vector x_v 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” x₀,...,x_c-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.