A novel discrete grey wolf optimizer for scientific workflow scheduling in heterogeneous cloud computing platforms

Document Type : Article

Author

Department of Computer Engineering, Sari Branch, Islamic Azad University, Sari, Iran

Abstract

There are several scientific workflow applications which need vast amount of processing so the cloud offerings give the sense of economic. Workflow scheduling has drastic impact on gaining desired quality of service (QoS). The main objective of workflow scheduling is to minimize the makespan. The workflow scheduling is formulated to a discrete optimization problem which is NP-Hard. This paper presents a novel discrete grey wolf optimizer (D-GWO) for scientific workflow scheduling problems in heterogeneous cloud computing platforms in the aim of minimizing makespan. Although the original GWO had great achievements in continuous optimization problems, it seems clear gap in utilizing GWO for combinatorial discrete optimization problems. It revolves around the fact that the continuous changes in search space during the course of discrete optimization lead inefficient or meaningless solutions. To this end, the proposed algorithm is customized in such a way to optimize discrete workflow scheduling problem by leveraging some new binary operators and Walking Around approaches to balance between exploration and exploitation in discrete search space. Scientific unstructured workflows were investigated in different circumstances to prove effectiveness of proposed novel meta-heuristic algorithm. The simulation results witnessed the superiority of proposed D-GWO against other state-of-the-arts in terms of scheduling metrics.

Keywords

References

References:
1. Hosseini Shirvani, M.S. "A hybrid meta-heuristic algorithm for scientific work flow scheduling in heterogeneous distributed computing systems", Eng. Appl. Artif. Intell., 90(December 2019), p. 103501 (Apr. 2020 DOI: 10.1016/j.engappai.2020.103501.
2. Armbrust, M., Fox, A., Griffith, A.R., et al., Above the Clouds: A Berkeley View of Cloud Computing, University of California, Berkeley (2009).
3. Jafari Navimipour, N. "A formal approach for the specification and verification of a trustworthy human resource discovery mechanism in the expert cloud", Expert Systems with Applications, 42(15-16), pp. 6112- 6131 (2015).
4. Roy, S.K., Devaraj, R., Sarkar, A., et al. "Contention-aware optimal scheduling of real-time precedence-constrained task graphs on heterogeneous distributed systems", Journal of Systems Architecture, 105(101706), pp. 1-26 (2020). DOI: https://doi.org/10.1016/j.sysarc.2019.10170 6.
5. Keshanchi, B. and Jafari Navimipour, N. "Prioritybased task scheduling algorithm in cloud systems using a memetic algorithm", Journal of Circuits, Systems, and Computers, 25(10), pp. 1-33 (2016).
6. Tong, Z., Chen, H., Deng, X., et al. "A scheduling scheme in the cloud computing environment using deep Q-learning", Information Sciences, 512, pp. 1170-1191 (2020). DOI: https://doi.org/10.1016/j.ins.2019.10.035.
7. Mohammadzadeh, A., Masdari, M., and Gharehchopogh, F.S. "Energy and cost-aware work flow scheduling in cloud computing data centers using a multi-objective optimization algorithm", J Netw Syst Manage, 29(31), pp. 1-34 (2021).https://doi.org/10.1007/s10922-021-09599-4.
8. Hosseini Shirvani, M.S. "A new shuffled genetic-based task scheduling algorithm in heterogeneous distributed systems", Heterog. Distrib. Syst. J. Adv. Comput. Res., 9(4), pp. 19-36 (2018).
9. Hosseini Shirvani, M.S. "Evaluating of feasible solutions on parallel scheduling tasks with DEA decision maker", J. Adv. Comput. Res., 6, pp. 109-115 (2015).
10. Topcuoglu, H., Hariri, S., and Wu, M.Y. "Performance-effective and low-complexity task scheduling for heterogeneous computing", IEEE Trans. Parallel Distrib. Syst., 13(3), pp. 260-274 (2002). DOI: 10. 1109/71.993206.
11. Arabnejad, H. and Barbosa, J.G. "List scheduling algorithm for heterogeneous systems by an optimistic cost table", IEEE Trans. Parallel Distrib. Syst., 25(3), pp. 682-694 (Mar. 2014). DOI: 10.1109/TPDS.2013.
12. Thaman, J. and Singh, M. "Green cloud environment by using robust planning algorithm", Egypt. Informatics J., 18(3), pp. 205-214 (Nov. 2017). DOI: 10.1016/j.eij.2017.02. 001.
13. Khan, M. "Scheduling for heterogeneous Systems using constrained critical paths", Parallel Comput., 38, pp. 175-193 (2012). DOI: 10.1016/j.parco.2012.01.001.
14. Lin, C.-S., Lin, C.-S., Lin, Y., et al. "Multi-objective exploitation of pipeline parallelism using clustering, replication and duplication in embedded multi-core systems", J. Syst. Archit., 59(10), pp. 1083-1094 (Nov. 2013). DOI: 10.1016/j.sysarc.2013.05.024.
15. Liou, J. and Palis, M.A. "An efficient task clustering heuristic for scheduling DAGs on multiprocessors", Symp. Parallel Distrib. Process. February, pp. 152-156 (1996).
16. Tang, Q., Zhu, L.-H., Zhou, L., et al. "Scheduling directed acyclic graphs with optimal duplication strategy on homogeneous multiprocessor systems", J. Parallel Distrib. Comput., 138, pp. 115-127 (Apr. 2020) DOI: 10. 1016/j.jpdc.2019.12.012.
17. Akbari, M., Rashidi, H., Alizadeh, S.H. "An enhanced genetic algorithm with new operators for task scheduling in heterogeneous computing systems", Eng. Appl. Artif. Intell, 61, pp. 35-46 (2017).http://dx.doi.org/10.1016/j.engappai.2017.02.013.
18. Zand, H.V., Raji, M., Pedram, H., et al. "A genetic algorithm-based tasks scheduling in multicore processors considering energy consumption", International Journal of Embedded Systems (IJES), 13(3), pp. 264- 273 (2020).
19. Sujana, J.A.J., Revathi, T., Priya, T.S.S., et al. "Smart PSO-based secured scheduling approaches for scientific work flows in cloud computing", Soft Comput., 23, pp. 1745-1765 (2019). https://doi.org/ 10.1007/s00500-017-2897-8.
20. Dordaie, N. and Jafari Navimipour, N., A Hybrid Particle Swarm Optimization and Hill Climbing Algorithm for Task Scheduling in the Cloud Environments, ICT Press., 4(4), pp. 199-202 (Dec. 2018).
21. Alsaidy, S.A., Abbood, A.D., and Sahib, M.A. "Heuristic initialization of PSO task scheduling algorithm in cloud computing", J. King Saud Univ. - Comput. Inf. Sci., 34(6A), pp. 2370-2382 (2022). https://DOI.org/10.1016/ j.jksuci.2020.11.002.
22. Boveiri, H.R. "An enhanced cuckoo optimization algorithm for task graph scheduling in cluster-computing systems", Soft Comput , 24, pp. 10075-10093 (2020).https://DOI.org/10.1007/s00500-019-04520-3.
23. Agrawal, M. and Sirvastava, G.M.S. "A cuckoo search algorithm-based task scheduling in cloud computing", In Advances in Computer and Computational Sciences (2018). DOI: 10.1007/978-981-10-3773-3 29.
24. Moschakis, I.A. and Karatza, H.D. "Multi-criteria scheduling of bag-of-tasks applications on heterogeneous interlinked clouds with simulated annealing", The Journal of Systems & Software, 101, pp. 1-14 (2015). DOI: 10.1016/j.jss.2014.11.014.
25. Osamy W., El-sawy A.A., and Khedr, A.M., "SATC: A simulated annealing based tree construction and scheduling algorithm for minimizing aggregation time in wireless sensor networks", Wireless Pers Commun, 108, pp. 921-938 (2019), https://doi.org/10.1007/s11277-019-06440-9.
26. De Vicente, J., Lanchares, J., and Hermida, R. "Placement by thermodynamic simulated annealing", A Physics Letters, 317(56), pp. 415-423 (2013).
27. Keshani, M. and Jahanshahi, M.H. "Using simulated annealing for task scheduling in distributed systems", International Conference on Computational Intelligence, Modelling and Simulation (2009).
28. Hosseini Shirvani, M.S. and Noorian Talouki, R. "Bi-objective scheduling algorithm for scientific work flows on cloud computing platform with makespan and monetary cost minimization approach", Complex Intell. Syst., 8, pp. 1058-1114 (2022). https://doi.org/10.1007/s40747-021-00528-1.
29. Mirjalili, S., Mirjalili, S.M., and Lewis, A. "Grey wolf optimizer", Adv. Eng. Softw., 69, pp. 46-61 (2014).
30. Gu, J., Jiang, T., Zhu, H., et al. "Low-carbon job shop scheduling problem with discrete genetic-grey wolf optimization algorithm", Journal of Advanced Manufacturing Systems, 19(1), pp. 1-14 (2020). doi:10.1142/S0219686720500018.
31. Mohammadzadeh, A., Masdari, M., Gharehchopogh, F.S., et al. "Improved chaotic binary grey wolf optimization algorithm for work flow scheduling in green cloud computing", Evol. Intel., 14, pp. 1997-2025 (2021). https://doi.org/10.1007/s12065-020-00479-5.
32. Hosseini Shirvani, M.S., Amirsoleimani, N., Salimpour, S., and Azab, A. "Multi-criteria task scheduling in distributed systems based on fuzzy TOPSIS," 2017 IEEE 30th Canadian Conference on Electrical and Computer Engineering (CCECE), pp.
1-4 (2017). DOI: 10.1109/CCECE.2017.7946721.
33. Guo, P. and Xue, Z. "Cost-effective fault-tolerant scheduling algorithm for real-time tasks in cloud systems", 17th IEEE International Conference on Communication Technology (2017).
34. Noorian Talouki, R., Hosseini Shirvani, M.S., and Motameni, H. "A heuristic-based task scheduling algorithm for scientific work flows in heterogeneous cloud computing platforms", Journal of King Saude University: Computer and Information Sciences, 34(8A), pp. 4902-4913 (2022).https://doi.org/10.1016/j.jksuci.2021.05.011.
35. Darbha, S. and Agrawal, D.P. "A task duplication based scalable scheduling algorithm for distributed memory systems", Journal of Parallel and Distributed Computing, 46, pp. 15-27 (1997).
36. Palis, M.A., Liou, J.C., and Wie, D.S.L. "Task clustering and scheduling for distributed memory parallel architectures", IEEE Transactions on Parallel and Distributed Systems, 7(1), pp. 46-55 (1996).
37. Xu, Y., Li, K., Hu, J., et al. "A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues", Information Sciences, 270, pp. 255-287 (2014).
38. Mohammadzadeh, A., Masdari, M., Gharehchopogh, F.S., et al. "A hybrid multi-objective metaheuristic optimization algorithm for scientific work flow scheduling", Cluster Comput, 24, pp. 1479-1503 (2021).https://doi.org/10.1007/s10586-020-03205-z.
39. Noorian Talouki, R., Hosseini Shirvani, M.S., and Motameni, H. "A hybrid meta-heuristic scheduler algorithm for optimization of work flow scheduling in cloud heterogeneous computing environment", Journal of Engineering, Design and Technology (2021).https://doi.org/10.1108/JEDT-11-2020-0474.
40. Tanha, M., Hosseini Shirvani, M.S., and Rahmani A.M. "A hybrid meta-heuristic task scheduling algorithm based on genetic and thermodynamic annealing algorithms in cloud computing environemnts", Neural Computing and Applications, 33, pp. 16951-16984 (2021). https://doi.org/10.1007/s00521-021-06289-9.
41. Javadian Kootanaee, A., Poor Aghajan, A., and Hosseini Shirvani, M.S. "A hybrid model based on machine learning and genetic algorithm for detecting fraud in financial statements", Journal of Optimization in Industrial Engineering, 14(2), pp. 169-186 (2021). doi:10.22094/joie.2020.1877455.1685.
42. Bharathi, S., Chervenak, A., Deelman, E., et al. "Characterization of scientific work flows", In Third Workshop on Work flows in Support of Large- Scale Science, pp. 1-10 (2008). DOI: 10.1109/WORKS.2008.4723958.
Scientia Iranica
Volume 29, Issue 5
Transactions on Computer Science & Engineering and Electrical Engineering (D)
September and October 2022
Pages 2375-2393

Files

History

  • Receive Date: 01 December 2020
  • Revise Date: 27 December 2021
  • Accept Date: 23 May 2022

Share

How to cite

Statistics