We consider the waiting time (delay) W in a first-come-first-served 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 Fi, with mi phases for the ith server. The distribution of W is then again phase-type, with m1 . . . mc phases for the general heterogeneous renewal case and (cm+c−1) phases for the homogeneous case Fi = F, mi = m. We derive the phase-type representation in a form which is explicit up to the solution of a matrix fixed point 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.
