I am re-posting the problem https://mathoverflow.net/questions/92783/random-task-scheduling-problem here because I think people here are more familiar with this topic.

Assume there are $m$ tasks, each task's working time conforms to some distribution, for instance an exponential distribution with mean $\lambda$. So let the r.v. $X_i$ is the working time of the $i$th task, and $\{X_i\}$ are i.i.d. random variables.

There are $n$ machines to do these tasks, the scheduling police is, once a task is finished on some machine, if there are still pending tasks, one of the pending tasks (randomly selected) will be scheduled to the idle machine immediately (ignore the scheduling latency here).

The finishing time of the system is defined to be the last job's finishing time which is defined to be a random variable $Y$. So my question is, what are the the distribution function of $Y$ and expectation of $\mathbb{E}(Y)$?

I am interested in the more general distribution of $X_i$, while the distribution of exponential is also welcomed. Papers about this problem is also very helpful to me.

  • $\begingroup$ It appears that you have crossposted this question simultaneously. While we don't mind a question being reposted, our site policy only permits a repost after sufficient time has passed and you have not obtained the desired answer elsewhere. I am closing the question since simultaneous crossposting duplicates effort and fractures discussion. Please wait a few days and then if your question is still not answered request a reopening by flagging the question for moderator attention (after summarizing relevant discussions from other sites). $\endgroup$ – Kaveh Apr 2 '12 at 5:29