Volume 15, Issue 2 (Journal of Control, V.15, N.2 Summer 2021)
JoC 2021, 15(2): 81-96 |
Back to browse issues page
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Sadeghi Hesar A, Kamel Tabakh S R, Houshmand M. Task Scheduling Using the PSO-IWD Hybrid Algorithm in Cloud Computing with Heterogeneous Resources. JoC 2021; 15 (2) :81-96
URL: http://joc.kntu.ac.ir/article-1-627-en.html
URL: http://joc.kntu.ac.ir/article-1-627-en.html
1- Islamic Azad University of Mashhad
Abstract: (12837 Views)
Optimal Task Scheduling is one of the most important challenges for achieving high performance in distributed environments such as cloud computing. The primary purpose of task scheduling is to allocate tasks to resources so that some of the system performance metrics will be optimized such as runtime or parallelism. Task scheduling is an NP-complete problem, so heuristic or metha-heuristic algorithms are used to solve it. Because cloud providers offer computing resources based on the pay-as-you-go model, the scheduling algorithm affects the users cost of the cloud. In this paper, a new cloud task scheduling algorithm based on particle swarm optimization as a metha-heuristic method is proposed that assigns users tasks to free resources in cloud computing environments. To enhance the convergence rate of the particle swarm optimization method, the intelligent water drops algorithm is applied. The results of this algorithm on random graphs showed a significant improvement in the performance of the proposed method compared to other task scheduling algorithms.
Keywords: Cloud Computing, Task Scheduling, Particle Swarm Optimization, Intelligent Water Drops, Heterogeneous Resources
Type of Article: Research paper |
Subject:
Special
Received: 2018/10/28 | Accepted: 2020/06/27 | ePublished ahead of print: 2020/07/10 | Published: 2021/07/4
Received: 2018/10/28 | Accepted: 2020/06/27 | ePublished ahead of print: 2020/07/10 | Published: 2021/07/4
References
1. [1] Erl Thomas, Puttini Ricardo, Mahmood Zaigham, Cloud Computing: Concepts, Technology & Architecture (1st Edition), Prentice Hall, 2013.
2. [2] Rountree Derrick, Castrillo Ileana, Understanding the Fundamentals of Cloud Computing in Theory and Practice (1st Edition), Syngress, 2013.
3. [3] Kumar Sehgal, Naresh, Cloud Computing: Concepts and Practices, Springer, 2018. [DOI:10.1007/978-3-030-24612-9_3]
4. [4] Ullman J.D, 1975, "NP-complete scheduling problems", Journal of Computer and System Sciences, 10(3), pp. 384-393. [DOI:10.1016/S0022-0000(75)80008-0]
5. [5] Lee K.Y, Park J.B, 2006, "Application of Particle Swarm Optimization to Economic Dispatch Problem: Advantages and Disadvantages", 2006 IEEE PES Power Systems Conference and Exposition, Atlanta, GA, USA. pp. 188-192. [DOI:10.1109/PSCE.2006.296295]
6. [6] Talbi El-Ghazali, Metaheuristics: From Design to Impelementation, John Wiley and sons, 2009.
7. [7] Arnav W, Theng D, 2016, "A survey on different scheduling algorithms in cloud computing", In 2016 2nd International Conference on Advances in Electrical, Electronics, Information, Communication and Bio-Informatics (AEEICB), pp. 665-669.
8. [8] Santhosh B, Manjaiah D. H, Suresh L.P, 2016, "A survey of various scheduling algorithms in cloud environment", 2016 International Conference on Emerging Technological Trends (ICETT), Kollam, India. [DOI:10.1109/ICETT.2016.7873782]
9. [9] SudhirShenai V, 2012, "Survey on Scheduling Issues in Cloud Computing", Procedia Engineering, 38, pp. 2881-2888. [DOI:10.1016/j.proeng.2012.06.337]
10. [10] Muhuri P.K, Rauniyar A, Nath R, 2019, "On arrival scheduling of real-time precedence constrained tasks on multi-processor systems using genetic algorithm", Future Generation Computer Systems, 93, pp. 702-726. [DOI:10.1016/j.future.2018.10.013]
11. [11] Sharma M, Garg R, 2019, "HIGA: Harmony-inspired genetic algorithm for rack-aware energy-efficient task scheduling in cloud data centers", Engineering Science and Technology, an International Journal, 23, pp. 211-224. [DOI:10.1016/j.jestch.2019.03.009]
12. [12] Alharkan I, Saleh M, Ghaleb M.A, Kaid H, Farhan A, Almarfadi A, 2019, "Tabu search and particle swarm optimization algorithms for two identical parallel machines scheduling problem with a single server", Journal of King Saud University - Engineering Sciences, xx, pp. xx-xx, (In-press). [DOI:10.1016/j.jksues.2019.03.006]
13. [13] Adhikari M, Srirama S.N, 2019, "Multi-objective accelerated particle swarm optimization with a container-based scheduling for Internet-of-Things in cloud environment", Journal of Network and Computer Applications, 137, pp. 35-61. [DOI:10.1016/j.jnca.2019.04.003]
14. [14] Mansouri N, HasaniZade B.H, Javidi M.M, 2019, "Hybrid task scheduling strategy for cloud computing by modified particle swarm optimization and fuzzy theory", Computers & Industrial Engineering, 130, pp. 597-633. [DOI:10.1016/j.cie.2019.03.006]
15. [15] AbdElaziz M, Ewees A.A, AliIbrahim R, Lu S.F, 2019, "Opposition-based moth-flame optimization improved by differential evolution for feature selection", Mathematics and Computers in Simulation, 168, pp. 48-75. [DOI:10.1016/j.matcom.2019.06.017]
16. [16] Casas I, Taheri J, Ranjan R, Wang L, Zomaya A.Y, 2018, "GA-ETI: An enhanced genetic algorithm for the scheduling of scientific workflows in cloud environments", Journal of Computational Science, 26, pp. 318-331. [DOI:10.1016/j.jocs.2016.08.007]
17. [17] Wu G, Wang H, Pedrycz W, Li H, Wang L, 2017, "Satellite observation scheduling with a novel adaptive simulated annealing algorithm and a dynamic task clustering strategy", Computers & Industrial Engineering, 113, pp. 576-588. [DOI:10.1016/j.cie.2017.09.050]
18. [18] Baizid K, Yousnadj A, Meddahi A, Chellali R, Iqbal J, 2015, "Time scheduling and optimization of industrial robotized tasks based on genetic algorithms", Robotics and Computer-Integrated Manufacturing, 34, pp. 140-150. [DOI:10.1016/j.rcim.2014.12.003]
19. [19] Kamalinia A, Ghaffari A, 2017, "Hybrid Task Scheduling Method for Cloud Computing by Genetic and DE Algorithms", Wireless Personal Communications, 97, pp. 6301-6323. [DOI:10.1007/s11277-017-4839-2]
20. [20] Keshanchi B, Souri A, Navimipour N.J, 2017, "An improved genetic algorithm for task scheduling in the cloud environments using the priority queues: Formal verification, simulation, and statistical testing", Journal of Systems and Software, 124, pp. 1-21. [DOI:10.1016/j.jss.2016.07.006]
21. [21] Boveiri HR, 2017 "An incremental ant colony optimization based approach to task assignment to processors for multiprocessor scheduling", Frontiers of Information Technology & Electronic Engineering, 18, pp. 498-510. [DOI:10.1631/FITEE.1500394]
22. [22] Moon Y.J, Yu H.C, Gil J.M, Lim J.B, 2017, "A slave ants based ant colony optimization algorithm for task scheduling in cloud computing environments, Human-centric Computing and Information Sciences", 12, pp. 128-139. [DOI:10.1186/s13673-017-0109-2]
23. [23] Thanka M.R, Maheswari P.U, Edwin E.B, 2017, "An improved efficient: Artificial Bee Colony algorithm for security and QoS aware scheduling in cloud computing environment", Cluster Computing, 20, pp. 1-9. [DOI:10.1007/s10586-017-1223-7]
24. [24] Reddy GN, Kumar S.P, 2017, "Multi Objective Task Scheduling Algorithm for Cloud Computing Using Whale Optimization Technique", Smart and Innovative Trends in Next Generation Computing Technologies, pp. 286-297. [DOI:10.1007/978-981-10-8657-1_22]
25. [25] Jiang T, Zhang C, Sun QM, 2017, "Green Job Shop Scheduling Problem With Discrete Whale Optimization Algorithm", IEEE Access, 7, pp. 43153 - 43166. [DOI:10.1109/ACCESS.2019.2908200]
26. [26] Wu S.Y, Zhang P, Li F, Gu F, Pan Y.I, 2017, "A hybrid discrete particle swarm optimization-genetic algorithm for multi-task scheduling problem in service oriented manufacturing systems", Journal of Central South University, 23, pp. 421-429. [DOI:10.1007/s11771-016-3087-z]
27. [27] Abdelaziz F.B, Mir H, 2016, "An Optimization Model and Tabu Search Heuristic for Scheduling of Tasks on a Radar Sensor", IEEE Sensors Journal, 16, pp. 6694-6702. [DOI:10.1109/JSEN.2016.2587730]
28. [28] Wu S.Y, Zhang P, Li F, Gu F, Pan Y, 2016, "A hybrid discrete particle swarm optimization-genetic algorithm for multi-task scheduling problem in service oriented manufacturing systems", Journal of Central South University, 23, pp. 421-429. [DOI:10.1007/s11771-016-3087-z]
29. [29] Akbari M, Rashidi H, "A multi-objectives scheduling algorithm based on cuckoo optimization for task allocation problem at compile time in heterogeneous systems", Expert Systems with Applications, 60, pp. 234-248. [DOI:10.1016/j.eswa.2016.05.014]
30. [30] Jiang Y.S, Chen W.M, 2015, "Task scheduling for grid computing systems using a genetic algorithm", The Journal of Supercomputing, 71, pp. 1357-1377. [DOI:10.1007/s11227-014-1368-6]
31. [31] Ramezani F, Lu J, Hussain F.K, 2014, "Task-Based System Load Balancing in Cloud Computing Using Particle Swarm Optimization", International Journal of Parallel Programming, 42, pp. 739-754. [DOI:10.1007/s10766-013-0275-4]
32. [32] Bukata L, Šůcha P, Hanzálek Z, 2015, "Solving the Resource Constrained Project Scheduling Problem using the parallel Tabu Search designed for the CUDA platform", Journal of Parallel and Distributed Computing, 77, pp. 58-68. [DOI:10.1016/j.jpdc.2014.11.005]
33. [33] Moschakis I.A, Karatza H.D, 2015, "Multi-criteria scheduling of Bag-of-Tasks applications on heterogeneous interlinked clouds with simulated annealing", Journal of Systems and Software, 101, pp. 1-14. [DOI:10.1016/j.jss.2014.11.014]
34. [34] Xu Y, Li K, Hu J, Li K, 2014, "A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues", Information Sciences, 270, pp. 255-287. [DOI:10.1016/j.ins.2014.02.122]
35. [35] Samal A.K, Mall R, Tripathy C, 2014, "Fault tolerant scheduling of hard real-time tasks on multiprocessor system using a hybrid genetic algorithm", Swarm and Evolutionary Computation, 14, pp. 92-105. [DOI:10.1016/j.swevo.2013.10.002]
36. [36] Lu H, Liu J, Niu R, Zhu Z, 2014, "Fitness distance analysis for parallel genetic algorithm in the test task scheduling problem", Soft Computing, 18, pp. 2385-2396. [DOI:10.1007/s00500-013-1212-6]
37. [37] Davidović T, Šelmić M, Teodorović D, Ramljak D, 2012, "Bee colony optimization for scheduling independent tasks to identical processors", Journal of Heuristics, 18, pp. 549-569. [DOI:10.1007/s10732-012-9197-3]
38. [38] Aziza H, Krichen S, 2018, "Bi-objective decision support system for task-scheduling based on genetic algorithm in cloud computing", Computing, 100, pp. 65-91. [DOI:10.1007/s00607-017-0566-5]
39. [39] DerChou F, 2013 "Particle swarm optimization with cocktail decoding method for hybrid flow shop scheduling problems with multiprocessor tasks", International Journal of Production Economics, 141, pp. 137-145. [DOI:10.1016/j.ijpe.2012.05.015]
40. [40] Orsila H, Salminen E, Hämäläinen T, 2013, "Recommendations for using Simulated Annealing in task mapping", Design Automation for Embedded Systems, 17, pp. 53-85. [DOI:10.1007/s10617-013-9119-0]
41. [41] Kennedy James, Eberhart Russell, Swarm Intelligence (1st ed), Academic Press, San Diego, CA, 2001.
42. [42] Annicchiarico W.D, Cerolazza M, 2019, "Improved Dynamical Particle Swarm Optimization Method for Structural Dynamics", Mathematical Problems in Engineering, 37, pp. 58-69. [DOI:10.1155/2019/8250185]
43. [43] Kennedy James, Particle Swarm Optimization, Encyclopedia of Machine Learning. Springer, Boston, MA, 2011.
44. [44] Shah-Hosseini H, 2009, "The intelligent water drops algorithm: a nature-inspired swarm-based optimization algorithm," International Journal of Bio-Inspired Computation, 1, pp. 71-79. [DOI:10.1504/IJBIC.2009.022775]
45. [45] Shah-Hosseini H, 2012, "An approach to continuous optimization by the Intelligent Water Drops algorithm", Procedia Social and Behavioral Sciences, 32, pp. 224-229. [DOI:10.1016/j.sbspro.2012.01.033]
46. [46] Surjanovic S, Bingham D, 2013, "Virtual Library of Simulation Experiments: Test Functions and Datasets", Retrieved August 31, 2019, from http://www.sfu.ca/~ssurjano.
47. [47] Mirjalili S, Lewis A, 2016, "The Whale Optimization Algorithm", Advances in Engineering Software, 95, pp. 51-67. [DOI:10.1016/j.advengsoft.2016.01.008]
48. [48] Mirjalili S, 2015, "Moth-flame optimization algorithm: A novel nature-inspired heuristic paradigm", Knowledge-Based Systems, 89, pp. 228-249. [DOI:10.1016/j.knosys.2015.07.006]
49. [49] Wittkowski K.M, (1988). "Friedman-Type statistics and consistent multiple comparisons for unbalanced designs with missing data". Journal of the American Statistical Association", 83(404), pp. 1163-1170. [DOI:10.1080/01621459.1988.10478715]
Send email to the article author
| Rights and permissions | |
 |
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. |
