Difference between greedy and work conserving scheduler for DAG

Question

For both schedulers I have found the definition, that no processor stays idle, if there is more work it can do.

However, I found two different upper bounds on the computation time of $T$. For the following equations $T_{\infty}$ is the computation time on infinite processors and $T_1$ is the duration on one processor.

[1] Greedy Schduler (Theorem 1): $T = T_1/m + T_\infty$

[2] Work-Conserving Scheduler (Theorem 1): $T = (T_1-T_\infty)/m + T_\infty$

Both consider the scheduling of directed acyclic graphs where each vertex $v$ represents a task with a certain execution time and the edges represent precendence constraints between the tasks. I.e. task $v_i$ has to execute before task $v_j$ if there exists an edge $(v_i,v_j)$ between those two tasks. I have x threads that can execute those tasks. However, I am not 100% sure if [2] considers preemptive scheduling for their upper bound, but it does seem to be the case for their theorem 1.

In this presentation (page 41) I have found both equations for an upper bounds of the greedy scheduler.

Is there by definition any difference between the two schedulers?

Answer 1

If I understand well, it is the same scheduling method with different names. I think Work-conserving Scheduler is the more "official" one. "greedy" can indeed qualify many aspects of the problem and one should always precise which. greedy algorithm is a paradigm not a specific method for a specific problem.

Anyway about the upper-bound, the presentation of your last link says that it is:

$T < (T_1-T_\infty) / m + T_\infty$

but that a simpler one is generally used:

$T < T_1 / m + T_\infty$

Of course the latter is greater than the former but both are true. Also note that they are both equivalent to $T_\infty$ when $m$ tends to $+\infty$.