Find execution time in DAG of tasks

Question

I have to find the difference between the worst and the best possible execution time in a DAG (directed acyclic graph) of tasks.

The DAG of tasks looks like the following: https://i.stack.imgur.com/IuES0.png

I already know that the worst possible execution time is 5 and the best possible execution time is 4. So the answer (the difference) is 1.

But I can't figure out how it is calculated.

In relation to what I have read, I guess the two vertices in the bottom are both initial vertices, since you should be able to get to all the other vertices from start.

I would really appreciate if somebody could explain to me how the worst and the best possible execution times are calculated.

Answer 1

The graph contains a path of four vertices, so you need at least 4 units of time regardless of the order of execution. It is easy to find an execution that is completed in 4 units of time.

As for the upper bound, there are 7 vertices, so you need at most 7 units of time. However, initially you have three possible start vertices, so in particular you will start by processing two tasks at once. Thus, the maximum amount of time needed is 6. Now where can we find another improvement in our upper bound? Think about it for yourself. In case you can't figure it out, you may consult the following hints and/or solution. But not after you've tried to figure it out for yourself for at least, say, 10 minutes. ;-)

Hint 1:

We have to prove that there will be another moment in time when two tasks are processed simultaneously, regardless of the order of execution.

Hint 2:

Try every order of execution you can think of. There is one vertex which is always processed simultaneously with another vertex, thereby saving one unit of time. Can you explain why this happens?

Solution:

Note that there is one vertex $v$ with out-degree 2. Let us call its neighbours $l$ (top left) and $r$ (above right). When we finish processing $v$, its left neighbour $l$ becomes available immediately. Furthermore, either $r$ becomes available or $r$ is still waiting for one the rightmost initial process to finish. Either way, $l$ and another process are available at the same time, so two tasks will be processed simultaneously.