Suppose we have a DAG of tasks:
Arrows represent flow (reversed dependencies: 8 must be run after 7). Some of the tasks (like 4, 5, 6) can be run in parallel (Par block). Dependent tasks (like 7, 8, 9) must be run sequentially (Seq block).
I need to parse this DAG into recursive structure of Seq and Par blocks (collections). DAG from the image above may be represented by the following structure:
Seq( 1, 2, Par( Seq(7, 8, 9), Seq( 3, Par(4, 5, 6), 10 ) ) )
Each DAG may be represented by a set of Seq-Par structures. I want to search for the most optimal. Optimality criteria — run in parallel as much as possible (without breaking dependencies).
More on optimality criteria: all tasks' have the same execution time
T. Execution time of
Seq(1, 2 ... N) equals to
N * T.
Par(1, 2 ... N) = T.
I believe, that this task is pretty well-known and simple. Can you, please, name some algorithm solving this problem.
If we add edge from 7 to 4 (proposal from comments), then one of representations may be:
Seq( 1, 2, Par( 7, 3 ), Par( Seq(8, 9), Seq( Par(4, 5, 6), 10 ) ) )