Two servers in series, studied in terms of a Markov renewal branching process

Abstract

This paper discusses the transient and limiting behavior of a system of queues, consisting of two service units in tandem in which the second unit has finite capacity. When the second unit reaches full capacity, a phenomenon termed “blocking” occurs. A wide class of rules to resolve blocking is defined and studied in a unified way. The input to the first unit is assumed to be Poisson, the service times in the first unit are independent with a general, common distribution. When the system is not blocked, the second unit releases its customers according to a state-dependent, death process. The analysis of the time-dependence relies heavily on several imbedded Markov renewal processes. In particular, the analog of the busy period for the M/G/1 queue is modeled here as a “Markov renewal branching process”. The study of this process requires the definition of a class of matrix functions which generalizes some classical definitions of matrix function. In terms of these “matrix functions” we are led to consider functional iterates and a matrix analog of Takács' functional equation for the transform of the distribution of the busy period in the M/G/1 model. We further discuss the joint distribution of the queue lengths in units I and II and its marginal and limiting distributions. A final section is devoted to an informal discussion on how the numerical analysis of this system of queues may be organized.