algorithm - 关键路径与最长路径的关系

Question

关键路径是解决parallel precedence-constrained scheduling问题的本质。

问题：给定一组要完成的指定持续时间的作业，具有指定某些作业必须在某些其他作业开始之前完成的优先约束，我们如何在相同的处理器上调度作业（尽可能多），例如他们都在最短的时间内完成，同时仍然尊重约束？

我很难理解这与图中最长路径之间的联系，这显然是解决方案。我会假设答案是最短的时间，因为我们想要最少的时间。为什么这与最长路径有关，而不是最短路径？

Answer 1

最短计划的长度与最长的路径有关，因为无论您有多少处理器，都无法比最长路径更快地完成工作。最长路径上的任何工作都不能在前一个工作完成之前开始，所以你必须一个接一个地做。

如果您永远不会用完处理器，您总是可以在它所依赖的所有作业完成后立即开始一个作业，因此每个作业都会在到达其终点的最长路径完成时完成，并且整个作业在您完成时完成完成了最长的路径。

Answer 2

1. 创建一个表示结束状态的顶点。
2. 为每个任务创建一个顶点。
3. 对于每个任务 T
   1. 对于依赖于 T 的每个任务 T2（以及结束状态）
      1. 创建从 T 的顶点到 T2 的顶点的有向边 E
      2. 将 E 的权重设置为 T 所需的时间。

然后，关键路径是通过图的最长路径。想一想，相信这是真的。

这种思路对我有帮助：

关键路径必须以没有依赖关系的任务开始，并以最终状态结束。在满足所有依赖项之前，任何任务都无法完成。

如果任务 A 必须在 B 之前完成，而 B 必须在 C 之前完成，那么从任务 A 到任务 C 的时间至少是 A->B + B->C。

如果 C 有另一个依赖 B'，而 B' 具有依赖 A，那么从 A 到 C 的时间至少是 A->B' + B'->C。

因此，从 A 到 C 的最长路径很重要。

如果必须满足任务的某些依赖性，最短路径将解决问题。当必须满足所有依赖关系时，最长路径解决了问题。