Column generation integer programming for allocating jobs with periodic demand variations

Ikbel Belaid (1, 2) , Lionel Eyraud-Dubois (1)

1 Realopt - Reformulations based algorithms for Combinatorial Optimization
2 IMB - Institut de Mathématiques de Bordeaux

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.

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

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⟩