云计算环境下基于遗传算法的优化的多任务调度算法

Multi-Task Scheduling Algorithm Based on Genetic Algorithm in Cloud Computing Environment

摘要: 任务调度是云计算中的一个关键问题，遗传算法是一种能较好解决优化问题的算法。本论文针对遗传算法在任务调度过程中随着任务调度问题复杂度增加，算法的性能出现下降的现象，引入K-means聚类算法，提出一种基于K-means聚类和遗传算法的云计算环境下任务调度的新算法。该算法借鉴 K-means 聚类方法的思想在任务调度前对任务进行聚类预处理，然后根据遗传算法的机制进行任务调度，并提出了时间–负载均衡约束的适应度函数，优化了变异算子。仿真实验结果表明，该算法在云环境下任务调度中具有较高的效率和性能。

Abstract: Task scheduling is a key problem in cloud environments and genetic algorithm is a good method to find a solution for this problem. For the phenomenon of genetic algorithm in task scheduling process the complexity of the task scheduling problem increased and algorithm performance declined. In this paper, a genetic algorithm based on K-means cluster method with time and load balancing constraint is proposed. This algorithm uses K-means cluster method to classify the tasks at the beginning of scheduling and uses genetic algorithm to scheduling tasks of each class. More-over, we proposed a time-load balancing constraints fitness function and optimized the mutation operator. Experiment results show that the proposed algorithm gives a better solution.