Top

Cluster Computing

Published in:

24-11-2020

Towards decomposition based multi-objective workflow scheduling for big data processing in clouds

Authors: Emmanuel Bugingo, Defu Zhang, Zhaobin Chen, Wei Zheng

Published in: Cluster Computing | Issue 1/2021

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

search-config

AI-assisted search

Off

Abstract

A workflow is a group of tasks that are processed in a particular order to complete an application. Also, it is a popular paradigm used to model complex big-data applications. Executing complex applications in a distributed system such as cloud or cluster implicates optimization of several conflicting objectives such as monetary cost, energy consumption, total execution time of the application (makespan). Regardless of this trend, most of the workflow scheduling approaches focused on single or bi-objective optimization problem. In this paper, we considered the problem of scheduling workflows in a cloud environment as a multi-objective optimization problem, and hence proposed a multi-objective workflow-scheduling algorithm based on decomposition. The proposed algorithm is capable of finding optimal solutions with a single run. Our evaluation results show that, by a single run, the proposed approach manages to obtain the Pareto Front solutions which are at least as good as schedules produced by running a single-objective scheduling algorithm with constraints for multiple times.

previous article MMHGE: detecting mild cognitive impairment based on multi-atlas multi-view hybrid graph convolutional networks and ensemble learning

next article Collective periodic pattern discovery for understanding human mobility

Dont have a licence yet? Then find out more about our products and how to get one 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

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"

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

Hu, Z., Li, D., Guo, D.: Balance resource allocation for spark jobs based on prediction of the optimal resource. Tsinghua Sci. Technol. 25(04), 487–497 (2020)CrossRef

Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1990)

Cloudsigma.: Cloudsigma. (2009). https://www.cloudsigma.com/, Accessed 27 Jan 2020

Elasticshosts.: Elastichosts. (2008). https://www.elastichosts.com/. Accessed 27 Jan 2020

Pietri, I., Sakellariou, R.: Cost-efficient cpu provisioning for scientific workflows on clouds. In: Altmann, J., Silaghi, G.C., Rana, O.F. (eds.) Economics of Grids, Clouds, Systems, and Services. Springer International Publishing, Cham (2016)

Zhang, Q., Li, H.: Moea/d: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans. Evolut. Comput. 11(6), 712–731 (2007)CrossRef

Alla, H.B., Alla, S.B., Touhafi, A., Ezzati, A.: A novel task scheduling approach based on dynamic queues and hybrid meta-heuristic algorithms for cloud computing environment. Clust. Comput. 21(3), 1797–1820 (2018)CrossRef

Hosseinzadeh, M., Ghafour, M.Y., Hama, H.K., Vo, B., Khoshnevis, A.: Multi-objective task and workflow scheduling approaches in cloud computing: a comprehensive review. J. Grid Comput. 18, 327–356 (2020)CrossRef

Abazari, F., Analoui, M., Takabi, H., Fu, S.: Mows: multi-objective workflow scheduling in cloud computing based on heuristic algorithm. Simul. Modell. Pract. Theory 93, 119–132 (2019)CrossRef

10.

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

11.

Zhou, X., Zhang, G., Sun, J., Zhou, J., Wei, T., Hu, S.: Minimizing cost and makespan for workflow scheduling in cloud using fuzzy dominance sort based heft. Future Gener. Comput. Syst. 93, 278–289 (2019)CrossRef

12.

Bugingo, E., Zheng, W., Zhang, D., Qin, Y., Zhang, D.: (2019) Decomposition based multi-objective workflow scheduling for cloud environments. In: 2019 Seventh International Conference on Advanced Cloud and Big Data (CBD), pp. 37–42

13.

Iranmanesh, A., Naji, H.R.: DCHG-TS: a deadline-constrained and cost-effective hybrid genetic algorithm for scientific workflow scheduling in cloud computing. Clust. Comput. (2019). https://doi.org/10.1007/s10586-020-03145-8CrossRef

14.

Emmanuel, B., Qin, Y., Wang, J., Zhang, D., Zheng, W.: Cost optimization heuristics for deadline constrained workflow scheduling on clouds and their comparative evaluation. Concurr. Comput. 30(20), e4762 (2018)CrossRef

15.

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

16.

Ahmad, W., Alam, B., Ahuja, S., Malik, S.: A dynamic VM provisioning and de-provisioning based cost-efficient deadline-aware scheduling algorithm for Big Data workflow applications in a cloud environment. Clust. Comput. (2020). https://doi.org/10.1007/s10586-020-03100-7

17.

Ijaz, S., Munir, E.U.: MOPT: list-based heuristic for scheduling workflows in cloud environment. J. Supercomput. 75(7), 3740–3768 (2020)CrossRef

18.

Zhou, N., Lin, W., Feng, W., Shi, F., Pang, X.: Budget-deadline constrained approach for scientific workflows scheduling in a cloud environment. Clust. Comput. (2020). https://doi.org/10.1007/s10586-020-03176-1

19.

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

20.

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

21.

Xue, C., Lin, C., Hu, J.: Scalability analysis of request scheduling in cloud computing. Tsinghua Sci. Technol. 24(03), 249–261 (2019)CrossRef

22.

Zhang, H., Xie, J., Ge, J., Shi, J., Zhang, Z.: Hybrid particle swarm optimization algorithm based on entropy theory for solving DAR scheduling problem. Tsinghua Sci. Technol. 24(03), 281–290 (2019)

23.

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

24.

Singh, V., Gupta, I., Jana, P.K.: An energy efficient algorithm for workflow scheduling in IAAS cloud. J. Grid Comput. 18, 357–376 (2020)CrossRef

25.

Li, F., Liu, J., Huang, P., Shi, H.: (2018) An indicator and decomposition based steady-state evolutionary algorithm for many-objective optimization. Math. Probl. Eng. (2018)

26.

Miettinen, K., Mustajoki, J., Stewart, T.J.: Interactive multiobjective optimization with nimbus for decision making under uncertainty. OR Spectrum 36(1), 39–56 (2014)MathSciNetCrossRef

27.

Miettinen, K., Mäkelä, M.M.: Synchronous approach in interactive multiobjective optimization. Eur. J. Operat. Res. 170(3), 909–922 (2006)CrossRef

28.

Zheng, W., Emmanuel, B., Wang, C., Qin ,Y., Zhang, D.: Cost optimization for scheduling scientific workflows on clouds under deadline constraints. In: 2017 Fifth International Conference on Advanced Cloud and Big Data (CBD), pp. 51–56 (2017)

29.

Juve, G.: Workflowgenerator. (2014). https://confluence.pegasus.isi.edu/display/pegasus/WorkflowGenerator. Accessed 27 Jan 2020

30.

Juve, G., Chervenak, A., Deelman, E., Bharathi, S., Mehta, G., Vahi, K.: Characterizing and profiling scientific workflows. Future Gener. Comput. Syst. 29(3), 682–692 (2013b)CrossRef

31.

Sun, T., Xiao, C., Xu, X.: A scheduling algorithm using sub-deadline for workflow applications under budget and deadline constrained. Clust. Comput. 22(3), 5987–5996 (2019)CrossRef

Title: Towards decomposition based multi-objective workflow scheduling for big data processing in clouds
Authors: Emmanuel Bugingo
Defu Zhang
Zhaobin Chen
Wei Zheng
Publication date: 24-11-2020
Publisher: Springer US
Published in: Cluster Computing / Issue 1/2021
Print ISSN: 1386-7857
Electronic ISSN: 1573-7543
DOI: https://doi.org/10.1007/s10586-020-03208-w

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+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 1/2021

Resource provisioning using workload clustering in cloud computing environment: a hybrid approach

Rendering high-quality PK bitmap font in Linux environment

Task replication to improve the reliability of running workflows on the cloud

SNORT based early DDoS detection system using Opendaylight and open networking operating system in software defined networking

A novel hybrid antlion optimization algorithm for multi-objective task scheduling problems in cloud computing environments

TOP-Storm: A topology-based resource-aware scheduler for Stream Processing Engine

Premium Partner