云计算环境下基于遗传算法的优化的多任务调度算法
Multi-Task Scheduling Algorithm Based on Genetic Algorithm in Cloud Computing Environment

作者: 孙政 :山东科技大学,信息科学与工程学院,山东 青岛;

关键词: 任务调度遗传算法K-means聚类云计算Task Scheduling Genetic Algorithm K-Means Cluster Cloud Computing

摘要: 任务调度是云计算中的一个关键问题,遗传算法是一种能较好解决优化问题的算法。本论文针对遗传算法在任务调度过程中随着任务调度问题复杂度增加,算法的性能出现下降的现象,引入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.

文章引用: 孙政 (2016) 云计算环境下基于遗传算法的优化的多任务调度算法。 计算机科学与应用, 6, 317-322. doi: 10.12677/CSA.2016.66038

参考文献

[1] Botta, A., de Donato, W., Persico, V., et al. (2016) Integration of Cloud Computing and Internet of Things: A Survey. Future Generation Computer Systems, 56, 684-700.
http://dx.doi.org/10.1016/j.future.2015.09.021

[2] Kampas, S.R., Tarkowski, A.R., Portell, C.M., et al. (2016) System and Method for Cloud Enterprise Services. US Patent 9,235,442.

[3] Haque, M.N., Noman, N., Berretta, R., et al. (2016) Heterogeneous Ensemble Combination Search Using Genetic Algorithm for Class Imbalanced Data Classification. PloS One, 11, 1-28.
http://dx.doi.org/10.1371/journal.pone.0146116

[4] Bahrami, M. and Singhal, M. (2015) The Role of Cloud Compu-ting Architecture in Big Data. Information Granularity, Big Data, and Computational Intelligence. Springer International Publishing, Berlin Heidelberg, 275-295.

[5] 朱宗斌, 杜中军. 基于改进GA的云计算任务调度算法[J]. 计算机工程与应用, 2013, 49(5): 77-80.

[6] Demir, Y. and İşleyen, S.K. (2014) An Effective Genetic Algorithm for Flexible Job-Shop Scheduling with Overlapping in Operations. International Journal of Production Research, 1-17. (Ahead-of-Print).

[7] Xu, Y., Li, K., Hu, J., et al. (2014) A Genetic Algorithm for Task Scheduling on Heterogeneous Computing Systems Using Multiple Priority Queues. Information Sciences, 270, 255-287.
http://dx.doi.org/10.1016/j.ins.2014.02.122

[8] Pop, F., Cristea, V., Bessis, N., et al. (2013) Reputation Guided Ge-netic Scheduling Algorithm for Independent Tasks in Inter-Clouds Environments. 2013 27th International Conference on Advanced Information Networking and Applications Workshops (WAINA), IEEE, 772-776.

分享
Top