How does variance in task completion time affect makespan?

Question

Let's say that we have a large collection of tasks $\tau_1, \tau_2, ..., \tau_n$ and a collection of identical (in terms of performance) processors $\rho_1, \rho_2, ..., \rho_m$ which operate completely in parallel. For scenarios of interest, we may assume $m \leq n$. Each $\tau_i$ takes some amount of time/cycles to complete once it is assigned to a processor $\rho_j$, and once it is assigned, it cannot be reassigned until completed (processors always eventually complete assigned tasks). Let's assume that each $\tau_i$ takes an amount of time/cycles $X_i$, not known in advance, taken from some discrete random distribution. For this question, we can even assume a simple distribution: $P(X_i = 1) = P(X_i = 5) = 1/2$, and all $X_i$ are pairwise independent. Therefore $\mu_i = 3$ and $\sigma^2 = 4$.

Suppose that, statically, at time/cycle 0, all tasks are assigned as evenly as possible to all processors, uniformly at random; so each processor $\rho_j$ is assigned $n/m$ tasks (we can just as well assume $m | n$ for the purposes of the question). We call the makespan the time/cycle at which the last processor $\rho^*$ to finish its assigned work, finishes the work it was assigned. First question:

As a function of $m$, $n$, and the $X_i$'s, what is the makespan $M$? Specifically, what is $E[M]$? $Var[M]$?

Second question:

Suppose $P(X_i = 2) = P(X_i = 4) = 1/2$, and all $X_i$ are pairwise independent, so $\mu_i = 3$ and $\sigma^2 = 1$. As a function of $m$, $n$, and these new $X_i$'s, what is the makespan? More interestingly, how does it compare to the answer from the first part?

Some simple thought experiments demonstrate the answer to the latter is that the makespan is longer. But how can this be quantified? I will be happy to post an example if this is either (a) controversial or (b) unclear. Depending on the success with this one, I will post a follow-up question about a dynamic assignment scheme under these same assumptions. Thanks in advance!

Analysis of an easy case: $m = 1$

If $m = 1$, then all $n$ tasks are scheduled to the same processor. The makespan $M$ is just the time to complete $n$ tasks in a complete sequential fashion. Therefore, $$\begin{align*} E[M] &= E[X_1 + X_2 + ... + X_n] \\ &= E[X_1] + E[X_2] + ... + E[X_n] \\ &= \mu + \mu + ... + \mu \\ &= n\mu \end{align*}$$ and $$\begin{align*} Var[M] &= Var[X_1 + X_2 + ... + X_n] \\ &= Var[X_1] + Var[X_2] + ... + Var[X_n] \\ &= \sigma^2 + \sigma^2 + ... + \sigma^2 \\ &= n\sigma^2 \\ \end{align*}$$

It seems like it might be possible to use this result to answer the question for $m > 1$; we simply need to find an expression (or close approximation) for $\max(Y_1, Y_2, ..., Y_m)$ where $Y_i = X_{i\frac{n}{m} + 1} + X_{i\frac{n}{m} + 2} + ... + X_{i\frac{n}{m} + \frac{n}{m}}$, a random variable with $\mu_Y = \frac{n}{m}\mu_X$ and $\sigma_Y^2 = \frac{n}{m}\sigma_X^2$. Is this heading in the right direction?

Answer 1

As $m = k \times n$, we can look at this in terms of $k$ and $n$ instead of $n$ and $m$. Let's say $T_i$ is the time it takes the $i$-th processor to finish its work.

As $n$ grows, the probability that $T_i$ = $5k$ (the processor was assigned only $T=5$ tasks) for some $i$ approaches $1$, so makespan being defined as $\mathrm{max}(T_i)$, $E[M]$ approaches $5k$.

For the second scenario this is $4k$ so increasing the number of processors makes the 4–2 split better.

What about $k$ — increasing the number of tasks per processor? Increasing $k$ has the opposite effect, it makes it less likely to have a processor with an unlucky set of tasks. I'm going home now but I'll come back to this later. My "hunch" is that as $k$ grows, the difference in $E[M]$ between the 4–2 split and the 5­­­–1 split disappears, $E[M]$ becomes the same for both. So I would assume that 4–2 is always better except maybe for some special cases (very small specific values of $k$ and $n$), if even that.

So to summarize:

• Lower variance is better, all else being equal.
• As the number of processors grows, lower variance becomes more important.
• As the number of tasks per processor grows, lower variance becomes less important.

Answer 2

I find that heuristic arguments are often quite misleading when considering task scheduling (and closely related problems like bin packing). Things can happen that are counter-intuitive. For such a simple case, it is worthwhile actually doing the probability theory.

Let $n = km$ with $k$ a positive integer. Suppose $T_{ij}$ is the time taken to complete the $j$-th task given to processor $i$. This is a random variable with mean $\mu$ and variance $\sigma^2$. The expected makespan in the first case is $$ E[M] = E[\max \left\{\sum_{j=1}^k T_{ij} \mid i=1,2,\dots,m \right\}]. $$ The sums are all iid with mean $k\mu$ and variance $k\sigma^2$, assuming that $T_{ij}$ are all iid (this is stronger than pairwise independence).

Now to obtain the expectation of a maximum, one either needs more information about the distribution, or one has to settle for distribution-free bounds, such as:

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

which can be applied if the processor-wise sums are iid. This would not necessarily be the case if the underlying times were just pairwise independent. In particular, by Theorem 1 the expected makespan is bounded above by $$ E[M] \le k\mu + \sigma\sqrt{k}\frac{n-1}{\sqrt{2n-1}}. $$ Downey also gives a particular distribution achieving this bound, although the distribution changes as $n$ does, and is not exactly natural.

Note that the bound says that the expected makespan can increase as any of the parameters increase: the variance $\sigma^2$, the number of processors $n$, or the number of tasks per processor $k$.

For your second question, the low-variance scenario resulting in a larger makespan seems to be an unlikely outcome of a thought experiment. Let $X = \max_{i=1}^m X_i$ denote the makespan for the first distribution, and $Y = \max_{i=1}^m Y_i$ for the second (with all other parameters the same). Here $X_i$ and $Y_i$ denote the sums of $k$ task durations corresponding to processor $i$ under the two distributions. For all $x \ge k\mu$, independence yields $$ Pr[X \le x] = \prod_{i=1}^m Pr[X_i \le x] \le \prod_{i=1}^m Pr[Y_i \le x] = Pr[Y \le x]. $$ Since most of the mass of the probability distribution of the maximum will be above its mean, $E[X]$ will therefore tend to be larger than $E[Y]$. This is not a completely rigorous answer, but in short, the second case seems preferable.