云任务调度演进:从经典启发式到人工智能驱动、可持续及分布式调度——跨代际批判性综述(2026)
《Computer Science Review》:Cloud task scheduling evolution: From classical heuristics to AI-driven, sustainable, and distributed scheduling — A cross-generational critical survey (2026)
【字体:
大
中
小
】
时间:2026年10月24日
来源:Computer Science Review 17.5
编辑推荐:
**摘要** 过去六十年来,云任务调度经历了巨大的演变,从简单的顺序启发式方法发展到先进的、AI驱动的、绿色感知的以及去中心化的范式。本综述提供了一个跨世代的分析性概览,涵盖六个世代:(1) 经典启发式方法,(2) 元启发式方法,(3) 单智能体强化学习(RL),(4) 多智
**摘要** 过去六十年来,云任务调度经历了巨大的演变,从简单的顺序启发式方法发展到先进的、AI驱动的、绿色感知的以及去中心化的范式。本综述提供了一个跨世代的分析性概览,涵盖六个世代:(1) 经典启发式方法,(2) 元启发式方法,(3) 单智能体强化学习(RL),(4) 多智能体强化学习(MARL),(5) 绿色和碳感知调度,以及 (6) 新兴AI范式(Kubernetes、无服务器、大语言模型、数字孪生)。与以往仅涵盖单一子领域的综述不同,本工作在单一分析框架下同时涵盖MARL、碳感知、Kubernetes、无服务器和可重复性基准。在所比较的十二篇综述中,未发现这种组合。具体而言,本综述:(i) 遵循受PRISMA启发的系统性协议,从四个数据库中4821篇候选论文中筛选出174篇进行评审,并通过针对性文献检索进行补充;本文引用了来自系统性语料库和补充来源的141个不同参考文献;(ii) 形式化了QMIX算法在云虚拟机调度中的表达能力限制;(iii) 提供了带有定量边界的边界条件失效场景;(iv) 以可证伪的性能目标为特征描述了八个开放研究空白,包括关于调度决策中碳足迹核算的空白8;(v) 引入了一条说明性的时延-质量帕累托前沿;(vi) 提出了一套标准化的可重复性框架;以及 (vii) 提供了一份指示性五年研究路线图。
**引言** 云计算已成为现代数字基础设施的骨干[2], [3], [4]。其核心在于云任务调度:如何在异构虚拟机(VM)上最优地分配任务,同时最小化成本、遵守服务级别协议(SLA)、减少碳排放并确保容错能力[5], [6]。该问题在形式上是NP-hard[11], [12],该领域在六十余年间经历了六个不同世代的方法论演变[10], [13], [29], [42], [50]。
尽管研究活动持续进行,但成果仍分散在各个子领域中。经典算法设计者[10], [13]、RL研究者[30], [32]、绿色倡导者[50], [51]、容器工程师[59], [82]以及无服务器设计者[66], [67]各自孤立地处理这一问题。
国际能源署(IEA)估计2024年全球数据中心用电量约为415太瓦时,预计到2030年将达到945太瓦时[7]。在这一基础设施中优化调度效率代表着巨大的可持续发展机遇,因为次优的资源分配直接决定功耗,进而决定碳足迹。
云运营商报告的SLA违规率为2%至8%。Patterson[8]估计大型企业每小时停机成本为100万美元或以上;Hamilton[9]指出调度低效是主要的运营成本驱动因素。这些数据出自超大规模云计算之前,代表了现代部署的保守下限。
本综述由三项观察驱动:(i) 没有现有综述同时以严格的数学深度跨越全部六个世代并涵盖MARL-碳感知-Kubernetes-无服务器的组合(表3展示了这一空白);(ii) 以往的综述孤立地处理各范式,而未追溯它们之间的演化关系;(iii) 文献缺乏带有可证伪性能目标的结构化空白分析。
**为何是现在。** 这种特定范围的综合此前尚不可行,而愈发紧迫,有三项趋同原因。首先,本综述统一的多项范式仅最近才达到研究成熟度。尽管本综述中比较的基础MARL算法(QMIX[42], QTRAN[44])可追溯到2018–2019年,但它们在云资源调度中的具体应用集中在2022–2024年[57], [58];类似地,将大语言模型作为调度决策者与调度承载大语言模型推理的基础设施(第7.6.3节)之间的区分,仅在2023年GPT-4级模型和PagedAttention等推理系统的出现后才成为有意义的研究问题。其次,本综述自身的系统性语料库直接反映了这一加速:174篇评审论文中有39%(174篇中的68篇)发表于2021–2026年间(图2),而表3中比较的十二篇综述中有五篇本身发表于2024–2026年,表明本综述所映射的研究领域仍在积极形成之中,而非已定。第三,运营利害关系已具体化:全球数据中心用电量预计从约415太瓦时(2024年)上升至2030年的945太瓦时[7],而同时2026年的一项系统性综述独立证实,碳感知调度仅被整合到6.3%的AI驱动资源分配研究中[136]——从一个无关的语料库中佐证了本综述所识别的空白(空白3)尽管领域快速增长仍未缩小。综合而言,这三项因素表明,鉴于各组成范式的近期成熟,跨世代综合不仅是新近可行的,而且鉴于新子领域(Kubernetes碳感知、大语言模型推理、数字孪生调度)持续涌现却未与更广泛的分类法关联的速度,也是新近必要的。本综述与十二篇最密切相关作品的详细定位将在第4.3节中阐述,紧随表3中的比较证据之后。
**范围与权衡。** 覆盖六个世代涉及固有的广度-深度权衡。第三代(单智能体RL)虽已有数百篇论文,但其覆盖比例低于其重要性所应得的比例;关于专门论述请参见Luong等人[97]。六代分类法是一个组织框架,而非严格的因果递进主张(第13节)。
本工作解决三个核心研究问题:
1. 调度目标和算法如何跨越六个世代演变,何种数学结构将它们统一?
2. 各范式的可量化局限是什么,表达为边界条件场景?
3. 哪些以可证伪性能目标定义的研究空白代表了影响力最高的开放问题?
**贡献:**
1. 跨六世代的跨世代分析,包含边界条件失效场景。与以往综述(表3)不同,本工作同时处理MARL、碳感知、Kubernetes原生调度、无服务器和可重复性。
2. 云虚拟机调度的QMIX形式化表达能力限制,明确区分于Son等人[44]的一般性结果(推论1)。
3. 八个以可证伪性能目标和基于已发表基准的阈值论证的研究空白(第11节)。
4. 空白8:将碳足迹核算作为开放问题,提出CEE+指标方向,形式化将硬件制造排放纳入调度目标(第11节)。
5. 说明性时延-质量帕累托前沿分析(第9节)。
6. 可重复性框架:公共轨迹、标准化指标和Docker基准接口(第10节)。
7. 指示性五年研究路线图(第12节)。
8. 统一局限性章节,明确讨论云调度研究的全球南方影响,包括非洲部署的具体约束(第14节)。
表1列出了本综述中使用的所有缩写。
**方法论:系统性文献综述协议** 本综述遵循受PRISMA启发的系统性综述协议[1]。文献从四个数据库中检索:IEEE Xplore、ACM Digital Library、Scopus和Web of Science(检索期:2026年1月至3月)。
**云任务调度问题** 一个调度实例由任务集合$T=\{t_1, \ldots, t_n\}$和虚拟机集合$V=\{v_1, \ldots, v_m\}$组成。任务$t_i$具有处理需求$d_i$(CPU秒)和截止期$\delta_i$;虚拟机$v_j$具有速度$s_j$和成本率$c_j$。一个调度$x: T \to V$将每个任务分配到一个虚拟机上,并附带每个虚拟机上任务的排序。对于调度在虚拟机$v = x(t_i)$上、在已分配到$v$的任务$\{t_1, \ldots, t_k\}$之后的任务$t_i$,其完成时间为$C_i = W_i + d_i/s_v$,其中$W_i = \sum_{j \leq k} d_j/s_v$是同一虚拟机上先前调度任务引起的等待时间;最大完成时间为$T_{\max}$。
**覆盖矩阵** 除表3中比较的十二篇综述外,Khaledian等人[108]的一项补充性系统综述分析了82篇雾/云工作流调度论文,报告25%使用基于启发式的机制,而75%使用基于AI和参数建模的方法,最大完成时间是最常处理的目标。与表3中比较的十二篇综述不同,本综述贡献了一项语料库构成统计量:基于启发式的方法和基于AI的方法之间的分布。
**扩展分类法** 云任务调度被组织为六个主题世代(图3)。"世代"一词用作分析标签,而非时间上的先后顺序或算法优越性的主张:各世代在时间上重叠并在生产系统中共存。来自2010年和2012年的基础性绿色调度出版物早于第四代(MARL),这说明了为何这是一个组织框架而非严格的时序划分。
**比较矩阵** 表6呈现了跨12项标准的11种方法。两个绿色目标行(能源感知、碳/二氧化碳)对所有11种现有方法均显示为×——这是空白3的主要动机。
**表6的解释性说明:** a. 在DQN、PPO、QMIX和MAPPO训练后的GPU(A100)推理。仅CPU:10–50毫秒(超出10毫秒预算)。b. $O(1)$复杂度条目(FCFS、Q-Lrn、DQN、PPO)仅反映与实例规模($n$个任务、$m$个虚拟机)的无关性,在固定且已训练网络下成立。实际每次决策的……
**带有定量边界条件场景的批判性分析** 对每个范式:(i) 主要优势;(ii) 固有结构局限性;(iii) 带有定量值的边界条件场景;(iv) 对下一代的动机。表7对所有场景进行分类。只有QMIX场景是结构性的;其他所有场景都展示算法在设计范围之外运行。
**目标函数演变**
第一代(Min-Min):$\min \max_{v \in V} \sum_{t: x_{t,v}=1} d_t$,$\sum_v x_{t,v} = 1$,$x_{t,v} \in \{0, 1\}$。
公式(5)将第3.1节的通用异构模型($C_i = W_i + d_i/s_v$)特化为经典同质情况($s_v = 1 \ \forall v$)。这与调度文献中的标准Min-Min公式一致。
第二代(GA/PSO):$\min w_1 C + w_2 T$,$C = \sum_v c_v \cdot load_v$,$T = \max_t C_t$,$w_1 + w_2 = 1$。
此处$C_t$遵循第3.1节中的完成时间定义($C_i = W_i + d_i/s_v$)。
第三代(RL):与第5节的奖励公式的关系。公式(1)给出了详细的……
**基本权衡:时延-质量帕累托前沿** 解质量$Q$被操作性地定义为$1 - n_{Makespan}$,即在固定基准实例上的最大完成时间超额(仅适用于最大完成时间目标;不同目标将产生不同的排序)。
**说明性观察。** 对于固定工作负载和最大完成时间目标,帕累托有效的(时延,质量)对预计形成一条非递减前沿。本综述将此预期视为定性、视觉拟合的趋势,而非数学推导的结果。曲线$f(\tau) = 100(1 - e^{-0.8\tau^{0.35}})$……
**可重复性问题** 三个结构性障碍阻碍了公平的跨论文比较,与更广泛的MARL文献中记录的可重复性危机一致[38], [95]:(1) 代码不可用——深度强化学习结果对很少完整报告的实现细节高度敏感;(2) 私有/合成轨迹——专有工作负载轨迹是公平比较的主要障碍[96];(3) 没有标准化的容器化基准环境——据我们所知,没有云调度论文……
**带有可证伪目标的开放研究空白** 对每个空白:(i) 当前最先进水平;(ii) 可证伪目标(数值、可验证);(iii) 空白仍未解决的原因。表10按性质和时间跨度对所有八个空白进行分类。所有目标都是工程性能目标,而非理论推导的最优解。空白4分为工程子空白(4a,可证伪)和理论开放问题(4b,无已知解决方案路径)。
**空白1——多目标 + 实时 + 去中心化** 最先进水平:MAPPO:≤4个目标在15–20毫秒内
**未来方向和五年研究路线图** 该路线图按估计时间跨度而非空白编号组织第11节的八个空白,以使短期/长期区分明确化。对于每一项,我们同时说明时间线以及证明该时间线的具体技术依赖。
**空白覆盖自评模板** 任何新的调度贡献应明确说明:(1) 它解决了八个空白中的哪一个(完全/部分/未解决)以及实现覆盖的具体设计选择;(2) 哪些空白仍然开放,定义未来工作;(3) 至少在一条公共轨迹[83], [86]上的所有四个标准化指标($n_{Makespan}$, $n_{Cost}$, $SLA_{99}$, $CEE$)。
**常见陷阱**
陷阱1:声称解决了一个空白但未达到其可证伪目标。$P[SLA] = 0.95$ 是对空白4的有效增量贡献;它不满足空白4a的目标……
**局限性** 本节将全文分散的局限性进行汇总,以便读者和评审者能够共同评估。
**地理轨迹偏差和全球南方影响。** 所有推荐的基准轨迹(Google Borg、阿里巴巴、Azure)均源自大型西方或东亚超大规模提供商。非洲、拉丁美洲、南亚和中东的云工作负载模式未得到代表;关于调度算法性能的结论可能无法推广到这些场景。
**跨世代讨论** 本节将前述各节的分析综合为一个统一视图,阐述调度范式如何相互权衡,以及为何没有单一世代在所有运营场景下占据主导地位。
**结论** 本综述呈现了云任务调度跨越六个世代的演进跨世代记述。它基于受PRISMA启发的四个主要数据库中174篇论文的评审,并通过针对性文献检索进行补充;全文引用了141个不同参考文献。第14节提供了统一的范围局限说明。范围刻意广泛:没有单一现有综述同时涵盖MARL、碳感知、Kubernetes原生调度……
**CRediT作者贡献声明** Kahina Ferhi:概念构思、方法论、原创草稿撰写、修订与编辑、项目管理。Assia Outamazirt:概念构思、形式化分析、修订与编辑。Djamil Aissani:监督、修订与编辑、资源。Kamel Barkaoui:监督、验证、修订与编辑。
Karima Adel-Aissanou:形式分析、数据整理、写作 – 审阅与编辑。
生成式人工智能及人工智能辅助技术在写作过程中的声明
在本工作准备期间,作者使用了 Claude (Anthropic) 来改进稿件的语言、清晰度和呈现方式;根据原始来源核实文献引用;交叉检查图表与稿件文本的内部一致性;并协助起草和完善给审稿人的回复及修订文档。作者根据需要审查和编辑了输出内容,并对内容承担全部责任。
利益冲突声明
作者声明,他们不存在已知的可能影响本文报告工作的相互冲突的财务利益或个人关系。
致谢
作者感谢匿名审稿人提供的建设性反馈。K. Ferhi、D. Aissani 和 K. Adel-Aissanou 感谢阿尔及利亚贝贾亚大学 LaMOS 研究单位(系统建模与优化实验室)的支持。A. Outamazirt 感谢法国巴黎 OptimIAum 的支持。K. Barkaoui 感谢法国巴黎 CNAM 的支持。
Kahina Ferhi|Assia Outamazirt|Djamil Aissani|Kamel Barkaoui|Karima Adel-Aissanou
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号