Column generation integer programming for allocating jobs with periodic demand variations

Ikbel Belaid 1, 2, * Lionel Eyraud-Dubois 1
* Corresponding author
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.
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/hal-01252770
Contributor : Lionel Eyraud-Dubois <>
Submitted on : Friday, January 8, 2016 - 11:00:53 AM
Last modification on : Tuesday, May 7, 2019 - 11:42:10 AM
Long-term archiving on : Thursday, November 10, 2016 - 9:42:09 PM

File

ALGOCLOUD_2015_Ikbel BELAID.pd...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01252770, version 1

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. ⟨hal-01252770⟩

Share

Metrics

Record views

444

Files downloads

356