6

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

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

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

如何分配工作负载，以便：

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

  • 完成总工作负载图需要尽可能短的时间。（请注意，最小化代理空闲时间通常是好的，但不是基本要求 - 可能存在一个特定代理空闲更长时间但完成所有代理的所有作业的总时间最少的情况。）

工作负载具有持续时间估计值，但为简单起见，假设每个工作负载都需要相同的计算时间。（只需将每个工作负载分解为多个连续依赖的工作负载，直到每个工作负载实际上都是一个恒定时间操作。）

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

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

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

4

2 回答 2

4

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

<无耻插件>

我的书“面试算法”中有一个非常相似的问题

< /无耻的塞子>

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

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

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

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

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

于 2010-10-23T03:25:23.327 回答
2

关于PERT的 Wikipedia 文章可能是一个有用的起点。

于 2010-10-20T07:06:07.907 回答