面向云计算环境任务调度的改进蚁群算法

摘要

Task scheduling problem in cloud computing environment is a NP-complete problem, the aim of task scheduling is to reasonably distribute tasks on every processing nodes to accomplish optimum scheduling scheme and complete tasks efficiently. Aiming at easily plunging into local optimization of ant colony optimization, an improved algorithm is presented to make total completing time of tasks shortest and computational cost lowest. It adopts two-point crossover operator in ant colony algorithm to improve its local search ability. Simulations on CloudSim platform shows that improved ant colony algorithm short-ens the total completing time of tasks and reduces the computational cost. Meanwhile, it can effectively solve the problem of task scheduling in cloud computing environment and has better optimization ability and convergence speed than ant colony algorithm and improved discrete particle swarm algorithm.%云计算环境下的任务调度问题是一个NP完全问题，其目的是在各个处理节点上合理分配任务，优化调度策略以保证有效完成任务。以总任务完成时间最短和计算成本最低为优化目标，针对蚁群优化算法易陷入局部最优的缺陷，提出了一种求解该问题的改进蚁群算法。该算法将遗传算法的二点交叉算子融入到蚁群优化算法中，以提高蚁群优化算法的局部搜索能力。通过在云仿真平台CloudSim上进行仿真实验，结果表明改进蚁群算法缩短了总任务完成时间，降低了计算成本，从而证明了该算法能有效地解决云计算环境下的任务调度问题，并且其优化能力和收敛速度优于蚁群优化算法和改进离散粒子群算法。