Abstract
Workflow scheduling is one of the burning topics that has drawn enormous attention recently in the research community of cloud computing due to its wide applications in astronomy, physics, bioinformatics, health care and so on. This is a well-known NP-complete problem. It presents an interesting aspect of achieving minimum processing time of all the tasks and maximum resource utilization in cloud resources. Therefore, many algorithms have been developed for workflow scheduling. However, most of them consider a static priority of the tasks which is non-realistic for heterogeneous cloud computing environment. In this paper, we propose a workflow scheduling algorithm which considers dynamic priority of the tasks. The algorithm undergoes a process of min–max normalization followed by the calculation of the dynamic threshold to dispatch the tasks into one of the virtual machines. The algorithm is extensively simulated using various benchmark, scientific and real-life workflows. All the simulated results are compared with other four existing workflow scheduling algorithms. The simulated results confirm that the proposed algorithm lags behind all the four existing algorithms in terms of makespan and average cloud resource utilization. The simulation results are also validated through analysis of variance statistical test.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
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 (2013)
https://confluence.pegasus.isi.edu/display/pegasus/ Workflow Generator. Accessed on 25 Nov 2016
Wieczorek, M.; Prodan, R.; Fahringer, T.: Scheduling of scientific workflows in the ASKALON grid environment. ACM SIGMOD Rec. 34(3), 56–62 (2005)
Cooper, K.; Dasgupta, A.; Kennedy, K.; Koelbel, C.; Mandal, A.; Marin, G.; Mazina, M.; Mellor-Crummey, J.; Berman, F.; Casanova, H.; Chien, A.: New grid scheduling and rescheduling methods in the GrADS project. In: 18th International on Parallel and Distributed Processing Symposium. IEEE (2004)
Alkhanak, E.N.; Lee, S.P.; Rezaei, R.; Parizi, R.M.: Cost optimization approaches for scientific workflow scheduling in cloud and grid computing: a review, classifications, and open issues. J. Syst. Softw. 113, 1–26 (2016)
Durillo, J.J.; Prodan, R.; Barbosa, J.G.: Pareto tradeoff scheduling of workflows on federated commercial clouds. Simul. Model. Pract. Theory 58, 95–111 (2015)
Buyya, R.; Vecchiola, C.; Selvi, S.T.: Mastering Cloud Computing: Foundations and Applications Programming. Morgan Kaufmann, Los Altos (2013)
Bochenina, K.; Butakov, N.; Boukhanovsky, A.: Static scheduling of multiple workflows with soft deadlines in non-dedicated heterogeneous environments. Future Gener. Comput. Syst. 55, 51–61 (2016)
Topcuoglu, H.; Hariri, S.; Min-You, W.: Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans. Parallel Distrib. Syst. 13, 260–274 (2002)
Ullman, J.D.: NP-complete scheduling problems. J. Comput. Syst. Sci. 10(3), 384–393 (1975)
Cao, H.; Jin, H.; Wu, X.; Wu, S.; Shi, X.: DAGMap: efficient and dependable scheduling of DAG workflow job in grid. J. Supercomput. 51(2), 201–223 (2010)
Li, J.; Qiu, M.; Ming, Z.; Quan, G.; Qin, X.; Gu, Z.: Online optimization for scheduling preemptable tasks on IaaS cloud system. J. Parallel Distrib. Comput. 72, 666–677 (2012)
Panda, S.K.; Jana, P.K.: Normalization-based task scheduling algorithms for heterogeneous multi-cloud environment. Inf. Syst. Front. (2016). https://doi.org/10.1007/s10796-016-9683-5
Panda, S.K.; Jana, P.K.: Uncertainty-based QoS min–min algorithm for heterogeneous multi-cloud environment. Arabian J. Sci. Eng. 41(8), 3003–3025 (2016)
Ding, Y.; Qin, X.; Liu, L.; Wang, T.: Efficient scheduling of virtual machines in cloud with deadline constraint. Future Gener. Comput. Syst. 50, 62–74 (2015)
Braun, T.D.; Siegel, H.J.; Beck, N.; Boloni, L.L.; Maheswaran, M.; Reuther, A.I.; Robertson, J.P.; Theys, M.D.; Yao, B.; Hensgen, D.; Freund, R.F.: A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. J. Parallel Distrib. Comput. 61(6), 810–837 (2001)
Panda, S.K.; Jana, P.K.: Efficient task scheduling algorithms for heterogeneous multi-cloud environment. J. Supercomput. 71(4), 1505–1533 (2015)
Muller, K.E.; Fetterman, B.A.: Regression and ANOVA: An Integrated Approach Using SAS Software. SAS Publisher Cary (2002)
Vasile, M.; Pop, F.; Tutueanu, R.; Cristea, V.; Kolodziej, J.: Resource-aware hybrid scheduling algorithm in heterogeneous distributed computing. Future Gener. Comput. Syst. 51, 61–71 (2015)
Celaya, J.; Arronategui, U.: Fair scheduling of bag-of-tasks applications on large-scale platforms. Future Gener. Comput. Syst. 49, 28–44 (2015)
Mao, M.; Humphrey, M.: Auto-scaling to minimize cost and meet application deadlines in cloud workflows. In: Proceedings of International Conference for High Performance Computing Networking, Storage and Analysis. ACM (2011)
Gorbenko, A.; Popov, V.: Task-resource scheduling problem. Int. J. Autom. Comput. 9, 429–441 (2012)
Panda, S.K.; Jana, P.K.: A multi-objective task scheduling algorithm for heterogeneous multi-cloud environment. In: International Conference on Electronic Design, Computer Networks and Automated Verification, pp. 82–87. IEEE (2015)
Gupta, I.; Kumar, M.S.; Jana, P.K.: Compute-intensive workflow scheduling in multi-cloud environment. In: International Conference on Advances in Computing, Communications and Informatics (ICACCI), pp. 315–321. IEEE (2016)
Ming, G.; Li, H.: An improved algorithm based on max–min for cloud task scheduling. In: Recent Advances in Computer Science and Information Engineering, Lecture Notes in Electrical Engineering, vol. 125, pp. 217–223 (2012)
Ibarra, O.H.; Kim, C.E.: Heuristic algorithms for scheduling independent tasks on nonidentical processors. J. ACM (JACM) 24(2), 280–289 (1977)
Malawski, M.; Juve, G.; Deelman, E.; Nabrzyski, J.: Cost-and deadline-constrained provisioning for scientific workflow ensembles in IaaS clouds. Future Gener. Comput. Syst. 48, 1–8 (2015)
Liu, Y.; Zhang, C.; Li, B.; Niu, J.: DeMS: a hybrid scheme of task scheduling and load balancing in computer clusters. J. Netw. Comput. Appl. 83, 213–220 (2015)
Ergu, D.; Kou, G.; Peng, Y.; Shi, Y.; Shi, Y.: The analytic hierarchy process: task scheduling and resource allocation in cloud computing environment. J. Supercomput. 64, 835–848 (2013)
OpenNebula, http://archives.opennebula.org/documentation:rel4.4:schg. Accessed on 16 July 2016
Rodriguez, M.A.; Buyya, R.: Deadline based resource provisioning and scheduling algorithm for scientific workflows on clouds. IEEE Trans. Cloud Comput. 2, 222–235 (2014)
Yu, B.; Yuan, X.; Wang, J.: Short-term hydro-thermal scheduling using particle swarm optimization method. Energy Convers. Manag. 48(7), 1902–1908 (2007)
Rashvand, H.F.; Salah, K.; Calero, J.M.A.; Harn, L.: Distributed security for multi-agent systems review and applications. IET Inf. Secur. 4(4), 188–201 (2010)
www.nimbusproject.org/docs/2.5/changelog.html. Accessed on 15 July 2016
Freund, R.F.; Gherrity, M.; Ambrosius, S.; Campbell, M.; Halderman, M.; Hensgen, D.; Keith, E.; Kidd, T.; Kussow, M.; Lima, J.D.; Mirabile, F.; Moore, L.; Rust, B.; Siegel, H.J.: Scheduling resources in multi-user. In: Heterogeneous, Computing Environments with SmartNet, 7th IEEE Heterogeneous Computing Workshop, pp. 184–199 (1998) Comput. Mach. 24(2), 280–289 (1977)
Braun, F.N.: https://code.google.com/p/hcspchc/source/browse/trunk/AE/Problem Instns/ HCSP. Accessed on 15 May 2016
Salah, K.; Elbadawi, K.; Boutabaa, R.: An analytical model for estimating cloud resources of elastic services. J. Netw. Syst. Manag. 24(2), 285–308 (2016)
Nudd, G.R.; Kerbyson, D.J.; Papaefstathiou, E.; Perry, S.C.; Harper, J.S.; Wilcox, D.V.: PACEA toolset for the performance prediction of parallel and distributed systems. Int. J. High Perform. Comput. Appl. 14(3), 228–251 (2000)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Gupta, I., Kumar, M.S. & Jana, P.K. Efficient Workflow Scheduling Algorithm for Cloud Computing System: A Dynamic Priority-Based Approach. Arab J Sci Eng 43, 7945–7960 (2018). https://doi.org/10.1007/s13369-018-3261-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s13369-018-3261-8