Past exam of the mathematics course of the University of Cambridge / 2010 / iii / Paper 30 / 2 / a / Solution

A multiclass queue must specify its service discipline as well as its arrival and service rates. Here is an ordered-queue model that includes the usual class-independent exponential single-server queue. Let class-$r$ arrivals be independent Poisson processes of rates ${\alpha }_r$, and let a class-$r$ service requirement have the exponential distribution of rate ${\mu }_r$. A state is a finite word $x=(c_1,\dots ,c_n)$ of customer classes.

Choose service fractions ${\gamma }_i(n)\ge 0$ with ${\sum }_{i=1}^n{\gamma }_i(n)=1$, and insertion probabilities ${\delta }_i(n)\ge 0$ with ${\sum }_{i=1}^n{\delta }_i(n)=1$. The customer at position $i$ departs at rate ${\mu }_{c_i}{\gamma }_i(n)$; a class-$r$ arrival is inserted at position $i$ at rate ${\alpha }_r{\delta }_i(n+1)$. All rates leading to the same word are added. For class-dependent ${\mu }_r$, impose the symmetric service discipline ${\delta }_i(n)={\gamma }_i(n)$. If all ${\mu }_r=\mu$, arbitrary class-independent $\gamma ,\delta$ are permitted, including first come first served with insertion at the tail and service at the head.

Put ${\rho }_r={\alpha }_r/{\mu }_r$ and $\rho ={\sum }_r{\rho }_r$. For $\rho <1$, the equilibrium word law isFor the symmetric service discipline, insertion and deletion satisfy detailed balance for a continuous-time Markov chain becauseFor the common-service-rate case, use time reversal of a continuous-time Markov chain instead: the reversed queue inserts with probabilities $\gamma$ and serves with fractions $\delta$. A forward insertion gives a reverse deletion rate $\mu {\delta }_i$, and a forward deletion gives a reverse insertion rate ${\alpha }_r{\gamma }_i$. Forward and reverse total rates both equal ${\sum }_r{\alpha }_r+\mu 1_{\{n>0\}}$, proving global balance for a continuous-time Markov chain.

Summing the weights of all words of length $n$ gives $(1-\rho ){\rho }^n$, so the law is normalized. If $n_r$ counts class-$r$ customers and $n={\sum }_r{n}_r$, the multinomial coefficient counting class orderings givesFor processor sharing, ${\gamma }_i(n)={\delta }_i(n)=1/n$, the class-count vector itself is a Markov chain, with arrival rate ${\alpha }_r$ and departure rate ${\mu }_r{n}_r/n$. Under first come first served, the ordered word is generally necessary. Class-dependent service rates combined with first come first served do not in general have the displayed simple equilibrium law; the discipline assumption matters.