云计算任务调度机制中多目标有向超图优化划分问题研究

随着云计算基础架构大量使用廉价的服务器集群，采用分而治之的策略将分散的应用程序任务按照特定的约束条件划分为多个规模较小的任务子集，并调度到不同的虚拟机上，能有效地减少资源空闲时间，提高资源的利用效益，促进云计算产业的迅速发展。本项目从云计算任务调度问题中多约束、多目标任务划分的实际需求出发，对依赖任务建立赋权有向超图模型，以多目标超图优化划分问题为主要研究目标，探索基于多水平方法的多约束、多目标的超图优化划分方法和理论；研究和解决粗化阶段的结点匹配策略、初始划分阶段的最小粗化超图划分方法、投影优化阶段的结点多目标迁移优化技术等关键科学问题，为得到超图的非劣最优划分集提供有效的理论和实验依据；进而将云计算任务优化划分问题转换为多目标超图优化划分问题，提出云计算任务调度系统的创新思路和整套技术路线。本项目的研究将对提高云计算任务调度机制的性能和云计算核心技术的研究水平有着重要的意义。

随着云计算基础架构大量使用廉价的服务器集群，采用分而治之的策略将分散的应用程序任务按照特定的约束条件划分为多个规模较小的任务子集，并调度到不同的虚拟机上，能有效地减少资源空闲时间，提高资源的利用效益，促进云计算产业的迅速发展。本项目系统地研究了云计算任务调度机制中多目标赋权有向超图优化划分问题，提出了基于多水平方法的多约束、多目标的赋权超图优化划分方法，主要研究工作如下：（一）针对赋权超图，提出了核值等概念并给出了形式化描述，分析了赋权超图k水平p-核的构造性属性，实现了时间复杂度为O(n)的结点核值求解算法；（二）在多水平方法的粗化阶段，提出了基于赋权超图压缩存储格式的核排序重边匹配算法，将结点核值全局信息引入到粗化超图的结点匹配过程，发挥结点核值的导向性作用；（三）在多水平方法的投影优化阶段，提出了基于离散群智能的结点多目标迁移优化算法，将结点迁移的收益值作为个体的启发式搜索信息，利用个体之间聚集协同表现出的智能行为，有效地搜索Pareto有效解；（四）给出了云计算环境下的依赖任务调度优化问题的形式化描述，采用赋权有向超图构造依赖任务调度优化问题的数学模型，实现了支持云计算特性的用户任务分解以及到赋权有向超图的转换系统；（五）将基于多水平方法的多目标赋权超图优化划分应用在云计算任务调度中，提出了基于多水平划分法和赋权有向超图的云计算任务调度方法，实现了云计算任务调度原型系统。本项目的研究成果对提高云计算任务调度机制的性能和云计算核心技术的研究水平有着重要意义。