针对于云计算的任务调度问题，长期以来学术界进行了大量的深入研究与探讨，并提出了基于不同策略的众多任务调度算法。

如图中所示，最小完成时间(Minimum Completion Time, MCT)[3]、轮循调度算法(Round Robin, RR) [4]等属于传统算法。在当前的复杂云计算环境下，传统算法已经无法应对复杂工作流和各种先进的云计算架构。相应地，任务调度算法越来越多的采用启发式搜索的策略。常用的基于启发式思想的方法包括遗传算法(Genetic Algorithm, GA)[5]、粒子群算法(Particle Swarm Optimization, PSO) [6]、模拟退火算法(Simulated Annealing, SA)[7]、蛙跳算法(Shuffled Frogleaping Algorithm, SFLA) [8]、蚁群优化算法(Ant Colony Optimization, ACO) [9]等。这些算法在任务调度过程中搜寻最佳调度的效率较高，但也存在易于早熟的缺陷，导致搜寻到的调度结果陷入局部最优。

相关研究表明，大部分任务调度问题可以归结为多约束的NP难问题[10]。此类问题通常会导致较高的计算时间复杂度[11]。国内外的大量学者通过研究表明将PSO算法应用于云计算任务调度问题上，能够取得相对较好的效果。Pandey等将PSO算法应用于云环境中的启发式工作流调度，并且获得了比较理想的调度结果[12]。在此基础上，赵莉提出基于改进量子粒子群算法（Quantum-behaved Particle Swarm Optimization, QPSO）的云计算任务调度算法，在采用QPSO求解最佳调度的同时，对平均最佳位置进行随机变化，使得搜寻粒子尽可能避免陷入局部最优解[13]。此外，邬开俊等在任务调度过程中引入了粒子离散化思想，增强了粒子群优化算法的离散程度，从而获得了较高的云计算任务调度性能[14]。

参 考 文 献

[1] 王意洁,孙伟东,周松. 云计算环境下的分布存储关键技术 [J]. 软件学报, 2012, 23(4): 962-986.

[2] FU X, CANG Y. Task scheduling and virtual machine allocation policy in cloud computing environment [J]. 系统工程与电子技术（英文版）, 2015, (4): 847-856.

[3] 钟一文,杨建刚. 异构计算系统中独立任务调度的混合遗传算法 [J]. 北京航空航天大学学报, 2004, 30(11): 1080-1083.

[4] TAHIR M A, BOURIDANE A. Novel Round-Robin Tabu Search Algorithm for Prostate Cancer Classification and Diagnosis Using Multispectral Imagery [J]. IEEE transactions on information technology in biomedicine, 2006, 10(4): 782-793.

[5] QI R-Z, WANG Z-J, LI S-Y. A Parallel Genetic Algorithm Based on Spark for Pairwise Test Suite Generation [J]. 计算机科学技术学报（英文版）, 2016, (2): 417-427.

[6] 郭力争,耿永军,姜长源. 云计算环境下基于粒子群算法的多目标优化 [J]. 计算机工程与设计, 2013, 34(7): 2358-2362.

[7] 朱颢东,钟勇. 一种改进的模拟退火算法 [J]. 计算机技术与发展, 2009, 19(6): 32-35.

[8] 李英海,周建中,杨俊杰. 一种基于阈值选择策略的改进混合蛙跳算法 [J]. 计算机工程与应用, 2007, 43(35): 19-21.

[9] 王登科, 李忠. 基于粒子群优化与蚁群优化的云计算任务调度算法 [J]. 计算机应用与软件, 2013, 30(1): 290-293.

[10] GHADER H M,FAKHR K,ARZIL S A. A hybrid method for task scheduling [C]. proceedings of the International Conference on Education Technology and Computer, 2010: V1-91-V1-95.

[11] 杨焕. 云计算环境下任务调度策略的研究 [D]. 河南大学, 2013.

[12] PANDEY S, WU L, GURU S M, et al. A Particle Swarm Optimization-Based Heuristic for Scheduling Workflow Applications in Cloud Computing Environments [C]. IEEE International Conference on Advanced Information Networking and Applications, 2010:400-407.

[13] 赵莉. 基于改进量子粒子群算法的云计算资源调度 [J]. Cloud computing resource scheduling based on improved quantum particle swarm optimization algorithm, 2016, (2): 223-228.

[14] 邬开俊,鲁怀伟. 云环境下基于DPSO的任务调度算法 [J]. 计算机工程, 2014, (1): 59-62.