BELAID, Ikbel; EYRAUD-DUBOIS, Lionel

Métadonnées

Licence d’utilisation du document

BELAID, Ikbel
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]

EYRAUD-DUBOIS, Lionel
Reformulations based algorithms for Combinatorial Optimization [Realopt]

Langue

Communication dans un congrès

Ce document a été publié dans

Advanced Research in Computing and Software Science, Lecture Notes in Computer Science, Advanced Research in Computing and Software Science, Lecture Notes in Computer Science, International Workshop on Algorithmic Aspects of Cloud Computing, 2015-09-14, Patras.

Springer

Résumé en anglais

In the context of service hosting in large-scale datacenters, we consider the problem faced by a provider for allocating services to machines. An analysis of a public Google trace corresponding to the use of a production cluster over a long period shows that long-running services experience demand variations with a periodic (daily) pattern, and that services with such a pattern account for most of the overall CPU demand. This leads to an allocation problem where the classical Bin-Packing issue is augmented with the possibility to co-locate jobs whose peaks occur at different times of the day, which is bound to be more efficient than the usual approach that consist in over-provisioning for the maximum demand. In this paper, we propose a column-generation approach to solving this problem, where the subproblem uses a sophisticated SOCP (Second Order Cone Program) formulation. This allows to explicitely select jobs which benefit from being co-allocated together. Experimental results comparing with theoretical lower bounds and with standard packing heuristics shows that this approach is able to provide very efficient assignments in reasonable time.< Réduire

URI

https://oskar-bordeaux.fr/handle/20.500.12278/194212

Project ANR

Simulation de systèmes de prochaine génération - ANR-11-INFR-0013

Origine

Importé de hal

Unités de recherche

Institut de Mathématiques de Bordeaux (IMB) - UMR 5251