Bin Packing with Linear Usage Costs
作者： Hadrien Cambazard , Helmut Simonis , Barry O'Sullivan , Deepak Mehta
DOI:
关键词: Constraint (information theory) 、 Virtual machine 、 Energy consumption 、 Bin packing problem 、 Mathematical optimization 、 Mathematics 、 Context (language use) 、 Service quality 、 Linear programming 、 Server
摘要: Bin packing is a well studied problem involved in many applications. The classical bin about minimising the number of bins and ignores how are utilised. We focus this paper, on variant that at heart efficient management data centres. In context, servers can be viewed as virtual machines items. data-centre involves energy costs while ensuring service quality. assignment these utilised has huge impact consumption. where linear associated to use model study lower bounds based Linear Programming extend global constraint with cost information.
arxiv.org参考文章(15)
Domenico Salvagnin, Orbital Shrinking: A New Tool for Hybrid MIP/CP Methods Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. pp. 204- 215 ,(2013) , 10.1007/978-3-642-38171-3_14
Hadrien Cambazard, Deepak Mehta, Barry O’Sullivan, Helmut Simonis, Bin Packing with Linear Usage Costs --- An Application to Energy Management in Data Centres principles and practice of constraint programming. pp. 47- 62 ,(2013) , 10.1007/978-3-642-40627-0_7
Michael A. Trick, A Dynamic Programming Approach for Consistency and Propagation for Knapsack Constraints Annals of Operations Research. ,vol. 118, pp. 73- 84 ,(2003) , 10.1023/A:1021801522545
Aman Kansal, Feng Zhao, Shekhar Srikantaiah, Energy aware consolidation for cloud computing international conference on cluster computing. pp. 10- 10 ,(2008)
J.M. Valério de Carvalho, Exact solution of bin‐packing problems using column generation and branch‐and‐bound Annals of Operations Research. ,vol. 86, pp. 629- 659 ,(1999) , 10.1023/A:1018952112615
Leah Epstein, Asaf Levin, Bin packing with general cost structures Mathematical Programming. ,vol. 132, pp. 355- 391 ,(2012) , 10.1007/S10107-010-0403-5
Michele Monaci, Algorithms for packing and scheduling problems A Quarterly Journal of Operations Research. ,vol. 1, pp. 85- 87 ,(2003) , 10.1007/S10288-002-0011-1
Mohamed Haouari, Mehdi Serairi, Relaxations and exact solution of the variable sized bin packing problem Computational Optimization and Applications. ,vol. 48, pp. 345- 368 ,(2011) , 10.1007/S10589-009-9276-Z
Chung-Lun Li, Zhi-Long Chen, Bin‐packing problem with concave costs of bin utilization Naval Research Logistics. ,vol. 53, pp. 298- 308 ,(2006) , 10.1002/NAV.20142
Mauro Maria Baldi, Teodor Gabriel Crainic, Guido Perboli, Roberto Tadei, The Generalized Bin Packing Problem Transportation Research Part E-logistics and Transportation Review. ,vol. 48, pp. 1205- 1220 ,(2012) , 10.1016/J.TRE.2012.06.005