algorithm - 为什么关键路径的权重提供了执行所有工作的总时间的下限？

Question

在算法介绍 P657，第 3 版中，它说：

关键路径是通过 dag 的最长路径，对应于执行任何作业序列的最长时间。因此，关键路径的权重提供了执行所有作业的总时间的下限。

我明白第一句话。但在第二句话中，它说

关键路径提供了一个下限

为什么它提供了执行所有工作的总时间的下限而不是上限？

我想我可能会误解关键路径？

Answer 1

在完成路径中的先前作业之前，您不能开始关键路径中的任何作业。因此，任何合法的时间表都将采用权重之和来完成关键路径上的所有工作。因此，任何关键路径都是完成所有工作的时间的下限。

（如果您始终有足够的资源同时处理所有当前可启动的作业，那么最长的关键路径也将是完成所有作业的时间）。