林海涛,姜栋瀚

(海军工程大学 电子工程学院，武汉 430033)

基于重建策略的云工作流调度算法优化

林海涛,姜栋瀚

(海军工程大学 电子工程学院，武汉 430033)

为了进一步提高算法性能，提出一种改进的蛙跳算法，并与调度方案相结合，以期为云工作流资源分配提供最优调度。通过在蛙跳算法的局部搜索中加入重建策略，提高了数据随机性，有效避免了局部最优。研究了调度方案生成算法，与改进算法相结合得到接近最优的调度。利用Java模拟器进行仿真试验，并与粒子群优化算法和传统蛙跳算法作比较。实验证明，提出的方法可以在满足最长截止时间约束的情况下，使总执行成本最小化。

蛙跳算法；资源调度；云工作流；重建策略

0 引 言

基础设施即服务(IaaS)是云计算最基本的应用形式[1]。当用户提出应用请求后，IaaS通过管理中间件中的任务管理机制为任务分配虚拟化资源，其资源调度机制是影响云计算效能的关键。云计算中的按需配置和资源可用性使其成为执行工作流应用程序的理想选择。然而，工作流调度是一个非确定性多项式(non-deterministic polynomial，NP)问题，云计算环境的异质性和动态性又使问题进一步复杂化。资源调度高效算法是提升云工作流系统效能亟待解决的问题，也是云计算领域内的研究热点。

工作流是指将一组任务按照业务需求进行合理传递的工作流程。工作流中任务数量大小不等，但所有任务需要分配至不同的虚拟资源，并在合理的时间内完成。……