Where does the properties of queue systems come from?

Question

I just started a course on queue theory, yet equations are given for granted without any demonstrations, which is very frustrating... Thus

1. Why is the mean number of people in a queue system following an $M/M/1$ system

$$E(L)=\frac{\rho}{1-\rho}$$

with $\rho=\frac{\lambda}{\mu}$ with $\lambda$ the clients arrival rate and $\mu$ the service rate.

2. And the mean number of people waiting in the queue:

$$E(L^q)=\frac{\rho^2}{1-\rho}$$

Answer 1

For every common queue system you can follow this route:

1. Set up the balance equations: Inflow equal outflow in steady state.

2. Solve the balance equations. Always straight forward.

3. Calculate $p_0$ and $E[L]$

And its not hard to see that this gives $E[L]$, right?

The fact that the first sum to 1 gives $p_0$

$$\sum_ n P_n = 1$$

$$E[L] = \sum_ n nP_n$$

The range of the sum depends on which kind of queue you have. In your case its from $0$ to $\infty$ because you have unlimited places in the queueing system. If its limited to K places you sum to K.

4. Once you have $E[L]$ most of what you are interested in follows from simple and obvious equations.

E.g. $E[L^{q}]$ follows from:

(omitting the E[] from here on as im used to)

$L = L_q + L_s$ (average number of people in the queue plus average number of people getting service)

$L_s = W_s*\lambda$ (average waiting time getting service times the inflow rate. $\lambda =\lambda_e = \lambda*(1-p_k)$ when you have a limited number of places in the queue)

$W_s = 1 / \mu$ ($\mu$ mean service time)

And with those equations you can solve for $L_q$

Answer 2

The $M/M/1$ queue can be modelled as a so called birth/death process. Since the arrivals are a Poisson process (the interarrival times are exponential) and the departures (service times) are exponentially distributed this will lead to some nice properties.

The birth/death process

If we call $X$ the state of the system, with the corresponding value being the number of customers in the system, we can start working towards long-term probabiltiies of the system being in a specific state. Once we have this we can use this to determine all kinds of metrics like $\mathbb{E}(L)$ and $\mathbb{E}(L^q)$.

The idea is that customers arrive and leave one at a time, this means the system can only change by one. Once this is established we can use the fact that between every two neighbour states the rate in has to be the same as the rate out. If we name the steady-state probabilities $\pi_i$ where $i$ is the number of customers, $\pi_i$ is the expected fraction of time the system is in state $i$. Using the rate in/rate out theorem we can get to a system of equations:

$\lambda\pi_0 = \mu\pi_1$

$\lambda\pi_1 = \mu\pi_2$

...

Rewriting this gives us:

$\pi_1 = \frac{\lambda}{\mu}\pi_0 = \rho\pi_0$

$\pi_2 = \frac{\lambda}{\mu}\pi_1 = \frac{\lambda^2}{\mu^2}\pi_0 = \rho^2\pi_0$

...

Now we have all the steady-state probabilities in terms of $\pi_0$, we also know that these have to add up to 1 since they are probabilities. This means:

$\pi_0 = \{\sum_{i=0}^\infty\rho^i\}^{-1}$

You can find a picture of this kind of system at Wikipedia (I don't know if I can post that here)

With these probabilities you can calculate all kind of expected values.

Answer 3

There is a pretty good series of video lectures on youtube that might help you out.