An energy-aware bi-level optimization model for multi-job scheduling problems under cloud computing
Tóm tắt
Recently, how to reduce huge energy consumption of data centers has caught wide attention in cloud computing. One effective way is to improve the energy efficiency of servers. To achieve this goal, we propose a new energy-aware multi-job scheduling model based on MapReduce in this paper. In the proposed model, first, the variation of energy consumption with the performance of servers is taken into account; second, since network bandwidth is a relatively limited resource in cloud computing, 100 % data locality is guaranteed; last but not least, considering that task-scheduling strategies depend directly on data placement policies, we formulate the problem as an integer bi-level programming model. It is worth noticing that there are usually tens of thousands of tasks to be scheduled in the cloud, so this is a large-scale optimization problem. In order to solve it efficiently, a local search operator is specifically designed, based on which, a bi-level genetic algorithm is proposed in this paper. Finally, numerical experiments indicate the effectiveness of the proposed model and algorithm.
Tài liệu tham khảo
Abts D, Marty MR, Wells PM, Klausler P, Liu H (2010) Energy proportional datacenter networks. in: Proceedings—International Symposium on Computer Architecture, pp 338–347
Bard JF (1991) Some properties of the bilevel programming problem. J Optim Theory Appl 68(2):371–378
Barroso LA, Holzle U (2007) The case for energy-proportional computing. Computer 40(12):33–7
Candler W, Norton RD (1977) Multi-level programming. World Bank, Washington, D.C.
Dean J, Ghemawat S (2008) Mapreduce: simplified data processing on large clusters. Commun ACM 51(1):107–113
Dempe S (2002) Foundations of bilevel programming. Springer, Dordrecht
Dempe S, Franke S (2013) Bilevel programming: stationarity and stability. Pac J Optim 9(2):183–199
Dempe S, Zemkoho AB (2013) The bilevel programming problem: reformulations, constraint qualifications and optimality conditions. Math Program 138(1–2):447–473
Ganesh L, Weatherspoon H, Marian T, Birman K (2013) Integrated approach to data center power management. IEEE Trans Comput 62(6):1086–1096
Garcia-Sanchez P, Gonzalez J, Castillo PA, Arenas MG, Merelo-Guervos JJ (2013) Service oriented evolutionary algorithms. Soft Comput 17(6):1059–1075
Hamilton J (2009) Cooperative expendable micro-slice servers (cems): low cost, low power servers for internet-scale services. CIDR 200–4th Biennal Conference on Innovative Data Systems Research
Jeroslow RG (1985) The polynomial hierarchy and a simple model for competitive analysis. Math Program 32(2):146–164
Li J, Song Y (2013) Community detection in complex networks using extended compact genetic algorithm. Soft Comput 17(6):925–937
Liu L, Masfary O, Antonopoulos N (2012) Energy performance assessment of virtualization technologies using small environmental monitoring sensors. Sensors 12(5):6610–6628
Liu Z, Wierman A, Chen Y, Razon B, Chen N (2013) Data center demand response: avoiding the coincident peak via workload shifting and local generation. In: Proceedings of the ACM SIGMETRICS/international conference on Measurement and modeling of computer systems, ACM, pp 341–342
Miller, R. (2009). Googles chiller-less data center. Data Center Knowledge, http://www.datacenterknowledge.com/archives/2009/07/15
Nunez A, Merayo MG, Hierons RM, Nunez M (2013) Using genetic algorithms to generate test sequences for complex timed systems. Soft Comput 17(2):301–315
Power EN (2009) Energy logic: reducing data center energy consumption by creating savings that cascade across systems. White paper, Emerson Electric Co
Ren Y, Wu Y (2013) An efficient algorithm for high-dimensional function optimization. Soft Comput 17(6):995–1004
Srikantaiah S, Kansal A, Zhao F (2008) Energy aware consolidation for cloud computing. In: Proceedings of the 2008 conference on Power aware computing and systems, vol 10, USENIX Association
(1952) The theory of the market economy. William Hodge, Edinburgh
Wang X, Wang Y, Zhu H, (2012a) Energy-efficient multi-job scheduling model for cloud computing and its genetic algorithm. Mathematical Problems in Engineering
Wang X, Wang Y, Zhu H (2012b) Energy-efficient task scheduling model based on mapreduce for cloud computing using genetic algorithm. J Comput (Finland) 7(12):2962–2970
Wang Y, Jiao Y-C, Li H (2005) An evolutionary algorithm for solving nonlinear bilevel programming based on a new constraint-handling scheme. IEEE Trans Syst Man Cybern Part C 35(2):221–232
(2012) Hadoop: the definitive guide. OReilly, Sebastopol
Xiao Z, Song W, Chen Q (2013) Dynamic resource allocation using virtual machines for cloud computing environment. IEEE Trans Parallel Distrib Syst 24(6):1107–1117
Young Choon L, Zomaya AY (2012) Energy efficient utilization of resources in cloud computing systems. J Supercomput 60(2):268–280