0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W. May 22 '17 at 15:55
  • $\begingroup$ @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? $\endgroup$ – Tester May 22 '17 at 16:18
  • 1
    $\begingroup$ @Tester Well, are you simulating it or modelling it? Those are two rather different things. $\endgroup$ – David Richerby May 22 '17 at 17:03
  • $\begingroup$ @ 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. $\endgroup$ – Tester May 23 '17 at 8:30
  • $\begingroup$ You need to know the distribution of service time. $\endgroup$ – Thumbnail May 23 '17 at 18:18
0
$\begingroup$

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$.
$\endgroup$
  • $\begingroup$ It seems that this formula is what I need, thank you. $\endgroup$ – Tester May 25 '17 at 9:20
  • $\begingroup$ @Tester My pleasure. I hadn't understood its power or scope before. $\endgroup$ – Thumbnail May 25 '17 at 12:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.