Cover
Vol. 16 No. 2 (2020)

Published: December 31, 2020

Pages: 103-112

Review Article

Heuristic and Meta-Heuristic Optimization Models for Task Scheduling in Cloud-Fog Systems: A Review

Mohammed Najm Abdulredha 1 Bara'a A. Attea Adnan Jumaa Jabir
1Department of Computer Science, College of Science, University of Baghdad, Baghdad, Iraq
History
  • Received: October 5, 2020
  • Revised: November 20, 2020
  • Accepted: December 1, 2020
  • Available Online: December 23, 2020
DOI

https://doi.org/10.37917/ijeee.16.2.11

Abstract

Nowadays, cloud computing has attracted the attention of large companies due to its high potential, flexibility, and profitability in providing multi-sources of hardware and software to serve the connected users. Given the scale of modern data centers and the dynamic nature of their resource provisioning, we need effective scheduling techniques to manage these resources while satisfying both the cloud providers and cloud users goals. Task scheduling in cloud computing is considered as NP-hard problem which cannot be easily solved by classical optimization methods. Thus, both heuristic and meta-heuristic techniques have been utilized to provide optimal or near-optimal solutions within an acceptable time frame for such problems. In this article, a summary of heuristic and meta-heuristic methods for solving the task scheduling optimization in cloud-fog systems is presented. The cost and time aware scheduling methods for both bag of tasks and workflow tasks are reviewed, discussed, and analyzed thoroughly to provide a clear vision for the readers in order to select the proper methods which fulfill their needs.

Keywords

References

  1. F. F. Moghaddam, M. Ahmadi, S. Sarvari, M. Eslami, and A. Golkar, “Cloud computing challenges and opportunities: A survey,” in 2015 1st International Conference on Telematics and Future Generation Networks (TAFGEN), 2015, pp. 34–38.
  2. A. A. Laghari, H. He, I. A. Halepoto, M. S. Memon, and S. Parveen, “Analysis of quality of experience frameworks for cloud computing,” IJCSNS, vol. 17, no. 12, p. 228, 2017.
  3. V. Kumar, A. A. Laghari, S. Karim, M. Shakir, and A. A. Brohi, “Comparison of fog computing & cloud computing,” Int. J. Math. Sci. Comput., vol. 5, no. 1, pp. 31–41, 2019.
  4. A. R. DAR, D. Ravindran, and S. Islam, “Fog-based Spider Web Algorithm to Overcome Latency in Cloud Computing,” Iraqi J. Sci., pp. 1781–1790, 2020.
  5. X. Tan and B. Ai, “The issues of cloud computing security in high-speed railway,” in Proceedings of 2011 International Conference on Electronic & Mechanical Engineering and Information Technology, 2011, vol. 8, pp. 4358–4363.
  6. R. A. Al-Arasi and A. Saif, “Task scheduling in cloud computing based on metaheuristic techniques: A review paper.,” EAI Endorsed Trans. Cloud Syst., vol. 6, no. 17, p. e4, 2020.
  7. N. Ranaldo and E. Zimeo, “Time and cost-driven scheduling of data parallel tasks in grid workflows,” IEEE Syst. J., vol. 3, no. 1, pp. 104–120, 2009.
  8. X.-Q. Pham and E.-N. Huh, “Towards task scheduling in a cloud-fog computing system,” in 2016 18th Asia- Pacific network operations and management symposium (APNOMS), 2016, pp. 1–4.
  9. D. Rahbari and M. Nickray, “Scheduling of fog networks with optimized knapsack by symbiotic organisms search,” in 2017 21st Conference of Open Innovations Association (FRUCT), 2017, pp. 278–283.
  10. D. Vasiljević, “Comparison of optimization algorithms,” in Classical and Evolutionary Algorithms in the Optimization of Optical Systems, Springer, 2002, pp. 83–88.
  11. N. Soltani, B. Soleimani, and B. Barekatain, “Heuristic algorithms for task scheduling in cloud computing: a survey,” Int. J. Comput. Netw. Inf. Secur., vol. 11, no. 8, p. 16, 2017.
  12. R. Van den Bossche, K. Vanmechelen, and J. Broeckhove, “Cost-efficient scheduling heuristics for deadline constrained workloads on hybrid clouds,” in 2011 IEEE third international conference on cloud computing technology and science, 2011, pp. 320–327.
  13. S. Abdi, S. A. Motamedi, and S. Sharifian, “Task scheduling using modified PSO algorithm in cloud computing environment,” in International conference on machine learning, electrical and mechanical engineering, 2014, pp. 8–9. Abdulredha, Attea & Jabir | 111
  14. Z. Zhu, G. Zhang, M. Li, and X. Liu, “Evolutionary multi-objective workflow scheduling in cloud,” IEEE Trans. parallel Distrib. Syst., vol. 27, no. 5, pp. 1344– 1357, 2015.
  15. S. Kaur, P. Bagga, R. Hans, and H. Kaur, “Quality of Service (QoS) aware workflow scheduling (WFS) in cloud computing: A systematic review,” Arab. J. Sci. Eng., vol. 44, no. 4, pp. 2867–2897, 2019.
  16. S. S. K. Kumar and P. Balasubramanie, “Dynamic scheduling for cloud reliability using transportation problem,” J. Comput. Sci., vol. 8, no. 10, p. 1615, 2012.
  17. S. Bandaru and K. Deb, “Metaheuristic techniques,” in Decision Sciences, CRC Press, 2016, pp. 693–750.
  18. M. A. Tawfeek, A. El-Sisi, A. E. Keshk, and F. A. Torkey, “Cloud task scheduling based on ant colony optimization,” in 2013 8th international conference on computer engineering & systems (ICCES), 2013, pp. 64– 69.
  19. A. S. Khalil and R. D. Al-Dabbagh, “A Comparative Study on Meta-Heuristic Algorithms For Solving the RNP Problem,” Iraqi J. Sci., pp. 1639–1648, 2019.
  20. S. Nesmachnow, “An overview of metaheuristics: accurate and efficient methods for optimisation,” Int. J. Metaheuristics, vol. 3, no. 4, pp. 320–347, 2014.
  21. D. B. LD and P. V. Krishna, “Honey bee behavior inspired load balancing of tasks in cloud computing environments,” Appl. Soft Comput., vol. 13, no. 5, pp. 2292–2303, 2013.
  22. C.-W. Tsai and J. J. P. C. Rodrigues, “Metaheuristic scheduling for cloud: A survey,” IEEE Syst. J., vol. 8, no. 1, pp. 279–291, 2013.
  23. T. G. Crainic and M. Toulouse, “Parallel strategies for meta-heuristics,” in Handbook of metaheuristics, Springer, 2003, pp. 475–513.
  24. Y. Zhang and J. Sun, “Novel efficient particle swarm optimization algorithms for solving QoS‐demanded bag‐ of‐tasks scheduling problems with profit maximization on hybrid clouds,” Concurr. Comput. Pract. Exp., vol. 29, no. 21, p. e4249, 2017.
  25. R. N. Calheiros and R. Buyya, “Cost-effective provisioning and scheduling of deadline-constrained applications in hybrid clouds,” in International Conference on Web Information Systems Engineering, 2012, pp. 171–184.
  26. Y. Zhang, J. Sun, and J. Zhu, “An effective heuristic for due-date-constrained bag-of-tasks scheduling problem for total cost minimization on hybrid clouds,” in 2016 International Conference on Progress in Informatics and Computing (PIC), 2016, pp. 479–486.
  27. S. Abdi, L. PourKarimi, M. Ahmadi, and F. Zargari, “Cost minimization for bag-of-tasks workflows in a federation of clouds,” J. Supercomput., vol. 74, no. 6, pp. 2801–2822, 2018.
  28. S. G. Domanal and G. R. M. Reddy, “An efficient cost optimized scheduling for spot instances in heterogeneous cloud environment,” Futur. Gener. Comput. Syst., vol. 84, pp. 11–21, 2018.
  29. Y. Zhang, J. Zhou, and J. Sun, “Scheduling bag-of-tasks applications on hybrid clouds under due date constraints,” J. Syst. Archit., vol. 101, p. 101654, 2019.
  30. Z. Tong, K. Li, Z. Xiao, and X. Qin, “H2ACO: An optimization approach to scheduling tasks with availability constraint in heterogeneous systems,” J. Internet Technol., vol. 15, no. 1, pp. 115–124, 2014.
  31. D. Zeng, L. Gu, S. Guo, Z. Cheng, and S. Yu, “Joint optimization of task scheduling and image placement in fog computing supported software-defined embedded system,” IEEE Trans. Comput., vol. 65, no. 12, pp. 3702– 3712, 2016.
  32. Y. Zhang, J. Sun, and Z. Wu, “An heuristic for bag-of- tasks scheduling problems with resource demands and budget constraints to minimize makespan on hybrid clouds,” in 2017 fifth international conference on advanced cloud and big data (CBD), 2017, pp. 39–44.
  33. S. Abdi, L. PourKarimi, M. Ahmadi, and F. Zargari, “Cost minimization for deadline-constrained bag-of-tasks applications in federated hybrid clouds,” Futur. Gener. Comput. Syst., vol. 71, pp. 113–128, 2017.
  34. S. Bitam, S. Zeadally, and A. Mellouk, “Fog computing job scheduling optimization based on bees swarm,” Enterp. Inf. Syst., vol. 12, no. 4, pp. 373–397, 2018.
  35. H. Xuan, S. Wei, Y. Li, and H. Guo, “Off-line time aware scheduling of bag-of-tasks on heterogeneous distributed system,” IEEE Access, vol. 7, pp. 104777– 104788, 2019.
  36. L. Thai, B. Varghese, and A. Barker, “Executing bag of distributed tasks on the cloud: Investigating the trade-offs between performance and cost,” in 2014 IEEE 6th International Conference on Cloud Computing Technology and Science, 2014, pp. 400–407.
  37. Y. Nan, W. Li, W. Bao, F. C. Delicato, P. F. Pires, and A. Y. Zomaya, “Cost-effective processing for delay- sensitive applications in cloud of things systems,” in 2016 IEEE 15th international symposium on network computing and applications (NCA), 2016, pp. 162–169.
  38. S. Sindhu and S. Mukherjee, “An evolutionary approach to schedule deadline constrained bag of tasks in a cloud,” Int. J. Bio-Inspired Comput., vol. 11, no. 4, pp. 229–238, 2018.
  39. B. M. Nguyen, H. Thi Thanh Binh, and B. Do Son, “Evolutionary algorithms to optimize task scheduling problem for the IoT based bag-of-tasks application in cloud–fog computing environment,” Appl. Sci., vol. 9, no. 9, p. 1730, 2019.
  40. P. Sun, Z. Cai, and D. Liu, “Budget Constraint Bag-of- Task Based Workflow Scheduling in Public Clouds,” in CCF Conference on Computer Supported Cooperative Work and Social Computing, 2019, pp. 243–260.
  41. N. Parlavantzas et al., “A service‐based framework for building and executing epidemic simulation applications in the cloud,” Concurr. Comput. Pract. Exp., vol. 32, no. 5, p. e5554, 2020.
  42. D. Tychalas and H. Karatza, “A scheduling algorithm for a fog computing system with bag-of-tasks jobs: Simulation and performance evaluation,” Simul. Model. Pract. Theory, vol. 98, p. 101982, 2020.
  43. P. Lu, G. Zhang, Z. Zhu, X. Zhou, J. Sun, and J. Zhou, “A review of cost and makespan-aware workflow scheduling in clouds,” J. Circuits, Syst. Comput., vol. 28, no. 06, p. 1930006, 2019. Abdulredha, Attea & Jabir
  44. E. Deelman et al., “Pegasus: A framework for mapping complex scientific workflows onto distributed systems,” Sci. Program., vol. 13, no. 3, pp. 219–237, 2005.
  45. T. Fahringer et al., “ASKALON: A grid application development and computing environment,” in The 6th IEEE/ACM International Workshop on Grid Computing, 2005., 2005, pp. 10-pp.
  46. L. F. Bittencourt and E. R. M. Madeira, “HCOC: a cost optimization algorithm for workflow scheduling in hybrid clouds,” J. Internet Serv. Appl., vol. 2, no. 3, pp. 207–227, 2011.
  47. C. Szabo and T. Kroeger, “Evolving multi-objective strategies for task allocation of scientific workflows on public clouds,” in 2012 IEEE Congress on Evolutionary Computation, 2012, pp. 1–8.
  48. J. J. Durillo and R. Prodan, “Multi-objective workflow scheduling in Amazon EC2,” Cluster Comput., vol. 17, no. 2, pp. 169–189, 2014.
  49. H. Xu, B. Yang, W. Qi, and E. Ahene, “A Multi- objective Optimization Approach to Workflow Scheduling in Clouds Considering Fault Recovery.,” KSII Trans. Internet Inf. Syst., vol. 10, no. 3, 2016.
  50. I. Casas, J. Taheri, R. Ranjan, L. Wang, and A. Y. Zomaya, “A balanced scheduler with data reuse and replication for scientific workflows in cloud computing systems,” Futur. Gener. Comput. Syst., vol. 74, pp. 168– 178, 2017.
  51. 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,” Futur. Gener. Comput. Syst., vol. 93, pp. 278–289, 2019.
  52. J. Zhou, T. Wang, P. Cong, P. Lu, T. Wei, and M. Chen, “Cost and makespan-aware workflow scheduling in hybrid clouds,” J. Syst. Archit., vol. 100, p. 101631, 2019.
  53. Q. Wu, M. Zhou, Q. Zhu, Y. Xia, and J. Wen, “Moels: Multiobjective evolutionary list scheduling for cloud workflows,” IEEE Trans. Autom. Sci. Eng., vol. 17, no. 1, pp. 166–176, 2019.
  54. A. A. A. Gad-Elrab and A. Y. Noaman, “A two-tier bipartite graph task allocation approach based on fuzzy clustering in cloud–fog environment,” Futur. Gener. Comput. Syst., vol. 103, pp. 79–90, 2020.
  55. A. Choudhary, I. Gupta, V. Singh, and P. K. Jana, “A GSA based hybrid algorithm for bi-objective workflow scheduling in cloud computing,” Futur. Gener. Comput. Syst., vol. 83, pp. 14–26, 2018.
  56. H. Alazzam, E. Alhenawi, and R. Al-Sayyed, “A hybrid job scheduling algorithm based on Tabu and Harmony search algorithms,” J. Supercomput., vol. 75, no. 12, pp. 7994–8011, 2019.
  57. R. Xu et al., “Improved particle swarm optimization based workflow scheduling in cloud-fog environment,” in International Conference on Business Process Management, 2018, pp. 337–347.
  58. A. Lal and C. R. Krishna, “Critical path-based ant colony optimization for scientific workflow scheduling in cloud computing under deadline constraint,” in Ambient Communications and Computer Systems, Springer, 2018, pp. 447–461.
  59. X. Liu et al., “FogWorkflowSim: an automated simulation toolkit for workflow performance evaluation in fog computing,” in 2019 34th IEEE/ACM International Conference on Automated Software Engineering (ASE), 2019, pp. 1114–1117.
  60. M. Abdullahi, M. A. Ngadi, S. I. Dishing, and B. I. Ahmad, “An efficient symbiotic organisms search algorithm with chaotic optimization strategy for multi- objective task scheduling problems in cloud computing environment,” J. Netw. Comput. Appl., vol. 133, pp. 60– 74, 2019.
  61. M. Kalra and S. Singh, “Multi‐criteria workflow scheduling on clouds under deadline and budget constraints,” Concurr. Comput. Pract. Exp., vol. 31, no. 17, p. e5193, 2019.
  62. C. Mouradian, S. Kianpisheh, M. Abu-Lebdeh, F. Ebrahimnezhad, N. T. Jahromi, and R. H. Glitho, “Application component placement in NFV-based hybrid cloud/fog systems with mobile fog nodes,” IEEE J. Sel. Areas Commun., vol. 37, no. 5, pp. 1130–1143, 2019.
  63. Y. Xie et al., “A novel directional and non-local- convergent particle swarm optimization based workflow scheduling in cloud–edge environment,” Futur. Gener. Comput. Syst., vol. 97, pp. 361–378, 2019.
  64. C. Mouradian, S. Kianpisheh, and R. H. Glitho, “Application component placement in NFV-based hybrid cloud/fog systems,” in 2018 IEEE International Symposium on Local and Metropolitan Area Networks (LANMAN), 2018, pp. 25–30.
  65. M. Afrin, J. Jin, A. Rahman, Y.-C. Tian, and A. Kulkarni, “Multi-objective resource allocation for Edge Cloud based robotic workflow in smart factory,” Futur. Gener. Comput. Syst., vol. 97, pp. 119–130, 2019.
  66. E. Rafieyan, R. Khorsand, and M. Ramezanpour, “An adaptive scheduling approach based on integrated best- worst and VIKOR for cloud computing,” Comput. Ind. Eng., vol. 140, p. 106272, 2020.