$k$ tasks on $n$ machines 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:


*

*$f_s(i) = i \mod n$ if the integer part of $i/n$ is even;

*$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$?
 A: 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.
