Grouping genetic algorithm for solving the serverconsolidation problem with conflicts

ABSTRACT

The advent of virtualization technologies encourages

organizations to undertake server consolidation exercises for improving the overall server utilization and for minimizing the capacity redundancy within data-centers. Identifying complimentary workload patterns is a key to the success of server consolidation exercises and for enabling multi-tenancy within data-centers. Existing works either do not consider incompatibility constraints or performs poorly on the disjointed conflict graphs. The algorithm proposed in the current work overcomes the limitations posed by the existing solutions. The current work models the server consolidation problem as a vector packing problem with conflicts (VPC) and tries to minimize the number of servers used for hosting applications within datacenters and maximizes the packing efficiency of the servers utilized. This paper solves the problem using techniques inspired from grouping genetic algorithm (GGA) - a variant of the traditional Genetic Algorithm (GA). The algorithm is tested over varying scenarios which show encouraging results.

REFERENCES

• 1: Phelps, J, "Server Consolidation can offer a range of benefits", White Paper, Gartner Inc, (2004).
• 2: Ajiro, Y., Tanaka, A., "A Combinatorial optimization algorithm for server consolidation", In: Proceedings of the 21st annual conference of the Japanese Society for Artificial Intelligence (2007)
• 3: Zhang, A., Safari, F., Beyer, D., "Applying Bin-packing algorithms to server consolidation", In: Proceedings of the Informs annual meeting in San Francisco (2005)
• 4: Rohit Gupta , Sumit Kumar Bose , Srikanth Sundarrajan , Manogna Chebiyam , Anirban Chakrabarti, A Two Stage Heuristic Algorithm for Solving the Server Consolidation Problem with Item-Item and Bin-Item Incompatibility Constraints, Proceedings of the 2008 IEEE International Conference on Services Computing, p.39-46, July 07-11, 2008 [doi>10.1109/SCC.2008.39]
• 5: Chengbin Chu , Rémy La, Variable-Sized Bin Packing: Tight Absolute Worst-Case Performance Ratios for Four Approximation Algorithms, SIAM Journal on Computing, v.30 n.6, p.2069-2083, 2001 [doi>10.1137/S009753979834669X]
• 6: Kang, J., Park, S., "Algorithms for the variable sized bin packing problem", European Journal of Operational Research. 147, 365--372 (2003)
• 7: Michel Gendreau , Gilbert Laporte , Frédéric Semet, Heuristics and lower bounds for the bin packing problem with conflicts, Computers and Operations Research, v.31 n.3, p.347-358, March 2004 [doi>10.1016/S0305-0548(02)00195-8]
• 8: Epstein, L., Levin, A., "On bin packing with conflicts", math.haifa.ac.il/lea/bpc.pdf
• 9: Jansen, K., "An approximations scheme for bin-packing with conflicts", Journal of combinatorial optimization. 3, 363--377 (1999)
• 10: Emanuel Falkenauer, Genetic Algorithms and Grouping Problems, John Wiley & Sons, Inc., New York, NY, 1998
• 11: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 12: Hans-Paul Schwefel , Günter Rudolph, Contemporary Evolution Strategies, Proceedings of the Third European Conference on Advances in Artificial Life, p.893-907, June 04-06, 1995
• 13: John J. Grefenstette , Rajeev Gopal , Brian J. Rosmaita , Dirk Van Gucht, Genetic Algorithms for the Traveling Salesman Problem, Proceedings of the 1st International Conference on Genetic Algorithms, p.160-168, July 01, 1985
• 14: Ravindra K. Ahuja , James B. Orlin , Ashish Tiwari, A greedy genetic algorithm for the quadratic assignment problem, Computers and Operations Research, v.27 n.10, p.917-934, Sept. 2000 [doi>10.1016/S0305-0548(99)00067-2]
• 15: Runwei Cheng , Mitsuo Gen , Yasuhiro Tsujimura, A tutorial survey of job-shop scheduling problems using genetic algorithms, part II: hybrid genetic search strategies, Computers and Industrial Engineering, v.36 n.2, p.343-364, April 1999 [doi>10.1016/S0360-8352(99)00136-9]
• 16: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 17: Falkenauer, E., "A hybrid grouping genetic algorithm for bin packing", Journal of Heuristics. 2, 5--30 (2004).

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

General Terms:
Algorithms, Management

Keywords:
enterprise grid, grouping genetic algorithm, incompatibility constraints, vector packing problem with conflicts (vpc), virtualization