Random Task Scheduling Problem

Question

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.

Answer 1

The case where $n > m$ is "easy": if $F$ is the distribution function of each of the $m$ iid random variables, then the distribution function of the maximum is $F^m$. Of course, $F^m$ may be difficult to compute, so even bounding the expectation of the makespan can be tricky.

• Peter J. Downey, Distribution-free bounds on the expectation of the maximum with scheduling applications, Operations Research Letters 9, 189–201. doi:10.1016/0167-6377(90)90018-Z

For the general case where $n \le m$ it seems difficult to obtain closed-form solutions.

Using Kendall's notation for queueing systems, this is a D/GI/n system, or in the extended notation D/GI/n/m/m/FIFO. Nothing is lost by requiring the tasks to form a queue. However, I do not know whether systems with such one-shot arrival distributions have been studied in the queueing theory literature.

The minimum of $n$ exponentially distributed random variables is also exponentially distributed. This does suggest a procedure to efficiently simulate the system, from which one can generate a numerical approximation to the distribution, but I don't immediately see how to obtain a closed form solution.

Suppose you choose a random partition of the tasks into $n$ blocks. This may fail to correspond to a valid schedule, since the block with the largest sum may still exceed the smallest block sum, even with a task removed. This suggests the following correction procedure. For the block with the largest sum, remove one of the tasks. If the sum without this task is no larger than the smallest block sum, then put the task back and stop. Otherwise put the task into the block with the smallest sum, and iterate. This procedure yields a valid schedule.

Now consider the maximum block sum. In the uncorrected case, this will be an upper bound for the makespan. As far as I can tell, it then seems feasible to find the distribution of the correction that is applied, as well as the distribution of the maximum block sum over all random partitions (though probably not in closed form). If $n \lt \lt m$ this might provide a reasonable way to go, perhaps in combination with bounding techniques for the distribution of the maximum.

---

Edit: This report by Coffman and Whitt seems to consider the precise question you ask. They say that multiprocessor scheduling is the generic name for this class of problems, and state: "Because of the difficulty of exact analysis, the results take the form of limits". There is also a published version from 1996 which explicitly focuses on Markov chain approaches to study the asymptotic behaviour.

• E. G. Coffman, Jr. and Ward Whitt, Recent Asymptotic Results in the Probabilistic Analysis of Schedule Makespans. Unpublished, 1993.
• E. G. Coffman, Jr. and Ward Whitt, Stochastic limit laws for schedule makespans. Communications in Statistics. Stochastic Models 12, 215–243, 1996. doi:10.1080/15326349608807382 (preprint)

Answer 2

For exponential random variables, a simulation isn't needed. For $m>n$, $Y$ is the sum of the lengths of the periods with and without tasks waiting. These pieces are independent and can be recognized as a gamma distribution $\Gamma(m-n,1/(n\lambda))$ and the maximum of $n$ exponential random variables, which has cdf $(1-\exp(-\lambda x))^n, x>0$. So, it's easy to work out the mean $\lambda^{-1}((m-n)/n + (1/n+1/(n-1)+ ... +1/2 + 1))$, and to write a convolution integral for the density.

For general distributions, you need to narrow the scope of your question.

Answer 3

I saw the question in the cstheory forum but before I could answer the question was closed. So I am posting my answer here.

Here is an idea which might work only when $X_i$ are exponential. (Note that since $X_i$ are i.i.d it is enough to assume that you schedule an arbitrary job instead of a randomly selected job).

For simplicity let me assume $\lambda=1$. It is simple to show that exponential random variables are memory less. i.e $Pr[X_i\leq a+b | X_i>a]=Pr[X_i\leq b]$. This might help us in writing a differential equation. Let me define $F(m,n,x)=Pr[Y\leq x]$ when the given number of jobs is m and machines is n.

Case 1) $m\leq n$. Then $Y$ is just a maximum over $m$ i.i.d random variables.

Case 2) $m>n$. Now let us make some crude approximations and try to get a differential equation. Consider the first $\partial x$ amount of time. Then

\begin{equation} F(m,n,x)=\sum_{i=1}^n Pr[i\textrm{ jobs finish in time }\partial x]F(m-i,n,x-\partial x) \end{equation}

\begin{equation} F(m,n,x)= (1-n \partial x)F(m,n,x-\partial x)+n F(m-1,n,x-\partial x)\partial x+ (\partial x)^2\textrm{error terms} \nonumber \end{equation}

As $\partial x\rightarrow 0$ we get that the differential equation $\frac{\partial F(m,n,x)}{\partial x}=n(F(m-1,n,x)-F(m,n,x))$. I haven't tried solving this differential equation. Hopefully it is solvable.