Prove a $M/D/1$ has the smallest waiting time among $M/G/1$

51 Views Asked by At

Fix $\lambda, \rho = \lambda E[S], \rho < 1$

Use the Pollaczek-Khinchine formula for an $M/G/1$ system $$ w^Q = \frac{\lambda E[S^2]}{2(1 - \rho)} $$

To show that if we take the service time to be deterministic that is, $S = d (constant)$ this distribution of $S$ gives the shortest waiting time

Since $E[S] = d$, and $E[S^2] = d^2$ the $P-K$ formula gives:

$$ w^Q = \frac{\lambda d^2}{2 - \lambda d} = \frac{\rho}{1 - \rho} \frac{d}{2} $$

Then to show this is the smallest possible a classmate said to look at the variance

$$ E[S^2] = E[S]^2 + VAR[S] $$

Since $VAR[S] \geq 0$ this gives the inequality

$$ E[S^2] \geq E[S]^2 $$

But how from either of these two results $w^Q$ or the above inequality did she conclude that the constant service time has the shortest waiting time?

1

There are 1 best solutions below

0
On BEST ANSWER

Assuming $E[S]$, $\lambda$ and $\rho$ are all constant and $\lambda \gt 0$ and $\rho \lt 1$

then $\dfrac{\lambda E[S^2]}{2(1 - \rho)} \ge \dfrac{\lambda E[S]^2}{2(1 - \rho)}$, with equality if and only if $VAR[S]=0$, i.e. the service time is almost surely constant, so a deterministic service time minimises the expected waiting time (for a given average service time)