This was a midterm question which I did not get correct.

Customers arrive at a grocery store's checkout counter according to a Poisson process with a rate 1 per minute. Each customer carries a number of items that is uniformly distributed between 1 and 40. The store has two checkout counters , each capable of processing items at a rate of 15 items per minute.

The P-K formula is: $$W = \frac{\lambda\overline{X^2}}{2(1-\rho)}$$

A. Define the queue using Kendal notation

B. Find the average waiting time, the average total delay, and the average number of customers in the queue.

My answers and thought process:

A. Kendal notation is: (Arrival Process)/(Service Time Distribution)/(Number of Servers)

(My answer was M/D/2) The correct answer was M/G/2.

My thinking was that I could translate the problem into thinking about 'items' rather than 'customers'. Since we know the items are uniformly distributed and have a discrete outcome 1,2,3,4... 40. However, I believe my thinking that it was deterministic, 'D', was incorrect as the customers who bring the items are still arriving in a random manner, therefore general distribution, 'G', is the correct answer to cater for this randomness.

Is this the correct thinking?

B. Using the P-K formula the unknowns are $\rho$ and $\overline{X^2}$.

From queuing theory, I believe $\rho=\lambda\bar{X}$, and $X=\frac{1}{2\mu}$

To find $\bar{X}$, the average service time for all items: $$ \bar{X}=\sum_{n=1}^{40}nP(n)X$$ Where $P(n)=1/40$, for all n. (My answer $\bar{X}=41sec$) I was marked off for this approach.

Similarly for $\overline{X^2}$:$$ \overline{X^2}=\sum_{n=1}^{40}(nX)^2P(n)$$

To solve for the waiting time I substituted the above formulas into the P-K formula:

$$W = \frac{\lambda\sum_{n=1}^{40}(nX)^2P(n)}{2(1-\lambda\sum_{n=1}^{40}nP(n)X)}$$ where $\lambda=1/60 $

Then average total delay $T = W + \bar{X}$ and the average number of customers, via Little's Law, $Nc=\lambda T$.

I was marked off for the above approach.


1 Answer 1


Let $T_n$ be the arrival time of the $n^{\mathsf{th}}$ customer, $C_n$ the number of items that the $n^{\mathsf{th}}$ customer has, $$N(t)=\sum_{n=1}^\infty \mathsf 1_{(0,t]}(T_n)$$ the number of customers that arrive by time $t$, and $$Y(t) = \sum_{i=1}^{N(t)}C_i$$ the number of items that arrive at the queue by time $t$. This is a compound Poisson process, which in general behaves very differently from a Poisson arrival process - in particular, it is not a birth-death process. Since the batch sizes are i.i.d. positive integer-valued, this is an example of a Markovian bulk-arrival process. Assuming that we do not distinguish items within a batch, in equilibrium we may treat the arrival process as Poisson with rate $1$. However, this means that the service time varies with the batch size, and is $S_n =\frac{C_n}{15}$.

The Pollaczek–Khinchine formula is not applicable for multi-server queues. Instead, we may find the mean waiting time by a correction factor applied to the mean waiting time in a $M/M/c$ queue: $$\mathbb E[W^{M/G/2}] = \left(\frac{C_s^2+1}2\right)\mathbb E[W^{M/M/2}]=\frac12\mathbb E[W^{M/M/2}],$$ where $C_s^2$ is the coefficient of variation of the service times. The mean queue length can then be computed by Little's Law.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .