Grid Computing Workflow Scheduling Clonal Selection Algorithm with Multi-QoS Constraints
ZHAO Jian-Feng1,2, ZENG Wen-Hua2,3, LIU Min1,2, ZHANG Xue2,3
1.Cognitive Science Department, School of Information Science and Technology, Xiamen University, Xiamen 361005 2.Fujian Key Laboratory of the Brain-Like Intelligent Systems, Xiamen University, Xiamen 361005 3.School of Software, Xiamen University, Xiamen 361005
Abstract Workflow scheduling with multi-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.
[1] Foster I, Kesselman C, Tuecke S. The Anatomy of the Grid: Enabling Scalable Virtual Organizations. International Journal of High Performance Computing Applications, 2001, 15(3): 200-223 [2] Yu J,Buyya R. A Taxonomy of Workflow Management Systems for Grid Computing. Journal of Grid Computing, 2006, 3(3): 171-200 [3] Deelman E, Gannon D, Shields M, et al.Workflows and E-Science: An Overview of Workflow System Features and Capabilities. Future Generation Computer Systems, 2009, 25(5): 528-540 [4] Wieczorek M, HoheiseL A, Prodan R. Towards a General Model of the Multi-Criteria Workflow Scheduling on the Grid. Future Generation Computer Systems, 2009, 25(3): 237-256 [5] Yuan Yingchun, Li Xiaoping, Wang Qian, et al. Cost Optimization Heuristics for Grid Workflows Scheduling Based on Serial Reduction. Journal of Computer Research and Development, 2008, 45(2): 246-253 (in Chinese) (苑迎春,李小平,王 茜,等.基于串归约的网格工作流费用优化方法.计算机研究与发展, 2008, 45(2): 246-253) [6] Yu Jia, Buyya R. Scheduling Scientific Workflow Applications with Deadline and Budget Constraints Using Genetic Algorithms. Scientific Programming, 2006, 4(3): 217-230 [7] Jin Hai, Chen Hanhua, Lü Zhipeng, et al. QoS Optimizing Model and Solving for Composite Service in CGSP Job Manager. Chinese Journal of Computers, 2005, 28(4): 578-587 (in Chinese) (金 海,陈汉华,吕志鹏,等.CGSP 作业管理器合成服务的QoS优化模型及求解.计算机学报, 2005, 28(4): 578-587) [8] Zhang Weizhe, Hu Mingzeng, Zhang Hongli, et al. A Multiobjective Evolutionary Algorithm for Grid Job Scheduling of Multi-QoS Constraints. Journal of Computer Research and Development, 2006, 43(11): 1855-1862 (in Chinese) (张伟哲,胡铭曾,张宏莉,等.多QoS 约束网格作业调度问题的多目标演化算法.计算机研究与发展, 2006, 43(11): 1855-1862) [9] Chen Weineng, Zhang Jun. An Ant Colony Optimization Approach to a Grid Workflow Scheduling Problem with Various QoS Requirements. IEEE Trans on Systems, Man and Cybernetics, 2009, 39(1): 29-43 [10] Garrett S. How Do We Evaluate Artificial Immune Systems? Evolutionary Computation, 2005, 13(2): 145-177
2011, Vol. 24 
