24

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

例如：

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

所以运行它的一种方法是并行运行 1、2 和 4。紧随其后的是 3。

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

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

有任何想法吗？

4

5 回答 5

14

让每个任务（例如A,B,...）成为有向无环图中的节点，并根据您的1,2,....

http://en.wikipedia.org/wiki/Topological_sorting

然后，您可以对图形进行拓扑排序（或使用基于搜索的方法，如BFS）。在您的示例中，C<-A->B->D&的深度为 0，需要先运行。然后就可以运行了，并在后面跟着并行。E->FAEFBCD

另外，看看PERT。

更新：

你怎么知道是否B有比 更高的优先级F？

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

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

于 2013-08-19T13:25:45.753 回答
9

给定项目和它们所依赖的项目之间的映射，拓扑排序对项目进行排序，以便没有项目位于它所依赖的项目之前。

这个 Rosetta 代码任务有一个Python 解决方案，它可以告诉您哪些项目可以并行处理。

鉴于您的输入，代码变为：

try:
    from functools import reduce
except:
    pass

data = { # From: http://stackoverflow.com/questions/18314250/optimized-algorithm-to-schedule-tasks-with-dependency
    # This   <-   This  (Reverse of how shown in question)
    'B':         set(['A']),
    'C':         set(['A']),
    'D':         set(['B']),
    'F':         set(['E']),
    }

def toposort2(data):
    for k, v in data.items():
        v.discard(k) # Ignore self dependencies
    extra_items_in_deps = reduce(set.union, data.values()) - set(data.keys())
    data.update({item:set() for item in extra_items_in_deps})
    while True:
        ordered = set(item for item,dep in data.items() if not dep)
        if not ordered:
            break
        yield ' '.join(sorted(ordered))
        data = {item: (dep - ordered) for item,dep in data.items()
                if item not in ordered}
    assert not data, "A cyclic dependency exists amongst %r" % data

print ('\n'.join( toposort2(data) ))

然后生成此输出：

A E
B C F
D

输出的一行中的项目可以按任何子顺序进行处理，或者实际上是并行处理；只要在后续行的项目之前处理较高行的所有项目以保留依赖关系。

于 2013-08-20T05:19:06.230 回答
2

您的任务是一个（希望）没有循环的有向图。

我包含sources和wells（源是不依赖的任务（没有入站边缘），井是不解锁任务的任务（没有出站边缘））。

一个简单的解决方案是根据任务的有用性（让我们称之为U.

通常，从井开始，它们很有用U = 1，因为我们希望它们完成。

将所有井的前辈放入L 当前正在评估的节点列表中。

然后，取 中的每个节点L，它的U值是依赖于他的节点的值的总和U+1。将当前节点的所有父节点放入L 列表中。

循环直到所有节点都被处理。

然后，启动可以启动且U价值最大的任务，因为它会解锁最多的任务。

在你的例子中，

U(C) = U(D) = U(F) = 1
U(B) = U(E) = 2
U(A) = 4

这意味着如果可能，您将首先从 E 开始 A，然后是 B 和 C（如果可能），然后是 D 和 F

于 2013-08-19T13:28:41.223 回答
1

首先生成任务的拓扑排序。在这个阶段检查周期。此后，您可以通过查看最大反链来利用并行性。粗略地说，这些是任务集，它们的元素之间没有依赖关系。

从理论角度来看，本文涵盖了该主题。

于 2013-08-19T13:39:34.683 回答
0

不考虑问题的串行/并行方面，这段代码至少可以确定整体串行解决方案：

def order_tasks(num_tasks, task_pair_list):
    task_deps= []
    #initialize the list
    for i in range(0, num_tasks):
        task_deps[i] = {}

    #store the dependencies
    for pair in task_pair_list:
        task = pair.task
        dep = pair.dependency

        task_deps[task].update({dep:1})

    #loop through list to determine order
    while(len(task_pair_list) > 0):
        delete_task = None

        #find a task with no dependencies
        for task in task_deps:
            if len(task_deps[task]) == 0:
                delete_task = task
                print task
                task_deps.pop(task)
                break

        if delete_task == None:
            return -1

        #check each task's hash of dependencies for delete_task
        for task in task_deps:
            if delete_key in task_deps[task]:
                del task_deps[task][delete_key]

    return 0

如果您更新检查已完全满足的依赖项的循环以遍历整个列表并同时执行/删除不再具有任何依赖项的任务，这也应该允许您利用完成任务平行。

于 2014-12-22T23:00:19.247 回答