I\'ve been researching ways of modeling and executing tasks which are dependent

Question

I've been researching ways of modeling and executing tasks which are dependent on each other (but in an acyclic way) and came up with task graphs. But the question that's bugging me is how can I find out the maximum degree of concurrency in a given task graph.

In my case, I'm talking of a relatively small graph, around 100 nodes, but nodes, representing tasks, are long running tasks. So the occuracy, more then complexity of such an algorithm would matter.

Assuming I came up of such a degree, the second problem, is how should I distrubute tasks? I've read about topological sort, and transforming the result in a list of sets, with each set being run in parallel. But again, I suspect if this is the best approach.

Explanation / Answer

If you turn an activity-on-node task graph into a partial order (by taking the transitive closure), then the largest independent set of tasks is what you are looking for.

(Taking a topological sort, as suggested in another answer, does not work in general. Consider the series-parallel task graph ((a|b)c)|(d(e|f)), where ?|? means parallel composition of task graphs and ?? means every task in task graph ? precedes every task in task graph ?. Here {a,b,e,f} is the largest independent set, yet the topological sort will produce {a,b,d}.)

Although finding largest independent sets is NP-complete in general, it can be done quickly for partial orders. This starts by noting the equivalence of an independent set in a poset with a set of witnesses that realise the width of the poset, and applying K

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.