A dynamic multipopulation genetic algorithm for multiobjective workflow scheduling based on the longest common sequence

A dynamic multipopulation genetic algorithm for multiobjective workflow scheduling based on the longest common sequence

DMGA approach

encoding & initialization

• 染色体 Chromosome 由两部分组成：

  • 任务执行序列

    • 初始化：如果任务的 predecessors 都已经被调度了，就将任务加入集合 S 中，然后在确定执行序列中下一个被执行的任务时，从 S 中随机取出一个。

      以此来保证任务之间的执行约束关系。

  • 任务和虚拟机之间的映射关系

    • 初始化：这篇论文其中一个调度目标是降低 makespan，所以优先将处理量大的任务分配给计算能力大的虚拟机。

  这两部分的长度都应该是任务的个数，即染色体的长度是任务的个数大小。

multipopulation framework

• 将种群划分为多个子种群（根据非支配排序和拥挤度计算），分别用不同的进化算子进行扩张。
  • superior：将其中前 k 个个体视为最优，用 LCS 取得这些个体的共同调度序列，标记为 bestLCS
    • 用于探索更优解和加快收敛速度
  • ordinary
    • 用于权衡 superior 和 inferior
  • inferior：将其中后 k 个个体视为最劣，用 LCS 取得这些个体的共同调度序列，标记为 inferiorLCS
    • 用于跳出局部最优

Genetic operation

Local search strategy

• 一个调度序列的局部序列的变化（局部任务执行顺序的变化，局部任务和虚拟机映射关系的变化），对最终的调度结果可能会有显著的影响。

Crossover

• 对任务的执行顺序与任务和虚拟机之间的映射关系都应该进行交叉操作。

  不使用传统的交叉操作简单的进行交叉，而是保留 superior 中的优异的调度序列结构，“摧毁” inferior 中的劣势的调度序列结构。