International Journal of Intelligent Systems and Applications (IJISA)
IJISA Vol. 6, No. 5, 8 Apr. 2014
Cover page and Table of Contents: PDF (size: 703KB)
Cloud Task Scheduling for Load Balancing based on Intelligent Strategy
Full Text (PDF, 703KB), PP.25-36
Views: 0 Downloads: 0
Author(s)
Index Terms
Cloud Computing, Task Scheduling, Make Span, Ant Colony Optimization, Load Balancing
Abstract
Cloud computing is a type of parallel and distributed system consisting of a collection of interconnected and virtual computers. With the increasing demand and benefits of cloud computing infrastructure, different computing can be performed on cloud environment. One of the fundamental issues in this environment is related to task scheduling. Cloud task scheduling is an NP-hard optimization problem, and many meta-heuristic algorithms have been proposed to solve it. A good task scheduler should adapt its scheduling strategy to the changing environment and the types of tasks. In this paper a cloud task scheduling policy based on ant colony optimization algorithm for load balancing compared with different scheduling algorithms has been proposed. Ant Colony Optimization (ACO) is random optimization search approach that will be used for allocating the incoming jobs to the virtual machines. The main contribution of our work is to balance the system load while trying to minimizing the make span of a given tasks set. The load balancing factor, related to the job finishing rate, is proposed to make the job finishing rate at different resource being similar and the ability of the load balancing will be improved. The proposed scheduling strategy was simulated using Cloudsim toolkit package. Experimental results showed that, the proposed algorithm outperformed scheduling algorithms that are based on the basic ACO or Modified Ant Colony Optimization (MACO).
Cite This Paper
Arabi E. keshk, Ashraf B. El-Sisi, Medhat A. Tawfeek, "Cloud Task Scheduling for Load Balancing based on Intelligent Strategy", International Journal of Intelligent Systems and Applications(IJISA), vol.6, no.5, pp.25-36, 2014. DOI:10.5815/ijisa.2014.05.02
Reference
[1]A. Weiss, "Computing in the Clouds" netWorker on Cloud computing: PC functions move onto the web, vol. 11, pp. 16-25, 2007.
[2]Gao Y., et al., "A multi-objective ant colony system algorithm for virtual machine placement in cloud computing," J. Comput. System Sci. vol.79 ,no. 8, pp. 1230–1242, 2013.
[3]F. Chang, J. Ren, and R. Viswanathan, "Optimal Resource Allocation in Clouds" in 2010 IEEE 3rd International Conference on Cloud Computing, pp.418-425, 2010.
[4]Qiyi, H., Tinglei, H., "An Optimistic Job Scheduling Strategy based on QoS for Cloud Computing" in 2010 IEEE International Conference on Intelligent Computing and Integrated Systems (ICISS), pp.673-675, 2010.
[5]F. Chang, J. Ren, and R. Viswanathan, "Optimal resource allocation for batch testing" in ICST, 2009 IEEE International Conference on Software Testing Veriļ¬cation and Validation, pp.91-100, 2009.
[6]Rubing Duan, Radu Prodan and Xiaorong Li, "A sequential cooperative game theoretic approach to scheduling multiple large-scale applications in grids" J. Comput. System Sci. vol.30 , pp. 27–43, 2014.
[7]M. Dorigo, C. Blum, "Ant colony optimization theory: A survey" in Theoretical Computer Science 344 (2–3) (2005), pp.243–278, 2005.
[8]M. Dorigo, M. Birattari, T. Stutzel, "Ant colony optimization", in IEEE Computational Intelligence Magazine, pp.28-39, 2006.
[9]Paul, M., Sanyal, G., "Survey and analysis of optimal scheduling strategies in cloud environment", IEEE International Conference on Information and Communication Technologies (WICT), pp. 789 – 792, 2012
[10]Jeyarani, R., Ram, R. Vasanth, Nagaveni, N., "Design and Implementation of an Efficient Two-Level Scheduler for Cloud Computing Environment", IEEE International Conference on Cloud and Grid Computing (CCGrid), PP. 585 – 586, 2010
[11]Meng Xu, Lizhen Cui, Haiyang Wang, Yanbing Bi, "A Multiple QoS Constrained Scheduling Strategy of Multiple Workflows for Cloud Computing", IEEE International Conference on Parallel and Distributed Processing with Applications, PP. 629 - 634, 2009
[12]G. L. Nemhauser and A. L. Wolsey. "Integer and Combinatorial Optimization" John Wiley & Sons, New York, 1988.
[13]C. R. Reeves, editor. "Modern Heuristic Techniques for Combinatorial Problems" Blackwell Scientific Publishing, Oxford, England, 1993.
[14]M. Dorigo, L.M. Gambardella, Ant colony system: A cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation 1 (1) (1997) 53–66.
[15]T. Stutzle,MAX-MINAnt Systemfor Quadratic Assignment Problems Technical Report AIDA-97-04, Intellectics Group, Department of Compute Science, Darmstadt University of Technology, Germany, July 1997.
[16]B. Bullnheimer, R.F. Hartl, C. Strauss, A new rank-based version of the ant system: A computational study, Central European Journal for Operations Research and Economics 7 (1) (1999) 25–38.
[17]E.D. Taillard, L.M. Gambardella, Adaptive memories for the quadratic assignment problem, Technical Report IDSIA-87-97, IDSIA, Lugano, Switzerland, 1997.
[18]M. Dorigo, V.Maniezzo, A. Colorni, The ant system: Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics, Part B 26 (1) (1996) 29–41.
[19]Abraham Silberschatz, Peter Baer Galvin, Greg Gagne, Operating System Concepts, 7th edition, JohnWiley & Sons, 2005.
[20]D. Saha, D. Menasce, S. Porto, Static and dynamic processor scheduling disciplines in heterogeneous parallel architectures, Journal of Parallel and Distributed Computing 28 (1) (1995) 1–18.
[21]Boloor, K., Chirkova, R., Salo, T., Viniotis, Y., "Heuristic-Based Request Scheduling Subject to a Percentile Response Time SLA in a Distributed Cloud". IEEE International Conference on Global Telecommunications Conference (GLOBECOM), PP.1-6 , 2010
[22]Laiping Zhao, Yizhi Ren, Yang Xiang, Sakurai, K., "Fault-tolerant scheduling with dynamic number of replicas in heterogeneous systems", IEEE International Conference on High Performance Computing and Communications (HPCC), PP. 434 – 441, 2010
[23]Chenhong Zhao, Shanshan Zhang, Qingfeng Liu, Jian Xie, Jicheng Hu, "Independent Tasks Scheduling Based on Genetic Algorithm in Cloud Computing", IEEE International Conference on Wireless Communications, Networking and Mobile Computing, PP. 1 – 4, 2009
[24]Kai Zhu, Huaguang Song, Lijing Liu, Jinzhu Gao, Guojian Cheng, "Hybrid Genetic Algorithm for Cloud Computing Applications", IEEE International Conference on Asia-Pacific Services Computing Conference (APSCC), PP. 182 – 187, 2011
[25]Kessaci, Y., Melab, N., Talbi, E.-G., "A pareto-based GA for scheduling HPC applications on distributed cloud infrastructures", IEEE International Conference on High Performance Computing and Simulation (HPCS), PP. 456 – 462,2011
[26]Ching-Hsien Hsu, Tai-Lung Chen, "Adaptive Scheduling Based on Quality of Service in Heterogeneous Environments", IEEE International Conference on Multimedia and Ubiquitous Engineering (MUE), PP. 1 - 6, 2010
[27]Manpreet Singh, "GRAAA: Grid Resource Allocation Based on Ant Algorithm" in 2010 Academy Publisher DOI: 10.4304/jait.1.3.133-135, 2010.
[28]Ku Ruhana Ku-Mahamud, Husna Jamal Abdul Nasir, "Ant Colony Algorithm for Job Scheduling in Grid Computing" in ams, 2010 Fourth Asia International Conference on Mathematical/Analytical Modelling and Computer Simulation, pp.40-45, 2010.
[29]Lorpunmanee, S., Sap, M.N, Abdul Hanan Abdullah, A.H., "An Ant Colony Optimization for Dynamic Job Scheduling in Grid Environment" in Proceedings of World Academy of Science, English and Technology Volume 23 august 2007, ISSN 1307-6884, 2007.
[30]Buyya, R., Ranjan, R., Calheiros, R.N., "Modeling and Simulation of Scalable Cloud Computing Environments and the CloudSim Toolkit: Challenges and Opportunities" in Proceedings of the 7th High Performance Computing and Simulation (HPCS 2009) Conference, Leipzig, Germany, 2009 .
[31]Ghalem, B., Fatima Zohra, T., and Wieme, Z. "Approaches to Improve the Resources Management in the Simulator CloudSim" in ICICA 2010, LNCS 6377, pp. 189–196, 2010.
[32]Medhat A. Tawfeek, Ashraf El-Sisi, Arabi E. keshk and Fawzy A. Torkey, " Cloud Task Scheduling Based on Ant Colony Optimization" in International Conference on Computer Engineering & Systems ICCES, 2013.
[33]Medhat A. Tawfeek, Ashraf El-Sisi, Arabi E. keshk and Fawzy A. Torkey, " An Ant Algorithm for Cloud Task Scheduling" in International Workshop on Cloud Computing and Information Security CCIS, 2013.
[34]Eric Bonabeau, Marco Dorigo, Guy Theraulaz, "Swarm intelligence: from natural to artificial intelligence",ISBN 0-19-513158-4, Published by Oxford University Press, Inc.198 Madison Avenue, New York,1999.
[35]V. Maniezzo, Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem, INFORMS J. Comput. 11 (4) pp. 358–369, 1999.