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

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,...)成为有向非循环图中的节点,并根据您的节点定义节点之间的弧1,2,....

然后,您可以在拓扑上对图表进行排序(或使用基于搜索的方法,如BFS).在你的榜样,C<-A->B->D并E->F因此,A与E具有0深度,需要先运行.然后你可以运行F,B然后C并行运行D.

另外,看看PERT.

更新:

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

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

它首先找到根(没有传入边)节点(因为一个必须存在于DAG中).在你的情况下,那是A&E.这解决了需要完成的第一轮工作.接下来,根节点的孩子(B,C和F)需要完成.通过查询图表可以轻松获得此信息.然后重复该过程,直到找不到(完成)节点(作业).

Answer 2

给定项目之间的映射以及它们所依赖的项目,拓扑排序会对项目进行排序,以使项目不在其所依赖的项目之前.

这个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

输出的一行上的项目可以按任何子顺序处理,或者实际上并行处理; 只要在更高行的所有项目之前处理以下行的项目以保留依赖项.