Reliability-Aware Multi-Objective Memetic Algorithm for Workflow Scheduling Problem in Multi-Cloud System

一篇在多云场景下，考虑了可靠性、完工时间、开销的多目标工作流调度论文，使用的是文化基因算法。
Memetic 算法是一个进化框架，它通过基于种群的全局搜索和基于个体的局部搜索相结合来实现最优化。
基于种群的全局搜索：遗传因子、进化策略、寻优编程
基于个体的局部搜索：模拟退火法、贪心策略、针对特定问题的社区搜索策略

Reliability-Aware Multi-Objective Memetic Algorithm for Workflow Scheduling Problem in Multi-Cloud System

Problem Statement

Multi-cloud System Scheduling Architecture

多云系统调度框架的核心在于 “the resources negotiation module”，它由三部分组成：
- “the task estimation module” 根据接收到的工作流应用和多云中可用的资源，计算工作流任务执行的参数；
- “the multi-objective optimization module” 接着会根据参数生成一组非支配解集（最小化开销、完工时间，最大化可靠性）
- “the schedule module” 执行用户从解集中选出的一个解

对于多云：$\psi = \left{\right.$
- 是第 m 个云中虚拟机的数量
- 每个云服务提供商有一个计费时间单元，根据计费单元的个数（即租赁资源时间 /）计费。
- 每个虚拟机都有四个参数：
  - ：虚拟机的计算能力
  - ：虚拟机的内存大小
  - ：单位时间间隔内的价格
  - ：虚拟机失效的概率
对于云内的虚拟机之间的带宽：100Mbps，对于云间的虚拟机之间的带宽：20Mbps

Workflow Model

- 任务集合
  - 任务的大小为
    - 和内存相关的部分
    - 和CPU相关的部分
    - 是一个比例系数
- 任务之间的依赖关系：
  - 任务和之间的通信大小
每个任务都可以运行在任何虚拟机上
- 任务的执行时间
  - ：任务中和 CPU 相关的部分
  - ：任务中和内存相关的部分
  - ：任务的内存大小需求上界
  - γ：单处理器的加速比，这里设置为 2/3
  - ：虚拟机的性能下降因子
- 任务的开始时间
  - ：数据传输完成时间，data communication finish time
    - ：通信完成时间
  - ：资源完成时间，即资源开始空闲时间，resource completion time
- 任务的结束时间
- 通信完成时间
  - ：通信完成时间
  - ：通信消耗时间
    $EC(e_{i,j}) = \left{\right. $，假设$ t_i $执行在$ vm_{k,z} $上，$ t_j $执行在$ vm_{l,x}$ 上
- ：资源开始使用的时间

Problem Formulation

租赁开销：
总开销：
工作流完工时间：
可靠性：用泊松分布来描述：
这篇论文用任务备份来提高可靠性，对于任务，若其有一个备份，令是任务执行失败的概率，则
$R(t_i) = \left{\right.$
工作流的可靠性：
多目标优化：
最小化开销 cost 和完工时间 makespan
最大化可靠性 reliability
尝试生成一组帕累托前沿，然后用户可以在这组前沿中选择自己偏好的调度方案。

Proposed algorithm

Memetic algorithm

Memetic 算法是一个进化框架，它通过基于种群的全局搜索和基于个体的局部搜索相结合来实现最优化。
- 基于种群的全局搜索：遗传因子、进化策略、寻优编程
- 基于个体的局部搜索：模拟退火法、贪心策略、针对特定问题的社区搜索策略

Encoding and Initialization

调度解的表示：
- 表示任务和虚拟机之间的调度关系
- 表示备份任务和虚拟机之间的调度关系
- 表示多云资源池提供的虚拟机实例，其值为虚拟机实例所属的类型，这里进一步根据虚拟机类型的计算能力对进行排序
- 表示任务的调度顺序，任务及其备份任务的调度顺序保持一致
  - 对于第 i 个任务，其执行的顺序为，其要调度给第个虚拟机执行，根据，可以知道该 vm 为第种虚拟机，即虚拟机类型为。
在 “initialization” 阶段，给出四个初始解，用于提高搜索效率：
- ：用 HEFT 算法生成的完工时间最短的解（没有用到任务备份）
- ：对所有任务都备份、用 HEFT 算法生成的解
- ：修改后的 HEFT 算法，每次调度任务的时候都选择最便宜的虚拟机，生成的调度解
- 类似，但是每个任务都有备份
上述四个初始解的调度顺序都是根据 Upward Rank 来生成的，所以都是一样的。
除了这四个初始解外，还有一些随机生成的解，除了对调度进行随机以外，对任务的执行顺序也进行随机。

Diversification Strategy

这篇论文要研究的问题有四个子问题：
- 任务 task 和虚拟机 vm 之间的映射关系确定
- 备份任务 backup task 和虚拟机 vm 之间的映射关系确定
- 资源池中虚拟机 vm 的类型确定
- 任务的执行顺序确定

Crossover

对任务执行顺序的交叉：对于两个执行顺序和，在 [1, n] 中选择一个随机的截止位置 p，将和分别分成两个子顺序，即、和、。再把、作为后代，而丢弃其他两个。
- 对于，从前往后扫描，对于中的任务，如果其不在中，就将其添加到末尾，这样，就在没有违反任务之间的约束关系的前提下，对任务的执行顺序进行了交叉。
- 对于也同理。
对任务和虚拟机之间的映射关系的交叉（多点交叉）：对于两个映射关系和，对于每个任务，如果小于交叉概率，就进行和的交叉：、。
同时，对于交叉后的 vm，其有一半的概率会改变自己的类型，改变为原来的 vm的类型。（vm指的是根据下标能够得到对应的 vm，并不是说就是 vm）。

Mutation

对任务执行顺序的变异：对于随机选择的一个任务，找到其最近的 parent 和 child，它们的调度顺序分别是和，然后将任务的执行顺序随机插在和之间。
对任务和虚拟机之间的映射关系的变异：对于每个任务，如果小于变异概率，就让随机变异为：。
对于虚拟机和虚拟机类型之间的变异：对于每个虚拟机，如果小于变异概率，就让的类型随机变异为：。

Intensification Strategy

强化策略包含四个针对特定问题的邻近算子：
- CP_perturb：随机将关键路径上的任务调度给别的和当前虚拟机类型不一样的虚拟机
- CP_remove：移除关键路径上的所有备份任务，将关键路径上的剩余任务随机调度给虚拟机
- VM_release：随机选择低使用率的虚拟机，将其上的任务重新调度给别的虚拟机
- VM_backup：随机将虚拟机上的任务备份给使用率低的虚拟机
强化策略是用在外部档案 External archive 的 solution 中的，目的是为了能进一步优化解。

Framework of RA-MOMA

RA-MOMA 包含三个关键的部分：
- 初始化种群
- 多样化策略：利用交叉变异来扩大问题的解空间 -> 全局
- 强化策略：利用四个邻近算子来深入搜索精英解的局部空间 -> 局部

Experimental Study

这篇论文的实验做的非常充分，包括参数设置的理由、消融实验、和其他算法的对比等。

Experimental Setup

实验环境 workflowsim
- 种群迭代进化过程的终止条件是评估函数的使用到了10000次。
数据集：科学工作流
多云：Amazon EC2 、Microsoft Azure
- Amazon EC2 按小时计费
- Microsoft Azure 按分钟计费
对解的评估：用 Hypervolumn 和 Set Coverage 来评估。

Parameters Analysis

实验参数的设置对算法的性能效果有很大的影响，所以对实验参数的不同选取进行分析。
- 对选取的不同的实验参数进行实验，用 ANOVA 对实验结果进行分析，由此来确定实验参数的设置。
  - 最终确定将种群的大小（即种群中解的个数） ps 设置为 150
  - 将交叉概率 cr 设置为 0.1
  - 将变异概率 mr 设置为 0.02
  - 将局部增强大小（即强化策略迭代的次数）ls 设置为 30

Ablation Analysis

为了证明种群初始化、种群多样化策略、强化策略都是起效果的，用消融实验来证明：
- RA-MOMA-NI：去除种群初始化策略的 RA-MOMA
- RA-MOMA-ND：去除种群多样化策略的 RA-MOMA
- RA-MOMA-NIT：去除强化策略的 RA-MOMA
然后用 RA-MOMA-NI、RA-MOMA-ND、RA-MOMA-NIT、RA-MOMA 进行实验，对比实验结果的 Hypervolumn 值来证明种群初始化、种群多样化策略、强化策略都是起效果的。

Comparison to Other Algorithms

主要通过 Hypervolumn 和 Set Coverage 的值来证明，RA_MOMA 优于其它 baseline。