计算能力的重要性日益被认识到是推动技术进步和高效执行各种任务的关键因素。智能计算领域的最新进展证明了数据驱动学习框架在复杂现实世界系统中的有效性[1]，[2]。这一趋势在广泛的学习范式和问题设置中也得到了体现，突显了数据驱动方法的广泛应用[3]，[4]，[5]。这样的智能计算范式通常需要大量的、可扩展的计算能力，无论是用于训练还是部署。云计算（CC）[6]是一种广泛使用的并行处理模型，它可以根据需求向用户提供处理器、内存、磁盘和通信网络等强大资源，无论用户位于何处。因此，将复杂任务卸载到云节点上已成为设备性能不足的用户的一个可行解决方案。这些任务通常被组织成复杂的工作流[7]，即旨在简化流程并确保高效执行的任务序列。第五代（5G）移动网络的最新发展[8]以及物联网（IoT）[9]等新应用领域改变了网络资源的访问模式。为了最小化延迟并提高服务质量，资源正在被重新部署到更接近最终用户的地方。这种转变催生了边缘计算（EC）[10]的概念。EC在数据源附近进行数据处理和分析。由于边缘节点位于生成数据的设备更近的地方，它们可以比云节点更快地做出响应。EC中的任务通常是要求快速响应的相对简单的工作流。
然而，应用程序的复杂性和多样性日益增加，这凸显了需要一种更细致的方法来弥合EC和CC之间的差距，从而产生了雾计算（FC）[6]，[11]，[12]。通常，FC通过中间节点（如网关、路由器或专用雾服务器）进行操作，这些节点位于边缘设备和云数据中心之间。这些雾节点提供了更接近网络边缘的计算和存储能力，但资源比单个边缘设备更多。FC通过支持任务的层次化分布，实现了更可扩展和灵活的服务部署：一些在边缘处理，一些在雾节点处理，其余的在云中处理[6]。这种分层架构提高了系统的响应能力，减少了核心网络的拥塞，并支持需要实时和高吞吐量处理的应用程序，例如智慧城市[13]、自动驾驶汽车[14]和工业自动化[15]。
尽管应用范围广泛，但在FC环境中的工作流调度仍然是一项远非简单的任务。工作流通常包含具有严格优先级和资源限制的相互依赖的任务，必须将它们映射到最合适的节点上，以优化诸如完成时间、预算和服务质量等重要目标[16]。此外，雾节点在计算能力、能源容量和网络带宽方面的异构性给调度过程带来了相当大的复杂性[6]。与以集中控制和丰富资源为特征的常规云环境不同，FC环境需要能够适应环境部分观测结果以及工作流到达、资源可用性和用户移动性的动态变化的去中心化调度策略[17]。这些困难促使本研究提出了一种新的分布式雾计算（DWSDFC）动态工作流调度模型，该模型具有到达的工作流、有限的资源和部分观测结果。与许多工作流调度问题类似，DWSDFC可以分为两个子问题：（1）从等待池中选择任务的排序；（2）将任务分配给节点的路由。
已经提出了许多启发式方法[19]，[20]、元启发式方法[21]，[22]和机器学习方法[23]，[24]来解决类似环境中的工作流调度挑战，每种方法在可扩展性、执行时间和解决方案质量方面都有各自的权衡。启发式方法通常轻量且快速，适用于实时场景。然而，它们往往依赖于固定的调度规则，容易陷入局部最优解。相比之下，元启发式方法进行全局搜索，可能产生更好的解决方案，但计算密集度较高，不太适合高度动态或时间受限的环境。
深度强化学习（DRL）[25]，[26]最近作为一种有前途的替代方案出现，因为它能够通过与环境的交互学习动态调度策略。多项研究探索了DRL在解决动态工作流调度问题中的应用，包括单智能体[27]，[28]，[29]和多智能体[30]，[31]设置。通常，DRL假设一个固定且有限的行动空间。然而，在FC的工作流调度背景下，这一常见假设并不总是适用。例如，任务排序决定了从候选池中执行的任务，其中每个行动都是选择一个单独的候选者。然而，这个候选池包含不同数量的候选任务。为了解决这个问题，一些研究[32]，[33]将调度规则作为行动使用。在这种设置下，DRL智能体能够选择其中一个规则，并识别出优先级最高的任务，而不管候选任务的数量如何变化。
显然，作为行动的可用调度规则集在DRL的性能中起着至关重要的作用。正是出于这个原因，本研究专注于为DRL自动设计基于调度规则的行动。为此，应用了遗传编程（GP）[34]，这是一种搜索满足给定规范的计算机程序的进化算法。这些计算机程序通常被编码为表达式树，并通过遗传操作符（例如子树交叉和子树变异）进行进化。GP在自动编程[35]、符号回归[36]和作业车间调度[37]等多个领域取得了成功应用。
为了增强进化规则的多样性和DRL的性能，我们引入了一种基于规则之间行为差异的生态位技术[38]。之后，使用了一个多智能体DRL框架，其中每个智能体对应一个子问题，并使用双重决斗深度Q网络（D3QN）[39]，[40]，[41]进行训练，以选择进化的行动。在本文的其余部分，我们将所提出的方法称为带有进化行动的DRL（DRL-EA）。这种混合设计比单独使用任一方法都有明显的优势。与产生单一固定规则的纯GP不同，DRL-EA使用学习到的策略根据当前系统状态选择不同的规则，从而更好地适应动态条件。与从手动设计的规则中选择的标准DRL不同，DRL-EA操作于由GP自动生成的更丰富的规则集。由于生态位机制，这些规则既高性能又多样化，为有效的策略学习提供了坚实的基础。在实验中，DRL-EA在大量的DWSDFC实例上进行了测试，与常见的调度规则以及基线DRL和GP方法进行了比较。实验结果突显了DRL-EA在解决DWSDFC方面的显著优势。这进一步证明了我们自动化设计DRL中行动的想法的有效性。本研究的主要贡献如下。
(1)介绍了一种名为DWSDFC的新工作流调度模型，该模型具有到达的工作流、有限的资源和部分观测结果，以捕捉FC中遇到的困难。
(2)采用基于D3QN的多智能体DRL框架来解决DWSDFC。这两个智能体分别对应于DWSDFC的排序子问题和路由子问题。
(3)首次在FC的工作流调度中提出了DRL行动的自动设计思想。为了实现这一思想，应用GP来搜索有前途的调度规则作为行动。
(4)将生态位技术集成到GP算法中，以增强生成的基于规则的行动的行为多样性，从而提高DRL的性能。
(5)通过在大量实例上的全面比较实验验证了所提出方法DRL-EA的有效性，这些实例涵盖了多种比较方法。
本文的其余部分组织如下。第2节提供了本研究的充分背景知识。第3节详细介绍了DWSDFC的数学建模。第4节介绍了所提出的方法DRL-EA，并在第5节进行了测试。最后，第6节总结了研究并指出了几个未来的研究方向。
