Abstract: Focusing on the characteristics of resource under large-scale, heterogeneous and dynamic environment in cloud computing, a workflow task scheduling algorithm based on resource fuzzy clustering was proposed. After quantizing and normalizing the resource characteristics, this algorithm integrated the theory of clustering to divide the resources based on the workflow task model and the resource model constructed in advance. The cluster with better synthetic performance was chosen firstly in scheduling stage. Therefore, it shortened the matching time between the task and the resource, and improved the scheduling performance. By comparing this algorithm with HEFT (Heterogeneous Earliest Finish Time) and DLS (Dynamic Level Scheduling), the experimental results show that the average SLR (Schedule Length Ratio) of this algorithm was smaller than that of HEFT by 3.4%, the DLS by 9.9%, and the average speedup of this algorithm was faster than that of HEFT by 59%, the DLS by 10.2% with the increase of tasks in a certain range of [0,100]; when the resources were increased in a certain range of [0,100], the average SLR of this algorithm was smaller than that of HEFT by 3.6%, the DLS by 9.7%, and the average speedup of this algorithm was faster than that of HEFT by 4.5%, the DLS by 10.8%. The results indicate that the proposed algorithm realizes the reasonable division of resources, and it surpasses HEFT and DLS algorithms in makespan.

Key words: cloud computing, workflow task scheduling, resource characteristics, fuzzy clustering, resource division

摘要： 针对云计算环境中资源具有规模庞大、异构性、多样性等特点，提出了一种对资源进行模糊聚类的工作流任务调度算法。经过对网络资源属性进行量化、规范化，以预先构建的任务模型和资源模型为基础，结合模糊数学理论划分资源，使得在任务调度时能够较准确地优先选择综合性能较好的资源类簇，缩短了任务资源相匹配的时间，提高了调度性能。通过仿真实验将此算法与HEFT、DLS进行比较，实验结果表明，当任务在[0,100]范围增加时，该算法平均SLR比HEFT小34%，比DLS小99%，其平均Speedup比HEFT大59%，比DLS大102%；当资源在[0,100]范围增加时，该算法平均SLR比HEFT小36%,比DLS小97%，其平均Speedup比HEFT大45%，比DLS大108%。所提算法实现了对资源的合理划分，且在执行跨度方面具有优越性。

关键词: 云计算, 工作流任务调度, 资源属性, 模糊聚类, 资源划分