基于资源分组的多约束云工作流调度算法  

Multi-Constrained Scheduling Algorithm of Cloud Workflow Based on Resource Grouping

作　　者：陈爱国[1] 王玲[1] 任金胜[1] 罗光春[1] 

机构地区：[1]电子科技大学计算机科学与工程学院,成都611731

出　　处：《电子科技大学学报》2017年第3期562-568,共7页Journal of University of Electronic Science and Technology of China

基　　金：四川省科技支撑计划(2016GZ0075;2016GZ0077);四川省技技厅国际合作项目(2017HH0075)

摘　　要：已有的云工作流调度算法采用全局搜索方式进行资源选取,存在计算成本高、对大规模云系统适应性差的问题。该文提出了基于资源分组的多约束云工作流调度算法,采用有向无环图的方法,对云工作流中的多任务之间的执行顺序和数据交换等属性进行量化建模;使用模糊聚类方法实现基于资源多维特征的分组处理,降低工作流任务到资源匹配过程中的搜索空间;并引入执行时间和成本预算约束,将工作流的任务调度问题转化为有约束条件的极小极大问题进行快速求解。仿真测试表明,该算法显著降低了任务执行完成时间和成本。The existing cloud workflow scheduling algorithms, using the global search for resource selection, exist a high computational cost and poor adaptability for large-scale cloud systems. Aimed at solving these problem, a multi-constrained cloud workflow scheduling algorithm based on resource grouping is proposed in this paper. It uses the direct acyclic graph to model the multi-task in cloud workflow and characterize the execution sequences and data transfer requirement between tasks with the DAG＇s node and edge＇s attributes. Then, fuzzy clustering method is employed to classify resources based on multidimensional features and reduce the computational load from workflow tasks to resource selection. By introducing execution time and cost budget constraints, the proposed algorithm transforms the scheduling problem into a minimax problem. Simulation results show that our algorithm significantly reduces the task execution time and cost.

关 键 词：云计算 云工作流 模糊聚类 资源分配 调度算法 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]