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



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}

  • $\begingroup$ 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$. $\endgroup$ – Whitesizzle Apr 13 '15 at 8:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.