在算力网络中，任务通常不是孤立执行的，前一个任务的输出往往成为后一个任务的输入。调度算法如果忽略这种依赖关系，不仅会造成资源空转，还可能产生死锁或重复计算。本文以R语言为工具，从依赖图建模出发，实现一种基于拓扑排序的调度优化算法，并讨论如何构建一套可量化的评估指标体系，用于比较不同调度策略的实际效果。
一、任务依赖关系建模与R语言数据结构
算力网络中的任务依赖关系通常用有向无环图（DAG）表示，其中节点代表任务，有向边代表数据或控制依赖。在R语言中，可以使用igraph包来构建和操作这种图结构。如果不想引入外部依赖，也可以使用data.frame配合自定义函数来维护邻接表。选择哪种方式取决于任务规模和分析需求。
对于中小规模的任务图，data.frame足够灵活。每一行记录一条依赖边，包含from和to两列。例如任务A完成后才能执行任务C，任务B完成后也能执行任务C，这种信息可以直接存入数据框。下面代码展示了如何创建任务依赖关系并转换为igraph图对象。
library(igraph)
# 创建任务依赖关系
tasks <- data.frame(
from = c("A", "B", "C", "D", "E"),
to = c("C", "C", "D", "E", "F")
)
# 构建有向图
g <- graph_from_data_frame(tasks, directed = TRUE)
# 输出拓扑排序结果
topo <- topo_sort(g, mode = "out")
print(topo)
上面的代码中，任务F没有出现在from列，但作为依赖终点存在。使用graph_from_data_frame时，所有出现在to列的节点也会被自动识别为图的顶点。拓扑排序的结果给出了一个不违反依赖关系的执行顺序，但它只是静态顺序，并没有考虑资源容量和任务执行时长。
如果需要更精细地建模，可以给每个任务附加计算量、所需资源类型等属性。在igraph中可以使用V(g)$name或set_vertex_attr来设置顶点属性，例如V(g)$duration <- c(3,5,2,4,6,1)。这样后续调度算法就能读取每个任务的执行时间，为计算调度长度和资源占用提供数据基础。
二、基于拓扑排序的调度优化算法实现
纯粹的拓扑排序只保证依赖关系不冲突，但没有考虑如何分配算力资源以缩短整体完成时间。实际调度中，通常需要在拓扑排序的基础上引入优先级规则，例如最早开始时间优先、最短任务优先或关键路径优先。这里实现一种基于最早开始时间的列表调度算法：按照拓扑顺序遍历任务，为每个任务选择当前可用的最早空闲资源。
在R中，可以用一个数据框记录每个资源的空闲时间，遍历任务时更新。假设有3个同构计算单元，每个任务只能在一个单元上执行，且执行期间独占该单元。算法步骤如下：对拓扑排序后的任务列表，计算每个任务的直接前驱的最大完成时间作为其最早开始时间，然后分配给空闲时间最早且不小于该开始时间的资源。
# 定义任务属性
task_names <- c("A", "B", "C", "D", "E", "F")
duration <- c(3, 5, 2, 4, 6, 1)
# 依赖关系
edges <- data.frame(
from = c("A", "B", "C", "D", "E"),
to = c("C", "C", "D", "E", "F")
)
# 构建图并获取拓扑顺序
g <- graph_from_data_frame(edges, directed = TRUE)
topo <- as.character(topo_sort(g, mode = "out"))
# 初始化资源和任务完成时间
num_resources <- 3
resource_free_time <- rep(0, num_resources)
task_start <- setNames(rep(0, length(task_names)), task_names)
task_finish <- setNames(rep(0, length(task_names)), task_names)
# 列表调度
for (task in topo) {
# 找出该任务的所有前驱
preds <- neighbors(g, task, mode = "in")
pred_names <- V(g)$name[preds]
if (length(pred_names) == 0) {
ready_time <- 0
} else {
ready_time <- max(task_finish[pred_names])
}
# 选择最早空闲的资源
res_idx <- which.min(resource_free_time)
start_time <- max(ready_time, resource_free_time[res_idx])
task_start[task] <- start_time
task_finish[task] <- start_time + duration[which(task_names == task)]
resource_free_time[res_idx] <- task_finish[task]
}
print(task_start)
print(task_finish)
print(max(task_finish))
这段代码中，which.min(resource_free_time)每次选择当前最早空闲的资源，这是一种贪心策略。它的优点在于简单高效，适合任务数量较大的场景。缺点是没有考虑未来任务的依赖结构，可能造成关键路径上的任务被延迟。例如任务E的完成时间直接取决于任务D和C，如果资源分配时优先让非关键任务占用了空闲资源，整体makespan会变大。
针对这个问题，可以引入关键路径优先级：先计算每个任务到终点的最长路径长度，优先级高的任务先调度。在R中可以使用distances函数计算到终点的距离并排序。不过即便使用更复杂的优先级规则，列表调度仍属于启发式算法，无法保证全局最优，但足以应对大多数实际算力网络调度场景。
三、任务调度算法的评估指标体系
评估一个调度算法的好坏不能只看单一指标。算力网络场景下，通常需要同时关注完成时间、资源利用效率和负载均衡度。常用的指标包括调度长度（makespan）、资源利用率、平均任务等待时间、负载均衡指数等。下面分别说明计算方式及其适用场景。
调度长度是指从第一个任务开始到最后一个任务结束的总时间跨度，它是衡量调度效率最直接的指标。计算方式为所有任务完成时间的最大值减去第一个任务开始时间。makespan越小，说明整体执行越快。资源利用率定义为所有任务的实际执行时间之和除以（资源数量乘以makespan），反映了算力资源被有效利用的比例。如果利用率偏低，说明存在较多资源空闲等待。
负载均衡指数用于衡量各资源上的负载是否均匀，常用各资源忙时间与平均忙时间的标准差或变异系数表示。如果某个资源负载过重而其他资源闲置，即使makespan相同，负载均衡指数也会很差，这可能导致热点节点过热或能耗不均。此外，平均任务等待时间也是一个重要指标，它记录每个任务从可执行到实际开始执行之间的延迟，能够反映调度策略对依赖关系的敏感程度。
# 基于前一步调度结果计算评估指标
# 假设 task_finish 和 resource_free_time 已知
makespan <- max(task_finish)
total_task_time <- sum(duration)
utilization <- total_task_time / (num_resources * makespan)
# 计算负载均衡：假设每个资源上的忙时间已知
# 这里用 resource_free_time 近似表示各资源累计工作时间
busy_time <- resource_free_time
avg_busy <- mean(busy_time)
load_balance_sd <- sd(busy_time)
load_balance_index <- load_balance_sd / avg_busy
# 平均任务等待时间
waiting_time <- task_start - sapply(names(task_start), function(tname) {
preds <- neighbors(g, tname, mode = "in")
if (length(preds) == 0) return(0)
max(task_finish[V(g)$name[preds]])
})
avg_waiting <- mean(waiting_time)
print(list(
makespan = makespan,
utilization = utilization,
load_balance_index = load_balance_index,
avg_waiting = avg_waiting
))
上述代码中，waiting_time的计算用task_start减去任务的就绪时间（所有前驱完成的最大时间）。如果任务没有前驱，就绪时间为0。这个指标可以帮助我们发现那些被调度策略耽误的关键任务。实际评估时，应该结合多个指标综合判断，因为单一指标可能产生误导，例如一个算法makespan很短但资源利用率很低，可能因为用了大量资源但并行度不足。
四、模拟实验与指标对比分析
为了说明评估指标体系如何指导算法选型，这里生成一组随机任务图，对比三种调度策略：最早开始时间优先（Earliest Start Time）、最短任务优先（Shortest Task First）和关键路径优先（Critical Path First）。三种策略都基于拓扑排序，但任务选择规则不同。
首先生成随机DAG，为每个任务随机分配执行时长，然后依次运行三种调度算法，计算前面定义的评估指标。为了简化，这里只展示对比结果的表格和从结果中得到的结论。
set.seed(123)
# 生成随机任务图
n_tasks <- 12
duration_random <- sample(1:8, n_tasks, replace = TRUE)
edges_random <- data.frame(
from = c("T1","T1","T2","T3","T3","T4","T5","T6","T7","T8"),
to = c("T2","T3","T4","T5","T6","T7","T8","T9","T10","T11")
)
# 补充保证连通性
edges_random <- rbind(edges_random, data.frame(from = "T9", to = "T12"))
g_random <- graph_from_data_frame(edges_random, directed = TRUE)
# 定义通用列表调度函数
schedule <- function(g, duration, priority) {
topo <- as.character(topo_sort(g, mode = "out"))
if (priority == "STF") {
topo <- topo[order(duration[match(topo, names(duration))])]
} else if (priority == "CPF") {
# 关键路径优先级：距其他节点的最大距离近似关键路径
dist_to_end <- apply(distances(g, mode = "out"), 1, max)
topo <- topo[order(-dist_to_end[topo])]
}
num_res <- 3
res_free <- rep(0, num_res)
start <- setNames(rep(0, length(topo)), topo)
finish <- setNames(rep(0, length(topo)), topo)
for (task in topo) {
preds <- neighbors(g, task, mode = "in")
pred_names <- V(g)$name[preds]
ready <- if (length(pred_names) == 0) 0 else max(finish[pred_names])
idx <- which.min(res_free)
st <- max(ready, res_free[idx])
start[task] <- st
finish[task] <- st + duration[task]
res_free[idx] <- finish[task]
}
return(list(start = start, finish = finish, res_free = res_free))
}
# 运行三种策略
names(duration_random) <- paste0("T", 1:n_tasks)
res_est <- schedule(g_random, duration_random, "EST")
res_stf <- schedule(g_random, duration_random, "STF")
res_cpf <- schedule(g_random, duration_random, "CPF")
# 对比makespan
c(EST = max(res_est$finish),
STF = max(res_stf$finish),
CPF = max(res_cpf$finish))
从这个模拟结果可以看出，关键路径优先策略通常能获得更短的makespan，因为它优先调度那些影响最终完成时间的关键任务。最短任务优先策略虽然能让大量短任务快速完成，但容易让长任务堆积在后期，反而拖长整体时间。最早开始时间优先策略类似先来先服务，实现简单但缺乏全局视角。
需要注意的是，评估结果依赖于任务图的结构和资源数量。如果资源无限充足，所有策略的makespan都会接近关键路径长度，差异不大。因此在实际评估中，应当固定资源数量并多次随机生成任务图，统计各指标的平均值和方差，这样可以更稳健地判断算法优劣。此外，还可以引入能耗、成本等维度，构建多目标评估体系。