云环境下基于改进蚁群算法的任务调度

Task Scheduling Based on Improved Ant Colony Algorithm in Cloud Environment

云计算是能够提供动态资源池、虚拟化和高可用性的计算平台,达到可扩展性和高可用性两个重要目标。其中云计算任务调度负责为用户的计算任务分配合适的资源,成为云计算一个核心问题。由于云计算任务调度问题是NP-hard问题,近些年提出的启发式(heuristics)算法和元启发式(meta-heuristics)算法取得了良好的效果,蚁群算法作为元启发式算法有良好的鲁棒性和并行性,适合求解组合优化问题。元启发式算法相比较启发式算法求解精度高,但算法运行时间长,基于精英策略的蚁群算法虽能加快收敛速度却易陷入局部最优。为了扩大蚁群搜索空间,防止算法陷入局部最优解,对信息素更新和最优路径奖励进行了改进。实验证明改进后的蚁群算法降低了最大完成时间和不平衡程度,提高了云资源的利用率。

Cloud computing is a computing platform that provides dynamic resource pooling,virtualization and high availability,achieving scalability and high availability of two important goals.Among them,the cloud computing task scheduling is responsible for allocating the appropriate resources for the user’s computing tasks and becomes a core issue of cloud computing.Because cloud computing task scheduling is NP-hard problem,heuristics and meta-heuristics algorithms in recent years are proposed to achieve better results.The ant colony algorithm as a meta-heuristic algorithm has strong robustness and parallelism,which is suitable for solving combinatorial optimization problems.Compared with the heuristic algorithm,meta-heuristic algorithm has higher solution precision,but runs for a long time.Although the ant colony algorithm based on the elite strategy can speed up the convergence speed,it is easy to fall into the local optimum.In order to expand the ant colony search space and prevent the algorithm from falling into the local optimal solution,the pheromone update and the optimal path reward are improved.Experiment shows that the improved ant colony algorithm can reduce the maximum completion time and degree of unbalance,and improve the cloud resource utilization.