Cost-effective and Low-complexity Non-constrained Workflow Scheduling for Cloud Computing Environment

Célestin Tshimanga Kamanga, Emmanuel Bugingo, Simon Ntumba Badibanga, Eugène Mbuyi Mukendi, Olivier Habimana

Abstract


Cloud computing possesses the merit of being a faster and cost-effective platform in terms of executing scientific workflow applications. Scientific workflow applications are found in different domains, such as security, astronomy, science, etc. They are represented by complex sizes, which makes them computationally intensive. The main key to the successful execution of scientific workflow applications lies in task resource mapping. However, task-resource mapping in a cloud environment is classified as NP-complete. Finding a good schedule that satisfies users' quality of service requirements is still complicated. Even if different studies have been carried out to propose different algorithms that address this issue, there is still a big room for improvement. Some proposed algorithms focused on optimizing different objectives such as makespan, cost, and energy. Some of those studies fail to produce low-time complexity and low-runtime scientific workflow scheduling algorithms. In this paper, we proposed a non-constrained, low-runtime, and low-time-complexity scientific workflow scheduling algorithm for cost minimization. Since the proposed algorithm is a list scheduling algorithm, its key success is properly selecting computing resources and its operating CPU frequency for each task using the maximum cost difference and minimum cost-execution difference from the mean. Our algorithm achieves almost the same cost reduction results as some of the current states of the arts while it is still low complex and uses less run-time.

Keywords


Workflow scheduling; resource management; difference from the mean; weighted sum difference; low complexity.

Full Text:

PDF

References


N. Mansouri, R. Ghafari, and B. M. H. Zade, "Cloud computing simulators: A comprehensive review," Simul. Model. Pract. Theory, vol. 104, p. 102144, 2020, doi: 10.1016/j.simpat.2020.102144.

C. Tshimanga, K. Emmanuel, S. Ntumba, B. Eugène, and M. Mukendi, "A multi ‑ criteria decision making heuristic for workflow scheduling in cloud computing environment," J. Supercomput., no. 0123456789, 2022, doi: 10.1007/s11227-022-04677-z.

Y. Liu, A. Soroka, L. Han, J. Jian, and M. Tang, "Cloud-based big data analytics for customer insight-driven design innovation in SMEs," Int. J. Inf. Manage., vol. 51, no. November, pp. 0–1, 2020, doi: 10.1016/j.ijinfomgt.2019.11.002.

Y. Gu and C. Budati, "Energy-aware workflow scheduling and optimization in clouds using bat algorithm," Futur. Gener. Comput. Syst., vol. 113, pp. 106–112, 2020, doi: 10.1016/j.future.2020.06.031.

S. Azizi, M. Zandsalimi, and D. Li, "An energy-efficient algorithm for virtual machine placement optimization in cloud data centers," Cluster Comput., vol. 23, no. 4, pp. 3421–3434, 2020, doi: 10.1007/s10586-020-03096-0.

L. Kong, J. Pepe, B. Mapetu, and Z. Chen, "Heuristic Load Balancing Based Zero Imbalance Mechanism in Cloud Computing," J. Grid Comput., vol. 18, no 1, pp. 123–148, 2019, [Online]. Available: //doi.org/10.1007/s10723-019-09486-y

A. Pujiyanta and L. Edi, "Job Scheduling Strategies in Grid Computing," Int. J. Adv. Sci. Eng. Inf. Technol., vol. 12, no. 3, pp. 1293–1300, 2022.

P. Paknejad, R. Khorsand, and M. Ramezanpour, "Chaotic improved PICEA-g-based multi-objective optimization for workflow scheduling in cloud environment," Futur. Gener. Comput. Syst., vol. 117, pp. 12–28, 2021, doi: 10.1016/j.future.2020.11.002.

"CloudSigma. Accessed on: , [Online]. Available: https://www.cloudsigma.com/us/."

H. R. Faragardi, M. R. Saleh Sedghpour, S. Fazliahmadi, T. Fahringer, and N. Rasouli, "GRP-HEFT: A Budget-Constrained Resource Provisioning Scheme for Workflow Scheduling in IaaS Clouds," IEEE Trans. Parallel Distrib. Syst., vol. 31, no. 6, pp. 1239–1254, 2020, doi: 10.1109/TPDS.2019.2961098.

V. Kelefouras and K. Djemame, "Workflow simulation and multi-threading aware task scheduling for heterogeneous computing," J. Parallel Distrib. Comput., vol. 168, pp. 17–32, 2022, doi: 10.1016/j.jpdc.2022.05.011.

S. Saeedi, R. Khorsand, S. Ghandi Bidgoli, and M. Ramezanpour, "Improved many-objective particle swarm optimization algorithm for scientific workflow scheduling in cloud computing," Comput. Ind. Eng., vol. 147, p. 106649, 2020, doi: 10.1016/j.cie.2020.106649.

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, 2019, doi: 10.1016/j.sysarc.2019.08.004.

F. Jauro, H. Chiroma, A. Y. Gital, M. Almutairi, S. M. Abdulhamid, and J. H. Abawajy, "Deep learning architectures in emerging cloud computing architectures: Recent development, challenges and next research trend," Appl. Soft Comput. J., vol. 96, p. 106582, 2020, doi: 10.1016/j.asoc.2020.106582.

B. Liang, X. Dong, Y. Wang, and X. Zhang, "A low-power task scheduling algorithm for heterogeneous cloud computing," J. Supercomput., vol. 76, no. 9, pp. 7290–7314, 2020, doi: 10.1007/s11227-020-03163-8.

E. Bugingo, D. Zhang, Z. Chen, and W. Zheng, "Towards decomposition based multi-objective workflow scheduling for big data processing in clouds," Cluster Comput., vol. 24, no. 1, pp. 115–139, 2021, doi: 10.1007/s10586-020-03208-w.

X. Guo, "Multi-objective task scheduling optimization in cloud computing based on fuzzy self-defense algorithm," Alexandria Eng. J., vol. 60, no. 6, pp. 5603–5609, 2021, doi: 10.1016/j.aej.2021.04.051.

J. E. Ndamlabin Mboula, V. C. Kamla, and C. Tayou Djamegni, "Cost-time trade-off efficient workflow scheduling in cloud," Simul. Model. Pract. Theory, vol. 103, no. October 2019, p. 102107, 2020, doi: 10.1016/j.simpat.2020.102107.

Y. Hao, J. Cao, Q. Wang, and J. Du, "Energy-aware scheduling in edge computing with a clustering method," Futur. Gener. Comput. Syst., vol. 117, pp. 259–272, 2021, doi: 10.1016/j.future.2020.11.029.

A. Mohammadzadeh, M. Masdari, and F. S. Gharehchopogh, Energy and Cost-Aware Workflow Scheduling in Cloud Computing Data Centers Using a Multi-objective Optimization Algorithm, vol. 29, no. 3. Springer US, 2021. doi: 10.1007/s10922-021-09599-4.

K. Mishra and S. K. Majhi, "A binary Bird Swarm Optimization based load balancing algorithm for cloud computing environment," Open Comput. Sci., vol. 11, no. 1, pp. 146–160, 2021, doi: 10.1515/comp-2020-0215.

M. Sardaraz and M. Tahir, "A parallel multi-objective genetic algorithm for scheduling scientific workflows in cloud computing," Int. J. Distrib. Sens. Networks, vol. 16, no. 8, 2020, doi: 10.1177/1550147720949142.

C. G. Ralha, A. H. D. Mendes, L. A. Laranjeira, A. P. F. Araújo, and A. C. M. A. Melo, "Multiagent system for dynamic resource provisioning in cloud computing platforms," Futur. Gener. Comput. Syst., vol. 94, pp. 80–96, 2019, doi: 10.1016/j.future.2018.09.050.

A. Asghari and M. K. Sohrabi, "Combined use of coral reefs optimization and multi-agent deep Q-network for energy-aware resource provisioning in cloud data centers using DVFS technique," Cluster Comput., vol. 25, no. 1, pp. 119–140, 2022, doi: 10.1007/s10586-021-03368-3.

P. S. Rawat, P. Dimri, P. Gupta, and G. P. Saroha, "Resource provisioning in scalable cloud using bio-inspired artificial neural network model," Appl. Soft Comput., vol. 99, p. 106876, 2021, doi: 10.1016/j.asoc.2020.106876.

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, doi: 10.1016/j.future.2018.10.046.

T. A. L. Genez, I. Pietri, R. Sakellariou, L. F. Bittencourt, and E. R. M. Madeira, "A Particle Swarm Optimization Approach for Workflow Scheduling on Cloud Resources Priced by CPU Frequency," Proc. - 2015 IEEE/ACM 8th Int. Conf. Util. Cloud Comput. UCC 2015, pp. 237–241, 2015, doi: 10.1109/UCC.2015.40.

W. Ahmad, B. Alam, S. Ahuja, and S. Malik, "A dynamic VM provisioning and de-provisioning based cost-efficient deadline-aware scheduling algorithm for Big Data workflow applications in a cloud environment," Cluster Comput., vol. 24, no. 1, pp. 249–278, 2021, doi: 10.1007/s10586-020-03100-7.

N. Rizvi and D. Ramesh, "Fair budget constrained workflow scheduling approach for heterogeneous clouds," Cluster Comput., vol. 23, no. 4, pp. 3185–3201, 2020, doi: 10.1007/s10586-020-03079-1.

T. A. L. Genez, L. F. Bittencourt, and E. R. M. Madeira, "Time-discretization for speeding-up scheduling of deadline-constrained workflows in clouds," Futur. Gener. Comput. Syst., vol. 107, pp. 1116–1129, 2020, doi: 10.1016/j.future.2017.07.061.

N. Rizvi and D. Ramesh, "HBDCWS: heuristic-based budget and deadline constrained workflow scheduling approach for heterogeneous clouds," Soft Comput., vol. 24, no. 24, pp. 18971–18990, 2020, doi: 10.1007/s00500-020-05127-9.

E. B. Edwin, P. Umamaheswari, and M. R. Thanka, "An efficient and improved multi-objective optimized replication management with dynamic and cost aware strategies in cloud computing data center," Cluster Comput., vol. 22, no. s5, pp. 11119–11128, 2019, doi: 10.1007/s10586-017-1313-6.

K. Kalyan Chakravarthi, L. Shyamala, and V. Vaidehi, "Budget aware scheduling algorithm for workflow applications in IaaS clouds," Cluster Comput., vol. 23, no. 4, pp. 3405–3419, 2020, doi: 10.1007/s10586-020-03095-1.

I. Pietri and R. Sakellariou, "Cost-efficient CPU provisioning for scientific workflows on clouds," Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 9512, pp. 49–64, 2016, doi: 10.1007/978-3-319-43177-2_4.

E. Saeedizade and M. Ashtiani, DDBWS: a dynamic deadline and budget-aware workflow scheduling algorithm in workflow-as-a-service environments, vol. 77, no. 12. Springer US, 2021. doi: 10.1007/s11227-021-03858-6.

N. Zhou, W. Lin, W. Feng, F. Shi, and X. Pang, "Budget-deadline constrained approach for scientific workflows scheduling in a cloud environment," Cluster Comput., vol. 1, 2020, doi: 10.1007/s10586-020-03176-1.

Y. Wen, J. Liu, W. Dou, X. Xu, B. Cao, and J. Chen, "Scheduling workflows with privacy protection constraints for big data applications on cloud," Futur. Gener. Comput. Syst., vol. 108, pp. 1084–1091, 2020, doi: 10.1016/j.future.2018.03.028.

S. Yassa, R. Chelouah, H. Kadima, and B. Granado, "Multi-objective approach for energy-aware workflow scheduling in cloud computing environments," Sci. World J., vol. 2013, 2013, doi: 10.1155/2013/350934.

G. Khojasteh Toussi and M. Naghibzadeh, "A divide and conquer approach to deadline constrained cost-optimization workflow scheduling for the cloud," Cluster Comput., vol. 24, no. 3, pp. 1711–1733, 2021, doi: 10.1007/s10586-020-03223-x.

Y. Pan et al., "A Novel Approach to Scheduling Workflows Upon Cloud Resources with Fluctuating Performance," Mob. Networks Appl., vol. 25, no. 2, pp. 690–700, 2020, doi: 10.1007/s11036-019-01450-0.

R. Valarmathi and T. Sheela, "Ranging and tuning based particle swarm optimization with bat algorithm for task scheduling in cloud computing," Cluster Comput., vol. 22, no. s5, pp. 11975–11988, 2019, doi: 10.1007/s10586-017-1534-8.

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. 6, 2019, doi: 10.1142/S021812661930006X.

W. Zheng, Y. Qin, E. Bugingo, D. Zhang, and J. Chen, "Cost optimization for deadline-aware scheduling of big-data processing jobs on clouds," Futur. Gener. Comput. Syst., vol. 82, pp. 244–255, 2018, doi: 10.1016/j.future.2017.12.004.

H. Topcuoglu, S. Hariri, and M. Y. Wu, "Performance-effective and low-complexity task scheduling for heterogeneous computing," IEEE Trans. Parallel Distrib. Syst., vol. 13, no. 3, pp. 260–274, 2002, doi: 10.1109/71.993206.

B. Emmanuel, Y. Qin, J. Wang, D. Zhang, and W. Zheng, "Cost optimization heuristics for deadline constrained workflow scheduling on clouds and their comparative evaluation," Concurr. Comput. Pract. Exp., vol. 30, no. 20, pp. 1–14, 2018, doi: 10.1002/cpe.4762.

"Workflow Galler. Accessed on: April 20, 2021, [Online]. Available: https://confluence.pegasus.isi.edu/display/pegasus/."




DOI: http://dx.doi.org/10.18517/ijaseit.13.1.17752

Refbacks

  • There are currently no refbacks.



Published by INSIGHT - Indonesian Society for Knowledge and Human Development