Scheduling task optimization

Question

I have the acyclic directed graph of tasks I want to perform. Each edge of the graph is a dependency, e.g. task 4 could be performed only after 1 and 2 completed.

0
`----> 1 ------------> 4 ---> 7
` ^ ^
`---> 3 | |
` `------> 2 -----/ |
` `------> 5 ----------- /
` `------> 6 ---------- /
`
`--> 8
 `------> 9
 `------> 10
 `------> 11

I need to perform all tasks consequently but with optimizations like running tasks in parallel where it is possible.

Topological sorting allows me to build just a sequence of tasks execution:

0, 1, 3, 8, 2, 5, 6, 9, 10, 11, 4, 7

But I need something like:

0, [1, 3, 8], [2, 5, 6, 9, 10, 11], 4, 7
// [...] - means parallel processing

Could you recommend any algorithm to achieve this?

• pprishchepa: Here is my implementation in golang: gist.github.com/PavelPrischepa/1435fb0b6d6319ba4974d81dba798021 And here play.golang.org/p/_cxtoTNkrhT

Answer 1

When you compute the topological ordering, you usually select one node with no predecessor and remove it from the graph. Instead you can scan the whole list of vertices and select all source vertices and remove them at once, only then you update the degree of the remaining vertices. The groups of vertices you remove together represent tasks that can be executed in parallel.

Note: As it stands now, all your tasks take the same amount of time. In reality however tasks started at the same time aren't finished at the same time. You maybe want to have a look into the Program evaluation and review technique

• pprishchepa: I use the ready-to-go implementation of topological ordering godoc.org/github.com/yourbasic/graph#TopSort, so I'll dive into and try to fork and rework this implementation for my needs. Thanks for your suggestion, Albjenow!