一、课题背景和意义：
一个云计算的简单定义是：云计算是一种虚拟化的、分布式和按需分配的、通过网络实现的计算和服务平台。[1]云计算能够以即付即用模式的形式提供大规模计算资源，并且由于规模经济而带来低成本和良好的投资回报。作为云计算的重要一部分，设备即服务变得非常流行。设备即服务提供者可以提供各种不同的虚拟机类型，不同类型的虚拟机拥有不同的CPU、内存以及价格。
众包任务应用程序由许多独立的任务组成，因此可以在没有同步或通信的情况下并行处理。[2]众包任务应用广泛应用于计算机成像，计算生物学，参数扫描，分形计算，数据挖掘等[3]。理论上，云计算环境是执行众包任务应用程序的理想平台[4]，因为云资源按照即付即用的方式交付，并且允许它们要尽可能快地执行，而不会为获得的快速周转带来额外的成本。因此，用户愿意在云上提交和执行众包任务应用程序。
云提供商接受多个订单，每个订单都有多个众包任务应用程序执行。从提供商的角度来看，如果多个众包任务应用程序以用户指定的服务质量需求执行，那么当私有云无法承担所有应用程序的任务时，云提供商必须将某些任务外包给公共云。因此，对云提供商而言，关键问题在于在满足服务质量需求的前提下，在混合云上如何合理安排任务以最大化收益[5]。
二、国内外研究现状：
在之前的诸多文献中，已经做了许多努力来研究混合云环境中的包任务调度问题。宋浒[6]在其工作中，以能够支持用户多种服务需求的云计算服务管理为目标，提出了顺序组合选择任务法、动态规划算法选择任务组合法等方法，以改进对任务执行时间预测的方法。刘晓茜[7]则分别从在线调度策略和批调度策略两个方面对云计算资源调度进行了研究，其方法中将优先级、截止时间、收益和资源风险等调度因素进行了综合评价，在此基础上提出了快速分配方法。其在线调度策略可适用于云资源的快速在线分发，但尚未考虑任务特性及异构资源的影响，因此其对混合云的适用度有限。云南大学的李锋华[8]以快速调度和负载均衡为目标，设计了基于蚁群算法的云计算资源调度负载均衡算法。该方法能够在多负载影响因素下得到均衡的最优解，但其计算复杂度较高，当资源规模较大时，其求解效率下降较快。东北师范大学邹丰阳[9]提出了混合云环境下的资源管理模型，针对混合云的特殊环境，实现了基于蚁群算法的资源调度算法。该工作对于混合云的资源特性分析较深入，覆盖了其异构性的主要特征，但对于调度算法，未涉及任务特性，因此无法直接适用于混合云上的任务调度。左利云[10]等人针对混合云调度中私有云利用率不高和公有云费用偏高的问题,基于性能和费用目标提出了两种调度策略——截止时间优先和费用优先策略,建立了混合云中的任务和资源模型,能够根据用户提交的任务需求自适应选择合适的调度资源,对截止时间要求比较高的任务可以优先调度至公有云,对费用要求高的任务可以优先调度至私有云,而且两种策略均满足截止时间和一定的费用约束。北京交通大学的李建丽等[11]提出混合云环境下基于二次聚类的多目标任务调度算法，通过二次聚类将异构资源按照其综合性能进行分簇, 解决混合云的资源异构问题;在此基础上, 选择满足任务需求并且最接近于任务截止时间的资源聚类, 更有效地完成任务对资源的选择。后来，同作者重点研究了如何结合用户的多目标需求,如何高效地将任务映射到合适的计算节点上[12]。
Anunugamand等[13]提出了将具有相同优先级和相同特点的作业放在同一队列中进行动态调度的方法，方法一方面按照任务的紧急程度，设置优先级，并为任务的设置一个等待时间阈值，保证任务不能等待很长时间，另一方面按照作业的特点，如计算密集型，内存密集型或者网络带宽密集型，动态定制和迁移虚拟机，并针对虚拟机提出了一种智能调度技术，通过监视负载类型和截止时间和计算系统花费，最大化在允许的截止时间内作业数。Ardagna等[14]提出资源分配能有效地解决负载的波动，同时保证用户的服务质量，其目标是最小化分配虚拟机实例的花费。张国香等[15]提出了基于工作负载预测的能力(容量)分配技术，可以协调多种工作在不同地理分布云站点的分布资源控制器，同时提出了一种动态负载重定向机制允许对请求做接近瞬时和智能的决策，当云处于高峰负载时，不得不从负载繁重的站点重定向到其他站点。
Van den Bossche等人[16]将问题描述为整数规划问题，并使用IBM CPLEX来解决问题。后来，同一作者[17]研究了一个更复杂的计算和数据密集型BTSP，并考虑了使用虚拟机实例和传输数据的成本。这个问题也被制定为整数规划问题，并提出了两个具有成本效益的启发式方法来解决它。Malawski等人[18]处理了一个特定的众包任务调度，其中只包含一个应用程序并将其表述为混合整数非线性问题。 Wang等人[19]专注于一种特殊的众包任务调度，其中考虑了私有云内部的物理机。该问题被公式化为二元非线性规划问题，并通过改善物理机的总成本和利用率的方法来解决。 Pelaez等人[20]提出了一个调度器和一个估计器，它能够通过采样来估计任务的运行时间。换句话说，他们提出的调度程序不需要任务运行时的先验知识。 Abdi等人[21]研究了联邦混合云中的BTSP，其中多个云贡献其资源以形成联合。在他们专注的众包任务调度中，每个众包任务应用程序由多个包组成，每个包包含多个独立任务。这种类型的复杂应用程序不同于常见的众包任务应用程序，每个应用程序都包含多个独立任务。这个特殊的众包任务调度问题被制定为二进制线性编程问题，由IBM CPLEX处理。实际上，之前的多个工作都只考虑了一种类型的QoS需求（即截止日期）。由于未指定应用程序所需的虚拟机类型，因此可以在私有云或公共云提供的任何虚拟机类型的实例中执行任务。
三、本课题研究的立论依据
本课题拟针对混合云环境下具有截止时间约束的众包任务的调度与优化展开研究，构建相应的任务调度模型；在理解进化算法的基础上设计改进的遗传算法求解此调度问题，并通过任务调度仿真实验对调度算法的实时性和寻优能力进行验证。
