An algorithm to maximize the number of parallel tasks

Question

I have a set of compute tasks I want to schedule, these tasks have dependencies and a task may not be executed until all its dependencies are executed.

The problem can be represented as a directed acyclic graph:

Scheduling graph

The current scheduler ensures correctness, and capable of culling unneeded tasks such as k in the previous graph (assuming the end goal is i).

I am struggling to find another equivalent algorithm to maximize number of tasks running in parallel (tasks on the same line may be executed in any order):

a, b, j
c
d
e, f, h, g
i

Flatten form, what is between () may be in any order and represent parallel tasks:

 (a, b, j), (c), (d), (e, f, h, g), (i)

The idea here I want to fill the compute engine with as much work as possible.

• dkaeae: How can you be processing "e" in the second step if there is a dependency to it from "d" (which is only executed in the third step)?
• Optidad: Can you give some precisions on the actual constraints ? You can execute any number of parrallel tasks ? All tasks have the same cost in time ? Your objective is to achieve $i$ task as soon as possible (can $j$ be executed a little later for instance as it is on a very short branch) ?
• user10655827: @dkaeae I am sorry, that was a mistake
• user10655827: @Vince There are no constraints on the number of tasks. Regarding j, no j should be executed as soon as possible. The idea here I want to fill the compute engine with as much work as possible.

Answer 1

From your initial DAG $G(E, V)$ You start reversing all edges to build a new DAG $G'(E, V')$. Then do a BFS from $i$ in $G'$ to remove any unneeded tasks (unreached nodes in the BFS). This step is $O(N)$ with $N = |V'|$, the number of edges.

From $G$, build the number of requirements of each task ($R(V)$) and at the same time the list $L$ of the tasks with no requirements. this takes $O(N)$.

Then you iterate on this pseudo-algorithm:

while(root is not executed)
 L' = empty list
 for v in L
 for each node v' with an edge in G' from v to v'
 R(v') -= 1
 if R(v') == O then add v' to L'
 execute all L in a parrallel step
 L = L'

this is $O(N)$.

• user10655827: Thank you! I have added a Python implementation of this algorithm.