2
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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