More Web Proxy on the site http://driver.im/

research-article

A job scheduling algorithm based on rock hyrax optimization in cloud computing

Authors:

Saurabh Singhal,

Ashish SharmaAuthors Info & Claims

Computing, Volume 103, Issue 9

Pages 2115 - 2142

https://doi.org/10.1007/s00607-021-00942-w

Published: 01 September 2021 Publication History

Abstract

For many years, job scheduling in cloud computing has been researched to improve and optimize the environment. Although many researchers have worked on the issue of job scheduling, however, a comprehensive approach still misses out on various fronts like consideration of multi objective functions, handling the problem of local minima, and best resource utilization. An attempt has been made in the paper to present a reliable and comprehensive scheduling approach based on the meta-heuristic for the cloud computing environment. The proposed algorithm imitates the behavior of Rock Hyrax optimization for scheduling the jobs in a dynamic and heterogeneous cloud environment by considering the quality of service parameters like makespan time and energy consumption of data centers. The result establishes the claim that the proposal presented in this paper can schedule jobs in a dynamic environment on the virtual machine by keeping energy consumption low. The proposal is implemented through an experimental setup in the CloudSim environment and considered for variable jobs. The proposed algorithm for scheduling in the cloud environment is evaluated both qualitatively and quantitatively by considering both jobs and virtual machines statically and dynamically. The proposed algorithm is also compared with the prevalent approaches proposed in the past and shows better results. Our results indicate that the proposed meta-heuristic algorithm based on Rock Hyrax has lowered the makespan time by 5–15% and reduces energy consumption by 4–12%.

References

[1]

Abdulhamid SM, Abd Latiff MS, Abdul-Salaam G, and Hussain Madni SH Secure scientific applications scheduling technique for cloud computing environment using global league championship algorithm PLoS ONE 2016 11 7 e0158102

[2]

Akbari M, Rashidi H, and Alizadeh SH An enhanced genetic algorithm with new operators for task scheduling in heterogeneous computing systems Eng Appl Artif Intell 2017 61 35-46

[3]

Al-Maamari A and Omara FA Task scheduling using pso algorithm in cloud computing environments Int J Grid Distrib Comput 2015 8 5 245-256

[4]

Aljammal AH, Manasrah AM, Abdallah AE, and Tahat NM A new architecture of cloud computing to enhance the load balancing Int J Bus Inf Syst 2017 25 3 393-405

[5]

Aljazzaf ZM (2015) Modelling and measuring the quality of online services. Kuwait J Sci 42(3)

[6]

An B, Lesser VR, Irwin DE, and Zink M Automated negotiation with decommitment for dynamic resource allocation in cloud computing AAMAS 2010 10 981-988

[7]

Ari AAA, Damakoa I, Titouna C, Labraoui N, Gueroui A (2017) Efficient and scalable aco-based task scheduling for green cloud computing environment. In: 2017 IEEE international conference on smart cloud (SmartCloud). IEEE, pp 66–71

[8]

Azad P and Navimipour NJ An energy-aware task scheduling in the cloud computing using a hybrid cultural and ant colony optimization algorithm Int J Cloud Appl Comput (IJCAC) 2017 7 4 20-40

[9]

Babu KRR, Samuel P (2016) Enhanced bee colony algorithm for efficient load balancing and scheduling in cloud. In: Innovations in bio-inspired computing and applications. Springer, pp 67–78

[10]

Bacanin N, Bezdan T, Tuba E, Strumberger I, Tuba M, Zivkovic M (2019) Task scheduling in cloud computing environment by grey wolf optimizer. In: 2019 27th telecommunications forum (TELFOR). IEEE, pp 1–4

[11]

Badenhorst S, van Niekerk KL, Henshilwood CS, and hyraxes R (procavia capensis) from middle stone age levels at blombos cave, South Africa Afr Archaeol Rev 2014 31 1 25-43

[12]

Barham P, Dragovic B, Fraser K, Hand S, Harris T, Ho A, Neugebauer R, Pratt I, and Warfield A Xen and the art of virtualization ACM SIGOPS Oper Syst Rev 2003 37 5 164-177

[13]

Bilgaiyan S, Sagnika S, Das M (2014) Workflow scheduling in cloud computing environment using cat swarm optimization. In: 2014 IEEE international advance computing conference (IACC). IEEE, pp 680–685

[14]

Braun TD, Siegel HJ, Beck N, Bölöni LL, Maheswaran M, Reuther AI, Robertson JP, Theys MD, Yao B, Hensgen D, et al. A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems J Parallel Distrib Comput 2001 61 6 810-837

[15]

Chen W-N and Zhang J An ant colony optimization approach to a grid workflow scheduling problem with various qos requirements IEEE Trans Syst Man Cybern Part C (Appl Rev) 2008 39 1 29-43

[16]

Dai Y, Lou Y, Lu X (2015) A task scheduling algorithm based on genetic algorithm and ant colony optimization algorithm with multi-qos constraints in cloud computing. In: 2015 7th international conference on intelligent human-machine systems and cybernetics, vol 2. IEEE, pp 428–431

[17]

Dasgupta K, Mandal B, Dutta P, Mandal JK, and Dam S A genetic algorithm (ga) based load balancing strategy for cloud computing Procedia Technol 2013 10 340-347

[18]

de Assunção MD, Costanzo A, and Buyya R A cost-benefit analysis of using cloud computing to extend the capacity of clusters Cluster Comput 2010 13 3 335-347

[19]

Ding L, Fan P, Wen B (2013) A task scheduling algorithm for heterogeneous systems using aco. In: 2013 2nd international symposium on instrumentation and measurement, sensor network and automation (IMSNA). IEEE, pp 749–751

[20]

Druce DJ, Brown JS, Castley JG, Kerley GIH, Kotler BP, Slotow R, and Knight MH Scale-dependent foraging costs: habitat use by rock hyraxes (procavia capensis) determined using giving-up densities Oikos 2006 115 3 513-525

[21]

Esa DI and Yousif A Scheduling jobs on cloud computing using firefly algorithm Int J Grid Distrib Comput 2016 9 7 149-158

[22]

Fard HM, Prodan R, Barrionuevo JJD, Fahringer T (2012) A multi-objective approach for workflow scheduling in heterogeneous environments. In: 2012 12th IEEE/ACM international symposium on cluster, cloud and grid computing (ccgrid 2012). IEEE, pp 300–309

[23]

Ge Y, Wei G (2010) Ga-based task scheduler for the cloud computing systems. In: 2010 international conference on web information systems and mining, vol 2. IEEE, pp 181–186

[24]

Ghasemi S, Kheyrolahi A, and Shaltooki AA Workflow scheduling in cloud environment using firefly optimization algorithm JOIV: Int J Informatics Visual 2019 3 3 237-242

[25]

Guo L, Zhao S, Shen S, and Jiang C Task scheduling optimization in cloud computing based on heuristic algorithm J Netw 2012 7 3 547

[26]

Gupta BB and Akhtar T A survey on smart power grid: frameworks, tools, security issues, and solutions Ann Telecommun 2017 72 9–10 517-549

[27]

Hu H, Wang H (2016) A prediction-based aco algorithm to dynamic tasks scheduling in cloud environment. In: 2016 2nd IEEE international conference on computer and communications (ICCC). IEEE, pp 2727–2732

[28]

Jacob L Bat algorithm for resource scheduling in cloud computing Population 2014 5 18 23

[29]

Jacob L, Jeyakrishanan V, and Sengottuvelan P Resource scheduling in cloud using bacterial foraging optimization algorithm Int J Comput Appl 2014 92 1 14-20

[30]

Jain N, Menache I, Naor JS, and Yaniv J A truthful mechanism for value-based scheduling in cloud computing Theory Comput Syst 2014 54 3 388-406

[31]

Jang SH, Kim TY, Kim JK, and Lee JS The study of genetic algorithm-based task scheduling for cloud computing Int J Control Autom 2012 5 4 157-162

[32]

Javanmardi S, Shojafar M, Amendola D, Cordeschi N, Liu H, Abraham A (2014) Hybrid job scheduling algorithm for cloud computing environment. In: Proceedings of the fifth international conference on innovations in bio-inspired computing and applications IBICA 2014. Springer, pp 43–52

[33]

Ji H, Bao W, and Zhu X Adaptive workflow scheduling for diverse objectives in cloud environments Trans Emerg Telecommun Technol 2017 28 2 e2941

[34]

Kashikolaei SMG, Hosseinabadi AAR, Saemi B, Shareh MB, Sangaiah AK, and Bian G-B An enhancement of task scheduling in cloud computing based on imperialist competitive algorithm and firefly algorithm J Supercomput 2020 76 8 6302-6329

[35]

Kaur P and Sharma M Diagnosis of human psychological disorders using supervised learning and nature-inspired computing techniques: a meta-analysis J Med Syst 2019 43 7 204

[36]

Keshanchi B, Souri A, and Navimipour NJ An improved genetic algorithm for task scheduling in the cloud environments using the priority queues: formal verification, simulation, and statistical testing J Syst Softw 2017 124 1 21

[37]

Keshavamurthy BN, et al Improved pso for task scheduling in cloud computing. In: Evolution in computational intelligence. Springer, pp 467–474

[38]

Keshk AE, El-Sisi AB, and Tawfeek MA Cloud task scheduling for load balancing based on intelligent strategy Int J Intell Syst Appl 2014 6 5 25

[39]

Kumar P, Verma A (2012) Scheduling using improved genetic algorithm in cloud computing for independent tasks. In: Proceedings of the international conference on advances in computing, communications and informatics, pp 137–142

[40]

Li J, Liu Z, Chen X, Xhafa F, Tan X, and Wong DS L-encdb: a lightweight framework for privacy-preserving data queries in cloud computing Knowl-Based Syst 2015 79 18-26

[41]

Li Z, Ge J, Haiyang H, Song W, Hao H, and Luo B Cost and energy aware scheduling algorithm for scientific workflows with deadline constraint in clouds IEEE Trans Serv Comput 2015 11 4 713-726

[42]

Liu C-Y, Zou C-M, Wu P (2014) A task scheduling algorithm based on genetic algorithm and ant colony optimization in cloud computing. In: 2014 13th international symposium on distributed computing and applications to business, engineering and science. IEEE, pp 68–72

[43]

Liu Z, Wang X (2012) A pso-based algorithm for load balancing in virtual machines of cloud computing environment. In: International conference in swarm intelligence. Springer, pp 142–147

[44]

Lu X, Gu Z (2011) A load-adapative cloud resource scheduling model based on ant colony algorithm. In: 2011 IEEE international conference on cloud computing and intelligence systems. IEEE, pp 296–300

[45]

Manasrah AM Dynamic weighted vm load balancing for cloud-analyst Int J Inf Comput Secur 2017 9 1–2 5-19

[46]

Manasrah AM, Smadi T, and ALmomani A A variable service broker routing policy for data center selection in cloud analyst J King Saud Univ-Comput Inf Sci 2017 29 3 365-377

[47]

Mantri A, Kendra SNS, Kumar G, Kumar S (2011) High performance architecture and grid computing: international conference, HPAGC 2011, Chandigarh, India, July 19–20, 2011. Proceedings, vol 169. Springer Science & Business Media

[48]

Mao Y, Chen X, Li X (2014) Max–min task scheduling algorithm for load balance in cloud computing. In: Proceedings of international conference on computer science and information technology. Springer, pp 457–465

[49]

Moon YJ, HeonChang Yu, Gil J-M, and Lim JB A slave ants based ant colony optimization algorithm for task scheduling in cloud computing environments Human-cent Comput Inf Sci 2017 7 1 28

[50]

Mustafa S, Nazir B, Hayat A, Madani SA, et al. Resource management in cloud computing: taxonomy, prospects, and challenges Comput Electrical Eng 2015 47 186-203

[51]

Nagadevi S, Satyapriya K, and Malathy D A survey on economic cloud schedulers for optimized task scheduling Int J Adv Eng Technol 2013 4 1 58-62

[52]

Natarajan Y, Kannan S, and Dhiman G Task scheduling in cloud using aco Recent Adv Comput Sci Commun 2021 13 1-6

[53]

Pan BL, Wang YP, Li HX, Qian J (2014) Task scheduling and resource allocation of cloud computing based on qos. In: Advanced materials research, vol 915, pp 1382–1385. Trans Tech Publ

[54]

Pandey S, Wu L, Guru SM, Buyya R (2010) A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments. In: 2010 24th IEEE international conference on advanced information networking and applications. IEEE, pp 400–407

[55]

Qiao Y, Wang H, and Dai G-Z Developing a new dynamic scheduling algorithm for real-time multiprocessor systems J Softw 2002 13 1 51-58

[56]

Raghavan S, Sarwesh P, Marimuthu C, Chandrasekaran K (2015) Bat algorithm for scheduling workflow applications in cloud. In: 2015 international conference on electronic design, computer networks & automated verification (EDCAV). IEEE, pp 139–144

[57]

Rajathy R, Taraswinee B, Suganya S (2015) A novel method of using symbiotic organism search algorithm in solving security-constrained economic dispatch. In: 2015 international conference on circuits, power and computing technologies [ICCPCT-2015]. IEEE, pp 1–8

[58]

Ramamritham K, Stankovic JA, and Shiah P-F Efficient scheduling algorithms for real-time multiprocessor systems IEEE Trans Parallel Distrib Syst 1990 1 2 184-194

[59]

Rana M, Bilgaiyan S, Kar U (2014) A study on load balancing in cloud computing environment using evolutionary and swarm based algorithms. In: 2014 international conference on control, instrumentation, communication and computational technologies (ICCICCT). IEEE, pp 245–250

[60]

Rueda DR, Cotta C, and Fernández-Leiva AJ Metaheuristics for the template design problem: encoding, symmetry and hybridisation J Intell Manuf 2020 32 559-578

[61]

Sagnika S, Bilgaiyan S, Mishra BSP (2018) Workflow scheduling in cloud computing environment using bat algorithm. In: Proceedings of first international conference on smart system, innovations and computing. Springer, pp 149–163

[62]

Saleh IA, Alsaif OI, Muhamed SA, Essa EI (2019) Task scheduling for cloud computing based on firefly algorithm. In: Journal of Physics: Conference Series, vol 1294. IOP Publishing, p 042004

[63]

Sedighi M, Jahangirnia H, Gharakhani M, and Farahani Fard S A novel hybrid model for stock price forecasting based on metaheuristics and support vector machine Data 2019 4 2 75

[64]

Sharma M, Kaur P (2020) A comprehensive analysis of nature-inspired meta-heuristic techniques for feature selection problem. Arch Comput Methods Eng 1–25

[65]

Sharma M, Singh G, and Singh R Design of ga and ontology based nlp frameworks for online opinion mining Recent Patents Eng 2019 13 2 159-165

[66]

Sharma M, Singh G, and Singh R A review of different cost-based distributed query optimizers Progress Artif Intell 2019 8 1 45-62

[67]

Sharma S, Singh G (2020) Diagnosis of cardiac arrhythmia using swarm-intelligence based metaheuristic techniques: a comparative analysis. EAI Endorsed Trans Pervasive Health Technol 6(23)

[68]

Sheetal AP and Ravindranath K Priority based resource allocation and scheduling using artificial bee colony (abc) optimization for cloud computing systems Int J Innov Technol Explor Eng 2019 8 6 39-44

[69]

Shenai S et al. Survey on scheduling issues in cloud computing Procedia Eng 2012 38 2881-2888

[70]

Singh L, Singh S (2014) A genetic algorithm for scheduling workflow applications in unreliable cloud environment. In: International conference on security in computer networks and distributed systems. Springer, pp 139–150

[71]

Singh R Nature inspired based meta-heuristic techniques for global applications Int J Comput Appl Inf Technol 2020 12 1 303-309

[72]

Son S, Jun SC (2013) Negotiation-based flexible SLA establishment with SLA-driven resource allocation in cloud computing. In: 2013 13th IEEE/ACM international symposium on cluster, cloud, and grid computing. IEEE, pp 168–171

[73]

Suresh A, Varatharajan R (2019) Competent resource provisioning and distribution techniques for cloud computing environment. Cluster Comput, pp 1–8

[74]

Talukder AKMKA, Kirley M, and Buyya R Multiobjective differential evolution for scheduling workflow applications on global grids Concurr Comput Practice Exp 2009 21 13 1742-1756

[75]

Valentini GL, Lassonde W, Khan SU, Min-Allah N, Madani SA, Li J, Zhang L, Wang L, Ghani N, Kolodziej J, et al. An overview of energy efficiency techniques in cluster computing systems Cluster Comput 2013 16 1 3-15

[76]

Van den Bossche R, Vanmechelen K, Broeckhove J (2011) Cost-efficient scheduling heuristics for deadline constrained workloads on hybrid clouds. In: 2011 IEEE third international conference on cloud computing technology and science. IEEE, pp 320–327

[77]

Vaquero LM, Rodero-Merino L, Caceres J, Lindner M (2008) A break in the clouds: towards a cloud definition pp 50–55

[78]

Verma A and Kaushal S Deadline constraint heuristic-based genetic algorithm for workflow scheduling in cloud Int J Grid Util Comput 2014 5 2 96-106

[79]

Verma A and Kaushal S Cost-time efficient scheduling plan for executing workflows in the cloud J Grid Comput 2015 13 4 495-506

[80]

Xue S, Li M, Xiaolong X, Chen J, and Xue S An aco-lb algorithm for task scheduling in the cloud environment J Softw 2014 9 2 466-473

[81]

Yu J, Buyya R, Ramamohanarao K (2008) Workflow scheduling algorithms for grid computing. In: Metaheuristics for scheduling in distributed computing environments. Springer, pp 173–214

[82]

Zhang L, Chen Y, Sun R, Jing S, and Yang B A task scheduling algorithm based on pso for grid computing Int J Comput Intell Res 2008 4 1 37-43

[83]

Zhang Z, Zhang X (2010) A load balancing mechanism based on ant colony and complex network theory in open cloud computing federation. In: 2010 The 2nd international conference on industrial mechatronics and automation, vol 2. IEEE, pp 240–243

[84]

Zhou Z, Li F, Zhu H, Xie H, Abawajy JH, and Chowdhury MU An improved genetic algorithm using greedy strategy toward task scheduling optimization in cloud environments Neural Comput Appl 2020 32 6 1531-1541

Cited By

Çavdar MKorpeoglu IUlusoy Ö(2024)Application Scheduling With Multiplexed Sensing of Monitoring Points in Multi-Purpose IoT Wireless Sensor NetworksIEEE Transactions on Network and Service Management10.1109/TNSM.2023.331775821:1(729-744)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1109/TNSM.2023.3317758
Beikzadeh Abbasi FRezaee AAdabi SMovaghar A(2023)Fault-tolerant scheduling of graph-based loads on fog/cloud environments with multi-level queues and LSTM-based workload predictionComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2023.109964235:COnline publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1016/j.comnet.2023.109964

Recommendations

Scheduling unrelated parallel batch processing machines with non-identical job sizes and unequal ready times

This research analyzes the problem of scheduling a set of n jobs with arbitrary job sizes and non-zero ready times on a set of m unrelated parallel batch processing machines so as to minimize the makespan. Unrelated parallel machine is a generalization ...
Simulation Based Job Scheduling Optimization for Batch Workloads
ICPE '19: Proceedings of the 2019 ACM/SPEC International Conference on Performance Engineering

We present a simulation based approach for scheduling jobs that are part of a batch workflow. Our objective is to minimize the makespan, defined as completion time of the last job to leave the system in a batch workflow with dependencies. The existing ...
Single machine batch scheduling problem with family setup times and release dates to minimize makespan

In this paper we consider the single machine batch scheduling problem with family setup times and release dates to minimize makespan. We show that this problem is strongly NP-hard, and give an $$O(n (\frac{n}{m}+1)^m)$$ time dynamic programming algorithm and an $$O(mk^{k}P^{2k-1})$$ time dynamic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computing

Computing Volume 103, Issue 9

Sep 2021

256 pages

ISSN:0010-485X

Issue’s Table of Contents

© The Author(s), under exclusive licence to Springer-Verlag GmbH Austria, part of Springer Nature 2021.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 September 2021

Accepted: 19 March 2021

Received: 18 December 2020

Author Tags

Author Tag

68M20

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Çavdar MKorpeoglu IUlusoy Ö(2024)Application Scheduling With Multiplexed Sensing of Monitoring Points in Multi-Purpose IoT Wireless Sensor NetworksIEEE Transactions on Network and Service Management10.1109/TNSM.2023.331775821:1(729-744)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1109/TNSM.2023.3317758
Beikzadeh Abbasi FRezaee AAdabi SMovaghar A(2023)Fault-tolerant scheduling of graph-based loads on fog/cloud environments with multi-level queues and LSTM-based workload predictionComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2023.109964235:COnline publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1016/j.comnet.2023.109964

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents