融合遗传和粒子群算法的云工作流调度算法

张 宇

(河南财政金融学院 软件学院，河南 郑州 450000)

0 引 言

云计算工作流调度由于其NP难属性得到了广泛研究，工作流应用需要大容量存储空间基础设施和更高的快速并行执行度，而云计算由于可以通过虚拟机化方式以即付即用模式提供基础设施，使其成为适用于工作流调度的有效平台[1-3]。然而，为了提供服务，实现不同目标优化，如执行跨度、执行代价、负载均衡或者能效调度，需要设计有效的工作流调度策略。近年来，多种类型的工作流调度算法已被提出。需要注意的是，给定任务组成的工作流和虚拟机集合，工作流调度可行解是指数级的，生成工作流调度解需消耗大量计算时间和存储空间。而元启发式算法，如遗传算法、粒子群算法成为可以在合理时间和空间内找到近似最优解的可行算法。然而，研究[4]表明混合式元启发式算法比单一算法性能更好。

本文在云环境中提出一种混合元启发式工作流调度算法，同时实现执行跨度优化和负载均衡。算法融合遗传算法和粒子群算法进行工作流调度问题求解。虽然已有算法[5,6]也将遗传算法和粒子群算法混合对任务调度求解。然而，仅仅是独立任务调度问题，不适用于云工作流调度。设计算法利用两个核心操作，即遗传算法中的交叉和变异操作融入粒子群算法的迭代过程中。粒子群相比遗传算法收敛更快，而粒子群算法的限制在于其高维度搜索空间中易于陷入局部最优，且遗传算法同样也有慢速收敛问题，混合元启发式算法将同时避免两种算法的限制。……