# Prove that $w/w_0$ (no idle over minimum possible) $\le 2-1/n$ for any set of tasks on an n processor system

$w/w_0$ $\le 2-1/n$

I've noticed this problem in a couple of discrete math and algorithm analysis textbooks. Many of them prove it for n=2, but I want to prove it for all n.

The idea is that we have a chain of tasks where some might be dependent on each other (e.g. we can't do task 2 until task 1 is finished). $w$ denotes the elapsed time if all tasks are executed with no intentional idle periods (i.e. a task starts execution as soon as a processor is ready to handle it), and $w_0$ is the elapsed time following the best possible schedule. Basically the greedy algorithm vs the optimal for task scheduling.

The solution with 2 processors considers idle periods $\phi_i$ and tasks that overlap the idle times on the other processor $T_{ik}$, for example $T_{11}$, $T_{12}$, and $T_{13}$ overlap $\phi_1$ below.

$-------|--\phi_1---|---T_{21}-T_{22}---|-\phi_i---|------$...

$------T_{11}-T_{12}-T_{13}----|-\phi_2-|---T_{i1}-T_{i2}---------$...

Based on these rules we can solve for the elapsed time with the greedy algorithm $w$:

$w= 1/2* [\sum (\mu*T_i) + \sum (\mu*\phi_i)]$ (half of task times + idle times)

$\le 1/2* [\sum (\mu*T_i) + \sum (\mu*T_k)]$ (half of task times + tasks during idle times)

and since the ideal time is at best half of the time for all tasks:

$w_0 \ge 1/2* \sum (\mu*T_i)$

and at best, the time for tasks to finish while one processor is idle:

$w_0 \ge \sum (\mu*T_k)$

Then $w \le w_0 +1/2w_0$

$w/w_0$ $\le 3/2$

But how can I extend this beyond 2 processors? For example with 3 processors, we can have 2 idle or 1 idle. Does this mean I need another term for each n that we add? Then how do we define $T_k$ relative to $\phi$, since we could now have both an idle period and a task overlapping $\phi$? I think I could get the pattern if I could figure it out for 3 processors.

For general $n$ we can define $T_k$ in the same way as for $n = 2$ as those jobs that are processed on one machine while at least one other machine is idle. Thus, while a job $T_k$ is running the idle time of the other machines is at most $(n - 1) \mu * T_k$. Therefore, you have to adapt your first inequality to \begin{align} w &= \frac{1}{n} \left[\sum (\mu * T_i) + \sum (\mu * \phi_i)\right] \\ &\leq \frac{1}{n} \left[\sum (\mu * T_i) + (n - 1) \sum (\mu * T_k)\right] \end{align} The two inequalities on $w_0$ still hold but the first one has to be adapted for the general case to \begin{align} w_0 \geq \frac{1}{n} \sum (\mu * T_i) \end{align} and we get \begin{align} w \leq w_0 + \frac{n - 1}{n} w_0 = \left(2 - \frac{1}{n}\right) w_0. \end{align}
• So any task that runs when any processor is idle is now in $T_k$? That is, if one processor were always idle, then the whole task chain would be in $T_k$? I understood the second equality for $w_0$ to mean "the time it would take to do all the tasks on one processor," so I thought perhaps it would have to change to accommodate the possibility of several processors active at once, but fewer than $n$. – Whitesizzle Apr 13 '15 at 8:25