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?
Estimation of average waiting time
algorithm analysis
If tasks arrive faster than they can be dealt with, average waiting time is unbounded. You can probably adapt the PollaczekKhinchine 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$.