| Résumé | Les plates formes à grande échelle s'intéressent aux ressources non
utilisés chez des utilisateurs reliées entre elles par Internet en vue de
les exploiter pour des problèmes parallélisables. L'objectif est
d'étendre ce système au travail de manière distribuée sur des
problèmes de taille importante, parallélisables et tels que chaque tâche
indépendante soit assez importante pour devoir être traitée par de
petits groupes de ressources. La formation de groupes de travail se ramène
à du bin covering distribué, et, comme il ne doit pas y avoir
d'éléments trop loin les uns des autres au sein d'un même groupe, une
contrainte de distance apparait. Le bin covering consiste, étant donnée
une liste d'éléments pondérés, à les assembler en groupes de poids
total supérieur à une certaine valeur, en essayant de maximiser le nombre
de groupes formés. Nous obtenons plusieurs résultats intéressants sur la
constuction de groupes de manière distribuée, sans contrainte de distance
tout d'abord, puis en incluant la contrainte de distance en dimension 1.
Seront enfin évoquées les pistes de travail pour des solutions en
dimensions supérieures, notamment l'utilisation d'une relaxation de la
contrainte de distance.
|