Cloud Computing Resource Planning Based on Imperialist Competitive Algorithm

Armita ABARGHOEI, Ebrahim MAHDIPOUR, Majid ASKARZADEH
1.664 526

Abstract


Abstract

Resource allocation in cloud computing and the scheduling of each user works on existing virtual machines is an NP-Complete problem, in which many algorithms are provided  for solving the problem so far. But none of these algorithms are able to meet the requirements related to speed and accuracy in cloud computing environments. In this paper, a combination of imperialist competitive and local search optimization algorithms is proposed to solve this problem. The algorithm attempts to improve the possible responses by creating an initial empire, through applying imperialist competitive algorithm. To avoid premature convergence, imperialist competitive algorithm is combined with a local search algorithm. The hybrid proposed algorithm used a convergence diagnosis mechanism based on semblance coefficient, and in times of premature convergence in imperialist competitive algorithm, local search algorithm runs. Quality and efficiency of the proposed algorithm are compared with round-robin, ant colony and genetic algorithms. The results show that the proposed algorithm in terms of time and the responses' quality is faster than the ant colony optimization and genetic algorithms.


Keywords


resource allocation, cloud computing, imperialist competitive algorithm, local search, NP-Complete

Full Text:

PDF


References


K. R. Baker, D. Trietsch, Principles of Sequencing and Scheduling, Wiley, 2000.

M. R. Garey, D. S., Johnson, R., Sethi, The complexity of flowshop and jobshop scheduling., Mathematics of operations research, Vol.1, 1976.

Yu, L. Wang, Genetic Algorithm Combined with Simulation for Job Shop Scheduling Problem in Mechanical Engineering, Advances in Mechanical and Electronic Engineering, Vol. 176, pp. 139-144, 2012.

L. Zhu, Q. Li, L. He, Study on cloud computing resource scheduling strategy based on the ant colony optimization algorithm, International Journal of Computer Science Issues, Vol. 9 (5), pp. 54-58, 2012.

W. N. Chen, and J. Zhang, An ant colony optimization approach to a grid workflow scheduling problem with various QoS requirements, IEEE Transactions on Systems, Man, and Cybernetics, Vol. 39 (1), pp. 29-43.

Javier, C., Fatos, X., Ajith, A.: Genetic Algorithm Based Schedulers For Gird. IEEE, International Journal of innovative Computing, Information and Control 3 (December 2007).

M. Dorigo, V. Maniezzo, and A. Colorni, Ant system: optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics, Vol. 26 (1), pp. 29-41, 1996.

E., Eiben, J. E.,Smith, Introduction to Evolutionary Computing, Springer, 2007.

E. Atashpaz-Gargari, C. Lucas, Imperialist competitive algorithm: An algorithm for optimization inspired by imperialistic competition, Evolutionary Computation, 2007. CEC 2007. IEEE Congress on, Singapore, pp. 4661-4667, 2007.

Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Program, Spring- Verlag, 1994.

Y.H. Chang, Adopting co-evolution and constraint-satisfaction concept on genetic algorithms to solve supply chain network design problems, Expert Systems with Applications, vol. 37, pp. 6919–6930, 2010.

J., Beasley, OR-Library: Distributing test problems by electronic mail, Journal of the Operational Research Society, Vol. 41, pp. 1069–1072, 1990.

J., Muth, G., Thompson, Industrial scheduling, Prentice-Hall, 1963.

S., Lawrence, Resource constrained project scheduling: An experimental investigation of heuristic scheduling techniques (Supplement). Pittsburgh, PA: Carnegie-Mellon University, 1984.

R. H., Storer, S. D., Wu, R. Vaccari, New search spaces for sequencing problems with application to job shop scheduling, Management Science, Vol. 39, pp. 1495–1509, 1992.