Taxonomy and survey of scientific workflow scheduling in infrastructure-as-a-service cloud computing systems

  • Authors

    • Fouakeu-Tatieze Stéphane University of Ngaoundere
    • kamla Vivient Corneille University of ngaoundere
    • Sonia Yassa CY Cergy Paris University
    • Kamgang Jean-Claude University of ngaoundere
    • Nkenlifack Marcellin Julius Antonio University of Dschang
    2024-05-27
    https://doi.org/10.14419/f8ka3p66
  • Scientific Workflows; Scheduling Algorithms; IaaS Cloud; Taxonomy; Survey.

  • Scientific workflows are groups of scientific application tasks organized in oriented graphs. These scientific workflows are characterized by a large number of tasks requiring sufficient resources for their execution. Tasks with all available input data can be computed simultaneously. Cloud computing is an appropriate environment for the implementation of scientific workflows. Although the cloud computing environment has unlimited resources and can run some scientific workflow tasks simultaneously, scheduling scientific workflow tasks using pay-as-you-go cloud computing resources is an NP-complete problem. This difficulty is due to constraints on the part of the cloud resource provider and the part of the user (customer). The algorithm tries to find efficient schedules that take into account several requirements of client service (QoS) such as deadlines, budgets, and resource providers’ profits, i.e., the minimization of energy consumption and many others. There have been several papers recommending effective solutions to workflow schedule problems. This paper reviews existing and more recent papers on the plan of scientific workflows in pay-as-you-go IaaS cloud computing environments, focusing on future directions for algorithms that can improve the optimal solution.

     

  • References

    1. R. Duan, T Fahringer, R. Prodan, J. Qin, A. Villazon, and M. Wieczorek. Real world workflow applications in the askalon grid envi-ronment. European Grid Conference, Springer, page 454–463, 2005. https://doi.org/10.1007/11508380_47.
    2. X. Geng, Y. Mao, M. Xiong, and Y. Liu. An improved task scheduling algorithm for scientific workflow in cloud computing environ-ment. Cluster Computing, 22:7539–7548, 2019. https://doi.org/10.1007/s10586-018-1856-1.
    3. S. Ostermann, A. Iosup, N. Yigitbasi, R. Prodan, T. Fahringer, and D. Epema. A performance analysis of ec2 cloud computing services for scientific computing. International Conference on Cloud Computing, 2009. https://doi.org/10.1007/978-3-642-12636-9_9.
    4. C. N. Hoefer and G. Karagiannis. Taxonomy of cloud computing services. EEE Globecom Workshops, page 1345–1350, 2010. https://doi.org/10.1109/GLOCOMW.2010.5700157.
    5. J. Liu, J. Ren, W. Dai, D. Zhang, P. Zhou, Y. Zhang, G. Min, and N. Najjari. Online multi-workflow scheduling under uncertain task execution time in iaas clouds. IEEE Transactions on Cloud Computing, 2019.
    6. M. Zhu, Q. Wu, and Y. Zhao. A cost-effective scheduling algorithm for scientific workflows in clouds. IEEE 31st International Per-formance Computing and Communications Conference (IPCCC), page 256–265, 2012.
    7. S. J. Nirmala and S. M. S. Bhanu. Catfish-pso based scheduling of scientific workflows in iaas cloud. Computing 98, page 1091–1109, 2016. https://doi.org/10.1007/s00607-016-0494-9.
    8. W. Jing, W. Qiang, and L. Xiongfei. A data placement and task scheduling algorithm in cloud computing. Journal of Computer Research and Development, 51, 2014.
    9. R. Ghafouri, A. Movaghar, and M. Mohsenzadeh. A budget constrained scheduling algorithm for executing workflow application in infrastructure as a service clouds. Peer-to-Peer Networking and Applications, 12:241–268, 2018. https://doi.org/10.1007/s12083-018-0662-0.
    10. J. Sun, L. Yin, M. Zou, Y. Zhang, T. Zhang, and J. Zhou. Makespan minimization workflow scheduling for complex networks with so-cial groups in edge computing. Journal of Systems Architecture, 2020. https://doi.org/10.1016/j.sysarc.2020.101799.
    11. S. Su, J. Li, Q. Huang, X. Huang, K. Shuang, and J. Wang. Cost-efficient task scheduling for executing large programs in the cloud. Par-allel Computing, 39:177–188, 2013. https://doi.org/10.1016/j.parco.2013.03.002.
    12. V. Singh, I. Gupta, and P. K. Jana. An energy efficient algorithm for workflow scheduling in iaas cloud. Journal of Grid Computing, 18:357–376, 2020. https://doi.org/10.1007/s10723-019-09490-2.
    13. X. Liu, W. Dou, J. Chen, S. Fan, S.C. Cheung, and S. Cai. On design, verification, and dynamic modification of the problem-based sci-entific workflow model. Simulation Modelling Practice and Theory, 15:1068–1088, 2007. https://doi.org/10.1016/j.simpat.2007.06.003.
    14. A. Asghari, M. K. Sohrabi, and F. Yaghmaee. Task scheduling, resource provisioning, and load balancing on scientific workflows us-ing parallel sarsa reinforcement learning agents and genetic algorithm. The Journal of Supercomputing, page 1–29, 2020. https://doi.org/10.1007/s11227-020-03364-1.
    15. X. Ye, J. Liang, S. Liu, and J. Li. A survey on scheduling workflows in cloud environment. International Conference on Network and Information Systems for Computers, page 344–348, 2015. https://doi.org/10.1109/ICNISC.2015.91.
    16. Vijindra and S. Shenai. Survey on scheduling issues in cloud computing. Procedia Engineering, 38:2881–2888, 2012. https://doi.org/10.1016/j.proeng.2012.06.337.
    17. K. Setrag and B. Marek. Groupware and workflow. Paris : Masson, 1998.
    18. P. Lawrence. Workflow management coalition. Workflow Handbook, 1997.
    19. T. E. El-Sayed, I.E Ali, and F.A Mohamed. Extended max-min scheduling using petri net and load balancing. Int. J. Soft Comput. Eng. (IJSCE), 2:198–203, 2012.
    20. I. Gupta, S. Gupta, A. Choudhary, and Jana P.K. A hybrid meta-heuristic approach for load balanced workflow scheduling in iaas cloud. Lecture Notes in Computer Science, 11319:73–89, 2019. https://doi.org/10.1007/978-3-030-05366-6_6.
    21. J. Gideon, C. Ann, D. Ewa, B. Shishir, M. Gaurang, and V. Karan. Characterizing and profiling scientific workflows. Future Generation Computer Systems, 29:682–692, 2013. https://doi.org/10.1016/j.future.2012.08.015.
    22. B. Ludascher, I. Altintas, C. Berkley, D. Higgins, E. Jaeger, M. Jones, J. Lee, E.A.and Tao, and Y Zhao. Scientific workflow manage-ment and the kepler system. Concurrency and computation: Practice and experience, 18:1039–1065, 2006. https://doi.org/10.1002/cpe.994.
    23. T. Oinn, M. Addis, J. Ferris, D. Marvin, M. Greenwood, T. Carver, A. Wipat, and P.L. Taverna. Lessons in creating a workflow envi-ronment for the life sciences. GGF10, 2004. https://doi.org/10.1002/cpe.993.
    24. I. Taylor, M. Shields, I. Wang, and A. Harrison. The triana workflow environment: Architecture and applications. In Workflows for e-Science, Springer, pages 320–339, 2007. https://doi.org/10.1007/978-1-84628-757-2_20.
    25. T. Fahringer, A. Jugravu, S. Pllana, R. Prodan, C. Seragiotto Jr, and H.L. Truong. Askalon: a tool set for cluster and grid computing. Concurrency and Computation: Practice and Experience, 17:143–169, 2005. https://doi.org/10.1002/cpe.929.
    26. E. Deelman, G. Singh, M.H. Su, J. Blythe, Y. Gil, C. Kesselman, G. Mehta, K. Vahi, G.B. Berriman, J. Good, and A. Laity. Pegasus: A framework for mapping complex scientific workflows onto distributed systems. Scientific Programming, 13:219–237, 2005. https://doi.org/10.1155/2005/128026.
    27. G.J. Toomer. Ptolemy’s almagest. Princeton: Princeton University Press, 712, 1998. https://doi.org/10.1515/9780691213361.
    28. Y.H. Jia, W.N. Chen, H. Yuan, T. Gu, H. Zhang, Y. Gao, and J. Zhang. An intelligent cloud workflow scheduling system with time estimation and adaptive ant colony optimization. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 51:634–649, 2018. https://doi.org/10.1109/TSMC.2018.2881018.
    29. S. Yassa, R. Chelouah, H. Kadima, and B. Granado. Multi-objective approach for energy-aware workflow scheduling in cloud compu-ting environments. The Scientific World Journal, pages 634–649, 2013. https://doi.org/10.1155/2013/350934.
    30. S. Yassa, J. Sublime, R. Chelouah, H. Kadima, G.S. Jo, and B. Granado. A genetic algorithm for multi-objective optimisation in work-flow scheduling with hard constraints. International Journal of Metaheuristics, 2:415–433, 2013. https://doi.org/10.1504/IJMHEUR.2013.058475.
    31. M.A. Rodriguez and R. Buyya. Budget-driven scheduling of scientific workflows in iaas clouds with fine-grained billing periods. ACM Transactions on Autonomous and Adaptive Systems (TAAS), 12:1– 22, 2017. https://doi.org/10.1145/3041036.
    32. V. Singh, I. Gupta, and P.K. Jana. A novel cost-efficient approach for deadline-constrained workflow scheduling by dynamic provi-sioning of resources. Future Generation Computer Systems, 79:95–110, 2018. https://doi.org/10.1016/j.future.2017.09.054.
    33. V. Arabnejad, K. Bubendorfer, and B. Ng. Budget and deadline aware e-science workflow scheduling in clouds. IEEE Transactions on Parallel and Distributed systems, 30:29–44, 2018. https://doi.org/10.1109/TPDS.2018.2849396.
    34. X. Zhou, G. Zhang, J. Sun, J. Zhou, T. Wei, and S. Hu. Minimizing cost and makespan for workflow scheduling in cloud using fuzzy dominance sort based heft. Future Generation Computer Systems, 93:278–289, 2019. https://doi.org/10.1016/j.future.2018.10.046.
    35. Y. Gao, S. Zhang, and J. Zhou. A hybrid algorithm for multi-objective scientific workflow scheduling in iaas cloud. IEEE Access, 7:125783–125795, 2019. https://doi.org/10.1109/ACCESS.2019.2939294.
    36. H.R. Faragardi, M.R.S. Sedghpour, S. Fazliahmadi, T. Fahringer, and N. Rasouli. Grp-heft: A budget-constrained resource provisioning scheme for workflow scheduling in iaas clouds. IEEE Transactions on Parallel and Distributed Systems, 31:1239–1254, 2019. https://doi.org/10.1109/TPDS.2019.2961098.
    37. K. Kalyan Chakravarthi, L. Shyamala, and V. Vaidehi. Budget-aware scheduling algorithm for workflow applications in iaas clouds. Cluster Computing, 23:3405–3419, 2020. https://doi.org/10.1007/s10586-020-03095-1.
    38. J.E. Ndamlabin Mboula, V.C. Kamla, and C.T. Djamegni. Cost-time trade-off efficient workflow scheduling in cloud. Simulation Mod-elling Practice and Theory, 103:102107, 2020. https://doi.org/10.1016/j.simpat.2020.102107.
    39. Z. Wen, S. Garg, G.S. Aujla, K. Alwasel, D. Puthal, S. Dustdar, A.Y. Zomaya, and R. Ranjan. Running industrial workflow applications in a software-defined multicloud environment using green energy aware scheduling algorithm. IEEE Transactions on Industrial Infor-matics, 17:5645–5656, 2020. https://doi.org/10.1109/TII.2020.3045690.
    40. A. Belgacem and K. Beghdad-Bey. Multi-objective workflow scheduling in cloud computing: trade-off between makespan and cost. Cluster Computing, 25:579–595, 2022. https://doi.org/10.1007/s10586-021-03432-y.
    41. J.E. Ndamlabin Mboula, V.C. Kamla, and C. Tayou Djam´egni. Dynamic provisioning with structure inspired selection and limitation of vms based cost-time efficient workflow scheduling in the cloud. Cluster Computing, 24:2697–2721, 2021. https://doi.org/10.1007/s10586-021-03289-1.
    42. A. Taghinezhad-Niar, S. Pashazadeh, and J. Taheri. Workflow scheduling of scientific workflows under simultaneous deadline and budget constraints. Cluster Computing, 24:3449–3467, 2021. https://doi.org/10.1007/s10586-021-03314-3.
    43. M. Hariri, M. Nouri-Baygi, and S. Abrishami. A hybrid algorithm for scheduling scientific workflows in iaas cloud with deadline con-straint. The Journal of Supercomputing, pages 1–22, 2022. https://doi.org/10.1007/s11227-022-04563-8.
    44. S. Saeedi, R. Khorsand, S.G. Bidgoli, and M. Ramezanpour. Improved many-objective particle swarm optimization algorithm for scien-tific workflow scheduling in cloud computing. Computers and Industrial Engineering, 147:106649, 2020. https://doi.org/10.1016/j.cie.2020.106649.
    45. J.K. Konjaang, J. Murphy, and L. Murphy. Energy-efficient virtual-machine mapping algorithm (evima) for workflow tasks with dead-lines in a cloud environment. Journal of Network and Computer Applications, 203:103400, 2022. https://doi.org/10.1016/j.jnca.2022.103400.
    46. L. Ye, Y. Xia, S. Tao, C. Yan, R. Gao, and Y. Zhan. Reliability-aware and energy-efficient workflow scheduling in iaas clouds. IEEE Transactions on Automation Science and Engineering, 2022. https://doi.org/10.1109/TASE.2022.3195958.
    47. M. Marwa, J.E. Hajlaoui, Y. Sonia, M.N. Omri, and C. Rachid. Multi-agent system-based fuzzy constraints offer negotiation of work-flow scheduling in fog-cloud environment. Computing, pages 1–33, 2023. https://doi.org/10.1007/s00607-022-01148-4.
    48. M. Mokni, S. Yassa, J.E. Hajlaoui, M.N. Omri, and R. Chelouah. Multi-objective fuzzy approach to scheduling and offloading work-flow tasks in fog–cloud computing. Simulation Modelling Practice and Theory, 123:102687, 2023. https://doi.org/10.1016/j.simpat.2022.102687.
    49. M.A. Rodriguez and R. Buyya. A taxonomy and survey on scheduling algorithms for scientific workflows in iaas cloud computing en-vironments. Concurrency and Computation: Practice and Experience, 29:4041, 2017. https://doi.org/10.1002/cpe.4041.
    50. P. Rajasekar and Y. Palanichamy. Scheduling multiple scientific workflows using containers on iaas cloud. Journal of Ambient Intelli-gence and Humanized Computing, 12:7621–7636, 2021. https://doi.org/10.1007/s12652-020-02483-0.
    51. F. Li and W. Jun. Multi-objective optimization of clustering-based scheduling for multi-workflow on clouds considering fairness. arXiv preprint arXiv:2205.11173, 2022. https://doi.org/10.2139/ssrn.4128847.
    52. L. Ye, Y. Xia, L. Yang, and Y. Zhan. Dynamic scheduling stochastic multiworkflows with deadline constraints in clouds. IEEE Trans-actions on Automation Science and Engineering, 2022. https://doi.org/10.1109/TASE.2022.3204313.
    53. M. Malawski, G. Juve, E. Deelman, and J. Nabrzyski. Algorithms for cost-and deadline-constrained provisioning for scientific work-flow ensembles in iaas clouds. Future Generation Computer Systems, 48:1–18, 2015. https://doi.org/10.1016/j.future.2015.01.004.
    54. Z. Zhu, G. Zhang, M. Li, and X. Liu. Evolutionary multi-objective workflow scheduling in cloud. IEEE Transactions on parallel and distributed Systems, 27:1344–1357, 2015. https://doi.org/10.1109/TPDS.2015.2446459.
    55. N. Arora and R.K. Banyal. A particle grey wolf hybrid algorithm for workflow scheduling in cloud computing. Wireless Personal Communications, 122:3313–3345, 2022. https://doi.org/10.1007/s11277-021-09065-z.
    56. J.K. Konjaang and L. Xu. Multi-objective workflow optimization strategy (mowos) for cloud computing. Journal of Cloud Computing, 10:1–19, 2021. https://doi.org/10.1186/s13677-020-00219-1.
    57. EG. Talbi. Metaheuristics: from design to implementation. John Wiley and Sons, 2009. https://doi.org/10.1002/9780470496916.
    58. Sonia Yassa. Allocation optimale multicontraintes des workflows aux ressources d’un environnement Cloud Computing. Th`ese de doctorat, Universit´ de Cergy Pontoise, 2014.
    59. N.A.B. Mary and K. Jayapriya. An extensive survey on qos in cloud computing. International Journal of Computer Science and Infor-mation Technologies, 5:1–5, 2014.
    60. K. Liu, H. Jin, J. Chen, X. Liu, D. Yuan, and Y. Yang. An extensive survey on qos in cloud compa compromised-time-cost scheduling algorithm in swindew-c for instance-intensive cost-constrained workflows on a cloud computing platform. The International Journal of High-Performance Computing Applications, 24:445–456, 2010. https://doi.org/10.1177/1094342010369114.
    61. J. Bushra, Humaira I., Mohammad S., Kashif M., and Rajkumar B. Resource allocation and task scheduling in fog computing and inter-net of everything environments: A taxonomy, review, and future directions. ACM Computing Surveys, 10, 2022.
    62. M.A. Rodriguez and R. Buyya. Deadline-based resource provisioning and scheduling algorithm for scientific workflows on clouds. IEEE transactions on cloud computing, 2:222–235, 2014. https://doi.org/10.1109/TCC.2014.2314655.
    63. L. Zhao, Y. Ren, and K. Sakurai. Reliable workflow scheduling with less resource redundancy. Parallel Computing, 39:567–585, 2013. https://doi.org/10.1016/j.parco.2013.06.003.
    64. Q. Tao, H. Chang, Y. Yi, C. Gu, and Y. Yu. Qos constrained grid workflow scheduling optimization based on a novel pso algorithm. Eighth International Conference on Grid and Cooperative Computing, pages 153–159, 2009. https://doi.org/10.1109/GCC.2009.39.
    65. M.A. Rodriguez and R. Buyya. A responsive knapsack-based algorithm for resource provisioning and scheduling of scientific work-flows in clouds.44th International Conference on Parallel Processing, pages 839–848, 2015. https://doi.org/10.1109/ICPP.2015.93.
    66. V.R. Pillareddy and G.R. Karri. Monws: Multi-objective normalization workflow scheduling for cloud computing. Applied Sciences, 13:1101, 2023. https://doi.org/10.3390/app13021101.

  • Downloads

  • How to Cite

    Stéphane , F.-T. ., Corneille , kamla V. ., Yassa, S., Jean-Claude , K. ., & Marcellin Julius Antonio, N. . (2024). Taxonomy and survey of scientific workflow scheduling in infrastructure-as-a-service cloud computing systems. Journal of Advanced Computer Science & Technology, 12(1), 19-32. https://doi.org/10.14419/f8ka3p66