【摘 要】云计算技术是利用分散的机器组织虚拟的超级计算机，合理利用众多闲置的可用资源，因此，如何高效地使用云计算资源是云计算研究的重点之一，云计算成为一项具有较高学术价值和应用价值的研究。根据云计算的新特性，必须研究新算法来解决一些新出现的问题。在任务调度方面，我们利用无回路有向图（Directed Acyclic Graph）DAG来描述问题，结合遗传算法（Genetic Algorithm）和蚁群算法（Ant Colony Optimization，ACO），从而实现算法。

　　【关键词】云计算；DAG图；遗传；蚁群；任务；融合

　　本文提出一种基于DAG模型的优先级表的依赖任务调度算法。以时间触发调度，采用重复调度。当每次调度事件发生时，包含那些上一次调度事件中已经被调度但还没有开始执行或被迫中断的任务， 还有新到达的任务，。这与云计算中资源的动态性是相应的。

　　在算法实现方面，我们考虑将遗传算法和蚁群算法相结合，利用遗传算法进行前期训练然后利用蚁群算法进一步进行搜索收敛，最终得到最优调度方案。结合云计算任务调度的特点，本文选取遗传算法和蚁群算法的参数设置，将问题转换到云计算任务调度问题上来，提出融合遗传算法[1]和蚁群算法[2][3]的云计算任务调度算法。

　　一、问题提出

　　每个子任务用圆圈表示，圈中T表示任务号，Q表示计算量，而DAG图中的箭头表示子任务之间的优先关系，C（i,j）表示任务Ti与Tj之间的通信量。图1所示，箭头从前驱指向后继，前驱是后继的必要，只有在某个任务的所有前驱都完成时，该任务才被执行。在任务调度过程中重复调度，当每次调度事件发生时，任务组中既包含新到达的任务，。这与云计算中资源的动态性相适应的。算法使用更新的资源信息对任务进行调度，这与动态的云计算环境是相适应的。

　　Fig.1 DAG task graph

　　图1 任务DAG图

　　由各种任务分配方案需要进行优化。如图2任务划分后的一种方案。

　　Fig.2 Sub-task resource allocation plan

　　图2 子任务资源分配图

　　设有m个计算结点所组成的云计算系统P={P1,P2,…，Pm}，每个结点Pj处理能力为d。需要运行m个子任务T={t1,t2,…，tm}，一般地。将任务调度问题描述成如下五元组∑=（T,?,Q,C,X,w）。其中：“？”是T中子任务间的优先关系；Q是一个维的矩阵，其元素qij表示子任务ti在处理机Pj上的执行时间；C是一个维通信矩阵，cij表示子任务ti与tj之间的通信时间；X是一个维的任务分配矩阵，其中Xij=1,表示ti分配到处理机Pj上执行，否则Xij=0；w表示通信和执行之间的差异。

　　二、算法实现

　　利用遗传算法进行前期的训练。得到的信息素作为蚁群算法的初始值，最终得到最优或次优调度方案。

　　（1）设置遗传算法参数；（2）假定遗传算法结束条件；

　　（3）生成初始种群P（0），g=0； （4）计算P（0）中的个体适应值；

　　（5）反复执行，直到满足结束条件；

　　①根据个体适应值及选择策略确定P（g）内选择概率；

　　②进行PC交叉操作；

　　③ 进行Pm变异操作；

　　④计算P（g+1）中个体的适应值，g=g+1；

　　（6）P（G）从中选择适应能力强的个体，放入集合中，作为优化集合；

　　（7）对于集合中的每个优化解，将遗传算法求解结果转换为蚁群算法中的信息素值；

　　（8）设置蚁群算法控制参数；（9）设置蚁群算法结束条件；

　　（10）将m只蚂蚁散布到n个计算结点上；

　　（11）对蚂蚁的分配结果计算目标函数，选取当前的最佳解；

　　（12）更新计算结点的信息素值；

　　（13）若满足蚁群算法结束条件，退出；否则，返回执行步骤（10）。

　　三、总结

　　在云计算环境里调度计算是影响云计算能否成功的最重要的因素之一。由于资源在广域上分布，本质上异构，相异的存取和花费模式、负载和可用性动态变化，因此云计算环境下的任务管理十分复杂。在云计算系统中，如何协调和分配任务，这就是调度需要解决的问题。本文在广泛阅读国内外相关文献后，归纳云计算和任务调度方面的研究成果，提出基于DAG以及融合遗传算法和蚁群算法的动态云计算任务调度算法。

　　通过实验结果分析比较可以看出，本文提出的算法在运行性能上具有一定的优势，充分验证了算法的合理性和有效性。当然，在仿真环境的限制下，可能实验结果有细微的差别，但我们相信本文提出的算法不失为合理而有效的算法。

　　参考文献：

　　[1]Annie S W, Han Y et al.An incremental genetic algorithm approach to multiprocessor scheduling[J],2004,15（9）：824-834

　　[2] Dorigo M,Gambardella L M.Ant colony system: A cooperative learning approach to the traveling salesman problem,IEEE Trans. Evolutionary Computation[J],1997,1（1）：53-66

　　[3] HUI YAN，XUE-QIN SHEN et al. AN IMPROVED ANT ALGORITHM FOR JOBSCHEDULING IN GRID COMPUTING.IEEE Proceeding of the Fourth International Conference on Machine Learning and Cybernetics[C], Guangzhou, August 2005:2957-2961

　　[4] Foster I,Kesselman C,Tuccke. The Anatomy of the Grid：Enabling Scalable Virtual Organizations[J].International Joural of Supercomputer Application，2001；15（3）：200-222

　　[5]I Foster,C Kesselman.Grid Services for Distributed System Integration[J].Computer,2002,35（6）：37-46

　　[6] 孙玉涛，网格计算环境中的动态任务调度算法研究，云南师范大学硕士论文。2007

　　本文系2014年安徽财经大学校级科研项目（ACKY1428，ACKY1451）、2014年安徽省教育科学规划项目（JG13001）

　　作者简介：孙玉涛（1980- ），男，山东烟台人，研究方向：计算机软件与理论。