Top

The Journal of Supercomputing

Published in:

27-03-2021

A novel cloud workflow scheduling algorithm based on stable matching game theory

Authors: Zhao-hong Jia, Lei Pan, Xiao Liu, Xue-jun Li

Published in: The Journal of Supercomputing | Issue 10/2021

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Workflow scheduling is one of the most popular and challenging problems in cloud computing. However, among the studies on cloud workflow scheduling, very few consider the fairness among workflow tasks which could significantly delay the workflows and hence deteriorates user satisfaction. In this paper, we propose a workflow scheduling algorithm based on stable matching game theory to minimize workflow makespan and ensure the fairness among the tasks. The local optimization methods based on critical path and task duplication are developed to improve the performance of the algorithm. In addition, a novel evaluation metric is proposed to measure the fairness among workflow tasks. Comprehensive experiments are conducted to compare the performance of the proposed algorithm with other four representative algorithms. Experimental results demonstrate that our algorithm outperforms the other compared algorithms in terms of all three performance metrics under different workflow applications.

previous article A frequency-aware and energy-saving strategy based on DVFS for Spark

next article DYRE: a DYnamic REconfigurable solution to increase GPGPU’s reliability

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Mukherjee D, Nandy S, Mohan S, Al-Otaibi YD, Alnumay WS (2021) Sustainable task scheduling strategy in cloudlets. Sustain Comput: Inform Syst 30:100513

Buyya R, Yeo CS, Venugopal S, Broberg J, Brandic I (2009) Cloud computing and emerging it platforms: vision, hype, and reality for delivering computing as the 5th utility. Fut Gener Comput Syst 25(6):599–616CrossRef

Wu Z, Liu X, Ni Z, Yuan D, Yang Y (2013) A market-oriented hierarchical scheduling strategy in cloud workflow systems. J Supercomput 63(1):256–293CrossRef

Deelman E, Gannon D, Shields M, Taylor I (2009) Workflows and e-science: an overview of workflow system features and capabilities. Fut Gener Comput Syst 25(5):528–540CrossRef

Liu X, Chen J, Liu K, Yang Y (2008) Forecasting duration intervals of scientific workflow activities based on time-series patterns. In: 2008 IEEE 4th International Conference on eScience. IEEE, pp 23–30

Darbha S, Agrawal DP (1998) Optimal scheduling algorithm for distributed-memory machines. IEEE Trans Parallel Distrib Syst 9(1):87–95CrossRef

Xie Y, Zhu Y, Wang Y, Cheng Y, Xu R, Sani AS, Yuan D, Yang Y (2019) A novel directional and non-local-convergent particle swarm optimization based workflow scheduling in cloud-edge environment. Fut Gener Comput Syst 97:361–378CrossRef

Huang B, Li Z, Tang P, Wang S, Zhao J, Hu H, Li W, Chang V (2019) Security modeling and efficient computation offloading for service workflow in mobile edge computing. Fut Gener Comput Syst 97:755–774CrossRef

Shih CS, Wei JW, Hung SH, Chen J, Chang N (2013) Fairness scheduler for virtual machines on heterogonous multi-core platforms. ACM Sigapp Appl Comput Rev 13(1):28–40CrossRef

10.

Rezaeian A, Naghibzadeh M, Epema DHJ (2019) Fair multiple-workflow scheduling with different quality-of-service goals. J Supercomput 75(2):746–769CrossRef

11.

Jang J, Jung J, Hong J (2019) K-LZF: an efficient and fair scheduling for edge computing servers. Fut Gener Comput Syst 98:44–53CrossRef

12.

Sethuraman J, Teo CP, Qian L (2006) Many-to-one stable matching: geometry and fairness. Math Oper Res 31(3):581–596MathSciNetCrossRef

13.

Zhang Y, Cui L, Zhang Y (2017) A stable matching based elephant flow scheduling algorithm in data center networks. Comput Netw 120:186–197CrossRef

14.

Topcuoglu H, Hariri S, My Wu (2002) Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans Parallel Distrib Syst 13(3):260–274CrossRef

15.

Xian-Fu M, Wei-Wei L (2010) A dag scheduling algorithm based on selected duplication of precedent tasks. J Comput-Aided Des Comput Graph 22(6):1056–1062

16.

Geng X, Xu G, Fu X, Zhang Y (2012) A task scheduling algorithm for multi-core-cluster systems. JCP 7(11):2797–2804

17.

Chen W, Xie G, Li R, Bai Y, Fan C, Li K (2017) Efficient task scheduling for budget constrained parallel applications on heterogeneous cloud computing systems. Fut Gener Comput Syst 74:1–11CrossRef

18.

Samadi Y, Zbakh M, Tadonki C (2018) E-heft: enhancement heterogeneous earliest finish time algorithm for task scheduling based on load balancing in cloud computing. In: 2018 International Conference on High Performance Computing and Simulation (HPCS). IEEE, pp 601–609

19.

Tian-mei zi C, Heng-zhou Y, Zhi-dan H (2018) K-heft: a static task scheduling algorithm in clouds. In: Proceedings of the 3rd International Conference on Intelligent Information Processing, pp 152–159

20.

Sahni J, Vidyarthi DP (2015) A cost-effective deadline-constrained dynamic scheduling algorithm for scientific workflows in a cloud environment. IEEE Trans Cloud Comput 6(1):2–18CrossRef

21.

Zheng W, Qin Y, Bugingo E, Zhang D, Chen J (2018) Cost optimization for deadline-aware scheduling of big-data processing jobs on clouds. Fut Gener Comput Syst 82:244–255CrossRef

22.

Wu T, Gu H, Zhou J, Wei T, Liu X, Chen M (2018) Soft error-aware energy-efficient task scheduling for workflow applications in DVFS-enabled cloud. J Syst Arch 84:12–27CrossRef

23.

Ijaz S, Munir EU (2019) Mopt: list-based heuristic for scheduling workflows in cloud environment. J Supercomput 75(7):3740–3768CrossRef

24.

Zhang H, Zheng X, Xia Y, Li M (2019) Workflow scheduling in the cloud with weighted upward-rank priority scheme using random walk and uniform spare budget splitting. IEEE Access 7:60359–60375CrossRef

25.

Djigal H, Feng J, Lu J, Ge J (2020) IPPTS: an efficient algorithm for scientific workflow scheduling in heterogeneous computing systems. IEEE Trans Parallel Distrib Syst 32(5):1057–1071CrossRef

26.

Geng X, Mao Y, Xiong M, Liu Y (2019) An improved task scheduling algorithm for scientific workflow in cloud computing environment. Clust Comput 22(3):7539–7548CrossRef

27.

Kumar MS, Gupta I, Panda SK, Jana PK (2017) Granularity-based workflow scheduling algorithm for cloud computing. J Supercomput 73(12):5440–5464CrossRef

28.

Gupta I, Kumar MS, Jana PK (2018) Efficient workflow scheduling algorithm for cloud computing system: a dynamic priority-based approach. Arab J Sci Eng 43(12):7945–7960CrossRef

29.

Maheswaran M, Ali S, Siegel HJ, Hensgen D, Freund RF (1999) Dynamic mapping of a class of independent tasks onto heterogeneous computing systems. J Parallel Distrib Comput 59(2):107–131CrossRef

30.

Elsherbiny S, Eldaydamony E, Alrahmawy M, Reyad AE (2018) An extended intelligent water drops algorithm for workflow scheduling in cloud computing environment. Egypt Inform J 19(1):33–55CrossRef

31.

Wu Z, Ni Z, Gu L, Liu X (2010) A revised discrete particle swarm optimization for cloud workflow scheduling. In: 2010 International Conference on Computational Intelligence and Security, IEEE, pp 184–188

32.

Kaur M, Kadam S (2018) A novel multi-objective bacteria foraging optimization algorithm (MOBFOA) for multi-objective scheduling. Appl Soft Comput 66:183–195CrossRef

33.

Hu H, Li Z, Hu H, Chen J, Ge J, Li C, Chang V (2018) Multi-objective scheduling for scientific workflow in multicloud environment. J Netw Comput Appl 114:108–122CrossRef

34.

Huang CL, Jiang YZ, Yin Y, Yeh WC, Chung VYY, Lai CM (2018) Multi objective scheduling in cloud computing using Mosso. In: 2018 IEEE Congress on Evolutionary Computation (CEC). IEEE, pp 1–8

35.

Ding R, Li X, Liu X, Xu J (2018) A cost-effective time-constrained multi-workflow scheduling strategy in fog computing. In: International Conference on Service-Oriented Computing. Springer, pp 194–207

36.

Alsmady A, Al-Khraishi T, Mardini W, Alazzam H, Khamayseh Y (2019) Workflow scheduling in cloud computing using memetic algorithm. In: 2019 IEEE Jordan International Joint Conference on Electrical Engineering and Information Technology (JEEIT). IEEE, pp 302–306

37.

Yang J, Jiang B, Lv Z, Choo KKR (2020) A task scheduling algorithm considering game theory designed for energy management in cloud computing. Fut Gener Comput Syst 105:985–992CrossRef

38.

Gao Z, Wang Y, Gao Y, Ren X (2018) Multi-objective non-cooperative game model for cost-based task scheduling in computational grid. arXiv preprint arXiv:1807.05506

39.

Wang Y, Jiang J, Xia Y, Wu Q, Luo X, Zhu Q (2018) A multi-stage dynamic game-theoretic approach for multi-workflow scheduling on heterogeneous virtual machines from multiple infrastructure-as-a-service clouds. In: International Conference on Services Computing. Springer, pp 137–152

40.

Sujana JAJ, Revathi T, Karthiga G, Raj RV (2015). Game multi objective scheduling algorithm for scientific workflows in cloud computing. In: 2015 International Conference on Circuits, Power and Computing Technologies [ICCPCT-2015]. IEEE, pp 1–6

41.

Zhang M, Li H, Liu L, Buyya R (2018) An adaptive multi-objective evolutionary algorithm for constrained workflow scheduling in clouds. Distrib Parallel Databases 36(2):339–368CrossRef

42.

Chen L, Li X, Ruiz R (2018) Idle block based methods for cloud workflow scheduling with preemptive and non-preemptive tasks. Fut Gener Comput Syst 89:659–669CrossRef

43.

Shishido HY, Estrella JC, Toledo CFM, Arantes MS (2018) Genetic-based algorithms applied to a workflow scheduling algorithm with security and deadline constraints in clouds. Comput Electr Eng 69:378–394CrossRef

44.

Casas I, Taheri J, Ranjan R, Wang L, Zomaya AY (2018) GA-ETI: an enhanced genetic algorithm for the scheduling of scientific workflows in cloud environments. J Comput Sci 6:318–331CrossRef

45.

Saharan S, Somani G, Gupta G, Verma R, Gaur MS, Buyya R (2020) QuickDedup: Efficient VM deduplication in cloud computing environments. J Parallel Distrib Comput 139:18–31CrossRef

46.

Manasrah AM, Ba Ali H (2018) Workflow scheduling using hybrid GA-PSO algorithm in cloud computing. Wirel Commun Mob Comput 2018

47.

Li W, Xia Y, Zhou M, Sun X, Zhu Q (2018) Fluctuation-aware and predictive workflow scheduling in cost-effective infrastructure-as-a-service clouds. IEEE Access 6:61488–61502CrossRef

48.

Ismayilov G, Topcuoglu HR (2018) Dynamic multi-objective workflow scheduling for cloud computing based on evolutionary algorithms. In: 2018 IEEE/ACM International Conference on Utility and Cloud Computing Companion (UCC companion). IEEE, pp 103–108

49.

Adhikari M, Koley S (2018) Cloud computing: a multi-workflow scheduling algorithm with dynamic reusability. Arab J Sci Eng 43(2):645–660CrossRef

50.

Kumar MS, Gupta I, Jana PK (2017) Delay-based workflow scheduling for cost optimization in heterogeneous cloud system. In: 2017 10th International Conference on Contemporary Computing (IC3). IEEE, pp 1–6

51.

Choudhary A, Gupta I, Singh V, Jana PK (2018) A GSA based hybrid algorithm for bi-objective workflow scheduling in cloud computing. Fut Gener Comput Syst 83:14–26CrossRef

52.

Luo F, Yuan Y, Ding W, Lu H (2018) An improved particle swarm optimization algorithm based on adaptive weight for task scheduling in cloud computing. In: Proceedings of the 2nd International Conference on Computer Science and Application Engineering, pp 1–5

53.

Mohanapriya N, Kousalya G, Balakrishnan P, Pethuru Raj C (2018) Energy efficient workflow scheduling with virtual machine consolidation for green cloud computing. J Intell Fuzzy Syst 34(3):1561–1572CrossRef

54.

Center SC (2014). Cybershake and epigenomics scientific workflow. https://confluence.pegasus.isi.edu/display/pegasus/WorkflowGenerator

Title: A novel cloud workflow scheduling algorithm based on stable matching game theory
Authors: Zhao-hong Jia
Lei Pan
Xiao Liu
Xue-jun Li
Publication date: 27-03-2021
Publisher: Springer US
Published in: The Journal of Supercomputing / Issue 10/2021
Print ISSN: 0920-8542
Electronic ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-021-03742-3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 10/2021

A frequency-aware and energy-saving strategy based on DVFS for Spark

Optimized area efficient quantum dot cellular automata based reversible code converter circuits: design and energy performance estimation

Improving the energy-efficiency of virtual machines by I/O compensation

Multidimensional adaptative and deterministic integration in CUDA and OpenMP

A novel approach for multilevel multi-secret image sharing scheme

JCOGIN: a programming framework for particle transport on combinatorial geometry

Premium Partner