$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}