Computer Science

Computer Science ›› 2019, Vol. 46 ›› Issue (11): 315-322.doi: 10.11896/jsjkx.181001866

• Interdiscipline & Frontier • Previous Articles     Next Articles

Load Balancing Scheduling Optimization of Cloud Workflow Using Improved Shuffled Frog Leaping Algorithm

XU Jun, XIANG Qian-hong, XIAO Gang   

  1. (College of Computer Science and Technology,Zhejiang University of Technology,Hangzhou 310023,China)
  • Received:2018-10-08 Online:2019-11-15 Published:2019-11-14

PDF (PC)

913

Abstract: In instance-intensive and open cloud environments,workflow scheduling always suffers from frequent calls of the cheap and high-quality resources,resulting in poor scheduling efficiency and disruption of stability.In addition,unlike general task scheduling,workflow tasks usually have associated dependencies,which greatly increase the complexity of task assignment.Aiming at the imbalance of load between cloud virtual machines,a workflow hierarchical scheduling model was proposed,which is hierarchically divided according to task priorities so as to alleviate virtual machine load pressure.Besides,to optimize the shuffled frog leaping algorithm(ISFLA),the time greedy strategy is applied to initia-lize population,as a result,improving the search efficiency.Then,by enhancing the position of best solutions locally,a reconstruction strategy was put forward to go out of the dilemma of local optimum.Finally,the experimental results in cloud workflow scheduling show that the improved shuffled frog leaping algorithm can optimize load balance degree and is more effective in task processing as well as searching compared with the traditional shuffled frog leaping algorithm and particle swarm optimization.

Key words: Cloud workflow, Load balancing, Local optimum, SFLA, Task scheduling

CLC Number: 

  • TP391
[1]CHAI X Z,CAO J.Cloud Computing Oriented Workflow Technology[J].Journal of Chinese Computer Systems,2012,33(1):90-95.(in Chinese)
柴学智,曹健.面向云计算的工作流技术[J].小型微型计算机系统,2012,33(1):90-95.
[2]ZHU Z,ZHANG G,LI M,et al.Evolutionary Multi-Objective Workflow Scheduling in Cloud[J].IEEE Transactions on Parallel & Distributed Systems,2016,27(5):1344-1357.
[3]CHEN H K,ZHU J H,ZHU X M,et al.Resource-Delay-Aware Scheduling for Real-Time Tasks in Clouds[J].Journal of Software,2017,54(2):446-456.(in Chinese)
陈黄科,祝江汉,朱晓敏,等.云计算中资源延迟感知的实时任务调度方法[J].软件学报,2017,54(2):446-456.
[4]ZHENG H S,YU D J,ZHANG L.Multi-QoS Cloud Workflow Scheduling Based on Firefly Algorithm and Dynamic Priorities[J].Computer Integrated Manufacturing Systems,2017,23(5):963-971.(in Chinese)
郑宏升,俞东进,张蕾.基于萤火虫算法和动态优先级的多QoS云工作流调度[J].计算机集成制造系统,2017,23(5):963-971.
[5]ULLMAN J D.NP-complete scheduling problems[M].AcademicPress,Inc.1975.
[6]RAHMAN M,VENUGOPAL S,BUYYA R.A Dynamic Critical Path Algorithm for Scheduling Scientific Workflow Applications on Global Grids[C]∥IEEE International Conference on E- Science and Grid Computing.IEEE Computer Society,2007:35-42.
[7]ZHU Y,LI W,LUO J Z.Multi-User Oriented Load-Aware Dynamic Service Selection Model[J].Journal of Software,2014,25(6):1196-1211.(in Chinese)
朱勇,李伟,罗军舟.一种面向多用户的负载感知动态服务选择模型[J].软件学报,2014,25(6):1196-1211.
[8]CHEN W,DA S R F,DEELMAN E,et al.Using imbalance metrics to optimize task clustering in scientific workflow executions[J].Future Generation Computer Systems,2014,46(1):69-84.
[9]DHINESH B L D,KRISHNA P V.Honey bee behavior inspired load balancing of tasks in cloud computing environments[J].Applied Soft Computing Journal,2013,13(5):2292-2303.
[10]TAWFEEK M A,EL-SISI A,KESHK A E,et al.Cloud taskscheduling based on ant colony optimization[C]∥International Conference on Computer Engineering & Systems.IEEE,2014:64-69.
[11]SUN L Y,LING M,ZHU P,et al.Load balancing Task Scheduling Algorithm Based on Tabu Search in Cloud Computing[J].Journal of Chinese Computer Systems,2015,36(9):1948-1952.(in Chinese)
孙凌宇,冷明,朱平,等.云计算环境下基于禁忌搜索的负载均衡任务调度优化算法[J].小型微型计算机系统,2015,36(9):1948-1952.
[12]EUSUFF M,LANSEY K,PASHA F.Shuffled frog-leaping algorithm:a memetic meta-heuristic for discrete optimization[J].Engineering Optimization,2006,38(2):129-154.
[13]LUO X H,YANG Y,LI X.Modified shuffled frog-leaping algorithm to solve traveling salesman problem[J].Journal on Communications,2009,30(7):130-135.(in Chinese)
罗雪晖,杨烨,李霞.改进混合蛙跳算法求解旅行商问题[J].通信学报,2009,30(7):130-135.
[14]WANG L,FANG C.An effective shuffled frog-leaping algorithm for multi-mode resource-constrained project scheduling problem[J].Information Sciences,2011,181(20):4804-4822.
[15]KAUR P,MEHTA S.Resource provisioning and workflowscheduling in clouds using augmented Shuffled Frog Leaping Algorithm[M].Academic Press,2017.
[16]JUVE G,CHERVENAK A,DEELMAN E,et al.Characterizing and profiling scientific workflows[J].Future Generation Computer Systems,2013,29(3):682-692.
[17]THANT P T,POWELL C,SCHLUETER M,et al.A Level-Wise Load Balanced Scientific Workflow Execution Optimization Using NSGA-II[C]∥IEEE/ACM International Symposium on Cluster,Cloud and Grid Computing.ACM,2017:882-889.
[18]EUSUFF M M,LANSEY K E.Optimization of Water Distribution Network Design Using the Shuffled Frog Leaping Algorithm[J].Journal of Water Resources Planning & Management,2003,129(3):210-225.
[19]CHEN H,WANG F,NA H,et al.User-priority guided Min-Min scheduling algorithm for load balancing in cloud computing[C]∥Parallel Computing Technologies.IEEE,2013:1-8.
[20]CHEN W,DEELMAN E.WorkflowSim:A toolkit for simulating scientific workflows in distributed environments[C]∥IEEE,International Conference on E-Science.IEEE,2013:1-8.
[21]ACCORSI R,STOCKER T.Discovering Workflow Changeswith Time-Based Trace Clustering[M]∥Data-Driven Process Discovery and Analysis.Berlin:Springer,2017:154-168.
[22]ALAM M,SHAKIL K A,SETHI S.Analysis and clustering of workload in google cluster trace based on resource usage[C]∥Computational Science and Engineering (CSE) and IEEE Intl Conference on Embedded and Ubiquitous Computing (EUC) and 15th Intl Symposium on Distributed Computing and Applications for Business Engineering (DCABES).IEEE,2016:740-747.
[23]DENG Y,CHENG X H.A heterogeneous multiprocessor taskscheduling algorithm based on SFLA[C]∥World Automation Congress.IEEE,2016:1-5.
[24]CHEN W N,ZHANG J.A set-based discrete PSO for cloudworkflow scheduling with user-defined QoS constraints[C]∥IEEE International Conference on Systems,Man,and Cyberne-tics.IEEE,2012:773-778.
[25]TAO X L,WEI Y,WANG Y.A Load Balancing Method Based on Hierarchy and Multi-agent for Cloud Computing Platform.Acta Electronica Sinica,2016,44(9):1068-1077.(in Chinese)
陶晓铃,韦毅,王勇.一种基于分层多代理的云计算负载均衡方法.电子学报,2016,44(9):1068-1077.
[26]WANG L.Research and implementation of task scheduling algorithm in cloud environment.Chengdu:University of Electronic Science and Technology of China,2016.(in Chinese)
王玲.云计算下任务调度算法的研究与实现.成都:成都电子科技大学,2016.
[27]WANG Y W,GUO Y F,LIU W Y,et al.A Task Scheduling Method for Cloud Workflow Security.Joural Computer Research and Development,2018,55(6):66-75. (in Chinese)
王亚文,郭云飞,刘文彦,等.面向云工作流安全的任务调度方法.计算机研究与发展,2018,55(6):66-75.
[1] TIAN Zhen-zhen, JIANG Wei, ZHENG Bing-xu, MENG Li-min. Load Balancing Optimization Scheduling Algorithm Based on Server Cluster [J]. Computer Science, 2022, 49(6A): 639-644.
[2] GAO Jie, LIU Sha, HUANG Ze-qiang, ZHENG Tian-yu, LIU Xin, QI Feng-bin. Deep Neural Network Operator Acceleration Library Optimization Based on Domestic Many-core Processor [J]. Computer Science, 2022, 49(5): 355-362.
[3] SHEN Biao, SHEN Li-wei, LI Yi. Dynamic Task Scheduling Method for Space Crowdsourcing [J]. Computer Science, 2022, 49(2): 231-240.
[4] TAN Shuang-jie, LIN Bao-jun, LIU Ying-chun, ZHAO Shuai. Load Scheduling Algorithm for Distributed On-board RTs System Based on Machine Learning [J]. Computer Science, 2022, 49(2): 336-341.
[5] XIA Zhong, XIANG Min, HUANG Chun-mei. Hierarchical Management Mechanism of P2P Video Surveillance Network Based on CHBL [J]. Computer Science, 2021, 48(9): 278-285.
[6] SONG Hai-ning, JIAO Jian, LIU Yong. Research on Mobile Edge Computing in Expressway [J]. Computer Science, 2021, 48(6A): 383-386.
[7] WANG Zheng, JIANG Chun-mao. Cloud Task Scheduling Algorithm Based on Three-way Decisions [J]. Computer Science, 2021, 48(6A): 420-426.
[8] ZHENG Zeng-qian, WANG Kun, ZHAO Tao, JIANG Wei, MENG Li-min. Load Balancing Mechanism for Bandwidth and Time-delay Constrained Streaming Media Server Cluster [J]. Computer Science, 2021, 48(6): 261-267.
[9] YAO Ze-wei, LIU Jia-wen, HU Jun-qin, CHEN Xing. PSO-GA Based Approach to Multi-edge Load Balancing [J]. Computer Science, 2021, 48(11A): 456-463.
[10] CAI Ling-feng, WEI Xiang-lin, XING Chang-you, ZOU Xia, ZHANG Guo-min. Failure-resilient DAG Task Rescheduling in Edge Computing [J]. Computer Science, 2021, 48(10): 334-342.
[11] YANG Zi-qi, CAI Ying, ZHANG Hao-chen, FAN Yan-fang. Computational Task Offloading Scheme Based on Load Balance for Cooperative VEC Servers [J]. Computer Science, 2021, 48(1): 81-88.
[12] GUO Fei-yan, TANG Bing. Mobile Edge Server Placement Method Based on User Latency-aware [J]. Computer Science, 2021, 48(1): 103-110.
[13] ZHANG Long-xin, ZHOU Li-qian, WEN Hong, XIAO Man-sheng, DENG Xiao-jun. Energy Efficient Scheduling Algorithm of Workflows with Cost Constraint in Heterogeneous Cloud Computing Systems [J]. Computer Science, 2020, 47(8): 112-118.
[14] GAO Zi-yan and WANG Yong. Load Balancing Strategy of Distributed Messaging System for Cloud Services [J]. Computer Science, 2020, 47(6A): 318-324.
[15] HUANG Mei-gen, WANG Tao, LIU Liang, PANG Rui-qin and DU Huan. Virtual Network Function Deployment Strategy Based on Software Defined Network Resource Optimization [J]. Computer Science, 2020, 47(6A): 404-408.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.