algorithm - 优化算法来安排具有依赖性的任务？

Question

有些任务从文件中读取，进行一些处理并写入文件。这些任务将根据依赖关系进行安排。任务也可以并行运行，因此需要优化算法以串行运行相关任务，并尽可能并行运行。

例如:

1. A -> B
2. A -> C
3. B -> D
4. E -> F

所以运行它的一种方法是运行1、2 和 4 并联。其次是 3.

另一种方法是运行 1，然后并行运行 2、3 和 4。

另一个可以串行运行 1 和 3，并行运行 2 和 4。

有什么想法吗？

Answer 1

让每个任务(例如 A,B,...)成为 directed acyclic graph 中的节点并根据您的 1,2,... 定义节点之间的弧线.

然后您可以 topologically order您的图表(或使用基于搜索的方法，如 BFS )。在您的示例中，C<-A->B->D和 E->F所以，A & E深度为 0，需要先运行。然后你可以运行 F , B和 C并行后跟 D .

另外，看看 PERT .

更新:

你怎么知道 B优先级高于 F ？

这是用于查找排序的拓扑排序背后的直觉。

它首先找到根(没有传入边)节点(因为 DAG 中必须存在一个节点)。在你的情况下，这是 A & E .这解决了需要完成的第一轮工作。接下来，需要完成根节点(B、C 和F)的子节点。这很容易通过查询您的图表获得。然后重复该过程，直到没有要找到(完成)的节点(作业)。