Generic placeholder image

Recent Advances in Computer Science and Communications

Author(s): Hicham Ben Alla*, Said Ben Alla and Abdellah Ezzati

DOI: 10.2174/2213275911666181018124742

DownloadDownload PDF Flyer Cite As
A Dynamic Task Scheduling Algorithm for Cloud Computing Environment

Page: [296 - 307] Pages: 12

  • * (Excluding Mailing and Handling)

Explore Articles
About Journal
For Authors
For Editors
For Reviewers

Abstract

Background: Cloud computing environment is a novel paradigm in which the services are hosted, delivered and managed over the internet. Tasks scheduling problem in the cloud has become a very interesting research area. However, the problem is more complex and challenging due to the dynamic nature of cloud and users’ needs as well as cloud providers’ requirements including the quality of service, users’ priorities and computing capabilities.

Objective: The main objective is to solve the problem of tasks scheduling through an algorithm which can not only improves the client satisfaction, but also allows cloud service provider to gain maximum profit and ensure that the cloud resources are utilized efficiently.

Method: (a) Optimization of the waiting time and the queue length.

(b) Distribution of all requests into a novel queueing system in a dynamic manner based on a decision threshold.

(c) Assignment of requests to VMs based on Particle Swarm Optimization and Simulated Annealing algorithms.

(d) Incorporation of the priority constraint in the scheduling process by considering three priorities levels including the tasks, queues and VMs.

Results: The results comparison of our algorithm with particle swarm optimization and First Come First Serve algorithms demonstrate the effectiveness of our algorithm in terms of waiting time, makespan, resources utilization and degree of imbalance.

Conclusion: This study introduces an efficient strategy to schedule users’ tasks by using dynamic dispatch queues and particle swarm optimization with simulated annealing algorithms. Moreover, it incorporates the priority issue in the scheduling process.

Keywords: Cloud computing, particle swarm optimization, DDQ-SAPSO algorithm, DPDQ-SAPSO algorithm, task scheduling, queueing system, simulated annealing.

Graphical Abstract

[1]
A. Shawish, and M. Salama, "Cloud computing: Paradigms and technologies", In: Inter-cooperative Collective Intelligence: Techniques and Applications.F. Xhafa and N. Bessis, eds.; Springer,Verlag, 2014, pp. 39-67.
[2]
M.G. Avram, "Advantages and challenges of adopting cloud computing from an enterprise perspective", Procedia Technol., vol. 12, pp. 529-534, 2014.
[http://dx.doi.org/10.1016/j.protcy.2013.12.525]
[3]
P. Mell, and T. Grance, "The NIST definition of cloud computing", National Institute of Standards and Technology., September 2011.Available from:.https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-145.pdf
[4]
H. Ben Alla, S. Ben Alla, and A. Ezzati, "A novel architecture for task scheduling based on dynamic queues and particle swarm optimization in cloud computing", 2016 2nd International Conference on Cloud Computing Technologies and Applications (CloudTech),. Marrakech, Morocco, 2016, pp. 108-114.
[http://dx.doi.org/10.1109/CloudTech.2016.7847686]
[5]
H. Ben Alla, S. Ben Alla, A. Touhafi, and A. Ezzati, "A novel task scheduling approach based on dynamic queues and hybrid metaheuristic algorithms for cloud computing environment", Cluster Comput., vol. 21, pp. 1797-1820, 2018.
[http://dx.doi.org/10.1007/s10586-018-2811-x]
[6]
H. Ben Alla, S. Ben Alla, A. Ezzati, and A. Touhafi, "An efficient dynamic priority-queue algorithm based on AHP and PSO for task scheduling in cloud computing", In: Advances in Intelligent Systems and Computing., Springer: Cham, 2017, pp. 134-143.
[7]
J. Ma, W. Li, T. Fu, L. Yan, and G. Hu, "A novel dynamic task scheduling algorithm based on improved genetic algorithm in cloud computing", In: Wireless Communications, Networking and Applications., Springer: New Delhi, 2015, pp. 829-835.https://www.researchgate.net/deref/http%3A%2F%2Fdx.doi.org%2F10.1007%2F978-81-322-2580-5_75
[8]
X. Wu, M. Deng, R. Zhang, B. Zeng, and S. Zhou, "A task scheduling algorithm based on QoS-driven in cloud computing", Procedia Comput. Sci., vol. 17, pp. 1162-1169, 2013.
[http://dx.doi.org/10.1016/j.procs.2013.05.148]
[9]
A. Beegom, and M. Rajasree, "A particle swarm optimization based pareto optimal task scheduling in cloud computing", Lect. Notes Comput. Sci., pp. 79-86, 2014.
[http://dx.doi.org/10.1007/978-3-319-11897-0_10]
[10]
Y. Dai, Y. Lou, and X. Lu, "A task scheduling algorithm based on genetic algorithm and Ant colony optimization algorithm with Multi-QoS constraints in cloud computing", 7th International Conference on Intelligent Human-Machine Systems and Cybernetics.Hangzhou, China 2015, pp. 428-431
[http://dx.doi.org/10.1109/IHMSC.2015.186]
[11]
"Himani and H. Sidhu,Cost-deadline based task scheduling in cloud computing", 2015 Second International Conference on Advances in Computing and Communication Engineering.Dehradun, India 2015, pp. 273-279.
[http://dx.doi.org/10.1109/ICACCE.2015.86]
[12]
R. Jena, "Multi objective task scheduling in cloud environment using nested pso framework", Procedia Comput. Sci., vol. 57, pp. 1219-1227, 2015.
[http://dx.doi.org/10.1016/j.procs.2015.07.419]
[13]
H. Al-Olimat, M. Alam, R. Green, and J. Lee, "Cloudlet scheduling with particle swarm optimization", 2015 Fifth International Conference on Communication Systems and Network Technologies.Gwalior, India 2015, pp. 991-995.
[http://dx.doi.org/10.1109/CSNT.2015.252 ]
[14]
A. Thomas, G. Krishnalal, and V. Jagathy Raj, "Credit based scheduling algorithm in cloud computing environment", Procedia Comput. Sci., vol. 46, pp. 913-920, 2015.
[http://dx.doi.org/10.1016/j.procs.2015.02.162]
[15]
A. Verma, and S. Kaushal, “Bi-criteria priority based particle swarm optimization workflow scheduling algorithm for cloud,” 2014 Recent Advances in Engineering and Computational Sciences., RAECS: Chandigarh, India, 2014, pp. 1-6.
[http://dx.doi.org/10.1109/RAECS.2014.6799614]
[16]
S. Patel, and U. Bhoi, "Improved priority based job scheduling algorithm in cloud computing using iterative method", 2014 Fourth International Conference on Advances in Computing and Communications. Cochin, India, 2014, pp. 199-202
[http://dx.doi.org/10.1109/ICACC.2014.55]
[17]
M. Vijayalakshmi, and V.V. Kumar, Investigations on job scheduling algorithms in cloud computing, 2018. Available from: , http://www.ijarcst.com/conference/ first/ conf33.pdf
[18]
A. Karthick, E. Ramaraj, and R. Subramanian, "An efficient multi queue job scheduling for cloud computing", 2014 World Congress on Computing and Communication Technologies.Trichirappalli, India 2014, pp. 164-166.
[http://dx.doi.org/10.1109/WCCCT.2014.8]
[19]
H. Chen, F. Wang, N. Helian, and G. Akanmu, "User-priority guided Min-Min scheduling algorithm for load balancing in cloud computing", 2013 National Conference on Parallel Computing Technologies (PARCOMPTECH).Bangalore, India 2013, pp. 1-8.
[http://dx.doi.org/10.1109/ParCompTech.2013.6621389]
[20]
J. Kennedy, and R. Eberhart, "Particle swarm optimization", International Conference on Neural Networks.Perth, WA, Australia Vol. 4, 1995, pp. 1942-1948.
[http://dx.doi.org/0.1109/ICNN.1995.488968]
[21]
A. Al-maamari, and F. Omara, "Task scheduling using PSO algorithm in cloud computing envi-ronments", Int. J. Grid Distrib. Comput., vol. 8, no. 5, pp. 245-256, 2015.
[http://dx.doi.org/10.14257/ijgdc.2015.8.5.24]
[22]
P. Komer, A. Abraham, and V. Snášel, Proceedings of the Fifth International Conference on Inno-vations in Bio-Inspired Computing and Applications IBICA 2014. Springer, Vol. 303, 2014
[23]
Y. Tan, Y. Shi, and B. Niu, "Advances in swarm intelligence", Lect. Notes Comput. Sci., 2014.
[24]
M. Clerc, and J. Kennedy, "The particle swarm - explosion, stability and convergence in a multidi-mensional complex space", IEEE Trans. Evol. Comput., vol. 6, no. 1, pp. 58-73, 2002.
[http://dx.doi.org/10.1109/4235.985692]
[25]
Y. Feng, G. Teng, A. Wang, and Y. Yao, "Chaotic inertia weight in particle swarm optimization", Second International Conference on Innovative Computing, Information and Control (ICICIC 2007).Kumamoto, Japan 2007, pp. 475-475.
[http://dx.doi.org/10.1109/ICICIC.2007.209]
[26]
J. Xin, G. Chen, and Y. Hai, "A particle swarm optimizer with multi-stage linearly-decreasing inertia weight", 2009 International Joint Conference on Computational Sciences and Optimization. Sanya, Hainan, 2009, pp. 505-508.
[http://dx.doi.org/10.1109/CSO.2009.420]
[27]
G. Yue-lin, and D. Yu-hong, "A new particle swarm optimization algorithm with random inertia weight and evolution strategy", 2007 International Conference on Computational Intelligence and Security Workshops (CISW 2007.Heilongjiang, China 2007, pp. 199-203.
[http://dx.doi.org/10.1109/CISW.2007.4425479]
[28]
J. Kennedy, and R.C. Eberhart, "A discrete binary version of the particle swarm algorithm", 1997 IEEE International Conference on Systems, Man, and Cybernetics. Computational Cybernetics and Simulation. Orlando, FL, USA, 1997, Vol. 5, pp. 4104-4108,
[http://dx.doi.org/10.1109/ICSMC.1997.637339]
[29]
S. Ghanbari, and M. Othman, "A priority based job scheduling algorithm in cloud computing", Procedia Eng., vol. 50, pp. 778-785, 2012.
[30]
"Parallel Workloads Archive. Available from:", http://www.cs.huji.ac.il/ labs/ parallel/workload/
[31]
H. Ben Alla, S. Ben Alla, and A. Ezzati, "A priority based task scheduling in cloud computing using a hybrid MCDM model", In: Ubiquitous Networking. UNet 2017. Lecture Notes in Computer Science. E. Sabir, A. García Armada, M. Ghogho, M. Debbah eds,Springer: Cham, Vol. 10542, 2017.
[http://dx.doi.org/10.1007/978-3-319-68179-5_21]
[32]
D. Król, L. Madeyski, and N. Thanh Nguyen, Recent Developments in Intelligent Information and Database Systems., 1st ed Springer, 2016.
[http://dx.doi.org/10.1007/978-3-319-31277-4]
[33]
R. Calheiros, R. Ranjan, A. Beloglazov, C. De Rose, and R. Buyya, "CloudSim: a toolkit for mod-eling and simulation of cloud computing environments and evaluation of resource provisioning algo-rithms", Softw. Pract. Exper., vol. 41, no. 1, pp. 23-50, 2011.
[http://dx.doi.org/10.1002/spe.995]
[34]
H. Ben, S. Ben Alla, A. Ezzati, and A. Mouhsen, "A novel architecture with dynamic queues based on fuzzy logic and particle swarm optimization algorithm for task scheduling in cloud computing", In: Advances in Ubiquitous Networking 2. UNet 2016. Lecture Notes in Electrical Engineering,. R. El-Azouzi, D. Menasche, E. Sabir, F.De Pellegrini and M. Benjillali, Eds.; Singapore: Springer, Vol. 397,2017.
[35]
"Parallel Workloads Archive", SDSC Blue Horizon.Available from:, http://www.cs.huji.ac.il/labs/parallel/workload/l_sdsc_blue/
[36]
"Web.iitd.ac.in. Available from: ", http://web.iitd.ac.in/~dharmar/virtuallab/Theory/QueuingNotes.pdf
[37]
M. Kalra, and S. Singh, "A review of metaheuristic scheduling techniques in cloud computing", Egyptian Inform. J., vol. 16, no. 3, pp. 275-295, 2015.
[http://dx.doi.org/10.1016/j.eij.2015.07.001]
[38]
"Parallel Workloads Archive: The Cornell Theory Center (CTC) IBM. Available from: ", http://www.cs.huji.ac.il/labs/parallel/workload/ l_ctc_sp2/ index.html
[39]
K. Li, G. Xu, G. Zhao, Y. Dong, and D. Wang, "Cloud task scheduling based on load balancing ant colony optimization", 2011 Sixth Annual Chinagrid Conference.Liaoning 2011, pp. 3-9.
[http://dx.doi.org/10.1109/ChinaGrid.2011.17]