WS-SSA：使用沙蚤群体算法的云计算工作流调度

为什么更聪明的数字流量很重要

在每一个在线地图、医学分析或引力波发现的背后，都有一连串必须按正确顺序、在合适机器上、并尽可能快速且低成本运行的计算任务。在现代云计算中，这些作业被拆分成数千个相互关联的步骤，分布在全球的数据中心。如果对这些数字流量的调度不当，科学家就要更久才能得到答案，服务提供商也会消耗比必要更多的电力。本文提出了一种新的编排复杂工作流的方法，灵感来自一个出人意料的来源：一种称为沙蚤的小型海洋生物链。

大型科学任务如何被拆分成若干部分

大型的科学和商业应用很少作为单一程序运行。相反，它们被分解成许多相互依赖的较小任务。研究人员用有向无环图来表示这种结构：节点表示任务，箭头表示某些结果必须在其他任务开始之前产生。在云数据中心中，这些任务被映射到虚拟机上——基于软件的计算单元，在速度、内存和网络能力上各不相同。挑战在于决定哪个任务应运行在哪台机器上、何时运行，以便整个工作流尽快完成并且高效利用资源。

为什么找到最佳方案如此困难

为成千上万个相互依赖的任务在多台不同机器上选择理想的调度，是一个典型的所谓 NP-困难问题：可能的分配数量以难以想象的速度爆炸增长，因此不可能逐一检验所有方案。正因如此，云系统依赖于巧妙的捷径，称为启发式和元启发式算法，来搜索良好但不保证完美的解决方案。传统规则如先来先服务或轮询算法简单却在大规模时效率低下。更先进的方法，包括遗传算法、粒子群优化和蚁群优化，搜索更智能，但仍可能陷入平庸解、需要精心调参，或忽视重要的任务依赖关系。

向海洋中的沙蚤链学习

这种称为 WS-SSA 的新方法，将沙蚤群体算法适配到云工作流的实际场景中。自然界中，沙蚤成链在海中移动，前方有领头者，后方是追随者，随着寻找食物不断调整方向。WS-SSA 将每一个可能的调度方案视为该链中的一个成员。已知的最佳方案扮演“食物”的角色，引导领头调度的移动，而追随者则逐步向有希望的区域靠拢。一个关键设计选择是让群体中每个位置直接以简单整数编码每个任务运行在哪台虚拟机上，而不是使用需要后续转换的连续值。结合始终尊重任务依赖关系的精心任务排序，这保证了群体中考虑的每一个候选调度都是有效且可立即执行的。

将新调度器付诸测试

为了评估 WS-SSA 的性能，作者使用 WorkflowSim 进行了大量仿真，该工具在广泛使用的 CloudSim 环境之上模拟真实科学工作流。他们测试了来自天文学、地震学、引力波物理和生物信息学的五个基准应用，工作流规模从几十个任务到一千个任务不等，云环境从几台到一百台虚拟机。WS-SSA 与六种经典调度规则和三种现代元启发式方法进行了比较，包括座头鲸优化算法、遗传算法和粒子群优化。主要评价指标是总完工时间（或称 makespan），同时跟踪虚拟机的总能耗作为紧密相关的次要度量。

对时间和能耗的意义

在这组广泛的实验中，WS-SSA 一贯比竞争方法产生更快的调度。平均而言，与传统启发式方法相比，它将 makespan 大约缩短了三分之一，并且相比成熟的元启发式算法仍能取得数个百分点到超过二十个百分点的改进。由于空闲时间和浪费计算也得到减少，总能耗同步下降——通常降幅相近——而无需算法显式地针对能耗进行优化。对 30 次独立运行的统计检验证实了这些改进并非偶然，尤其在更大、更复杂的工作流上更为显著。研究表明，一种简单的、离散化的沙蚤启发策略可以可靠地在庞大的调度空间中导航，并适应不同的工作流结构和机器配置。

更快的科学与更精简的云

通俗地说，WS-SSA 是支撑现代科学与云服务的数据高速公路上的更智能的交通指挥官。通过协调每个任务何时何地运行，它缩短了启动复杂作业与获得最终结果之间的时间，同时减少了底层数据中心的能耗。这项工作并不改变工作流本身的定义；相反，它为在现有云平台上运行这些工作流提供了更高效的方式。未来若能将成本、能耗和截止期限等因素同时纳入考虑，受群体启发的调度器可能成为更环保、更灵敏的计算基础设施的重要工具。

引用: Sharawy, A.A., Sakr, R.H., Eladrosy, W. et al. WS-SSA: workflow scheduling in cloud computing using salp swarm algorithm. Sci Rep 16, 13402 (2026). https://doi.org/10.1038/s41598-026-48037-w

关键词: 云工作流调度, 启发式优化, 沙蚤群体算法, 科学计算, 节能云