Distribution of waiting time in queueing system

1.9k Views Asked by At

Suppose I'm in line at a bank. There are 4 bank tellers, and 12 people in line in front of me. All the tellers are idle in the beginning so the first 4 customers get processed immediately. Each customer takes a random amount of time to be processed, with time drawn from a normal distribution with mean 10 minutes and standard deviation 2 minutes. How long should I expect to wait before I get to a teller?

I coded up a simulation in R and found that in this case, the distribution of wait time has mean 26.6 and standard deviation 2.2. Is there any way to solve this analytically? I'm not very well-versed in queueing theory, so any references would be appreciated.

Edit: If changing the model in some way makes it easier (eg: exponential rather than normal distribution), then you are allowed to do so.

2

There are 2 best solutions below

0
On

If instead the service times are exponentially distributed, then the memoryless property means that you are essentially looking at a sum of $9$ variables distributed as exponential with rate $4r$, then three more that are distributed as exponential with rate $3r,2r,r$ respectively (decreasing because now some of the service is idle). All are independent because of the strong Markov property of the relevant Markov chain. Those first 9 can be straightforwardly written as a Gamma distribution; incorporating the other three is messier but still tractable.

0
On

I think Ian's answer refers to the time until the system clears (assuming no new arrivals). But the question was about waiting time until admission into service.

Assume all service times are iid exponential with rate $\mu$, $X_i\sim$exp$(\mu)$. As long as you are in the queue the departure rate is $4\mu$, because if there was an idle teller you would go to him. You have to wait for nine departures so the total time is an Erlang random variable (special case of Gamma) with parameters $(9,4\mu)$. The expected time until you start service is then $\frac{9}{4\mu}$.