MODE: A Multi-Objective Strategy for Dynamic Task Scheduling through Elastic Cloud Resources

Majlesi Journal of Electrical Engineering

مقاله 17، دوره 14، شماره 2، شهریور 2020، صفحه 127-141   

نوع مقاله: Review Article

نویسندگان

Mina Yazdanbakhsh¹؛ Reihaneh Khorsand Motlagh Isfahani^{* 1}؛ Mohammadreza Ramezanpour²

¹Department of Computer Engineering, Dolatabad Branch, Islamic Azad University, Isfahan, Iran.

²Department of Computer Engineering, Mobarakeh Branch, Islamic Azad University, Isfahan, Iran.

چکیده

Cloud computing is introduced as a high-performance computing environment that manages a variety of virtualized resources. One of the major aspects of cloud computing is its dynamic scheduling of great number of task requests that are submitted by users. Cloud data centers in addition to implementing these tasks, should meet the conflicting multiple requirements of different users. Minimizing makespan and deadline violation on a great number of tasks are difficult while costs are reduced. Therefore, in this paper, a multi-objective strategy for dynamic task scheduling through elastic cloud resources (MODE) is proposed, where an algorithm is proposed to construct individual non-dominated sets of new received tasks. These non-dominated sets are sorted in different levels through a new crowding distance of the individuals. In addition, an elastic resource provisioning based on the maximum available VMs’ load is proposed to provide resources in a dynamic manner. The total cost, makespan, and the deadline violations are reduced by 85.84%, 58.03%, and 47.77%, respectively, and the utilization of virtual machines is increased up to 53.2% through this strategy when compared to its counterparts.

کلیدواژه‌ها

cloud computing؛ Dynamic Task Scheduling؛ Multi-Objective Scheduling؛ Elasticity؛ Quality of Service

مراجع

[1] Lin W, Liang C, Wang JZ, Buyya R. “Bandwidth‐aware divisible task scheduling for cloud computing”. Software: Practice and Experience. Vol. 44, No. 2, pp. 63-74, 2014.

[2] Khorsand R, Ghobaei‐Arani M, Ramezanpour M. “FAHP approach for autonomic resource provisioning of multitier applications in cloud computing environments”. Software: Practice and Experience. Vol. 48, No. 12, pp. 2147-73, 2018.

[3] Ramezani F, Lu J, Taheri J, Hussain FK. “Evolutionary algorithm-based multi-objective task scheduling optimization model in cloud environments.” World Wide Web. Vol. 18, No. 6, pp. 1737-57, 2015.

[4] Zhou Z, Li F, Zhu H, Xie H, Abawajy JH, Chowdhury MU. “An improved genetic algorithm using greedy strategy toward task scheduling optimization in cloud environments.” Neural Computing and Applications. Vol. 8, pp. 1-1, 2019.

[5] Ghobaei-Arani M, Khorsand R, Ramezanpour M. “An autonomous resource provisioning framework for massively multiplayer online games in cloud environment.” Journal of Network and Computer Applications. 2019 Jun 7.

[6] Zhan ZH, Liu XF, Gong YJ, Zhang J, Chung HS, Li Y. “Cloud computing resource scheduling and a survey of its evolutionary approaches.” ACM Computing Surveys (CSUR). Vol. 47, No. 4, pp. 63, 2015.

[7] Pantuza Júnior G. “A multi-objective approach to the scheduling problem with workers allocation.” Gestão & Produção. Vol. 23, No. 1, pp. 32-45, 2016.

[8] de Campos CP, Benavoli A. “Joint analysis of multiple algorithms and performance measures.” New Generation Computing. Vol. 35, No. 1, pp. 69-86, 2017.

[9] Kamesh SP, Priya S. “Security enhancement of authenticated RFID generation.” Int. J. Appl. Eng. Res. Vol. 9, No. 22, pp. 5968-74, 2014.

[10] Srichandan S, Kumar TA, Bibhudatta S. “Task scheduling for cloud computing using multi-objective hybrid bacteria foraging algorithm.” Future Computing and Informatics Journal. Vol. 3, No. 2, pp. 210-30, 2018.

[11] Khorsand R, Safi-Esfahani F, Nematbakhsh N, Mohsenzade M. “Taxonomy of workflow partitioning problems and methods in distributed environments.” Journal of Systems and Software. Vol. 132, pp. 253-71, 2017.

[12] Torabi S, Safi-Esfahani F. “A dynamic task scheduling framework based on chicken swarm and improved raven roosting optimization methods in cloud computing.” The Journal of Supercomputing. Vol. 74, No. 6, pp. 2581-626, 2018.

[13] Tang L, Pan JS, Hu Y, Ren P, Tian Y, Zhao H. “A Novel Load Balance Algorithm for Cloud Computing.” In International Conference on Genetic and Evolutionary Computing, pp. 21-30, Springer, Cham, 2015.

[14] Babu KR, Samuel P. “Enhanced bee colony algorithm for efficient load balancing and scheduling in cloud.” In Innovations in bio-inspired computing and applications, pp. 67-78, 2016.

[15] Patel G, Mehta R, Bhoi U. “Enhanced load balanced min-min algorithm for static meta task scheduling in cloud computing”. Procedia Computer Science. Vol. 57, pp. 545-53, 2015.

[16] Ali HG, Saroit IA, Kotb AM. “Grouped tasks scheduling algorithm based on QoS in cloud computing network.” Egyptian informatics journal. Vol. 18, No. 1, pp. 11-9, 2017.

[17] Lakra AV, Yadav DK. “Multi-objective tasks scheduling algorithm for cloud computing throughput optimization.” Procedia Computer Science. Vol. 48, pp. 107-13, 2015.

[18] Aslanpour MS, Ghobaei-Arani M, Toosi AN. “Auto-scaling web applications in clouds: a cost-aware approach”. Journal of Network and Computer Applications. Vol. 95, pp. 26-41, 2017.

[19] Gabi D, Ismail AS, Zainal A, Zakaria Z, Al-Khasawneh A. “Hybrid cat swarm optimization and simulated annealing for dynamic task scheduling on cloud computing environment.” Journal of ICT. Vol. 17, No. 3, pp. 435-67, 2018.

[20] Hu B, Sun X, Li Y, Sun H. “An improved adaptive genetic algorithm in cloud computing.” In2012 13th International Conference on Parallel and Distributed Computing, Applications and Technologies 2012 Dec 14 (pp. 294-297). IEEE.

[21] Ghanbari S, Othman M. “A priority based job scheduling algorithm in cloud computing.” Procedia Engineering. Vol. 50, No. 0, pp. 778-85, 2012.

[22] Bhoi U, Ramanuj PN. “Enhanced max-min task scheduling algorithm in cloud computing”. International Journal of Application or Innovation in Engineering and Management (IJAIEM). Vol. 2, No. 4, pp. 259-64, 2013.

[23] Kaleeswaran A, Ramasamy V, Vivekanandan P. “Host Scheduling Algorithm U sing Genetic Algorithm” In Cloud Computing Environment. International Journal of Advances in Engineering & Technology. 2013 Jan.

[24] Panda SK, Gupta I, Jana PK. “Task scheduling algorithms for multi-cloud systems: allocation-aware approach.” Information Systems Frontiers. Vol. 21, No. 2, pp. 241-59, 2019.

[25] Islam S, Lee K, Fekete A, Liu A. “How a consumer can measure elasticity for cloud platforms.” In Proceedings of the 3rd ACM/SPEC International Conference on Performance Engineering 2012 Apr 22 (pp. 85-96). ACM.

[26] Shawky DM, Ali AF. “Defining a measure of cloud computing elasticity.” In2012 1st International conference on systems and computer science (ICSCS) 2012 Aug 29 (pp. 1-5). IEEE.

[27] Beltran M. BECloud: “A new approach to analyse elasticity enablers of cloud services.” Future Generation Computer Systems. Vol. 64, pp. 39-49, 2016.

[28] Ghobaei-Arani M, Jabbehdari S, Pourmina MA. “An autonomic approach for resource provisioning of cloud services.” Cluster Computing. Vol. 19, No. 3, pp. 1017-36, 2016.

[29] Bansal N, Maurya A, Kumar T, Singh M, Bansal S. “Cost performance of QoS Driven task scheduling in cloud computing.” Procedia Computer Science. Vol. 57, pp. 126-30, 2015.

[30] Banerjee S, Adhikari M, Kar S, Biswas U. “Development and analysis of a new cloudlet allocation strategy for QoS improvement in cloud.” Arabian Journal for Science and Engineering. Vol. 40, No. 5, pp. 1409-25, 2015.

[31] Gawali MB, Shinde SK. “Task scheduling and resource allocation in cloud computing using a heuristic approach.” Journal of Cloud Computing. Vol. 7, No. 1, pp. 4, 2018.

[32] Zhang L, Zhang Y, Jamshidi P, Xu L, Pahl C. “Service workload patterns for Qos-driven cloud resource management.” Journal of Cloud Computing. Vol. 4, No. 1, pp. 23, 2015.

[33] Sun Y, Lin F, Xu H. “Multi-objective optimization of resource scheduling in Fog computing using an improved NSGA-II.” Wireless Personal Communications. Vol. 102, No. 2, pp. 1369-85, 2018.

[34] Bikas MA, Alourani A, Grechanik M. “How elasticity property plays an important role in the cloud: a survey.” In Advances in Computers, Elsevier, Vol. 103, pp. 1-30, 2016.

[35] Calheiros RN, Ranjan R, Beloglazov A, De Rose CA, Buyya R. “CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms.” Software: Practice and experience. Vol. 41(1), pp. 23-50, 2011.

[36] Kamalinasab S, Safi-Esfahani F, Shahbazi M. “CRFF. GP: cloud runtime formulation framework based on genetic programming.” The Journal of Supercomputing. pp. 1-35, 2019.

[37] Vecchiola C, Chu X, Mattess M, Buyya R. “Aneka—integration of private and public clouds.” Cloud Computing Principles and Paradigms. Hoboken, NJ, USA: Wiley. pp. 251-74, 2011.

[38] Wu L, Garg SK, Versteeg S, Buyya R. “SLA-based resource provisioning for hosted software-as-a-service applications in cloud computing environments.” IEEE Transactions on services computing. Vol. 7, No. 3, pp. 465-85, 2013.

[39] Khorsand R, Safi-Esfahani F, Nematbakhsh N, Mohsenzade M. “ATSDS: adaptive two-stage deadline-constrained workflow scheduling considering run-time circumstances in cloud computing environments.” The Journal of Supercomputing. Vol. 73, No. 6, pp. 2430-55, 2017.

[40] Ma L, Lu Y, Zhang F, Sun S. “Dynamic task scheduling in cloud computing based on greedy strategy.” In International Conference on Trustworthy Computing and Services, Springer, Berlin, Heidelberg, pp. 156-162, 2012.

[41] Safari M, Khorsand R. “PL-DVFS: combining Power-aware List-based scheduling algorithm with DVFS technique for real-time tasks in Cloud Computing.” The Journal of Supercomputing. Vol. 74, No. 10, pp. 5578-600, 2018.

[42] Safari M, Khorsand R. “Energy-aware scheduling algorithm for time-constrained workflow tasks in DVFS-enabled cloud environment.” Simulation Modelling Practice and Theory. Vol. 87, pp. 311-26, 2018.

[43] Wang G, Yu HC. “Task scheduling algorithm based on improved Min-Min algorithm in cloud computing environment.” InApplied Mechanics and Materials, Trans Tech Publications, Vol. 303, pp. 2429-2432, 2013.

[44] Salot P. “A survey of various scheduling algorithm in cloud computing environment.” International Journal of Research in Engineering and Technology. Vol. 2, No. 2, pp. 131-5, 2013.

[45] Komarasamy D, Muthuswamy V. “ScHeduling of jobs and Adaptive Resource Provisioning (SHARP) approach in cloud computing.” Cluster Computing. Vol. 21, No. 1, pp. 163-76, 2018.

[46] Hemasian-Etefagh F, Safi-Esfahani F. “Dynamic scheduling applying new population grouping of whales meta-heuristic in cloud computing.” The Journal of Supercomputing. pp. 1-65, 2019.