The semi-Markovian queue: Theory and applications

In this paper, a first-come-first-served single server semi-Markovian queue is studied, in which both the arrival and service mechanisms are semi-Markov processes. The interarrival time and service times may depend on one another and the marginal distribution of the service times is assumed to be phase-type. For this queue, it is shown that the distributions of waiting time, time in system and virtual waiting time are matrix-exponential. Further, these matrix-exponential distributions have phase-type representations. For the special case when the interarrival times are independent of the service times, it is shown that the queue length distribution is matrix-geometric. For this special case, it is proven that the queue length distribution problem is the dual of the waiting time distribution problem, i.e., finding the solution of one problem immediately gives the solution of the other. It is shown that the present methods are computationally feasible and the numerical experience is reported. Examples are given where such queues arise naturally. In particular, an application in manufacturing, a periodic queue and a queue with Markov modulated arrivals and services are discussed.