云环境中基于分解的多目标工作流调度算法

计算机工程与科学

云环境中基于分解的多目标工作流调度算法

李克武,张功萱,朱昭萌

（南京理工大学计算机科学与工程学院,江苏南京 210094）

收稿日期:2016-04-15 修回日期:2016-06-11 出版日期:2016-08-25 发布日期:2016-08-25
基金资助:
国家自然科学基金（61272420）

A decomposition-based multi-objective workflow scheduling algorithm in cloud environment

LI Ke-wu,ZHANG Gong-xuan,ZHU Zhao-meng

（School of Computer Science and Engineering,Nanjing University of Science and Technology,Nanjing 210094,China）

Received:2016-04-15 Revised:2016-06-11 Online:2016-08-25 Published:2016-08-25

摘要/Abstract

摘要：

云服务提供商在给用户提供海量虚拟资源的同时，也面临着一个现实的问题，即怎样调度这些资源，以最小的代价（完工时间、执行费用、资源利用率等）完成工作流的执行。针对IaaS环境下的工作流调度问题，以完工时间和执行费用作为目标，提出了一种基于分解的多目标工作流调度算法。该算法结合了基于列表的启发式算法和多目标进化算法的选择过程，采用一种分解方法，将多目标优化问题分解为一组单目标优化子问题，然后同时求解这些单目标子问题，使得调度过程更为简单有效。算法利用天马项目发布的现实世界中的工作流进行实验，结果表明，和MOHEFT算法以及NSGA-II*算法相比较，所提出的算法能得到更优的Pareto解集，同时具有更低的时间复杂度。

关键词: 云计算, 科学工作流, 调度算法, 多目标优化

Abstract:

Cloud service providers can provide large-scale virtual computing resources to users, but at the same time they are also facing a scheduling problem, that is how to schedule the computing resources with minimum cost (including makespan, monetary cost, resource utilization rate, etc.) to complete workflow execution. To address the workflow scheduling problem in IaaS, we propose a multi-objective workflow scheduling algorithm based on decomposition which optimizes both the makespan and the monetary cost simultaneously. This algorithm combines the designs of the list-based heuristic algorithm and the multi-objective evolutionary algorithm. Using a decomposition method, it decomposes the multi-objective optimization problem into a set of single objective optimization problems. Then the algorithm focuses on solving single-objective problems, in which way the scheduling process becomes more effective. The experiments based on the real-world applications published by the Pegasus project show that the proposed algorithm can achieve better Pareto fronts and at the same time has lower time complexity in comparison with the MOHEFT algorithm and the NSGA-II* algorithm.

Key words: cloud computing, scientific workflow, scheduling algorithm, multi-objective optimization

李克武,张功萱,朱昭萌. 云环境中基于分解的多目标工作流调度算法[J]. 计算机工程与科学.

LI Ke-wu,ZHANG Gong-xuan,ZHU Zhao-meng. A decomposition-based multi-objective workflow scheduling algorithm in cloud environment [J]. Computer Engineering & Science.

参考文献

［1］Chai Xue-zhi,Cao Jian.Cloud computing oriented workflow technology［J］.Journal of Chinese Computer Systems,2012,33（1）:90-95.（in Chinese）
［2］Topcuoglu H,Hariri S,Wu M Y.Performance-effective and low-complexity task scheduling for heterogeneous computing［J］.IEEE Transactions on Parallel & Distributed Systems,2002,13（3）:260-274.
［3］Pandey S,Wu L,Guru S M,et al.A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments［C］∥Proc of 2010 24th IEEE International Conference on Advanced Information Networking and Applications,2010:400-407.
［4］Yu J,Kirley M,Buyya R.Multi-objective planning for workflow execution on Grids［C］∥Proc of the 8th IEEE/ACM International Conference on Grid Computing,2010:10-17.
［5］Deb K,Pratap A,Agarwal S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-II［J］.IEEE Transactions on Evolutionary Computation,2002,6（2）:182-197.
［6］Zuo Li-yun,Zuo Li-feng.Multi-objective integrated ant colony optimization scheduling algorithm based on cloud resource［J］.Journal of Computer Applications,2012,32（7）:1916-1919.（in Chinese）
［7］Durillo J J,Prodan R.Multi-objective workflow scheduling in Amazon EC2［J］.Cluster Computing,2014,17（2）:169-189.
［8］Zhang Q,Li H.MOEA/D:A multiobjective evolutionary algorithm based on decomposition［J］.IEEE Transactions on Evolutionary Computation,2007,11（6）:712-731.
［9］Yu Nai-bo.Discussion on the model of IaaS service in cloud computing［J］.Telecommunications Science,2011（S1）:39-43.（in Chinese）
［10］Amazon EC2［EB/OL］.［2016-01-13］.http://aws.amazon.com/ec2.
［11］Gong Mao-guo, Jiao Li-cheng, Yang Dong-dong, et al.Research on evolutionary multi-objective optimization algorithms［J］.Journal of Software,2009,20（2）:271-289.（in Chinese）
［12］Juve G,Rynge M,Deelman E,et al.Comparing futuregrid,amazon Ec2,and open science grid for scientific workflows［J］.Computing in Science Engineering,2013，15（4）:20-29.
［13］Bharathi S,Chervenak A,Deelman E,et al.Characterization of scientific workflows［C］∥Proc of the 3rd Workshop on Workflows in Support of Large-Scale Science （WORKS）,2008:1-10.
［14］Zhu Z,Zhang G,Li M,et al.Evolutionary multi-objective workflow scheduling in cloud［J］.IEEE Transactions on Parallel & Distributed Systems,2015,27(5):1344-1357.
附中文参考文献：
［1］柴学智,曹健.面向云计算的工作流技术［J］.小型微型计算机系统,2012,33（1）:90-95.
［6］左利云,左利锋.云资源中多目标集成蚁群优化调度算法［J］.计算机应用，2012，32（7）:1916-1919.
［9］俞乃博.云计算IaaS服务模式探讨［J］.电信科学,2011（S1）:39-43.
［11］公茂果,焦李成,杨咚咚，等.进化多目标优化算法研究［J］.软件学报,2009,20（2）:271-289.

[1]	李卫平1,2，武海燕2，杨杰1. 基于效益博弈的云计算资源动态可协调分配策略研究[J]. J4, 20160101, 38(01): 57-61.
[2]	罗莉, 石伟, 何鸿君, 潘国腾, 王蕾, 龚锐. 一种面向IO Die的敏捷验证方法[J]. 计算机工程与科学, 2023, 45(04): 571-576.
[3]	申晓宁, 游璇, 陈庆洲, 潘红丽, 黄遥. 采用双档案协同进化离散多目标烟花算法的低碳疫苗冷链优化配送[J]. 计算机工程与科学, 2022, 44(12): 2255-2265.
[4]	李文佳, 史岚, 季航旭, 罗意彭. 面向Flink的负载均衡任务调度算法的研究与实现[J]. 计算机工程与科学, 2022, 44(07): 1141-1151.
[5]	杨柏蔼, 赵山, 刘芳. 无服务器计算技术研究综述[J]. 计算机工程与科学, 2022, 44(04): 611-619.
[6]	李艺辉, 刘作军, 李洁. 基于模糊逻辑NSGA-Ⅲ的开关磁阻发电机多目标优化算法[J]. 计算机工程与科学, 2021, 43(03): 542-550.
[7]	李波, 侯鹏, 牛力, 武浩, 丁洪伟. 基于软件定义网络的云边协同架构研究综述[J]. 计算机工程与科学, 2021, 43(02): 242-257.
[8]	张明珠, 曹杰, 王斌. 基于精英集的多目标差分进化聚类算法[J]. 计算机工程与科学, 2021, 43(01): 170-179.
[9]	嵇友浪, 朱君, 邹云峰１, 周子馨, 陈兴. 面向在线客服系统的调度算法研究[J]. 计算机工程与科学, 2020, 42(12): 2242-2251.
[10]	廖建锦, 孙庆骁, 杨海龙, 栾钟治, 钱德沛. 满足工作流执行时限的可抢占虚拟机实例配置和调度方法研究[J]. 计算机工程与科学, 2020, 42(11): 1956-1964.
[11]	关川江, 李建鹏, 史国振, 毛明. 基于关联数据本地化的多密码作业流调度算法[J]. 计算机工程与科学, 2020, 42(11): 1988-1995.
[12]	马永杰, 陈满丽, 陈敏. 基于Pareto解集分段预测策略的动态多目标进化算法[J]. 计算机工程与科学, 2020, 42(08): 1454-1462.
[13]	林涛, 冯竞凯, 郝章肖, 黄少群. 基于组合预测模型的云计算资源负载预测研究[J]. 计算机工程与科学, 2020, 42(07): 1168-1173.
[14]	衡红军, 戚馨桐. 考虑任务均衡的加油车动态调度问题[J]. 计算机工程与科学, 2020, 42(05): 923-930.
[15]	朱登京，段倩倩. 无参分组大规模变量的多目标算法研究[J]. 计算机工程与科学, 2020, 42(04): 603-609.