qoutes中的并行性，因为我实际上并不是指并行编程(线程/分叉等)
目前正在处理依赖图问题，其中给定一个DAG(有向无环图)，其中每个顶点表示必须完成的任务，从一个顶点v到另一个顶点u的边意味着v必须在u完成之前完成。每个任务都需要一定的时间才能完成。
例： 依赖关系图
(这只是一个例子，程序应该能够解决任何DAG)
使用拓扑排序，我发现如果一次完成一个任务，则有多个订单来完成所有任务。但是，我有兴趣介绍可以同时启动和/或处理多个任务的想法。我假设无限的"人力"，这意味着可以同时处理任意数量的任务。我想找到一种方法在最快的时间内完成项目中的所有任务。
我的任务(顶点)类有以下变量(Java)：
class Task{
int id, time;
String name;
List<Task> outEdges;
List<Task> inEdges;
boolean isFinished;
Task(int id, String name, int time){
this.id = id;
this.name = name;
this.time = time;
isFinished = false;
outEdges = new ArrayList<Task>();
inEdges = new ArrayList<Task>();
//Tasks and edges between them are generated while reading from a file.
}
...
}
(以及获取/操作它们的方法) 图形本身由一系列任务表示。
我可以使用哪些概念/算法来做到这一点？
假设你的意思是，如果你的图中有一个从v到u的弧线，那么v必须先完成u然后才能开始。
这只是当您将图形视为项目优先级图时，查找最短的项目完成时间。给定节点 j(任务)的活动时间dj >= 0，设sj表示其开始时间。
然后，以下线性程序解决了您的问题
Minimize sN [i.e., minimize the starting time of the last activity]
such that sj >= si + di , forall (i,j) in graph [i.e., ensure starting time of jth activity is after completion of ith activity if j follows i in the precedence graph]
such that all si's >= 0 [i.e., all starting times are nonnegative. Without these constraints, problem is unbounded.]
在这里，为了方便起见，1和N分别是项目开始和结束时的虚拟活动，活动时间为0。1位于图形中的所有其他节点之前。N位于图形中所有其他节点的后方。
这可能取决于特定图形的结构。
如果只需要到达一个最终节点，则可以使用深度优先搜索等算法来提供事件序列。一旦可用，就没有平行化选项，因为存在严格的序列依赖关系。
如果需要到达多个节点(并且图形可在合理的时间内遍历)，则可以使用诸如广度优先搜索之类的算法来提供所需的序列。然后，假设您要到达 n 个不同的顶点。一个新的语义图(我们称之为g2)可以由到达所需顶点的常见路径部分来定义。这意味着新图形中的每个边都将由到达这些顶点的公共部分的串联组成。对于g2，所有边可以并行发射。
免责声明：以上不是严格证明的算法，只是一个实现思路。
我假设您还指定了"工人"(处理器)的 K 数来完成任务。也就是说，最多可以同时处理 K 个任务。显然，完成所有任务所需的时间将取决于K。
此问题称为优先约束调度。
如果工作线程 K 的数量大于或等于任务的数量 N，则 Tryer 概述的解决方案是正确的：依赖项 DAG 中最重路径的权重将为您提供所需的时间。(最重的路径有时称为关键路径，可以使用特定的最短路径算法在线性时间内计算。
如果 K = 1，正如您已经注意到的那样，您只需遵循拓扑顺序，所需的时间将是任务时间的总和。
不幸的是，在 1
可以严格证明，列表调度算法完成最后一个任务的时间T'最多为T*+P，其中T*为最优时间，P为关键路径的权重。因此，如果关键路径上的任务只占总数的一小部分，则算法将很好地工作。