# Difference between greedy and work conserving scheduler for DAG

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?

$$T < (T_1-T_\infty) / m + T_\infty$$
$$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$$.