Maximum degree of concurrency in task dependency graphs
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 $\alpha|\beta$ means parallel composition of task graphs and $\alpha\beta$ means every task in task graph $\alpha$ precedes every task in task graph $\beta$.  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önig's theorem to compute the witnesses by a perfect matching.

Some of these basic algorithms are already part of software toolkits, like the Graph CPAN module for Perl, and the Boost Graph Library for C++.