Multi-objective workflow scheduling based on genetic algorithm in cloud environment

• 调度目标是降低 makespan 和 energy consumption。
• 创新点：用 LCS 调整不同个体的交叉和变异概率，以保留优异的基因块。
  • 为了防止因此种群的交叉变异陷入局部最优，在前期并不使用 LCS 机制，只有当种群进化了一定的轮数之后，才开始使用 LCS 机制。

Multi-objective workflow scheduling based on genetic algorithm in cloud environment

Proposed approach

Encoding scheme and initialization

• 工作流调度要解决两方面的问题：工作流任务和虚拟机调度关系的确定以及工作流任务执行顺序的确定。

  • 表示任务和虚拟机之间的调度关系。
  • 表示任务的执行顺序，肯定是第一位，肯定是最后一位。

• 任务执行序列的形成：

  1. 对给定的任务集，令。
  2. 新建集合、。
  3. 对中的每一个任务，如果其 predecessor 都在中，则，由此形成集合。
  4. 随机从中取出任务，令，，。
  5. 重复步骤3、4，直到为 空。从而得到任务执行序列。

• 为了降低 makespan，将数据量大的任务（数据量大于所有任务平均数据量的任务）直接分配给处理能力最大的虚拟机。

Genetic operators

Crossover

• 交叉分为两部分：工作流任务和虚拟机调度关系的交叉以及工作流任务执行顺序的交叉。
  • 均使用单点交叉。

Mutation

• 变异分为两部分：工作流任务和虚拟机调度关系的变异以及工作流任务执行顺序的变异。
  • 对工作流任务和虚拟机调度关系的变异没什么好说的。
  • 对工作流任务执行顺序的变异：
    1. 在中随机选择一个基因要进行变异。
    2. 从前往后遍历，直到所有被遍历到，记录此时的位置。
    3. 从后往前遍历，直到所有被遍历到，记录此时的位置。
    4. 在和之间随机选择一个位置作为所在的任务变异后的位置。

Selection

• 为了提高搜索帕累托最优解的效率，用到了最长公共子序列 LCS。

  • 用动态规划解决寻找 LCS 问题。

• 将 offspring 的选择和 LCS 相结合：

  1. 将父代种群和新种群合并。
  2. 对合并后的种群进行非支配排序和拥挤度计算。再根据非支配等级和拥挤度对种群中的个体进行排序。
  3. 继而进行选择。
  • 值得一提的是，目前比较常用的 offspring 选择策略是 NSGA-Ⅱ 中的非支配排序和拥挤度计算。
  • LCS 在选择阶段的作用：
    • 如果当前个体包含有优异个体的 LCS，则降低当前个体的交叉和变异概率（所以每个个体都有其不同的交叉和变异概率），则在下一轮的交叉变异过程中，该个体的交叉和变异可能性就会下降，防止对优良的基因块造成破坏。

• 为了防止因此种群的交叉变异陷入局部最优，在前期并不使用 LCS 机制，只有当种群进化了一定的轮数之后，才开始使用 LCS 机制。