3

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.

Bai Li
  • 131
  • 1
    Theoretically speaking this is a very weird problem because there is a positive, if small, probability that a teller takes negative time to serve a customer. The other difficulty is that this is not memoryless, so you cannot "restart" the process when a teller finishes with a customer--you have to keep track of how long that took. – Ian Aug 16 '17 at 14:48
  • True, the normal distribution can produce arbitrarily large negative values. I'm not sure I understand what the second difficulty is. I'm trying to understand the differences between these two systems, is there any similar "standard" formulation that avoids these difficulties? – Bai Li Aug 16 '17 at 15:25
  • 1
    Yes, everything I just said disappears if the service times are exponentially distributed. – Ian Aug 16 '17 at 15:38
  • Sure, I will accept an answer that uses an exponential distribution, if it makes the problem better defined. – Bai Li Aug 17 '17 at 10:55

2 Answers2

0

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.

Ian
  • 101,645
0

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}$.

QQQ
  • 751