# Estimation of average waiting time

I'm simulating a procedure that assigns tasks to servers and want to estimate the average waiting time until a task is served (finds a free server). This procedure runs periodically, thus every task that is rejected in a run can try in the next runs until it finds a free server. The inter-arrival times of tasks follow an exponential distribution. Between runs, some tasks may finish.

Is there a way to estimate the average waiting time of tasks?

• Welcome to CS.SE! You say you're writing a simulation. One way is to run the simulation and measure what the average waiting time is in the simulation. Is that not what you are asking? Is there a reason you have rejected that approach? Alternatively, you could try to figure out whether this case can been analyzed using tools from queuing theory, but that might be harder. – D.W. May 22 '17 at 15:55
• @D.W. I'm interested in deriving this value using a formula. With queuing theory, I should model the process as a queue, there are lots of types of queues. Any hint on what type of queue do I need? – Tester May 22 '17 at 16:18
• @Tester Well, are you simulating it or modelling it? Those are two rather different things. – David Richerby May 22 '17 at 17:03
• @ David Richerby Both, but I'm asking about the model. I thought there were some formulas that could give me the average waiting time but it seems that I need queuing theory. – Tester May 23 '17 at 8:30
• You need to know the distribution of service time. – Thumbnail May 23 '17 at 18:18

If tasks arrive faster than they can be dealt with, average waiting time is unbounded.

You can probably adapt the Pollaczek–Khinchine formula to give an analytic answer to your question:

$$L = \rho + \frac{\rho^2 + \lambda^2 \operatorname{Var}(S)}{2(1-\rho)}$$

where

• $L$ is the mean queue length;

• $\lambda$ is the arrival rate of the Poisson process;

• $1/\mu$ is the mean of the service time distribution $S$;
• $\rho={\lambda \over \mu}$ is the utilization; and
• $Var(S)$ is the variance of the service time distribution $S$.
• It seems that this formula is what I need, thank you. – Tester May 25 '17 at 9:20
• @Tester My pleasure. I hadn't understood its power or scope before. – Thumbnail May 25 '17 at 12:54