云计算环境下基于装箱策略的多目标调度方法

The task scheduling is a NP-complete problem in the cloud computing environment, and there are some problems needed to be solved, such as scheduling with insufficient objects, the low efficiency of the scheduling model, designing the scheduling policy in a single system level, and deficiency of the way to evaluate the performance of algorithms. Aiming at these problems, a multi-objective scheduling strategy based on the bin-packing policy is proposed, and the research contents are presented as follows. First, the scheduling objects include minimizing application's makespan, reducing the energy consumption of the platform and improving the system's robustness, so that mapping relationship between the application and resources are defined, and a general mathematical model for the multiple scheduling objects in the cloud is presented. Second, considering the uncertainty of the computing resources and tasks in the cloud, a hierarchical resource model is discussed in the application level, in the resource level, as well as in the benefit level. Third, in order to be adaptable to different cloud environments, several multi-objective scheduling algorithms based on bin packing strategy are proposed, such as the scheduling algorithm with batch packing, the one with variable-size bin packing, as well as the with open-end bin packing. Finally, with a thorough study on the control of the algorithms, a framework to evaluate the heuristic algorithms is provided. The implementation of the project presents a feasible method for multi-objective scheduling in the cloud environment, which will enhance the overall performance of the cloud computing platform, and expand the range of applications in the cloud.

云计算环境下的任务调度问题是一个NP完全问题，且存在着调度目标少、调度模型效率低、调度层次单一、算法性能评价方法缺失等亟待解决的问题。针对这些问题，提出基于装箱策略的多目标调度机制，内容包括：（1）针对最小化应用完成时间、减少云平台能耗、提高系统的健壮性等多目标，定义云计算 环境下应用-资源匹配关系，进而研究云计算环境下多目标调度策略的一般数学模型；（2）综合考虑云计算节点资源与计算任务的不确定性，以层次化思想分别研究以应用为中心、以资源为中心和以效益为中心的资源模型；（3）为了应对各种云计算应用环境，基于装箱策略，研究利用批量装箱机制、变尺寸装箱机制和Open-end装箱机制设计多目标调度算法；（4）深入研究算法的调控机制，提供一种针对启发式算法的评价模型和方法。项目的实施为云计算中的多目标任务调度提供一种可行的方法实践，进而提升云计算平台的综合性能，拓展云计算应用的范围。

由于云计算具有分布性、虚拟化等特征，传统的分布式调度策略不能直接处理云计算环境下的资源分配和任务调度；为了适应云环境的复杂性，面向云环境下的多个目标，综合考虑云计算节点资源与计算任务的不确定性，从应用层和资源层协同设计，研究基于装箱策略的多目标任务调度方法。首先，提出了云环境下任务调度的多种目标规划模型：研究面向各个目标的任务调度的线性规划模型，结合多个目标的优先因子，研究多目标综合调度的目标规划模型。其次，研究云环境下的调度资源模型：基于用户的服务质量，构建一种资源主动匹配架构；基于层次化结构，由上至下包括请求接收器、负载分析器、资源匹配器以及虚拟机创建器；结合系统负载，研究了云环境下的动态资源匹配策略。接着，研究了基于装箱策略的调度算法：针对基于同构虚拟机的云计算环境、基于异构虚拟机的云计算环境和基于弹性虚拟机部署方式的云计算环境，结合任务调度目标模型和资源限制模型，研究了利用装箱策略研究适应于各种云计算环境的任务调度算法。最后，研究云计算环境下调度的性能评价方法，构建了一个基于云计算的虚拟实验室管理系统，提出一种动态的虚拟机生成机制，并相应地扩展了一种云计算模拟器。在项目的实施过程中，已完成多篇SCI论文、国内中文核心期刊论文、国际会议等，另有多篇论文在审稿中；已授权专利2项，公开专利3项，已授权软件著作版权2项；培养了3名博士和7名硕士。在应用上，项目的实施一方面为在线的实验室管理机制提供个性化的一体化实验过程解决方案，部分成果已经应用在教学改革及实际的在线教育过程中；另一方面，构建了基于动态资源管理机制的云计算仿真平台，能够匹配实际的云环境，扩展了应用范围，推进了云计算的发展。