Abstract
Data centres are facilities with large amount of machines (i.e., servers) and hosted processes (e.g., virtual machines). Managers of data centres (e.g., operators, capital allocators, CRM) constantly try to optimise them, reassigning ‘better’ machines to processes. These managers usually see better/good placements as a combination of distinct objectives, hence why in this paper we define the data centre optimisation problem as a multi-objective machine reassignment problem. While classical solutions to address this either do not find many solutions (e.g., GRASP), do not cover well the search space (e.g., PLS), or even cannot operate properly (e.g., NSGA-II lacks a good initial population), we propose GeNePi, a novel hybrid algorithm. We show that GeNePi outperforms all the other algorithms in terms of quantity of solutions (nearly 6 times more solutions on average than the second best algorithm) and quality (hypervolume of the Pareto frontier is 106% better on average).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Li, X., Ventresque, A., Stokes, N., Thorburn, J., Murphy, J.: ivmp: an interactive vm placement algorithm for agile capital allocation. In: CLOUD, pp. 950–951 (2013)
Mills, K., Filliben, J., Dabrowski, C.: Comparing vm-placement algorithms for on-demand clouds. In: CloudCom, pp. 91–98 (2011)
Xu, J., Fortes, J.: A multi-objective approach to virtual machine management in datacenters. In: CAC, pp. 225–234 (2011)
Zitzler, E., Thiele, L.: Multiobjective optimization using evolutionary algorithms - a comparative case study. In: Eiben, A.E., Bäck, T., Schoenauer, M., Schwefel, H.-P. (eds.) PPSN 1998. LNCS, vol. 1498, pp. 292–301. Springer, Heidelberg (1998)
Angel, E., Bampis, E., Gourves, L.: A dynasearch neighborhood for the bicriteria traveling salesman problem. In: Metaheuristics for Multiobjective Optimisation, pp. 153–176 (2004)
Basseur, M.: Design of cooperative algorithms for multi-objective optimization: application to the flow-shop scheduling problem. In: 4OR, pp. 255–258 (2006)
Alsheddy, A., Tsang, E.E.: Guided pareto local search based frameworks for biobjective optimization. In: CEC (2010)
Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: Nsga-ii. In: TEVC, pp. 182–197 (2002)
Feo, T.A., Resende, M.G.: Greedy randomized adaptive search procedures. In: JGO, pp. 109–133 (1995)
Gabay, M., Zaourar, S.: A GRASP approach for the machine reassignment problem. In: EURO (2012)
Bansal, N., Caprara, A., Sviridenko, M.: Improved approximation algorithms for multidimensional bin packing problems. In: FOCS, pp. 697–708 (2006)
Batu, T., Rubinfeld, R., White, P.: Fast approximate PCPs for multidimensional bin-packing problems. In: Information and Computation, pp. 42–56 (2005)
Hermenier, F., Demassey, S., Lorca, X.: Bin repacking scheduling in virtualized datacenters. In: Lee, J. (ed.) CP 2011. LNCS, vol. 6876, pp. 27–41. Springer, Heidelberg (2011)
Mehta, D., O’Sullivan, B., Simonis, H.: Comparing solution methods for the machine reassignment problem. In: Lee, J. (ed.) CP 2011. LNCS, vol. 6876, pp. 782–797. Springer, Heidelberg (2011)
Google/roadef/euro challenge 2012: Definition of the machine reassignment problem (2012), http://challenge.roadef.org/2012/files/problem_definition_v1.pdf
Bin, E., Biran, O., Boni, O., Hadad, E., Kolodner, E.K., Moatti, Y., Lorenz, D.H.: Guaranteeing high availability goals for virtual machine placement. In: ICDCS, pp. 700–709 (2011)
Purshouse, R.C., Fleming, P.J.: On the evolutionary optimization of many conflicting objectives. In: TEVC, pp. 770–784 (2007)
Schroeder, B., Gibson, G.A.: A large-scale study of failures in high-performance computing systems. In: TDSC, pp. 337–351 (2010)
Google/roadef/euro challenge 2012, http://challenge.roadef.org/2012/en/
Voorsluys, W., Broberg, J., Venugopal, S., Buyya, R.: Cost of virtual machine live migration in clouds: A performance evaluation. In: Jaatun, M.G., Zhao, G., Rong, C. (eds.) Cloud Computing. LNCS, vol. 5931, pp. 254–265. Springer, Heidelberg (2009)
Filani, D., He, J., Gao, S., Rajappa, M., Kumar, A., Shah, P., Nagappan, R.: Comparing vm-placement algorithms for on-demand clouds. In: Dynamic Data Center Power Management: Trends, Issues, and Solutions (2008)
Datacentre energy efficiency, http://re.jrc.ec.europa.eu/energyefficiency/html/standby_initiative.htm
Xu, J., Fortes, J.A.: Multi-objective virtual machine placement in virtualized data center environments. In: GreenCom, pp. 179–188 (2010)
Lien, C.-H., Bai, Y.-W., Lin, M.-B.: Estimation by software for the power consumption of streaming-media servers. In: TIM, pp. 1859–1870 (2007)
Gandibleux, X., Martin, B., Perederieieva, O., Rosembly, S.: Sur la résolution approchée en trois étapes du sac-à-dos bi-objectif unidimensionnel en variables binaires. In: ROADEF, pp. 2–4 (2011)
Falkenauer, E.: Genetic algorithms and grouping problems (1998)
Zitzler, E., Laumanns, M., Thiele, L., Fonseca, C.M., da Fonseca, V.G.: Why quality assessment of multiobjective optimizers is difficult. In: GECCO, pp. 666–673 (2002)
Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C.M., Da Fonseca, V.G.: Performance assessment of multiobjective optimizers: An analysis and review. In: TEVC, pp. 117–132 (2003)
Fleischer, M.: The measure of pareto optima applications to multi-objective metaheuristics. In: Fonseca, C.M., Fleming, P.J., Zitzler, E., Deb, K., Thiele, L. (eds.) EMO 2003. LNCS, vol. 2632, pp. 519–533. Springer, Heidelberg (2003)
Panigrahy, R., Talwar, K., Uyeda, L., Wieder, U.: Heuristics for vector bin packing. Research. Microsoft. Com (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Saber, T., Ventresque, A., Gandibleux, X., Murphy, L. (2014). GeNePi: A Multi-Objective Machine Reassignment Algorithm for Data Centres. In: Blesa, M.J., Blum, C., Voß, S. (eds) Hybrid Metaheuristics. HM 2014. Lecture Notes in Computer Science, vol 8457. Springer, Cham. https://doi.org/10.1007/978-3-319-07644-7_9
Download citation
DOI: https://doi.org/10.1007/978-3-319-07644-7_9
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-07643-0
Online ISBN: 978-3-319-07644-7
eBook Packages: Computer ScienceComputer Science (R0)