Hybrid Task Scheduling Method for Cloud Computing by Genetic and PSO Algorithms
محورهای موضوعی : Cloud computing
Amin Kamalinia
1
,
Ali Ghaffari
2
1 - Islamic azad university, Urmia branch
2 - Azad EslamiTabriz University
کلید واژه: Cloud Computing , Task Scheduling , Genetic Algorithm , Particle Swarm Optimization Algorithm,
چکیده مقاله :
Cloud computing makes it possible for users to use different applications through the internet without having to install them. Cloud computing is considered to be a novel technology which is aimed at handling and providing online services. For enhancing efficiency in cloud computing, appropriate task scheduling techniques are needed. Due to the limitations and heterogeneity of resources, the issue of scheduling is highly complicated. Hence, it is believed that an appropriate scheduling method can have a significant impact on reducing makespans and enhancing resource efficiency. Inasmuch as task scheduling in cloud computing is regarded as an NP complete problem; traditional heuristic algorithms used in task scheduling do not have the required efficiency in this context. With regard to the shortcomings of the traditional heuristic algorithms used in job scheduling, recently, the majority of researchers have focused on hybrid meta-heuristic methods for task scheduling. With regard to this cutting edge research domain, we used HEFT (Heterogeneous Earliest Finish Time) algorithm to propose a hybrid meta-heuristic method in this paper where genetic algorithm (GA) and particle swarm optimization (PSO) algorithms were combined with each other. The results of simulation and statistical analysis of proposed scheme indicate that the proposed algorithm, when compared with three other heuristic and a memetic algorithms, has optimized the makespan required for executing tasks.
Cloud computing makes it possible for users to use different applications through the internet without having to install them. Cloud computing is considered to be a novel technology which is aimed at handling and providing online services. For enhancing efficiency in cloud computing, appropriate task scheduling techniques are needed. Due to the limitations and heterogeneity of resources, the issue of scheduling is highly complicated. Hence, it is believed that an appropriate scheduling method can have a significant impact on reducing makespans and enhancing resource efficiency. Inasmuch as task scheduling in cloud computing is regarded as an NP complete problem; traditional heuristic algorithms used in task scheduling do not have the required efficiency in this context. With regard to the shortcomings of the traditional heuristic algorithms used in job scheduling, recently, the majority of researchers have focused on hybrid meta-heuristic methods for task scheduling. With regard to this cutting edge research domain, we used HEFT (Heterogeneous Earliest Finish Time) algorithm to propose a hybrid meta-heuristic method in this paper where genetic algorithm (GA) and particle swarm optimization (PSO) algorithms were combined with each other. The results of simulation and statistical analysis of proposed scheme indicate that the proposed algorithm, when compared with three other heuristic and a memetic algorithms, has optimized the makespan required for executing tasks.
[1] A. Ghaffari, "Real-time routing algorithm for mobile ad hoc networks using reinforcement learning and heuristic algorithms," Wireless Networks, pp. 1-12, 2016.#
[2] Z. Mottaghinia and A. Ghaffari, "A Unicast Tree-Based Data Gathering Protocol for Delay Tolerant Mobile Sensor Networks," Information Systems & Telecommunication, p. 59, 2016.#
[3] A. Ghaffari, "Congestion control mechanisms in wireless sensor networks: A survey," Journal of Network and Computer Applications, vol. 52, pp. 101-115, 6// 2015.#
[4] C.-S. Chen, W.-Y. Liang, and H.-Y. Hsu, "A cloud computing platform for ERP applications," Applied Soft Computing, vol. 27, pp. 127-136, 2// 2015.#
[5] Y.-D. Lin, M.-T. Thai, C.-C. Wang, and Y.-C. Lai, "Two-tier project and job scheduling for SaaS cloud service providers," Journal of Network and Computer Applications, vol. 52, pp. 26-36, 6// 2015.#
[6] R. Masoudi and A. Ghaffari, "Software defined networks: A survey," Journal of Network and Computer Applications, vol. 67, pp. 1-25, 5// 2016.#
[7] M. Pinedo, Scheduling : theory, algorithms, and systems, 4th ed. New York: Springer, 2012.#
[8] Y. Robert and F. d. r. Vivien, Introduction to scheduling. Boca Raton: CRC Press, 2010.#
[9] F. Magoulès, J. Pan, and F. Teng, Cloud Computing : Data-Intensive Computing and Scheduling. Boca Raton: CRC Press, 2012.#
[10] Y. Li and W. Cai, "Update schedules for improving consistency in multi-server distributed virtual environments," Journal of Network and Computer Applications, vol. 41, pp. 263-273, 5// 2014.#
[11] B. Xu, C. Zhao, E. Hu, and B. Hu, "Job scheduling algorithm based on Berger model in cloud environment," Advances in Engineering Software, vol. 42, pp. 419-425, 7// 2011.#
[12] T. S. Somasundaram and K. Govindarajan, "CLOUDRB: A framework for scheduling and managing High-Performance Computing (HPC) applications in science cloud," Future Generation Computer Systems, vol. 34, pp. 47-65, 5// 2014.#
[13] S. Su, J. Li, Q. Huang, X. Huang, K. Shuang, and J. Wang, "Cost-efficient task scheduling for executing large programs in the cloud," Parallel Computing, vol. 39, pp. 177-188, 4// 2013.#
[14] B. Keshanchi and N. J. Navimipour, "Priority-Based Task Scheduling in the Cloud Systems Using a Memetic Algorithm," Journal of Circuits, Systems and Computers, vol. 25, p. 1650119, 2016.#
[15] S. Pandey, L. Wu, S. M. Guru, and R. Buyya, "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, 2010, pp. 400-407.#
[16] Y. C. Liang, A. H. L. Chen, and Y. H. Nien, "Artificial Bee Colony for workflow scheduling," in 2014 IEEE Congress on Evolutionary Computation (CEC), 2014, pp. 558-564.#
[17] L. Wang and L. Ai, "Task Scheduling Policy Based on Ant Colony Optimization in Cloud Computing Environment," in LISS 2012: Proceedings of 2nd International Conference on Logistics, Informatics and Service Science, Z. Zhang, R. Zhang, and J. Zhang, Eds., ed Berlin, Heidelberg: Springer Berlin Heidelberg, 2013, pp. 953-957.#
[18] Y. Xu, K. Li, J. Hu, and K. Li, "A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues," Information Sciences, vol. 270, pp. 255-287, 6/20/ 2014.#
[19] X. Kong, C. Lin, Y. Jiang, W. Yan, and X. Chu, "Efficient dynamic task scheduling in virtualized data centers with fuzzy prediction," Journal of Network and Computer Applications, vol. 34, pp. 1068-1077, 7// 2011.#
[20] H. Topcuoglu, S. Hariri, and W. Min-You, "Performance-effective and low-complexity task scheduling for heterogeneous computing," Parallel and Distributed Systems, IEEE Transactions on, vol. 13, pp. 260-274, 2002.#
[21] G. Giftson Samuel and C. Christober Asir Rajan, "Hybrid: Particle Swarm Optimization–Genetic Algorithm and Particle Swarm Optimization–Shuffled Frog Leaping Algorithm for long-term generator maintenance scheduling," International Journal of Electrical Power & Energy Systems, vol. 65, pp. 432-442, 2// 2015.#
[22] R. L. Haupt and S. E. Haupt, Practical genetic algorithms, 2nd ed. Hoboken, N.J.: John Wiley, 2004.#
[23] F. T. Hecker, M. Stanke, T. Becker, and B. Hitzmann, "Application of a modified GA, ACO and a random search procedure to solve the production scheduling of a case study bakery," Expert Systems with Applications, vol. 41, pp. 5882-5891, 10/1/ 2014.#
[24] S. N. Sivanandam and S. N. Deepa, Introduction to genetic algorithms. Berlin ; New York: Springer, 2007.#
[25] A. Mahor and S. Rangnekar, "Short term generation scheduling of cascaded hydro electric system using novel self adaptive inertia weight PSO," International Journal of Electrical Power & Energy Systems, vol. 34, pp. 1-9, 1// 2012.#
[26] D. Y. Sha and H.-H. Lin, "A multi-objective PSO for job-shop scheduling problems," Expert Systems with Applications, vol. 37, pp. 1065-1070, 3// 2010.#
[27] A. P. Engelbrecht, Computational intelligence : an introduction, 2nd ed. Chichester, England ; Hoboken, NJ: John Wiley & Sons, 2007.#
[28] U. Defense Acquisition and Press, Scheduling guide for program managers. Fort Belvoir, VA; Washington, DC: Defense Acquisition University Press ; For sale by the U.S. G.P.O., Supt. of Docs., 2001.#
