Mutation and dynamic objective-based farmland fertility algorithm for workflow scheduling in the cloud

• 在 Deadline 约束下最小化执行开销
• 农田肥力算法：从自然界农田的肥力出发的一种新的元启发式算法——农田肥力算法(Farmland fertility algorithm, FFA)，该算法将农田分成若干部分，并在内部存储和外部存储中以两种类型的最优效率对每个部分的解进行优化。

Mutation and dynamic objective-based farmland fertility algorithm for workflow scheduling in the cloud

Proposed algorithm

• 在已有的 Farmland Fertility 算法基础之上的改进：
  1. 首先，采用不同的搜索策略的新部分来增加种群的多样性。
  2. 其次，为了有效地防止其过早收敛问题，重新定义了种群更新机制，即在进化过程和部分粒子中采用单点突变。
  3. 引入动态目标策略，根据约束是否满足来调整当前优化目标，加快收敛速度，更适合求解有约束的优化问题。

Initialization

• 由于云资源是动态的和弹性的，所以资源池的大小是可以变化的。

  • 资源池太大会增加在解空间中寻找近似最优解的难度。

  • 设置资源池大小和任务数量的关系：

    • 是可以被同时处理的任务的最大数量
    • 是虚拟机类型的数量

  • 用均匀分布初始化种群，而不是随机生成。

    $\left{
    \right.$

    • 是种群
    • 是其中一个解，一个粒子
    • 是粒子中的一个维度，的值代表要将第 j 个任务调度给那个虚拟机

• 在得到初始化的种群后，将种群分为三个子种群。

Fitness evaluation

• 根据调度目标，优先考虑 makespan，再考虑 cost。

Dynamic objective strategy

• 动态调整调度目标策略，该策略用于寻找全局最优。

• 对种群中的所有解，先找到其中最短的完工时间，然后将其和约束时间相比较，如果其比约束时间还大，就将 makespan 作为优化目标。

  如果有解的完工时间小于约束时间，就将 cost 作为优化目标。

Updating mechanism

• 局部内存为前所述，用于存储局部部分的最优解，大小约为 0.1n（四舍五入）
  • 不同的 section 使用不同的 updating strategies
• 全局内存用于存储全局最优解，大小约为 0.1N（四舍五入）

Section update

• 对三块，根据调度目标计算其适应值，由此将其分为
  • 对：
  • 对：
  • 对：进行单点变异

Combinational population update

• 根据随机生成的数和设定的数的比较，来确定是进行变异操作还是等式操作。