代码之家 › 专栏 › 技术社区 › Yetanotherjosh

将工作流DAG转换为并行资源分配的算法?

directed-acyclic-graphs parallel-processing graph algorithm

Yetanotherjosh · 技术社区 · 14 年前

假设我有一个图,其中节点是各种类型的工作负载,边是工作负载之间的依赖关系。(这是一个DAG,因为循环依赖项不能存在。)

某些工作负载类型可以赋予任何代理,其他工作负载类型必须赋予特定代理,其他工作负载类型必须赋予特定代理组中的一个代理。

如何分配工作负载,以便:

在代理的所有阻塞工作负载完成之前,不会将工作负载分配给代理

工作负载有持续时间估计,但是为了简单起见,假设每个工作负载的计算时间相等。(只需将每个工作负载分解为多个连续相关的工作负载,直到每个工作负载实际上都是一个固定的时间操作。)

我知道拓扑DAG排序,但这会产生一个单一的、串行的节点排序。我有多个代理并行操作,并且这些关系使得潜在的大型时间优化可以通过不明显的任务重新排序来实现。

这样做的结果最好是作为总工期最小的甘特图呈现。事实上,如果你认为这个问题是将一个里程碑中的bug票分配给团队中的工程师,目标是尽快完成里程碑,那么你就得到了这个想法。(不。。。请不要告诉我将我的图形导入MS Project,然后导出它:)-我对它背后的算法感兴趣!)

指向著名算法、软件库或一般问题和原则的指针非常受欢迎!

2 回复 | 直到 14 年前

Amit Prakash 14 年前

除非你有无限多的代理,这样一个兼容的代理在一个任务的所有前置任务完成后就可以使用,否则这是一个NP难问题。

我的书中也有类似的问题” Algorithms For Interviews "

</无耻插头>

以下是本书中的问题和解决方案:

我们需要在M个教室安排N个讲座。有些讲座是其他讲座的先决条件。为了尽快完成所有的讲座,你将如何选择何时何地举行讲座?

解决方案: 我们有一套N个单元的课程和M个教室。只要不需要在同一教室同时进行两次讲课,并且满足所有优先约束条件,就可以同时进行讲课。安排这些讲座以使完成时间最小化的问题被称为NP完全问题。这个问题自然是用图来建模的。我们将讲座建模为顶点,从顶点u到顶点v有一条边,如果u是v的先决条件,那么图必须是非循环的,才能满足优先约束。如果只有一个教室,我们可以简单地按拓扑顺序举办讲座,并在N个时间内完成N个讲座(假设每个讲座的持续时间为单位)。我们可以通过观察以下情况来发展启发式:在任何时候,都有一组讲课的优先级约束得到满足。如果这个集合小于M,我们可以调度所有的集合;否则,我们需要选择要调度的子集。子集选择可以基于几个度量:

根据课程开始时最长依赖链的长度对课程进行排序。
基于直接或间接先决条件的讲座总数的排名顺序讲座。

我们也可以使用这些标准的组合来排序当前可调度的讲座。如果候选集小于M,我们将安排所有的讲座;否则,我们将选择M个最关键的讲座,并安排那些讲座。我们的想法是,由于它们处于较长的依赖链的起点,因此应该提前安排。该准则是启发式的,可能不会导致最优调度这是预期的,因为问题是NP完全的。也可以使用其他的启发式方法,例如,我们可以使用依赖于L课的讲课次数作为L课的临界性或标准的某种组合。

High Performance Mark 14 年前

维基百科关于 PERT