Column generation integer programming for allocating jobs with periodic demand variations

Ikbel Belaid 1, 2, * Lionel Eyraud-Dubois 3, 1
* Auteur correspondant
1 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
Abstract : 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.
Type de document :
Communication dans un congrès
International Workshop on Algorithmic Aspects of Cloud Computing, Sep 2015, Patras, Greece. Springer, Advanced Research in Computing and Software Science, Lecture Notes in Computer Science
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01252770
Contributeur : Lionel Eyraud-Dubois <>
Soumis le : vendredi 8 janvier 2016 - 11:00:53
Dernière modification le : jeudi 11 janvier 2018 - 06:22:12
Document(s) archivé(s) le : jeudi 10 novembre 2016 - 21:42:09

Fichier

ALGOCLOUD_2015_Ikbel BELAID.pd...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01252770, version 1

Collections

Citation

Ikbel Belaid, Lionel Eyraud-Dubois. Column generation integer programming for allocating jobs with periodic demand variations. International Workshop on Algorithmic Aspects of Cloud Computing, Sep 2015, Patras, Greece. Springer, Advanced Research in Computing and Software Science, Lecture Notes in Computer Science. 〈hal-01252770〉

Partager

Métriques

Consultations de la notice

301

Téléchargements de fichiers

117