Abstract

Cloud computing is the growth of distributed computing, parallel computing, utility computing and grid computing, or defined as the commercial implementation of these computer science theories. One of the fundamental issues in cloud environment is the task scheduling which plays the key role of efficiency of the whole cloud computing facilities. Scheduling maps the user’s tasks to resources to be executed efficiently in order to benefit both the service providers and customers. Since the cloud task scheduling is an NP-hard optimization problem, many meta -heuristic algorithms have been proposed to solve it. In this paper a policy based on particle swarm optimization compared with genetic algorithm and FCFS, has been introduced. PSO is a population-based search algorithm based on the simulation of the social behavior of birds within the flock. The main goal in this research is minimizing the makespan and flowtime of a given tasks set. Proposed policy and two other algorithms have been simulated using Cloudsim toolkit package. The results showed that PSO performed better than genetic and FCFS algorithms.

Keywords: Cloud computing, task scheduling, particle swarm optimization, makespan.


  Download Full Text

References

[1] Mell, P., Grance, T., 2011. “The NIST Definition of Cloud Computing-Recommendations of the National Institute of Standards and Technology”. NIST Special Publication, 800-145, pp. 1–3.

[2] Paul, M., Sanyal, G., 2012. “Survey and analysis of optimal scheduling strategies in cloud environment”. ”. Information and Communication Technologies (WICT), Dec, pp. 789 – 792.

[3] Jeyarani, R., Ram, R., Versants, Nagaveni, N., 2010. “Design and Implementation of an Efficient Two Level Scheduler for Cloud Computing Environment”, Advances in Recent Technologies in Communication and Computing, Oct. pp. 884 – 886.

[4] Qi-yi, H., Ting-lei, H., 2010. “An optimistic job scheduling strategy based on QoS for Cloud Computing”. Intelligent Computing and Integrated Systems (ICISS), Oct, pp. 673 - 675

[5] Lee, K., Fu, M., Kuo, Y., 2011. “A hierarchical scheduling strategy for the composition services architecture based on cloud computing”. Next Generation Information Technology (ICNIT), Oct, pp. 163 – 169.

[6] Leey, G., Chunz, B., Randy H., 2011. “Heterogeneity-Aware Resource Allocation and Scheduling in the Cloud”. University of California.

[7] Wang, Sh., Yan, K., Wang, Sh., 2011. “Ching-Wei Chen, "A Three-Phases Scheduling in a Hierarchical Cloud Computing Network”. IEEE.

[8] Peixoto, M.L.M., Santana, M.J., Estrella, J.C., Tavares, T.C., Kuehne, B.T., Santana, R.H.C., 2010. “A Metascheduler architecture to provide QoS on the cloud computing”. IEEE.

[9] Kirkpatrick, S., Gelatt Jr, C.D., Vecchi, M.P., 1983. “Optimization by Simulated Annealing”. Science, vol. 220, no. 4598, pp. 671-680.

[10] Holland, J.H., 1975. “Adaptation in Natural and Artificial Systems”. Univ. of Michigan Press.

[11] Bonabeau, E., Dorigo, M., Theraulaz, G., 2000. “Inspiration for Optimization from Social Insect Behavior”. Nature, vol. 406, pp. 39-42.

[12] Glover, F., Laguna, M., 1997. Tabu Search. Kluwer Academic Publishers.

[13] Dueck, G., Scheuer, T., 1990. “Threshold Accepting: A General Purpose Optimization Algorithm Appearing Superior to Simulated Annealing”. J. Computational Physics, vol. 90, pp. 161-175.

[14] Kennedy, J., Eberhart, R.C., 1995. “Particle swarm optimization”. Proc, IEEE Conf. Neural Netw., vol. IV, IEEE, Piscataway, NJ, pp. 1942-1948.

[15] In proceedings, Kennedy, J., berhart, R., “Particle swarm optimization”. Proceedings of ICNN’95 - International Conference on Neural Networks, vol. 4, pp. 1942–1948.

[16] Pierobom, J. L., Delgado, M. R., Kaestner C. A., 2011. “Particle swarm optimization for task assignment problem”. 10th Brazilian Congress on Computational Intelligence (CBIC2011), vol. 10, pp. 1–8.

[17] Zhang, L., Chen, Y., Sun, R. 2008. “A task scheduling algorithm based on PSO for grid computing”. International Journal of Computational Intelligence Research, 1(4), pp. 37–43.

[18] Izakian, H., Ladani, B. T., Zamanifar, K., Abraham, A., 2009. “A novel particle swarm optimization approach for grid job scheduling. Information Systems, Technology and Management - Communications in Computer and Information Science”. vol. 31, pp. 100–109.