Length of a queue

Question

Let's say we have a queue of independent events. The events are processed in the order of arrival, processing one event takes $t$ time.

Events arrive in average $N$ events per identity time.

What it the average length of the queue?

I am waiting up to three days for a company to process my request and wonder why the queue is so long (three days), while obviously processing one item should not take much time (it can be done in a minute, I think). So I want to see a formula for this. I do not need a proof.

Answer 1

In this situation, queue length will depend on the number of processors for queued events. Assuming there is one server:

Events arrive at $N$ events per hour: so $\lambda =\frac{1}{N}$
Average processing time of $t$: so $\mu = \frac{1}{t}$

the probability, $p$, that the server will be busy is therefore: $\frac{t}{N}$

We can use the properties of the exponential distribution to make observations on the queue length $L$ which is

$$L = \frac{p^2}{1-p} = \frac{\left(\frac{t}{N}\right)^2}{1-\frac{t}{N}}.$$

Here's a link to introductory queue theory

Answer 2

The Real Problem

Near the end of the original post we read:

I am waiting up to three days for a company to process my request and wonder why the queue is so long (three days), while obviously processing one item should not take much time (it can be done in a minute, I think).

You cannot expect to answer this question with the presented information.

Even with $t$ an $N$ given, you have not suggested to us how many servers are supporting the handling of these tasks, whether there is process sharing, whether there is scheduling, or whether this company even uses FIFO on their requests (e.g. maybe they have a priority system).

This is to leave aside whatever business process model they are using (and how compliant they are with following it).

Answer 3

Tyler Ever's answer assumes that we are dealing with an M/M/1, which may not be the case. Otherwise the equation

$$L = \frac{\left( \frac{t}{N} \right)^2}{ 1 - \frac{t}{N}}$$

(which is a special case of Kingman's formula) may not be valid. And from the phrasing it isn't; we actually have an M/G/1 queue model because the service times are not exponentially-distributed. That is if I take "an order takes $t$ units of time" then I'll take that mean they all do. The mean is different from the individuals: see Does The Average Person Exist?

According to the link they shared, we should rather use the Pollaczek–Khinchine formula

$$L_q = \rho + \frac{\rho^2 + \lambda^2 \text{Var}[S]}{2(1-\rho)}$$

where $\rho := \frac{t}{N}$ is the utilization parameter, $\lambda = \frac{1}{N}$ is the arrival rate, and the random variable $S$ is the service time.

Since we know that $S = t$ is constant, we also know that $\text{Var}[S] = 0$. So the expression simplifies to:

$$L_q = \frac{t \left(2 N - t\right)}{2 N \left(N - t\right)}$$

Although it is worth noting that the difference

$$D(t,N) = \frac{\left( \frac{t}{N} \right)^2}{ 1 - \frac{t}{N}} - \frac{t \left(2 N - t\right)}{2 N \left(N - t\right)} = \frac{t \left(2 N - 3 t\right)}{2 N \left(t - N\right)}$$

depends on $t$ and $N$.