问题描述：
有n tasks，在这些任务中，有one might be dependent on the others，这意味着如果A依赖于B，那么B必须在A完成之前完成。
1.想办法尽快完成这些任务吗？
2.如果是take parallelism into account，如何设计程序来完成这些任务？
问题：
显然，第一个问题的答案是，对这些任务进行拓扑排序，然后按顺序完成。
但是，如果考虑到并行性，该怎么做呢？
我的答案是，首先对这些任务进行拓扑排序，然后选择那些独立的任务并首先完成它们，然后选择并完成其余的独立任务…
我说得对吗？
拓扑排序算法可能会给你各种不同的结果顺序，所以你不能只取前几个元素，并假设它们是独立的。
我建议不要进行拓扑排序，而是根据传入依赖边的数量对任务进行排序。例如，如果你的图有A->B，A->C，B->C，D->C，你会把它排序为A[0]，D[0]，B[1]，C[3]，其中[i]是传入边的数量。
通过拓扑排序，你也可以得到A，B，D，C。在这种情况下，很难发现您可以并行执行A和D。
请注意，在任务完全处理后，您必须更新剩余的任务，特别是那些依赖于已完成任务的任务。然而，如果任务中的依赖项数量限制在相对较小的数量(比如几百个(，则可以很容易地依赖基数/桶排序，并保持排序结构在恒定时间内更新。
使用这种方法，您还可以在单个并行任务完成后轻松启动新任务。只需更新依赖项计数，并启动所有现在有0个传入依赖项的任务。
请注意，这种方法假设您有足够的处理能力来同时处理所有没有依赖关系的任务。如果你的资源有限，并且关心处理时间方面的最佳解决方案，那么你就必须投入更多的精力，因为问题变得NP难(正如arne已经提到的(。
因此，为了回答你最初的问题：是的，你基本上是对的，然而，你缺乏解释如何有效地确定这些独立任务(见我上面的例子(。
我会尝试在有向林结构中对它们进行排序，将任务执行时间作为边缘权重。从最重到最轻排序，从最重开始。使用这种方法，您可以同时检查循环依赖关系。
使用并行性，可以得到bin问题，这是NP难的问题。试着找出那个问题的近似解。
看看关键路径方法，它取自项目管理的are。它基本上做你需要的事情：给定有依赖性和持续时间的任务，它会产生需要多少时间，以及何时激活每个任务。
(*(请注意，该技术假设有无限数量的资源用于最优解。对于有限的资源，有贪婪算法的启发式算法，如：GPRW[当前+后续任务时间]或MSLK[最小总空闲时间]。
(*(还要注意，这需要知道[或至少估计]每项任务需要多长时间。