优化算法以计划具有依赖性的任务？ [英] Optimized algorithm to schedule tasks with dependency?

问题描述

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

例如：

1. A-> B


2. A-> C


3. B- > D


4. E-> F

所以运行此方法的一种方法是运行
1、2& 4个并行。其次是3。

另一种方法可能是
运行1，然后运行2、3& ;；并行运行4。

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

有想法吗？

解决方案

让每个任务（例如 A，B，... ）是您的图表（或使用基于搜索的方法，例如 BFS ）。在您的示例中， C< -A-> B-> D 和 E-> F 这样， A & E 的深度为0，需要首先运行。然后可以并行运行 F ， B 和 C 其次是 D 。

此外，请查看 PERT 。

更新：

您如何知道 B 的优先级是否高于 F ？

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

它首先找到根节点（没有输入边缘）（因为DAG中必须存在一个）。您的情况是 A & E 。这样就解决了需要完成的第一轮工作。接下来，根节点的子节点（ B ， C 和 F ）需要完成。通过查询您的图形可以轻松获得。然后重复此过程，直到找不到（完成）节点（作业）为止。

There are tasks that read from a file, do some processing and write to a file. These tasks are to be scheduled based on the dependency. Also tasks can be run in parallel, so the algorithm needs to be optimized to run dependent tasks in serial and as much as possible in parallel.

eg:

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

So one way to run this would be run 1, 2 & 4 in parallel. Followed by 3.

Another way could be run 1 and then run 2, 3 & 4 in parallel.

Another could be run 1 and 3 in serial, 2 and 4 in parallel.

Any ideas?

解决方案

Let each task (e.g. A,B,...) be nodes in a directed acyclic graph and define the arcs between the nodes based on your 1,2,....

You can then topologically order your graph (or use a search based method like BFS). In your example, C<-A->B->D and E->F so, A & E have depth of 0 and need to be run first. Then you can run F,B and C in parallel followed by D.

Also, take a look at PERT.

Update:

How do you know whether B has a higher priority than F?

This is the intuition behind the topological sort used to find the ordering.

It first finds the root (no incoming edges) nodes (since one must exist in a DAG). In your case, that's A & E. This settles the first round of jobs which needs to be completed. Next, the children of the root nodes (B,C and F) need to be finished. This is easily obtained by querying your graph. The process is then repeated till there are no nodes (jobs) to be found (finished).

这篇关于优化算法以计划具有依赖性的任务？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！