多QoS约束下网格工作流调度的克隆选择算法  

Grid Computing Workflow Scheduling Clonal Selection Algorithm with Multi-QoS Constraints

作　　者：赵建峰[1,2] 曾文华[2,3] 刘敏[1,2] 张雪[2,3] 

机构地区：[1]厦门大学信息科学与技术学院智能科学与技术系,厦门361005 [2]厦门大学福建省仿脑智能系统重点实验室,厦门361005 [3]厦门大学软件学院,厦门361005

出　　处：《模式识别与人工智能》2011年第5期713-722,共10页Pattern Recognition and Artificial Intelligence

基　　金：国家自然科学基金项目(No.60672018;40774065);国家863计划项目(No.2006AA01Z129)资助

摘　　要：多QoS约束下的工作流调度是网格计算中难以求解的问题.在深入剖析该问题难解性基础上,采用克隆选择算法求解该问题.首先通过增加网格服务的唯一标识,简化工作流调度的编码方式.其次,提出QoS偏好的概念,将调度问题的目标函数转换为适应值函数.该算法具有QoS属性的可扩展性.最后通过大量实验,优化算法参数,与基于遗传算法、蚁群算法的调度算法对比,克隆选择算法求解效率较优.在扩展情况下,与单一QoS约束下的时间、费用贪婪算法对比,克隆选择算法能进行最优调度.Workflow scheduling with muhi-QoS constraints is hard to be solved under the grid computing environment. A clonal selection algorithm, named EvoWF, is proposed to solve workflow scheduling problem based on deep analysis on the difficulty of this problem. The encoding of working scheduling is simplified by adding the grid service identification. The concept of QoS preference is proposed, which converts object function of workflow scheduling to fitness function, and QoS attributes can be extended. Compared to genetic algorithm and ant colony optimization, EvoWF is more efficient. In extension, EvoWF gets the same optimum scheduling results compared with the single-QoS constraint greed time or cost algorithm. Moreover, the effect of parameters is analyzed by experiments.

关 键 词：工作流调度 克隆选择算法 多QOS约束 网格计算 

分 类 号：TP393.01[自动化与计算机技术—计算机应用技术]