Column generation integer programming for allocating jobs with periodic demand variations
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| dc.contributor.author | BELAID, Ikbel | |
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| dc.contributor.author | EYRAUD-DUBOIS, Lionel | |
| dc.date.accessioned | 2024-04-04T03:16:24Z | |
| dc.date.available | 2024-04-04T03:16:24Z | |
| dc.date.created | 2015 | |
| dc.date.conference | 2015-09-14 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/194212 | |
| dc.description.abstractEn | 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. | |
| dc.description.sponsorship | Simulation de systèmes de prochaine génération - ANR-11-INFR-0013 | |
| dc.language.iso | en | |
| dc.publisher | Springer | |
| dc.source.title | Advanced Research in Computing and Software Science, Lecture Notes in Computer Science | |
| dc.title.en | Column generation integer programming for allocating jobs with periodic demand variations | |
| dc.type | Communication dans un congrès | |
| dc.subject.hal | Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC] | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.conference.title | International Workshop on Algorithmic Aspects of Cloud Computing | |
| bordeaux.country | GR | |
| bordeaux.title.proceeding | Advanced Research in Computing and Software Science, Lecture Notes in Computer Science | |
| bordeaux.conference.city | Patras | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-01252770 | |
| hal.version | 1 | |
| hal.invited | non | |
| hal.proceedings | oui | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-01252770v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.btitle=Advanced%20Research%20in%20Computing%20and%20Software%20Science,%20Lecture%20Notes%20in%20Computer%20Science&rft.au=BELAID,%20Ikbel&EYRAUD-DUBOIS,%20Lionel&rft.genre=unknown |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||