Suppose I have $k$ tasks that I can run independently on $n$ machines where $k\geq n$. Let $t\_i\in\mathbb{N}$ be the number of seconds that task $i$ takes to be done on any machine (for any $i\in[k] :=\{0,\ldots,k-1\}$). I want to assign the tasks to the $n$ machines such that the parallel run-time gets minimized. This goal is described below in a more formal way.


For any "machine assignment" $f: [k]\to [n]$ and $j\in[n]$ we let the *total running time on machine* $j$ be $T\_j = \sum\{t\_i: i\in [k] \land f(i) = j\}$, and let the *parallel running time* be $$M(f) = \max\{T\_j: j\in [n]\}.$$ The *best parallel running time* is defined by $$\text{BR}((t\_i)) := \min\{M(f): f: [k]\to [n]\}.$$


Now, suppose the times are ordered descendingly: $t\_{i+1}\geq t\_i$ for all $i\in[k-1]$. We look at the following simple machine assignment $f\_s:[k]\to [n]$: $f\_s(i) = i$ for $i \leq n-1$, and then $f\_s(n) = n-1, f\_s(n+1) = n-2,\ldots$, or more formally:


1. $f\_s(i) = i \mod n$ if the integer part of $i/n$ is even;
2. $f\_s(i) = (n-1) - (i \mod n)$ otherwise.


**Question.** Given $n\in\mathbb{N}$, is there a constant $D\_n$ such that $$\frac{M(f\_s)}{\text{BR}((t\_i))} \leq D\_n,$$ independent of the choice of the number $k$ of tasks, and the running times $t\_i$?



$k$ tasks on $n$ machines
Let me quote a really great computer science professor (<http://www.cs.ucsb.edu/~teo/>), who taught this bound and others in one of his lectures: "Two times optimum".


In fact, we always have
$$D\_n = 2 - \frac{1}{n}$$
as a bound.
To see this, let's first look at the worst thing that can happen with $M(f\_s)$: While scheduling the first $k-2$ tasks, it turns out that they all end at the same time. Thus, the last one (and longest one!) is executed all by itself.
This gives us as bound
$$M(f\_s) \leq \frac{\sum\_{i=0}^{k-2} t\_i + nt\_{k-1}}{n}.$$


This bound can be rewritten as
$$M(f\_s) \leq \frac{\sum\_{i=0}^{k-1} t\_i}{n} + \frac{n-1}{n}t\_{k-1}.$$


Now the first of these two terms is a lower bound for $BR((t\_i))$, being achieved when we have no idle time at all, and $t\_{k-1}$ is of course also a lower bound of $BR((t\_i))$, you will need to run this task at some point.


Thus, we get that


$$\frac{M(f\_s)}{BR((t\_i))} \leq 1 + \frac{n-1}{n} = 2 - \frac{1}{n}.$$


To show that this bound is tight, take $k = (n-1)n+1$, $t\_{k-1} = n$ and $t\_i = 1$ for all other $i$. Then the optimal solution will have running time $n$ (put the long one on a single processor and divide the rest), while $M(f\_s)$ will give a running time of $n-1+n$ - first filling all processors with short tasks, then running the longest in the end. Thus, the fraction will be 
$$\frac{n-1+n}{n} = 2 - \frac{1}{n}$$
in this case and the above bound for $D\_n$ is hence tight.


