算力网络把分布在不同位置的算力节点连接起来，任务调度时不仅要决定任务放到哪个节点执行，还要处理任务之间的先后依赖。一个下游任务往往需要等待多个上游任务的输出结果，如果只按照节点空闲状态分配任务，很容易出现关键路径上的任务被延迟，而非关键任务却占用资源的情况。关键路径法CPM正是解决这类依赖调度问题的有效手段。本文以R语言为工具，演示如何从任务依赖图出发计算关键路径，并将计算结果转化为算力调度策略。
一、任务依赖图与关键路径法的核心原理
在算力网络中，一个作业通常可以拆分为多个子任务，例如数据预处理、模型训练、参数聚合、结果写回等。这些任务之间存在强依赖，通常用有向无环图DAG来表示。每个节点代表一个计算任务，节点权重可以是该任务的预计执行时长；每条有向边代表前驱任务向后继任务传递数据或控制信号，如果跨节点传输，还可以把通信延迟作为边的权重合并到调度计算中。
关键路径法围绕四类时间量展开。对任务i来说，最早开始时间ES表示在所有前驱任务完成后能够启动的最早时刻，最早完成时间EF等于最早开始时间加上任务时长。与此对应，最晚开始时间LS和最晚完成时间LF表示在不推迟总工期的前提下，任务最迟必须开始和结束的时间。浮动时间等于最晚开始时间减去最早开始时间，它反映了任务可以被推迟而不影响整体进度的余量。
计算时遵循两个核心公式。正向计算先求ES和EF，每个任务的最早开始时间等于所有前驱任务最早完成时间的最大值，最早完成时间等于最早开始时间加自身时长。反向计算再求LS和LF，每个任务的最晚完成时间等于所有后继任务最晚开始时间的最小值，最晚开始时间等于最晚完成时间减自身时长。浮动时间为零的任务串起来就是关键路径，关键路径上的任何延迟都会直接拉长整个作业的完成时间。
二、用R语言构建任务依赖图并计算关键路径
R语言的igraph包能够方便地构建有向图并进行拓扑排序。假设有一个算力作业包含六个任务A到F，任务A可以同时启动B和C，B完成后启动D，C完成后启动E，D和E都完成后启动F。六个任务时长分别为3、5、2、4、6、3个时间单位。下面这段代码先构造任务表、依赖边表和有向图，并检查图中是否存在环。
library(igraph)
tasks <- data.frame(
id = c("A","B","C","D","E","F"),
duration = c(3,5,2,4,6,3),
stringsAsFactors = FALSE
)
edges <- data.frame(
from = c("A","A","B","C","D","E"),
to = c("B","C","D","E","E","F"),
stringsAsFactors = FALSE
)
g <- graph_from_data_frame(edges, vertices = tasks, directed = TRUE)
stopifnot(is_dag(g))
topo <- topo_sort(g, mode = "out")
task_names <- V(g)$name
ES <- setNames(rep(0, length(task_names)), task_names)
EF <- setNames(rep(0, length(task_names)), task_names)
for (v in as.numeric(topo)) {
preds <- neighbors(g, v, mode = "in")
if (length(preds) == 0) {
ES[V(g)$name[v]] <- 0
} else {
ES[V(g)$name[v]] <- max(EF[V(g)$name[preds]])
}
EF[V(g)$name[v]] <- ES[V(g)$name[v]] + V(g)$duration[v]
}
拓扑排序后，代码按顺序遍历每个任务，使用neighbors函数找到前驱节点。如果某个任务没有前驱，它的最早开始时间就是零；否则从所有前驱的最早完成时间中取最大值。得到最早开始时间后，加上该任务自身的执行时长，就得到最早完成时间。这段代码的核心价值在于，无论任务依赖关系多复杂，只要图是无环的，都能一次性完成正向推导。
total_duration <- max(EF)
LF <- setNames(rep(total_duration, length(task_names)), task_names)
LS <- setNames(rep(total_duration, length(task_names)), task_names)
for (v in rev(as.numeric(topo))) {
succs <- neighbors(g, v, mode = "out")
if (length(succs) == 0) {
LF[V(g)$name[v]] <- total_duration
} else {
LF[V(g)$name[v]] <- min(LS[V(g)$name[succs]])
}
LS[V(g)$name[v]] <- LF[V(g)$name[v]] - V(g)$duration[v]
}
slack <- LS - ES
result <- data.frame(
task = task_names,
duration = V(g)$duration,
ES = ES,
EF = EF,
LS = LS,
LF = LF,
slack = slack,
stringsAsFactors = FALSE
)
print(result)
critical_tasks <- result$task[result$slack == 0]
print(critical_tasks)
反向计算从拓扑序的末端开始，先令所有任务的最晚完成时间等于总工期，再逐级向前推导。对没有后继的任务，最晚完成时间就是总工期；对有后继的任务，最晚完成时间等于所有后继任务最晚开始时间的最小值。减去任务时长后得到最晚开始时间。浮动时间用最晚开始时间减最早开始时间即可。
根据示例数据，A、B、D、F四个任务的浮动时间为零，构成关键路径A指向B指向D指向F，总工期为15个时间单位。任务C和E存在1个时间单位的浮动，说明它们可以在一定范围内推迟启动而不会影响最终交付。若要用图形展示依赖关系，可以继续执行下面这段绘图代码，其中关键任务使用橙色标记。
plot(g,
layout = layout_with_sugiyama(g)$layout,
vertex.label = paste0(V(g)$name, "\n", V(g)$duration),
vertex.color = ifelse(V(g)$name %in% critical_tasks, "orange", "lightblue"),
edge.arrow.size = 0.5,
main = "任务依赖图与关键路径")
三、把关键路径结果转化为算力调度策略
CPM计算出的浮动时间可以直接指导调度器的优先级设置。关键路径上的任务必须获得最高优先级，因为它们没有延迟空间，一旦排队等待资源就会直接推迟总工期。调度器可以先为这些任务预留算力，例如绑定CPU核心、GPU卡或网络带宽，避免在同一节点上被普通任务挤占。对浮动时间较小的近关键任务，也要重点监控，防止它们因累计延迟而变成新的关键任务。
对于非关键任务，可以采用填谷策略，把它们安排到节点负载较低的时间段执行。下面代码按照最晚开始时间和最早开始时间排序，并为每个任务生成优先级标签。这样调度器可以先处理顺序靠前的关键任务，再安排后面的普通任务。
schedule <- result[order(result$LS, result$ES), ]
schedule$priority <- ifelse(schedule$slack == 0, "critical", "normal")
print(schedule[, c("task", "duration", "ES", "LS", "slack", "priority")])
算力网络与本地集群的重要区别在于跨节点通信延迟不可忽略。假设任务E运行在另一个算力节点上，它向任务F传递中间结果需要额外2个时间单位的传输时间。原路径A到C到E到F的总时长从14变为16，超过原关键路径的15，关键路径就会发生漂移。因此，当网络状态或节点位置变化时，不能沿用初始CPM结果，必须重新计算。可以把通信代价并入后继任务的启动延迟，或者将其设置为边的权重，统一参与正向和反向推导。
四、CPM在资源约束下的局限与改进方向
关键路径法默认资源是无限的，也就是所有任务只要依赖满足就能立即执行。实际算力网络中，CPU核心数、内存容量、GPU数量和带宽都是有限的，两个关键任务可能竞争同一个节点的同一张GPU卡，这会导致排队等待，实际工期大于CPM理论值。因此，CPM更适合作为调度优化的下界和优先级依据，而不是一个完整的调度结果。
资源受限项目调度问题通常被称为RCPSP，它需要同时考虑任务依赖和资源容量约束。R语言中可以用CPM生成初始优先级，再结合启发式规则进行模拟。例如每次资源释放后，从可执行任务集合中优先选择关键路径任务，其次选择最小浮动任务，最后按最晚开始时间排序。这样既保留了CPM对依赖关系的精确描述，又能适应资源竞争环境。
此外，任务实际执行时长可能偏离预估值，节点也可能出现故障或算力降级，因此生产系统中的任务调度需要动态重算。每当有任务完成、新增任务到达或网络拓扑发生变化，都可以重新提取当前未完成任务，重建DAG并计算关键路径。借助R脚本、R Markdown或Shiny面板，可以周期性地生成关键路径报告，辅助运维人员识别当前最需要保障资源的任务链路。关键路径法的价值不仅在于一次计算，更在于它提供了一种持续识别瓶颈、动态调整算力分配的分析框架。