云计算是一种按量计费的商业计算模式[1]，目的在于使用一切可以使用的资源为用户提供更好的服务。云计算任务调度是云计算的重要研究方向，调度算法对于云计算的性能的优劣有着重要的影响。任务调度主要可以分为确定性任务调度和不确定性任务调度。对任务调度算法进行分析总结，论述其优缺点，并分析云计算任务调度存在的主要障碍，对云计算任务调度算法做出总结和展望。
由于云资源以即付即用的方式交付，用户愿意提交和执行任务包云上的应用程序。从云提供商的角度来看，当云提供商的私有云没有足够的资源来处理用户提交的BoT应用程序[2]以满足用户指定的服务质量(QoS)要求时，云提供商不得不将一些任务外包给公共云，从而产生额外的成本。关键问题是如何在混合云上安排任务，以在满足QoS要求的同时最大化利润。但是，大多数现有算法都存在函数收敛陷入局部最优的情况，且后期收敛速度慢，这通常会导致违反应用程序截止日期并影响提供给用户的服务质量，且利润得不到最大化。因此，本课题拟针对混合云环境下具有截止时间约束的任务调度与资源优化问题展开研究，面向计算和数据双密集型众包应用构建相应的任务调度模型，致力于在保证云计算平台服务质量的同时最大化云提供商的利润。本文总结了当前部分任务调度算法，并对此进行评估总结。
- 任务调度算法分析
在许多文献中，已经探讨过云计算任务调度算法的改进及优化，对任务调度问题进行了大量的研究。如宋等人[3]在其工作中，旨在支持能够支持用户多种服务需求的云计算服务管理，提出了顺序组合选择任务法和动态规划算法选择任务组合法，改进了任务执行时间预测方法。刘[4]从在线调度策略和批量调度策略两个方面对云计算资源调度进行了研究，提出了快速分配方法。Anunugamand等人[5]提出了在相同队列中动态调度具有相同优先级和特征的作业的方法。Ardagna等人[6]提出了资源分配算法，旨在在保证用户服务质量的同时，最小化虚拟机实例分配的成本。张[7]提出了一种基于工作负荷预测的容量分配技术，该技术可以协调在不同地理分布的云站点上工作的各种分布式资源控制器。Pelaez等人[8]提出了一个调度器和一个估计器，可以通过采样估计任务的运行时间。换句话说，他们提出的调度器不需要知道先前的任务运行时间。
而在本文中，则将介绍常见的几种任务调度算法并对其进行分析。如遗传算法GA[9]、粒子群优化算法PSO[10-11]、Firefly算法FA[12]、模拟退火算法SA[13]、蚁群算法ACO[14-15]等。
1.1遗传算法（GA）[9]
遗传算法（Genetic Algorithm, GA）起源于对生物系统所进行的计算机模拟研究。它是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法，能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最佳解。
该算法形式化描述如下：
a)初始化:设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。
b)个体评价:计算群体P(t)中各个个体的适应度。
c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。
