论文发表于 Elsevier 旗下期刊Future Generation Computer Systems卷 175文章号 108050DOI 为10.1016/j.future.2025.108050。Future Generation Computer Systems 长期关注未来计算系统、分布式计算、云计算、雾计算、边缘计算、资源管理和工作流调度等方向属于系统与应用计算领域较有影响力的国际期刊。至于具体分区、影响因子和单位认定级别建议以所在单位采用的最新版目录为准。这篇论文提出了一个名为IoTGA-SRC²的算法全称是Internet of Things Genetic Algorithm with Selective Repair under Combined Criteria。下文为了阅读方便统一简称为 IoTGA-SRC²。从名字就能看出它基于遗传算法。但真正的亮点并不是“用了 GA”而是作者围绕 deadline 约束设计了一套更细致的选择与修复机制。简单说这篇论文想解决的问题是在 IoT-Fog-Cloud 异构环境中如何调度带 deadline 的 IoT 工作流使任务尽量按时完成同时降低资源使用成本一、为什么这个问题难在论文中IoT 应用被建模为 workflow。一个 workflow 由多个任务组成任务之间存在前后依赖关系通常可以表示为有向无环图 DAG。例如一个 IoT 人脸识别应用可能包含图像采集、预处理、特征提取、模型推理、结果返回等多个任务。某个任务必须等前一个任务完成并传输数据后才能开始。因此调度器不能只看单个任务的运行时间还要考虑整个任务链路的完成时间。这个问题难主要来自几个方面。首先是资源异构。IoT 设备、Fog VM、Cloud VM 的算力、价格和通信位置都不同。把任务放到 IoT 设备上可能成本低、传输快但执行慢放到 Cloud 上可能执行快但通信慢、成本高。Fog 介于两者之间既不是最弱也不是最强而是提供了一种折中选择。其次是 workflow 依赖复杂。一个任务被加速并不一定能缩短整个 workflow 的完成时间。如果它不在关键路径上或者它的后继任务仍然要等待其他任务完成那么加速它的收益可能很有限。这其实是调度问题里非常核心的一点局部最优不一定带来全局最优。第三是 deadline 约束严格。很多 IoT 场景不只是追求平均性能而是要求任务在特定时间之前完成。调度方案如果成本很低但频繁超时在实际应用中并不可接受。第四是问题本身计算复杂。论文指出D-IoTWS也就是 Deadline-Constrained IoT Workflow Scheduling可以归约到 job shop scheduling 问题因此是 NP-hard。对于大规模场景精确算法往往难以直接使用启发式和元启发式方法就成为常见选择。二、学术界通常怎么做现有方法大致可以分为三类。第一类是启发式算法例如 HEFT、JIT-C、IC-PCP 等。这类方法通常根据最早完成时间、关键路径、最低成本资源等规则快速生成调度方案。它们的优点是速度快、实现相对简单适合工程系统中的快速决策。但面对复杂 deadline、异构资源和多 workflow 并发时容易陷入局部最优。第二类是混合启发式或学习增强方法例如 ET2FA、QL-HEFT 等。这些方法会在传统启发式基础上加入任务分类、强化学习或 VM 空闲管理等机制。它们通常比基础启发式更灵活但在处理 deadline 违约时仍然不一定能系统解释“为什么这个 workflow 超时”。第三类是元启发式算法例如遗传算法、粒子群、蚁群和多目标进化算法。元启发式算法的优势是能够探索更大的解空间尤其适合 NP-hard 调度问题。但它们也有一个典型挑战搜索过程中会产生很多不可行解也就是违反 deadline 的调度方案。传统做法常常使用 penalty function也就是给 deadline violation 加惩罚项。但论文指出仅仅惩罚不可行解并不总能稳定地找到高质量可行解。于是近年来越来越多研究开始关注 repair method与其简单淘汰或惩罚不可行解不如尝试把它们修复成可行解。这正是本文的切入点。三、IoTGA-SRC² 的核心思想IoTGA-SRC² 基于遗传算法。每个染色体表示一个完整调度方案每个基因对应一个 workflow task基因值表示该任务被分配到哪个资源上执行。比如某个任务可以被分配到 IoT 设备、Fog VM 或 Cloud VM。整个染色体组合起来就表示一组 workflow 中所有任务的资源分配方案。不过这篇论文真正有价值的地方在于两个设计SVC 选择算子在父代选择时同时考虑 deadline violation 和 costSRC² 修复机制对不可行解进行有选择、有原因分析、有多指标依据的定向修复。这两个模块共同构成了本文方法的主要创新。如果用一句话概括 IoTGA-SRC²它不是简单地惩罚 deadline 违约而是尝试理解违约发生在哪里、为什么发生以及应该怎样修复。这也是这篇论文最值得关注的地方。四、第一处亮点选择父代时不只看“能不能按时”也看“贵不贵”论文提出的 SVC全称是Selection with Violation Degree and Cost Function。它是一种 tournament selection。每次从种群中随机选出若干个候选个体然后以 0.5 的概率选择 deadline violation 最低的个体以 0.5 的概率选择 cost 最低的个体。这个设计看起来不复杂但它很贴近问题本质。如果只关注 deadline violation算法可能会倾向于大量使用高性能资源。这样虽然更容易按时完成但成本可能偏高。如果只关注 cost算法又可能选择便宜但算力不足的资源导致 deadline 违约。SVC 的作用是让进化过程同时受到两个方向的牵引一方面向可行解靠近另一方面保留低成本解的竞争力。这种设计属于比较朴素但有效的工程化改进。它没有把选择过程复杂化却让遗传算法更贴近 cost-constrained 和 deadline-constrained 的双重目标。这也是调度优化里经常会遇到的取舍一个好调度方案不只是“能跑完”还要“花得值”。五、第二处亮点不可行解不是简单惩罚而是诊断后修复本文最核心的贡献是 SRC²即Selective Repair under Combined Criteria。传统 repair 方法可能会简单地随机调整任务资源或者只根据单一指标进行重分配。IoTGA-SRC² 的思路更加细致先判断哪些不可行解值得修再分析为什么超时最后根据原因选择合适的资源。SRC² 大致分为三个阶段。1. 先选择哪些不可行解值得修第一阶段是选择要修复的不可行解。并不是所有不可行解都值得修。有些解可能离可行区域太远修复成本很高有些解虽然不可行但只差一点点可能通过少量调整就能满足 deadline。IoTGA-SRC² 会根据当前种群中不可行解的比例以及每个不可行解的 violation degree选择那些更有可能被修复、且修复价值更高的个体。如果不可行解比例很低算法也不会强行修复所有不可行解而是保留进化搜索自身继续优化的空间。这点很重要。因为 repair 不是越多越好。过度修复可能会削弱遗传算法本身的搜索多样性让算法过早收敛到某些局部区域。