基于最长路径优先级的拓扑排序：算法名称与构建系统咨询

假设有A、B、C、D四个任务，D依赖于另外三个，依赖图如下：

*---> A
     /
   D -----> B
     \
      *---> C

单worker可按拓扑排序顺序（如A、B、C、D）执行任务；双worker时，常规调度会出现等待情况。但为任务分配运行时间估计后，可通过优先级优化全局运行时间：

*---> A (5s)
           /
    D (2s) -----> B (10s)
           \
            *---> C (5s)

最优策略是优先执行到根节点最长路径的任务，优先级P为路径节点运行时间之和：

P(A) = 5s + 2s = 7s
    P(B) = 10s + 2s = 12s
    P(C) = 5s + 2s = 7s

该策略也适用于含交叉依赖的图，优先级取所有路径运行时间的最大值：

*---> A (12s)
           /
    D (2s) -----> B (10s) -*----> X (5s)
           \                \
            *---> C (5s)  ---*--> Y (6s)

P(A) = 12s + 2s = 14s
    P(X) = 5s + 10s + 2s = 17s
    P(Y) = 6s + 10s + 2s = 18s    (and not the runtime of the "shorter" path over C)

技术问题解答 #

1. 这种基于最长路径优先级的拓扑排序算法是否有标准名称？
   该算法属于关键路径法（Critical Path Method, CPM）的调度应用，常被称为关键路径调度。核心逻辑是通过计算每个任务到最终节点的最长路径（关键路径）来确定优先级，优先调度关键路径上的任务，以此最小化总完工时间。

2. 是否存在类似GNU make、Ninja的构建系统实现了该算法？

   • Ninja原生支持该策略：它会根据任务的预估运行时间和依赖关系计算关键路径，优先调度对总构建时间影响最大的任务，以此优化构建效率。
   • GNU make原生未实现该算法，但可以通过第三方扩展或自定义规则近似模拟类似逻辑，不过原生功能不支持关键路径优先级调度。

内容的提问来源于stack exchange，提问作者Jakob Stark