论文标题：A Multi-objective reinforcement learningalgorithm for deadline constrained scientific workflow scheduling in clouds

期刊：Frontiers of Computer Science

作者：Yao QIN, Hua WANG, Shanwen YI, Xiaole LI, Linbo ZHAI

发表时间：15 Oct 2021

DOI：10.1007/s11704-020-9273-z

微信链接：点击此处阅读微信文章

原文信息

• 标题：

A Multi-objective reinforcement learningalgorithm for deadline constrained scientific workflow scheduling in clouds

• 原文链接：

https://journal.hep.com.cn/fcs/EN/10.1007/s11704-020-9273-z

• 引用格式：

Yao QIN, Hua WANG, Shanwen YI, Xiaole LI, Linbo ZHAI. A multi-objective reinforcement learning algorithm for deadline constrained scientific workflow scheduling in clouds. Front. Comput. Sci., 2021, 15(5): 155105

• 公众号推文链接：

云计算中基于多目标强化学习的期限约束科学工作流调度

1导读

云计算可为云用户提供按需服务而受到欢迎，成为当今重要的计算范式之一。随着云计算的普及，云数据中心的能耗问题日益突出：到2030年，云数据中心的用电量将占全球用电量的3%-13%。据悉，亚马逊的数据中心将19%的预算用于云计算的能耗上。数据中心的高能耗不仅增加了运营成本，而且加速了全球气候变暖。研究表明，工作流已成为数据中心的主要能耗源，科学有效的工作流调度方法可有效降低能耗和运行成本。因此，科学工作流调度问题越来越受到研究人员的重视。

为了解决云计算带来的问题，研究人员将工作流调度问题转化成多目标优化问题，通过多目标优化算法科学地降低工作流调度中的能耗和运行成本。然而，大多数现有的多目标工作流调度优化方法忽略了对权重的选择，导致解决方案质量的下降。虽然部分关键路径（PCP）策略被广泛用在期限约束的工作流调度问题中，但其不能准确地反映每个时间步长的工作流调度情况。针对PCP中存在的问题，本文提出了MPCP方法，以解决期限约束下的工作流调度问题。

首先，设计了一种基于多目标强化学习的期限约束科学工作流调度算法，基于Chebyshev标量函数刻画强化学习过程中的Q值，实现了对目标的权重选择；其次，提出了可准确反应每个时间步长的工作流调度情况的MPCP方法。结果表明，本文提出的方法在给定的期限内可以最小的成本和最低的能耗实现对工作流的科学调度。

2模型细节

在DCMORL中，时间步长i的可用动作集用表示，状态空间表示调度阶段每种虚拟机类型的利用率。表示每个虚拟机类型在第i个时间步长的利用率，n表示虚拟机类型的序号。

为了保证工作流能够在期限内被执行，首先为工作流中的每个未执行任务分配子期限，并分别定义最早开始时间和最晚结束时间。定义任务的最早开始时间为，其数学描述为：

上式中，表示任务的所有父任务的集合，表示任务的可能执行时间，其计算如下：

定义最晚结束时间为，其数学描述为：

本文基于分配任务和关键父级的概念构建了MPCP方法。将非计划任务分为两类：分配任务和未分配任务。任务的关键父级定义为：

未分配任务的子期限定义为：

上式中的表示通道P的子期限。

根据每个任务的子期限，可用的动作集可表示为：

上式中表示任务的可能完成时间，其计算方式为：

在强化学习中，通常基于奖励向量优化多目标问题。因此，本文定义奖励向量为 ，而定义为：

上式中表示在不考虑期限情况下的最小执行成本，表示虚拟机类型的单价。

定义为：

式中表示在不考虑期限情况下的最小能耗，表示任务的能量消耗。

在工作流被调度之前，首先要对工作流中的任务进行分级。任务的级别由表示，即

式中表示任务在所有虚拟机类型中的平均执行时间。在强化学习框架下，实现对工作流调度问题的优化。

3 主要贡献

本文的主要贡献有：

（1）制定调度问题，而后基于切比雪夫标量函数设计DCMORL，降低了选择权重的难度。与其他方法相比，Chebyshev标量化函数可在更大的范围内找到解。

（2）为了满足期限约束，提出了一个改进的PCP策略（MPCP）。 MPCP 中的sub-deadlines在调度阶段会定期更新。

（3）提出了一种衡量解决方案质量的指标。

（4）实验表明，DCMORL在执行成本、能耗和超容量方面比其他算法更具优势。

4 实验结果

为了评价算法的性能，本文将所提算法DCMORL与IC-PCPD2， CEAS，S-CEDA和HPSO这四种算法作比较。实验结果表明，在大多数情况下，DCMORL的性能获得了很大的提升。以CyberShake结构为例，其实验结果如图1,2,3所示。图1展示了CyberShake结构工作流执行成本，从图中可看出，执行成本随着期限因子的增加而下降：当a=1.5时，CDMORL的执行成本分别比IC-PCPD2、CEAS、S-CEDA和HPSO的低52.50%、51.57%、41.43%和29.40%；当a上升到4时，DCMORL的执行成本分别比IC-PCPD2、CEAS、S-CEDA和HPSO的降低38.25%、36.97%、13.43%和18.75%。

图2给出了能量消耗的对比图，从图中可看出，能量消耗总体上随着期限因子的增加而下降：当增加时，更多的任务将在具有较低电源电压的虚拟机上执行，其能耗也随之降低。当a=1.5时，DCMORL的能耗比CEAS、S-CEDA和HPSO的低41.48%、28.00%和13.83%。当a上升到4时，DCMORL的能耗分别比CEAS、S-CEDA和HPSO的低36.31%、17.22%和9.93%。

图3展示了不同期限因子下的超容量值（超容量指标用于评估Pareto逼近集的质量）。DCMORL产生的超容量值大于S-CEDA和HPSO产生的超容量值。主要原因是DCMORL根据超容量值选择权重元组，而S-CEDA和HPSO只是将权重设置为相等的值。

Abstract

Recently, a growing number of scientific applications have been migrated into the cloud. To deal with the problems brought by clouds, more and more researchers start to consider multiple optimization goals in workflow scheduling. However, the previous works ignore some details, which are challenging but essential. Most existing multi-objective workflow scheduling algorithms overlook weight selection, which may result in the quality degradation of solutions. Besides, we find that the famous partial critical path (PCP) strategy, which has been widely used to meet the deadline constraint, can not accurately reflect the situation of each time step. Workflow scheduling is an NP-hard problem, so self-optimizing algorithms are more suitable to solve it.

In this paper, the aim is to solve a workflow scheduling problem with a deadline constraint. We design a deadline constrained scientific workflow scheduling algorithm based on multi-objective reinforcement learning (RL) called DCMORL. DCMORL uses the Chebyshev scalarization function to scalarize its Q-values. This method is good at choosing weights for objectives. We propose an improved version of the PCP strategy calledMPCP. The sub-deadlines in MPCP regularly update during the scheduling phase, so they can accurately reflect the situation of each time step. The optimization objectives in this paper include minimizing the execution cost and energy consumption within a given deadline. Finally, we use four scientific workflows to compare DCMORL and several representative scheduling algorithms. The results indicate that DCMORL outperforms the above algorithms. As far as we know, it is the first time to apply RL to a deadline constrained workflow scheduling problem.

解读：胡亚洲 郑州大学

审核：张琨 合肥工业大学

Frontiers of Computer Science

Frontiers of Computer Science （FCS）是由教育部主管、高等教育出版社和北京航空航天大学共同主办、SpringerNature 公司海外发行的英文学术期刊。本刊于 2007 年创刊，双月刊，全球发行。主要刊登计算机科学领域具有创新性的综述论文、研究论文等。本刊主编为周志华教授，共同主编为熊璋教授。编委会及青年 AE 团队由国内外知名学者及优秀青年学者组成。本刊被 SCI、Ei、DBLP、INSPEC、SCOPUS 和中国科学引文数据库（CSCD）核心库等收录，为 CCF 推荐期刊；两次入选“中国科技期刊国际影响力提升计划”；入选“第4届中国国际化精品科技期刊”；入选“中国科技期刊卓越行动计划项目”。

《前沿》系列英文学术期刊

由教育部主管、高等教育出版社主办的《前沿》（Frontiers）系列英文学术期刊，于2006年正式创刊，以网络版和印刷版向全球发行。系列期刊包括基础科学、生命科学、工程技术和人文社会科学四个主题，是我国覆盖学科最广泛的英文学术期刊群，其中13种被SCI收录，其他也被A&HCI、Ei、MEDLINE或相应学科国际权威检索系统收录，具有一定的国际学术影响力。系列期刊采用在线优先出版方式，保证文章以最快速度发表。

中国学术前沿期刊网

http://journal.hep.com.cn