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

Question

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

我还有一组可以执行这项工作的多个代理。

一些工作负载种类可以分配给任何代理，其他的必须分配给特定的代理，还有一些必须分配给特定代理组中的一个代理。

如何分配工作负载:

• 在代理的所有阻塞工作负载完成之前，不会向代理分配任何工作负载

• 完成总工作负载图需要尽可能短的时间。 (请注意，尽量减少代理空闲时间通常是好的，但这不是基本要求 - 可能存在某个特定代理空闲时间较长但所有代理完成所有作业的总时间最少的情况。)

工作负载有持续时间估计，但为简单起见假设每个工作负载需要相同的时间来计算。 (只需将每个工作负载分解为多个串行相关的工作负载，直到每个工作负载实际上都是一个恒定时间操作。)

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

此结果最好呈现为最短总持续时间的甘特图。事实上，如果您将问题视为将里程碑中的错误票分配给团队中的工程师，目标是尽快完成里程碑，那么您就明白了。 (不......请不要告诉我将我的图表导入 MS Project 然后导出它:) - 我对它背后的算法很感兴趣!)

非常感谢指向众所周知的算法、软件库或一般问题和原则的指针!

Answer 1

除非您有无限数量的代理，以便在任务的所有前置任务完成后立即有一个兼容的代理可用，否则这是一个 NP-hard 问题。

<不要脸的外挂>

我的书“Algorithms For Interviews”中有一个非常相似的问题

/无耻的外挂>

这是书中的问题和解决方案:

我们需要在 M 个教室安排 N 个讲座。其中一些讲座是其他讲座的先决条件。你会如何选择何时何地举办讲座，以便尽快完成所有讲座？

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

• 根据讲座开头的最长依赖链的长度对讲座进行排序。
• 根据直接先决条件的讲座数量对讲座进行排序。
• 根据直接或间接先决条件的讲座总数对讲座进行排序。

我们还可以使用这些标准的组合来对当前可安排的讲座进行排序。例如，对于每个顶点，我们将其关键性定义为从它到汇点的最长路径的长度。我们通过按拓扑顺序处理顶点来安排讲座。在我们的算法中的任何一点，我们都有一组候选讲座——这些是其先决条件已经安排好的讲座。如果候选集小于 M，我们安排所有的讲座；否则，我们选择 M 个最关键的讲座并安排它们——我们的想法是它们应该被安排得更快，因为它们处于更长的依赖链的开始。该标准是启发式的，可能不会导致最佳调度——这是可以预料的，因为问题是 NP 完全的。可以采用其他启发式方法，例如，我们可以使用依赖于讲座 L 的讲座数作为讲座 L 的关键性或标准的某种组合。