Efficient simulation of tail probabilities in a queueing model with heterogeneous servers

This paper considers a multi-server queue with Markov-modulated Poisson input and server-dependent phase-type service times. We develop an efficient rare-event simulation technique to estimate the probability that the number of customers in this system reaches a high value. Relying on explicit bounds on the probability under consideration as well as the associated likelihood ratio, we succeed in proving that the proposed estimator is of bounded relative error. Simulation experiments illustrate the significant speed-up that can be achieved by the proposed algorithm.