# Délégation de lots de tâches pour la réduction de la durée moyenne de réalisation

Ellie Beauprez, Anne-Cécile Caron, Maxime Morge, Jean-Christophe Routier

► To cite this version:

Ellie Beauprez, Anne-Cécile Caron, Maxime Morge, Jean-Christophe Routier. Délégation de lots de tâches pour la réduction de la durée moyenne de réalisation. Revue Ouverte d'Intelligence Artificielle, 2023, ROIA, 4 (2), pp.193-221. 10.5802/roia.62 . hal-04163796

HAL Id: hal-04163796

https://hal.science/hal-04163796

Submitted on 17 Jul 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
<figure><img src="image_2.png" /></figure>

ELLIE BEAUPREZ, ANNE-CÉCILE CARON,
MAXIME MORGE, JEAN-CHRISTOPHE ROUTIER

Délégation de lots de tâches pour la réduction de la durée moyenne de réalisation
Volume 4, n° 2 (2023), p. 193-221.

DOI not yet assigned

© Les auteurs, 2023.

<figure><img src="image_3.png" /></figure>

Cet article est diffusé sous la licence

CREATIVE COMMONS ATTRIBUTION 4.0 INTERNATIONAL LICENSE.

http://creativecommons.org/licenses/by/4.0/

<figure><img src="image_4.png" /></figure>

La Revue Ouverte d'Intelligence Artificielle est membre du
Centre Mersenne pour l'édition scientifique ouverte

www.centre-mersenne.org

e-ISSN : 2967-9672
# Délégation de lots de tâches pour la réduction de la durée moyenne de réalisation

Ellie Beauprez<sup>a</sup>, Anne-Cécile Caron<sup>a</sup>, Maxime Morge<sup>a</sup>, Jean-Christophe Routier<sup>a</sup>

RÉSUMÉ. — Nous étudions le problème de la réallocation de tâches pour l'équilibrage de charge dans les modèles distribués de traitement de données massives. Nous proposons une stratégie qui repose sur des agents coopératifs pour optimiser le réordonnancement de tâches dans un ensemble de jobs devant être exécutés le plus tôt possible. Elle permet aux agents de déterminer localement les prochaines tâches à exécuter, à déléguer, voire à échanger grâce à leurs connaissances, leurs croyances et leur modèle des pairs. La nouveauté réside dans la capacité des agents à identifier les opportunités et les agents limitants pour réallouer efficacement des lots de tâches à travers des négociations bila- térales concurrentues. La stratégie mise en œuvre par les agents permet de garantir une amélioration continue du délai de réalisation. Nos expérimentations montrent que la durée moyenne de réalisation atteinte par notre stratégie est meilleure que celle obtenue avec une résolution DCOP et reste proche de celle obtenue avec une heuristique classique, avec dans tous les cas un temps de réordonnancement significativement réduit.

MOTS-CLÉS. — Système multi-agents, résolution collective de problèmes, négociation multi-agents.

# 1. INTRODUCTION

La problématique de l'affectation efficace de tâches parmi des entités exécutantes est commune à de nombreuses applications réelles pour la logistique [16, 18], la robotique collective [9, 26], le calcul distribué [15, 24], ou plus récemment le traitement de données massives [1]. En particulier, les sciences des données, qui exploitent de larges volumes de données sur lesquelles des calculs sont effectués en parallèle par différents nœuds, mettent à l'épreuve l'informatique distribuée en ce qui concerne l'allocation de tâches et l'équilibrage de charge. Cet article traite d'une classe d'applications pratiques où : (a) des jobs (c'est-à-dire des ensembles de tâches) concurrents doivent être exécutés le plus tôt possible, et (b) les ressources (c'est-à-dire les données) requises sont distribuées. Nous considérons particulièrement le modèle de traitement le plus répandu pour traiter des données massives sur une grappe de serveurs, c'est-à-dire le patron de conception MapReduce [28]. Les jobs y sont composés d'un ensemble de tâches

<footnote><sup>a</sup> Univ. Lille, CNRS, Centrale Lille, UMR 9189 CRIStAL, F-59000 Lille, France</footnote>

<footnote>E-mail: Ellie.Beauprez@univ-lille.fr, Anne-Cecile.Caron@univ-lille.fr,</footnote>

<footnote>Maxime.Morge@univ-lille.fr, Jean-Christophe.Routier@univ-lille.fr.</footnote>
exécutées par les différents nœuds où sont réparties les ressources. Comme plusieurs ressources sont requises pour réaliser une tâche sur un nœud, son exécution nécessite de récupérer des ressources disponibles sur d'autres nœuds, ce qui induit un surcoût.

De nombreux travaux adoptent le paradigme multi-agents pour aborder le problème de la réallocation de tâches et de l'équilibrage de charge dans les systèmes distribués [15]. L'approche centrée individus permet la distribution d'heuristiques pour des problèmes impraticables à cause de la combinatoire des ordonnancements pour permettre le passage à l'échelle. De plus, intrinsèquement réactives, les méthodes multi-agents de réallocation s'adaptent aux estimations inexactes des temps d'exécution et aux perturbations (consommation/libération de tâches, ralentissement des exécutants, etc.) La plupart de ces travaux adoptent l'approche orientée marché en modélisant le problème comme un jeu non-coopératif [9, 27], voire en s'appuyant sur des méthodes d'apprentissage qui nécessitent un historique [24, 26]. Par contraste, nous supposons comme [1] que : (a) les agents sont coopératifs, c'est-à-dire ils ont une perception locale et partielle de l'allocation, mais ils partagent le même objectif, et (b) aucun modèle préalable n'existe, ni des données, ni de l'environnement, de par la classe d'applications pratiques visées. Nous allons ici au-delà en considérant plusieurs jobs composés d'ensembles de tâches, chacune pouvant être exécutée par un seul des nœuds exécutants, tous compétents. Chaque agent, représentant un nœud, souhaite minimiser la durée moyenne de réalisation des jobs, c'est-à-dire le *flowtime* moyen. La principale difficulté réside dans la formulation de comportements individuels joués de manière asynchrone par les exécutants qui doivent aboutir à l'émergence d'affectations faisables qui combinent les objectifs des commanditaires.

Nous proposons des stratégies qui décident quelle réallocation bilatérale est suggérée ou acceptée. Elles reposent sur un modèle des pairs et déterminent le comportement de l'agent à chaque point de choix dans le protocole de négociation. La stratégie d'offre sélectionne une délégation potentielle, c'est-à-dire un lot de tâches et un répondant. La stratégie d'acceptation détermine si l'agent accepte ou refuse toute ou partie de cette délégation.

Nos contributions sont les suivantes :

(1) Nous formalisons le problème d'allocation multi-agents de jobs composés de tâches situées dont les coûts diffèrent selon la localisation des ressources.

(2) Nous proposons une stratégie qui identifie en continu les agents limitants et les opportunités au sein de répartitions déséquilibrées pour déclencher des négociations concurrentes et bilatérales afin de déléguer voire d'échanger des tâches.

(3) Nous avons conduit des expériences approfondies qui montrent que notre méthode atteint une durée de réalisation proche de celle obtenue par l'heuristique classique et réduit significativement le temps de réordonnancement.

Cet article est une version étendue de [3] où :

(1) la notion de délégation a été généralisée sous la forme de réallocation bilatérale ce qui permet d'envisager des délégations *n*-aires et des échanges ;
(2) la rationalité des réallocations a été redéfinie, ce qui a permis de réduire non seulement la durée moyenne de réalisation atteinte par notre stratégie mais également le temps de réordonnancement;

(3) nous comparons les performances de notre stratégie à celles des techniques d'optimisation distribuée sous contraintes (DCOP).

Après un aperçu des travaux connexes dans la section 2, nous formalisons le pro-
blème d’allocation multi-agents de jobs composés de tâches (cf. section 3). La section 4 décrit les opérations de consommation/délégation et le processus de négociation. La section 5 précise comment les agents choisissent quelles tâches négocier et avec qui. Notre évaluation expérimentale est décrite dans la section 6. La section 7 résume notre contribution et présente nos perspectives.

## 2. TRAVAUX CONNEXES

<table><caption>TABLE 2.1 – Grille d’analyse des méthodes d’affectation (haut) ou de réaffectation (bas)</caption><thead><tr><th></th><th>Ressources</th><th>Tâches</th><th>Exécutants</th><th>Objectif</th><th>Dynamique</th><th>Décentralisé</th><th>Technique/ Modèle</th></tr></thead><tbody><tr><td>(Kuhn-Munkres, 1955) [16]</td><td>—</td><td>n<br>mono-exécutant</td><td>R<sub>n</sub><br>mono-tâche</td><td>W(Å)</td><td>✗</td><td>✗</td><td>LP</td></tr><tr><td>(SPT, 1967) [10]</td><td>—</td><td>n<br>mono-exécutant</td><td>P<sub>m</sub><br>multi-tâches</td><td>C(Å)</td><td>✗</td><td>✗</td><td>Heuristique</td></tr><tr><td>(Bruno et al., 1974) [7]</td><td>—</td><td>n<br>mono-exécutant</td><td>R<sub>m</sub><br>multi-tâches</td><td>C(Å)</td><td>✗</td><td>✗</td><td>LP</td></tr><tr><td>(Shehory et Krause, 1998) [25]</td><td>—</td><td>n<br>multi-exécutant</td><td>R<sub>m</sub><br>mono-tâche</td><td>W(Å)</td><td>✓</td><td>✓</td><td>Coalition</td></tr><tr><td>(GPGP, 2004) [17]</td><td>consommables<br>ou pas</td><td>n<br>mono-exécutant</td><td>R<sub>m</sub><br>multi-tâches</td><td>W(Å)</td><td>✓</td><td>✓</td><td>Équipe</td></tr><tr><td>(Turner et al., 2018) [26]</td><td>limitées</td><td>n<br>mono-exécutant</td><td>R<sub>m</sub> en ligne<br>multi-tâches</td><td>W(Å)</td><td>✓</td><td>✓</td><td>CBBA +<br>classification</td></tr><tr><td>(Li et al., 2014) [18]</td><td>—</td><td>n<br>mono-exécutant</td><td>P<sub>m</sub><br>multi-tâches</td><td>C(Å)<br>⊕W(Å)</td><td>✓</td><td>✓</td><td>DCOP</td></tr><tr><td>(Schaerf et al., 1995) [24]</td><td>—</td><td>n<br>mono-exécutant</td><td>P<sub>m</sub><br>multi-tâches</td><td>W(Å)</td><td>✓</td><td>✓</td><td>MARL</td></tr><tr><td>(MASTA, 2021) [1]</td><td>transférables<br>duplicables</td><td>n<br>mono-exécutant</td><td>R<sub>m</sub><br>multi-tâches</td><td>C<sub>max</sub>(Å)</td><td>✓</td><td>✓</td><td>Équipe</td></tr><tr><td>(SMASTA+, 2021) [4]</td><td>transférables<br>duplicables</td><td>n<br>mono-exécutant</td><td>R<sub>m</sub><br>multi-tâches</td><td>C(Å)</td><td>✓</td><td>✓</td><td>Équipe</td></tr></tbody></table>

Le tableau 2.1 synthétise l'ensemble des travaux évoqués ici selon notre grille d'analyse. Cette grille fait référence à un état de l'art plus large que nous avons publié [2]. La partie gauche du tableau discerne les différents problèmes abordés : leurs ingrédients (ressources, tâches, exécutants) et les objectifs visés. La partie droite révèle les caractéristiques de ces méthodes ainsi que les techniques et modèles sous-jacents. La partie supérieure du tableau contient les méthodes classiques d'affectation alors que la partie inférieure présente les méthodes de réaffectation dynamique et continue.

La théorie de l'ordonnancement [8] propose des méthodes hors-ligne pour résoudre différents problèmes d'affectation efficace de tâches parmi des entités exécutantes. Par
exemple, l'algorithme polynomial de Kuhn-Munkres, appelé méthode hongroise, minimise le coût total de l'affectation (noté $W(\vec{A})$) de $n$ tâches à $n$ exécutants [16]. La règle du « plus court processus en premier » – *shortest processing time first* (SPT) – est une méthode très simple qui minimise le débit de réalisation pour un problème avec un seul exécutant multi-tâches et $n$ tâches mono-exécutant [10]. Ce résultat se généralise au problème avec $m$ exécutants multi-tâches si le coût d'une tâche est identique d'un exécutant à l'autre (noté $P_m$). Le problème d'ordonnancement qui consiste à minimiser la durée totale de réalisation (notée $C(\vec{A})$) avec $m$ exécutants multi-tâches et $n$ tâches mono-exécutant dont les coûts dépendent de l'entité exécutante (noté $R_m$) peut être formalisé par programmation linéaire – *Linear Programming* (LP). Ce problème se réduit à un problème d'appariement pondéré dans un graphe biparti avec $n$ tâches et $n \times m$ positions. Ce problème est polynomial [14]. Reposant sur l'algorithme de Ford-Fulkerson, la complexité de l'algorithmme décrit par [7] est $O(\max(mn^2, n^3))$. Ces approches ne sont pas toujours adaptées à la réallocation de tâches dans des systèmes distribués où décentralisation et adaptativité sont nécessaires. En effet, un contrôle global constitue un goulot d'étranglement en matière de performance, car il doit en permanence collecter des informations sur l'état du système. À l'opposé, nos agents prennent des décisions locales sur une allocation existante dans le but d'améliorer l'équilibrage de charges. De plus, les problèmes d'ordonnancement classiques sont statiques. L'estimation inexacte du temps d'exécution des tâches, aggravée par des perturbations (consommation de tâches, libération de jobs, ralentissement des nœuds, etc.) peut nécessiter d'importantes modifications de l'allocation existante pour qu'elle reste optimale. Qui plus est, les agents peuvent agir dans des environnements dynamiques qui évoluent au cours du temps.

Le paradigme multi-agents est particulièrement approprié pour la conception et l'implémentation de mécanismes distribués et adaptatifs de réaffectation de tâches-exécutants [15]. Les modèles existants se distinguent de par la nature des tâches et des agents, qu'ils représentent les exécutants ou les commanditaires des tâches. Les modèles de formation d'une coalition se justifient si la réalisation d'une tâche nécessite plus d'un exécutant ou si son coût diminue avec le nombre d'exécutants affectés. Par exemple, Shehory et Kraus proposent des algorithmes décentralisés gloutons et *anytime* pour l'assignation de tâches multi-exécutants et soumises à des contraintes de précédence, à des exécutants dont les capacités/efficacités sont hétérogènes [25]. Une équipe vise à maximiser une fonction objectif globale plutôt que la satisfaction individuelle des membres, comme pour une coalition, mais les tâches sont mono-exécutant. En particulier, Lesser et al. proposent un modèle hiérarchique de représentation des tâches pour la coordination qui est indépendant du domaine : affecter les ressources, assigner les tâches et les ordonnancer [17]. L'objectif premier de *Generalized Partial Global Planning* (GPGP) est de maximiser l'utilité combinée de l'ensemble des agents par la réalisation de ses objectifs de plus haut niveau. GPGP est un modèle de coordination basée sur la planification des activités. Cette approche suppose que l'effort nécessaire à la coordination (raisonnement et communication) est négligeable par rapport aux temps d'exécution des tâches à coordonner. S'inspirant de théories économiques, la « programmation orientée marché » aborde les problèmes de planification
distribuée à travers la recherche d'un équilibre pour un jeu non-coopératif [27]. Les agents délèguent des (lots de) tâches voire les échangent. Contrairement à une équipe, une place de marché suppose que les contraintes et les objectifs sont complètement distribués. Parmi les méthodes orientées marché, on distingue trois familles.

**DCOP.** Les problèmes de réaffectation peuvent être représentés sous la forme d'un problème d'optimisation sous contraintes distribué – *Distributed Constraint Optimization Problems (DCOP)*. De nombreuses méthodes ont été développées pour la recherche d'une solution optimale à un DCOP qui est un problème NP-difficile (voir [12] pour une synthèse récente). La principale difficulté dans la mise en œuvre de ces méthodes pour la réaffectation de tâches réside dans la représentation d'un problème réaliste sous la forme d'un DCOP, voire de plusieurs sous-problèmes COP, car elle nécessite une expertise de la méthode de résolution (e.g. [18]).

**CBBA.** L'algorithme à base de consensus (CBBA – *Consensus Based Bundle Algorithm*) [9] est une méthode multi-agents d'affectation en deux phases qui consiste à : (a) sélectionner les tâches à négocier ; (b) déterminer l'agent qui remporte ces négociations. Dans la continuité, Turner et al. étudient l'affectation en continu de tâches à une flotte de robots pour maximiser le débit de réalisation avec des ressources en carburant limitées [26]. Grâce à l'apprentissage automatique supervisé à partir des exécutions précédentes, les robots choisissent dynamiquement et de manière décentralisée la meilleure heuristique de sélection de tâche.

**MARL.** Les problèmes de réaffectation peuvent également être modélisés via des processus de décision markoviens [6], en particulier des processus de décision markoviens partiellement observables décentralisés – *Decentralized Partially Observed Markov Decision Process* (Dec-POMDP). L'optimisation d'un Dec-POMDP à horizon fini est un problème NEXPTIME. Les méthodes de résolution approchée ne peuvent être appliquées que sur de très petites instances de problèmes, elles ne passent pas à l'échelle. Au-delà de ces méthodes de planification hors-ligne, l'apprentissage multi-agents par renforcement (MARL-*Multi-Agent Reinforcement Learning*) nécessite une connaissance parfaite de l'environnement et requiert une phase d'apprentissage [24].

À l'inverse, nous ne considérons aucun modèle préalable, ni des données, ni de l'environnement, car cela ne serait pas pertinent pour la classe d'applications pratiques qui nous concerne. Le volume de données rend son pré-traitement trop coûteux et la variabilité des données rend rapidement le pré-traitement obsolète. De la même manière, Baert et al. visent dans [1] un objectif égalitaire qui est la minimisation du temps nécessaire à la réalisation de l'ensemble des tâches (noté $C_{max}(\vec{A})$). Nous considérons ici le problème de la coordination des décisions entre agents pour trouver une solution globalement optimale pour des fonctions multi-objectifs. Les agents tentent de minimiser la durée moyenne de réalisation de plusieurs jobs concurrents, chacun constitué de plusieurs tâches. Les tâches considérées sont mono-exécutants et les ressources qu'elles requièrent sont transférables et non consommables. Les agents exécutants sont multi-tâches et tous compétents.
Alors que nos travaux précédents ne considèrent que des délégations d'une seule tâche à la fois, nous généralisons ici notre cadre formel pour considérer n'importe quelle réallocation bilatérale (échange ou délégation de plusieurs tâches) afin de réduire non seulement la durée moyenne de réalisation mais également le temps de réordonnancement.

Nous redéfinissons ici la rationalité des reallocations. Précédemment, ce critère était défini à partir du *flowtime* local, c'est-à-dire la durée de réalisation pour les deux agents impliqués dans la transaction. Comme ce critère seul ne permet pas de garantir la terminaison de l'algorithme multi-agents de réallocation, il était combiné avec le *makespan*, le temps nécessaire à la réalisation de l'ensemble des jobs. Dans cet article, une réallocation bilatérale est rationnelle si elle réduit le *flowtime* global du système. Ce critère s'avère suffisant pour garantir la convergence du processus de réallocation. De plus, il permet de réduire le temps de réordonnancement et la durée moyenne de réalisation atteinte par notre stratégie.

Nous comparons quantitativement les performances de notre stratégie à celles des techniques d'optimisation distribuée sous contraintes (DCOP).

### 3. TÂCHES SITUÉES

Nous formalisons ici le problème d'allocation multi-agents des jobs concurrents composés de tâches situées.

Un job est un ensemble de tâches indépendantes, non divisibles et non-préemptives. L'exécution de chaque tâche nécessite l'accès à des ressources distribuées sur les nœuds du système. Nous considérons les ressources transférables et non consommables.

**DÉFINITION 3.1 (Système distribué).** — *Un système distribué est un triplet $\mathcal{D} = (\mathcal{N}, \mathcal{E}, \mathcal{R})$ où :*

* $\mathcal{N} = \{v_1, \dots, v_m\}$ est un ensemble de nœuds;

* $\mathcal{E}$ est une relation d'accointance, i.e. une relation binaire et symétrique sur $\mathcal{N}$;

* $\mathcal{R} = \{\rho_1, \dots, \rho_k\}$ est un ensemble de ressources de tailles $|\rho_i|$. La localisation des ressources, éventuellement répliquées, est déterminée par la fonction :

$$l: \mathcal{R} \to 2^{\mathcal{N}} \qquad (3.1)$$

Pour plus de simplicité, nous faisons l'hypothèse ici qu'il y a exactement un agent par nœud et que toutes les ressources sont accessibles pour tous les agents même celles sur les nœuds distants car la relation d'accointance est totale.

L'exécution d'un job (sans date butoir) consiste à exécuter un ensemble de tâches indépendantes nécessitant des ressources pour produire un résultat.

**DÉFINITION 3.2 (Job/Tâche).** — *Soient $\mathcal{D}$ un système distribué et Res l'espace des résultats. On considère un ensemble de $l$ jobs $J = \{J_1, \dots, J_l\}$. Chaque job $J_i$*
est un ensemble de $k_i$ tâches $J_i = \{\tau_1, \dots, \tau_{k_i}\}$ où chaque tâche $\tau$ est une fonction
$\tau: 2^{\mathcal{R}} \mapsto \text{Res.}$

On note $\mathcal{T} = \cup_{1 \le i \le \ell} J_i$ l'ensemble des $n$ tâches sous-jacentes à $\mathcal{J}$ et $\mathcal{R}_{\tau} \subseteq \mathcal{R}$
l'ensemble des ressources requises pour la tâche $\tau$. Par souci de concision, on note
job($\tau$) le job contenant la tâche $\tau$. Nous faisons l'hypothèse que le nombre de jobs est
négligeable par rapport au nombre de tâches, $|\mathcal{J}| \ll |\mathcal{T}|$.

Le coût d'une tâche est une estimation de son temps d'exécution par un nœud.

PROPRIÉTÉ 3.3 (Coût). — Soient $\mathcal{D}$ un système distribué et $\mathcal{T}$ un ensemble de tâches. La fonction de coût $c : \mathcal{T} \times \mathcal{N} \mapsto \mathbb{R}_+^*$ est telle que :

$$
c(\tau, v_i) \le c(\tau, v_j) \iff \sum_{\rho \in \mathcal{R}_{\tau}, v_i \in \mathcal{L}(\rho)} |\rho| > \sum_{\rho \in \mathcal{R}_{\tau}, v_j \in \mathcal{L}(\rho)} |\rho| \quad (3.2)
$$

Comme la collecte de ressources distantes représente un surcoût, une tâche est
moins coûteuse si les ressources nécessaires sont « plus locales » (cf. section 6). La
fonction de coût peut être étendue à un ensemble de tâches :

$$
\forall T \subseteq \mathcal{T}, c(T, v_i) = \sum_{\tau \in T} c(\tau, v_i) \quad (3.3)
$$

En substance, nous considérons le problème d'allocation multi-agents de jobs
composés de tâches situées.

DÉFinition 3.4 (MASTA+). — *Un problème d’allocation multi-agents de jobs est un quadruplet MASTA+ = (\mathcal{D}, \mathcal{T}, \mathcal{J}, c) où :*

• $\mathcal{D}$ est un système distribué de m nœuds;

• $\mathcal{T} = \{\tau_1, \dots, \tau_n\}$ est un ensemble de n tâches;

• $\mathcal{J} = \{J_1, \dots, J_\ell\}$ est un partitionnement des tâches en $\ell$ jobs;

• $c: \mathcal{T} \times \mathcal{N} \mapsto \mathbb{R}_+^*$ est la fonction de coût.

Une allocation de tâches est une répartition des tâches dans des lots ordonnés.

DÉFinition 3.5 (Allocation) . — Une allocation pour un problème MASTA+ est un vecteur de m lots de tâches ordonnées $\vec{A} = ((B_1, <_1), \dots, (B_m, <_m))$ où chaque lot $(B_i, <_i)$ est l'ensemble des tâches $(B_i \subseteq \mathcal{T})$ affectées au nœud $v_i$ associé à un ordre total strict $(<_i \subseteq \mathcal{T} \times \mathcal{T})$. $\tau_j <_i \tau_k$ signifie que si $\tau_j, \tau_k \in B_i$ alors $\tau_j$ est exécutée avant $\tau_k$ par $v_i$. L'allocation $\vec{A}$ vérifie :

$$
\forall \tau \in \mathcal{T}, \exists v_i \in \mathcal{N}, \tau \in B_i \quad (3.4)
$$

$$
\forall v_i \in \mathcal{N}, \forall v_j \in \mathcal{N} \setminus \{v_i\}, B_i \cap B_j = \emptyset \quad (3.5)
$$

Toutes les tâches sont allouées (équation (3.4)) et chacune n'est allouée qu'à un
seul nœud (équation (3.5)). Par souci de concision, on note :

• $\vec{B}_i = (B_i, <_i)$, le lot trié de $v_i$;

• $\min_{<_i} B_i$, la prochaine tâche à exécuter par $v_i$ :
* jobs($B_i$), l'ensemble des jobs affectés à $v_i$, i.e. les jobs ayant au moins une tâche dans $B_i$;

* $v(\tau, \vec{A})$, le nœud chargé de $\tau$ dans $\vec{A}$;

* $w_i(\vec{A}) = \sum_{\tau \in B_i} c(\tau, v_i)$, la charge de travail du nœud $v_i$ pour l'allocation $\vec{A}$.

Par abus de notation, une allocation réduite à un singleton, $\vec{A} = (\vec{B}_i)$, est notée $\vec{A} = \vec{B}_i$.

Comme on suppose que les nœuds sont toujours actifs, la durée de réalisation d'une tâche (completion time) correspond au temps d'attente avant que la tâche soit entamée plus l'estimation de son temps d'exécution :

$$C_{\tau}(\vec{A}) = t(\tau, v(\tau, \vec{A})) + c(\tau, v(\tau, \vec{A})) \quad (3.6)$$
$$\text{avec } t(\tau, v_i) = \sum_{\tau' \in B_i | \tau' < i} \tau c(\tau', v_i)$$

Contrairement aux coûts, les durées de réalisation dépendent de l'ordre d'exécution.

Pour évaluer la qualité d'une allocation de tâches, nous considérons le flowtime moyen, qui mesure le temps moyen écoulé entre la date de libération des jobs (on suppose ici que tous les jobs sont libérés à la même date $t = 0$) et leur date d'achèvement, et le makespan qui est le temps nécessaire à la réalisation de l'ensemble des jobs.

**DÉFinition 3.6 (Flowtime/Makespan).** — Soient MASTA+ un problème d'allocation de tâches et $\vec{A}$ une allocation. On définit :

* la durée de réalisation de $J \in \mathcal{J}$ pour $\vec{A}$,

$$C_J(\vec{A}) = \max_{\tau \in J} \{C_{\tau}(\vec{A})\} \quad (3.7)$$

* le flowtime (moyen) de $\mathcal{J}$ pour $\vec{A}$,

$$C_{\text{mean}}(\vec{A}) = \frac{1}{l} C(\vec{A}) \text{ avec } C(\vec{A}) = \sum_{J \in \mathcal{J}} C_J(\vec{A}) \quad (3.8)$$

* le makespan de $\mathcal{J}$ pour $\vec{A}$,

$$C_{\max}(\vec{A}) = \max_{v_i \in \mathcal{N}} \{w_i(\vec{A})\} \quad (3.9)$$

* le taux de disponibilité locale de $\vec{A}$,

$$L(\vec{A}) = \sum_{\tau \in \mathcal{F}} \frac{\sum_{\rho \in \mathcal{R}_{\tau}, v(\tau, \vec{A}) \in l(\rho)} |\rho|}{\sum_{\rho \in \mathcal{R}_{\tau}} |\rho|} \quad (3.10)$$

Contrairement au makespan, le flowtime dépend de l'ordre d'exécution des tâches sur chacun des nœuds. Le taux de disponibilité locale d'une allocation mesure la proportion des ressources traitées localement (équation (3.10)).

**Exemple 3.7 (MASTA+).** — À partir du système distribué $\mathcal{D} = \langle \mathcal{N}, \mathcal{E}, \mathcal{R} \rangle$ avec $\mathcal{N} = \{v_1, v_2, v_3\}$, $\mathcal{E} = \{(v_1, v_2), (v_1, v_3), (v_2, v_3)\}$ et $\mathcal{R} = \{\rho_1, \dots, \rho_9\}$ où les ressources sont répliquées sur 2 nœuds (cf. figure 3.1a), nous considérons MASTA+ =
⟨D, T, J, c⟩ avec T = {τ₁, ..., τ₉} où chaque tâche τᵢ nécessite la ressource ρᵢ, J = {J₁, J₂, J₃} tel que J₁ = {τ₁, τ₂, τ₃}, J₂ = {τ₄, τ₅, τ₆} et J₃ = {τ₇, τ₈, τ₉} et la fonction de coût donnée dans la table 3.1. Nous supposons que le coût d'une tâche est proportionnel à la taille des ressources et qu'il est deux fois plus important si la ressource est distante. Nous considérons ici l'allocation ⃗A (cf. figure 3.1b) avec ⃗B₁ = (τ₅, τ₈, τ₃, τ₂), ⃗B₂ = (τ₄, τ₉) et ⃗B₃ = (τ₇, τ₁, τ₆). Le makespan et le flowtime sont Cmax(⃗A) = 12 et C(A) = 8 + 12 + 12 = 32.

<table><caption>TABLE 3.1 – Le coût des tâches pour chacun des nœuds</caption><thead><tr><th></th><th>τ<sub>1</sub></th><th>τ<sub>2</sub></th><th>τ<sub>3</sub></th><th>τ<sub>4</sub></th><th>τ<sub>5</sub></th><th>τ<sub>6</sub></th><th>τ<sub>7</sub></th><th>τ<sub>8</sub></th><th>τ<sub>9</sub></th></tr></thead><tbody><tr><th>c(τ, v<sub>1</sub>)</th><td>5</td><td>3</td><td>1</td><td>8</td><td>2</td><td>10</td><td>4</td><td>2</td><td>4</td></tr><tr><th>c(τ, v<sub>2</sub>)</th><td>10</td><td>3</td><td>2</td><td>4</td><td>2</td><td>5</td><td>2</td><td>2</td><td>8</td></tr><tr><th>c(τ, v<sub>3</sub>)</th><td>5</td><td>6</td><td>1</td><td>4</td><td>4</td><td>5</td><td>2</td><td>4</td><td>4</td></tr></tbody></table>

<figure><img src="image_5.png" /><figcaption>FIGURE 3.1 – Distributions des ressources et des tâches pour notre exemple fil rouge</figcaption></figure>
En résumé, le coût des tâches dépend du nœud qui l'exécute en raison de la localité des ressources. Notre objectif est de minimiser le *flowtime* moyen des jobs composés de tâches.

## 4. CONSOMMATION ET RÉALLOCATION

Nous décrivons ici les opérations de consommation et de réallocation ainsi que le protocole de négociation.

Une **consommation** de tâche consiste pour un nœud à supprimer une tâche de son lot pour l'exécuter. Cette opération modifie non seulement l'allocation courante mais également le problème MASTA+ sous-jacent où la tâche consommée n'est plus présente. La stratégie de consommation d'un agent spécifie l'ordonnancement des tâches pour le nœud dont il a la charge. Comme nous voulons minimiser le *flowtime* moyen des jobs, nous considérons ici une stratégie orientée job qui trie le lot d'abord par job puis par tâche au sein d'un même job (les tâches d'un même job sont conséutives dans le lot). En particulier, les jobs les moins coûteux sont prioritaires sur ceux plus coûteux pour minimiser localement le délai de réalisation des jobs. Par la suite, $J_1 \triangleleft_i J_2$ signifie que les tâches de $J_1$ sont prioritaires sur celles de $J_2$ et $\tau_1 \prec_i \tau_2$ que la tâche $\tau_1$ est prioritaire sur la tâche $\tau_2$. Plus formellement :

$$ \forall \tau_j, \tau_k \in B_i \ \tau_j <_i \tau_k \Leftrightarrow \\ \text{job}(\tau_j) \triangleleft_i \text{ job}(\tau_k) \lor (\text{job}(\tau_j) = \text{job}(\tau_k) \land \tau_j <_i \tau_k) \quad (4.1) $$

L'ajout ou la suppression d'une liste de tâches T dans le lot $\overrightarrow{B_i}$ du nœud $v_i$ peuvent changer l'ordre d'exécution des tâches puisque ces opérations impliquent un réordonnancement du lot :

* $\overrightarrow{B_i} \oplus T$ désigne le lot qui contient l'ensemble des tâches $B_i \cup T$ trié selon $<_i$;

* $\overrightarrow{B_i} \ominus T$ désigne le lot qui contient $B_i \setminus T$ trié selon $<_i$.

* $\overrightarrow{B_i} \ominus T_1 \oplus \overrightarrow{T_2}$ désigne le lot qui contient $(B_i \setminus T_1) \cup T_2$ trié selon $<_i$.

Une **réallocation bilatérale** est une opération qui modifie l'allocation courante via l'échange d'une ou de plusieurs tâches entre deux agents.

**DÉFINITION 4.1 (Réallocation bilatérale).** — Soient MASTA+ = $\langle \mathcal{D}, \mathcal{T}, \mathcal{J}, c \rangle$ un problème d'allocation et $\overrightarrow{A} = (\overrightarrow{B_1}, \dots, \overrightarrow{B_m})$ une allocation. La réallocation bilatérale de la liste non vide de tâches $T_1$ allouées au proposant $v_i$ en échange de la liste de tâches $T_2$ allouées au répondant $v_j$ dans $\overrightarrow{A}$ ($T_1 \subseteq B_i$ et $T_2 \subseteq B_j$) aboutit à l'allocation $\gamma(T_1, T_2, v_i, v_j, \overrightarrow{A})$ avec les m lots $\gamma_k(T_1, T_2, v_i, v_j, \overrightarrow{A})$ définis tels que :

$$ \gamma_k(T_1, T_2, v_i, v_j, \overrightarrow{A}) = \begin{cases} \overrightarrow{B_i} \ominus T_1 \oplus T_2 & \text{si } k = i, \\ \overrightarrow{B_j} \ominus T_2 \oplus T_1 & \text{si } k = j, \\ \overrightarrow{B_k} & \text{sinon.} \end{cases} \quad (4.2) $$
Pour une réallocation bilatérale $\gamma(T_1, T_2, v_i, v_j, \vec{A})$, on distingue deux cas :

* un **échange** où les deux listes de tâches sont non vides ($T_1 \neq \emptyset \land T_2 \neq \emptyset$), noté $\sigma(T_1, T_2, v_i, v_j, \vec{A})$;

* une **délégation** où un agent donne une partie de ses tâches à l'un de ses pairs sans contre-partie ($T_2 = \emptyset$), notée $\delta(T_1, v_i, v_j, \vec{A})$. Si $|T_1| = 1$, on parle de **délégation unaire**. Dans le cas contraire, on parle de **délégation n-aire**.

Nous verrons par la suite que la réallocation bilatérale de listes de tâches plutôt que d'ensembles permet de spécifier l'ordre selon lequel les tâches doivent être évaluées pour valider l'intérêt de tout ou partie de la réallocation.

Afin d'améliorer une allocation, nous introduisons la notion de réallocation bilatérale socialement rationnelle qui vérifie qu'une réallocation réduit le *flowtime* global, i.e. le délai de réalisation des jobs pour l'ensemble des nœuds.

**DÉFinition 4.2** (Réallocation bilatérale socialement rationnelle). — Soient MASTA+ = ⟨D, T, J, c⟩ un problème d'allocation, $\vec{A}$ une allocation. La réallocation bilatérale $\gamma(T_1, T_2, v_i, v_j, \vec{A})$ est socialement rationnelle vis-à-vis du flowtime global ssi le flowtime global décroît,

$$C(\gamma(T_1, T_2, v_i, v_j, \vec{A})) < C(\vec{A}) \quad (4.3)$$

Une allocation est dite **stable** s'il n'existe aucune réallocation bilatérale socialement rationnelle.

Contrairement à [3], nous ne considérons pas comme socialement rationnelles des réallocations qui réduisent le *flowtime* local (le délai de réalisation des jobs pour les seuls nœuds impliqués dans la réallocation) qui ne permet pas de garantir la convergence du processus de réallocation, ni même comme rationnelles des réallocations qui réduisent le *flowtime* local et le *makespan* (la charge maximale des agents). La réduction du *flowtime* global permet de garantir la terminaison du processus. Dorénavant lorsque nous parlerons de *flowtime* il s'agira, sauf précision, du *flowtime* global (= $C(\vec{A})$ défini équation (3.8)).

**Propriété 4.3** (Terminaison). — Soient MASTA+ = ⟨D, T, J, c⟩ un problème d'allocation et $\vec{A}$ une allocation qui n'est pas stable vis-à-vis du flowtime. Toute séquence de réallocations bilatérales socialement rationnelles issue de $\vec{A}$ est finie car elle atteint une allocation stable.

*Démonstration*. — La preuve est similaire à celles du théorème 7 et du lemme 3 dans [11]. En effet, comme le nombre d'allocations est fini et $\Sigma_{J \in J} C_J(\vec{A})$ décroît strictement à chaque étape, il ne peut y avoir qu'un nombre fini de réallocations socialement rationnelles aboutissant à une allocation stable. $\square$

Pour réaliser des réallocations de tâches, les agents réalisent de multiples négociations bilatérales à un tour. Comme illustré sur la figure 4.1, chaque négociation, reposant sur un protocole d'offres alternées [21], inclut trois étapes de décision : (a) la
stratégie d'offre du proposant qui sélectionne une délégation, c'est-à-dire une liste de tâches dans son lot et un répondant (message **Propose**), (b) la stratégie de contre-offre qui permet au répondant de déterminer s'il décline la délégation (**Reject**), l'accepte (**Accept**), voire fait une contre-offre (**CounterPropose**) et (c) l'éventuelle réallocation est confirmée (**Confirm**) ou annulée (**Withdraw**) par le proposant selon les consommations qui ont eu lieu de manière concurrente.

<figure><img src="image_6.png" /><figcaption>FIGURE 4.1 – Protocole de négociation bilatérale entre un agent « proposant » et un agent « répondant » pour la réallocation bilatérale de tâches.</figcaption></figure>

Exemple 4.4 (Consommation et réallocation). — Considérons le problème MASTA+ de l'exemple 3.7, en particulier l'allocation $\vec{A}$ représentée dans la figure 3.1b. Selon la stratégie de consommation adoptée par les agents, chaque lot est trié par job, c'est-à-dire les jobs les moins coûteux sont prioritaires (e.g. $J_3 \triangleleft_3 J_1 \triangleleft_3 J_2$). L'ordre naturel sur les identifiants permet de défaire les égalités (e.g. $J_2 \triangleleft_1 J_3$). Les tâches au
<figure><img src="image_7.png" /><figcaption>FIGURE 4.2 – Allocations de l’exemple fil rouge résultant de réallocations bilatérales</figcaption></figure>

sein d'un même job sont triées par ordre de coût croissant ($\tau_3 < \tau_1 < \tau_2$). La délégation de la tâche $\tau_9$ par le nœud $v_2$ au nœud $v_1$ aboutissant à l'allocation $\vec{A}' = \delta([\tau_9], v_2, v_1, \vec{A})$ (cf. figure 4.2a) est socialement rationnelle vis-à-vis du flowtime car elle fait décroître le flowtime de 32 à 31 (les nouveaux temps de réalisation des jobs étant respectivement $C_{J_1}(\vec{A}') = 7$, $C_{J_2}(\vec{A}') = C_{J_3}(\vec{A}') = 12$). Toutefois, l'échange de $\tau_9 \in B_2$ contre $\tau_5 \in B_1$ entre les nœuds $v_2$ et $v_1$, qui aboutit à l'allocation $\vec{A}'' = \sigma([\tau_9], [\tau_5], v_2, v_1, \vec{A})$ (cf. figure 4.2b), est meilleur car il fait décroître le flowtime de 32 à 29 ($C_{J_1}(\vec{A}'') = 7$, $C_{J_2}(\vec{A}'') = 12$, $C_{J_3}(\vec{A}'') = 10$).

# 5. STRATÉGIE DE NÉGOCIATION

Nous décrivons ici les différentes parties de la stratégie de négociation et nous esquissons le comportement de l'agent lors du processus de négociation qui concerne les délégations de lots de tâches.

## 5.1. MODÈLE DES PAIRS

Le modèle des pairs est construit à partir des informations échangées entre agents via des messages. En particulier, avant le processus de négociation et après chaque réallocation bilatérale dans laquelle il est impliqué, l'agent $v_i$ informe ses pairs de ce que chaque job J lui coûte ($c(J, v_i)$). Comme le nombre de jobs est négligeable par rapport au nombre de tâches, la taille de ces messages est dérisoire par rapport à la description des lots. Le modèle de la cible $v_k$ par le sujet $v_i$ repose sur :

(1) la base de croyances du sujet, éventuellement partielle ou obsolète, qui contient les croyances concernant les coûts des jobs pour $v_k$ ($c^i(J, v_k)$, $\forall J \in \mathcal{J}$) et donc les croyances concernant la charge de travail de $v_k$ ($w_k^i(\vec{A}) = \sum_{J \in \mathcal{J}} c^i(J, v_k)$);

(2) l'ordre des jobs dans le lot de la cible en se basant sur la stratégie de consommation commune, et sur la base de croyances.
Par souci de cohérence, on écrit $c^i(J, v_i) = c(J, v_i)$ et $w_i^i(\vec{A}) = w_i(\vec{A})$.

Le sujet peut alors déduire :

* la durée de réalisation ($C_J^i(\vec{B}_k)$) du job J pour une cible $k$, éventuellement lui-même ($v_k = v_i$), après l'ajout ($C_J^i(\vec{B}_k \oplus \vec{T})$), la suppression ($C_J^i(\vec{B}_k \ominus \vec{T})$) et le remplacement de tâches ($C_J^i(\vec{B}_k \ominus \vec{T}_1 \oplus \vec{T}_2)$);

* la durée de réalisation d'un job J pour l'allocation,

$$C_J^i(\vec{A}) = \max_{v_k \in \mathcal{N}} C_J^i(\vec{B}_k) \text{ où } C_J^i(\vec{B}_i) = C_J(\vec{B}_i) \quad (5.1)$$

* le nœud **limitant** pour chaque job J, noté $v_{\max}^i(\vec{A}, J)$, i.e. le nœud $v_k$ pour lequel la durée de réalisation de ce job est la durée de réalisation maximale,

$$C_J^i(\vec{B}_k) = C_J^i(\vec{A}) \quad (5.2)$$

* le flowtime de l'allocation $\vec{A}$

$$C^i(\vec{A}) = \sum_{J \in \mathcal{J}} C_J^i(\vec{A}) \quad (5.3)$$

## 5.2. RÈGLE D'ACCEPTABILITÉ

La règle d'acceptabilité est une décision locale prise par un agent impliqué dans une réallocation bilatérale, qui est basée sur ses connaissances et le modèle de ses pairs, pour accepter ou décliner la réallocation.

**DÉFinition 5.1 (Acceptabilité).** — Soient MASTA+ = $\langle \mathcal{D}, \mathcal{T}, \mathcal{J}, c \rangle$ un problème d'allocation et $\vec{A}$ une allocation. La réallocation bilatérale $\gamma(T_1, T_2, v_i, v_j, \vec{A})$ est acceptable par l'agent $v_k \in \mathcal{N}$ vis-à-vis du flowtime ssi l'agent croit que le flowtime décroît,

$$\sum_{J \in \mathcal{J}} \max_{\forall v_o \in \mathcal{N} \setminus \{v_i, v_j\}} (C_J^k(\vec{B}_i \ominus \vec{T}_1 \oplus \vec{T}_2), C_J^k(\vec{B}_j \ominus \vec{T}_2 \oplus \vec{T}_1), C_J^k(B_o)) < C^k(\vec{A}) \quad (5.4)$$

L'acceptabilité vis-à-vis du flowtime repose sur la croyance à propos des durées de réalisation des jobs pour les nœuds avant et après la réallocation (équation (5.4)).

Nous proposons ici un processus où les agents initient des négociations bilatérales concurrentes qui doivent aboutir à des reallocations socialement rationnelles.

## 5.3. STRATÉGIE D'OFFRE

La **stratégie d'offre** d'un agent, qui repose sur ses connaissances, ses croyances et son modèle des pairs, identifie une délégation en trois étapes. Il s'agit donc pour un agent $v_i$ de sélectionner un lot d'offre, c'est-à-dire une liste de tâches à déléguer à un receveur dans un ensemble $\mathcal{N}'$ afin de réduire la durée de réalisation d'un job pour lequel il est limitant dans un ensemble $\mathcal{J}'$. Initialement, $\mathcal{J}' = \mathcal{J}, \mathcal{N}' = \mathcal{N}$.
(1) **Sélection d'un job.** Afin de réduire non seulement la durée de réalisation globale d'un job qui lui est affecté mais également celles des jobs qui suivent dans son lot, notre heuristique sélectionne le job $J_*$ le plus prioritaire parmi ceux dont il est l'agent limitant,

$$ J_* = \min_{\langle \downarrow_i \rangle} \{ J \in \text{jobs}(B_i) \cap \mathcal{J}' \mid v_{\max}^i(\vec{A}, J = v_i) \} \quad (5.5) $$

(2) **Sélection d'un receveur.** Les jobs d'un receveur impactés par la délégation sont ceux placés après $J_*$ selon $\langle \downarrow_j \rangle$. Afin de ne pas augmenter la durée de réalisation de ces jobs, notre heuristique sélectionne un receveur $v_*$ pour qui la somme des différences entre la durée de réalisation pour l'allocation et celle pour l'agent est la plus grande,

$$ v_* = \text{random} \left\{ \underset{v_j \in \mathcal{N}'}{\operatorname{argmax}} \sum_{J_* \downarrow_j} (C_J^i(\vec{A}) - C_J^i(\vec{B}_j)) \right\} \quad (5.6) $$

où random est une fonction de choix aléatoire qui à chaque ensemble de nœuds associe un nœud de cet ensemble.

(3) **Sélection du lot d'offre.** Afin de déterminer le lot d'offre, on distingue une stratégie qui propose de déléguer une unique tâche comme dans [3] et une stratégie qui peut proposer plusieurs tâches.

(a) **Sélection d'une délégation unaire.** Afin de réduire les durées de réalisation, l'initiateur sélectionne une tâche distante, c'est-à-dire dont la délégation réduira son coût d'exécution. Notre heuristique sélectionne la tâche du job $J_*$ ou des jobs qui le précèdent dans $\vec{B}_i$ avec le meilleur gain en terme de coût. En cas d'égalité, c'est la tâche prioritaire du lot qui est choisie,

$$ \forall \mathcal{F}' \subseteq \mathcal{F}, \tau_* = \min_{\langle \downarrow_i \rangle} \left\{ \underset{\tau \in \mathcal{F}' \cap \mathcal{B}_i}{\operatorname{argmax}} c(\tau, v_i) - c(\tau, v_*) \right\} $$

La délégation $\delta([\tau_*], v_i, v_*, \vec{A})$ est déclenchée si elle est acceptable pour l'initiateur (cf. définition 5.1).

(b) **Sélection d'une délégation n-aire.** L'initiateur construit itérativement un lot d'offre $T_*$. Ce lot est une pile de tâches qui sera évaluée par la stratégie d'acceptation (cf. Section 5.4) pour que le receveur puisse refuser toute ou partie de ces tâches en dépilant le lot d'offre. Comme illustré dans l'algorithme 1, notre heuristique considère les tâches du job $J_*$ ou des jobs qui le précèdent dans $\vec{B}_i$ (ligne 2). L'initiateur $v_i$ sélectionne en priorité les tâches distantes, i.e. celles dont la délégation réduit le plus le coût d'exécution (lignes 3 et 6). Selon cet algorithme à cliquet, le délai de réalisation décroît strictement au cours de la construction du lot d'offre (ligne 8). De plus, la construction du lot d'offre est stoppée dès qu'une tâche candidate ne permet pas d'améliorer le délai de réalisation. Si le lot d'offre $T_*$ est non vide, alors la délégation $\delta(T_*, v_i, v_*, \vec{A})$, qui est acceptable pour l'initiateur, est déclenchée.
**Algorithme 1 :** Construction du lot d'offre par l'initiateur $v_i$

**Entrées :** $J_*$ le job sélectionné dans l'étape 1;

$v_*$ le receveur sélectionné dans l'étape 2;

1 $T_* \leftarrow \text{empty_stack}$;

2 $T = \{\tau \mid \text{job}(\tau) = J_* \lor (\text{job}(\tau) \triangleleft J_*)\}$;

3 $T' \leftarrow (\dots, \tau^k, \dots, \tau^l, \dots) \mid \tau^i \in T \land (k < l \iff c(\tau^k, v_i) - c(\tau^k, v_*) > c(\tau^l, v_i) - c(\tau^l, v_*)) / * \text{ la liste des tâches par gain de coût d'exécution décroissant } * /$

4 $\text{bestFlowtime} = C^i(\vec{A})$;

5 tant que $T' \neq \emptyset$ faire

6 $\tau_* \leftarrow \text{head}(T')$;

7 $T' \leftarrow \text{tail}(T')$;

8 si $C^i(\delta(T_* \cup \{\tau_*\}, v_i, v_*, \vec{A})) < \text{bestFlowtime}$ alors

9 $T_* . \text{push}(\tau_*)$;

10 $\text{bestFlowtime} \leftarrow C^i(\delta(T_*, v_i, v_*, \vec{A}))$;

11 fin

12 sinon

13 $\text{Retourner } T_*$;

14 fin

15 fin

16 $\text{Retourner } T_*$;

Quelque soit la stratégie de sélection du lot d'offre (3.a ou 3.b, si aucune délégation n'est déclenchée, la stratégie d'offre retourne dans l'étape 2 pour choisir un autre receveur ($N' \leftarrow N' \setminus \{v_*\}$). À défaut, la stratégie d'offre retourne dans l'étape 1 pour choisir un autre job ($J' \leftarrow J' \setminus \{J_*\}$). En cas d'échec, aucune délégation n'est proposée et l'agent passe en état de pause jusqu'à ce que sa base de croyances soit mise à jour et qu'une nouvelle opportunité (i.e. une délégation) soit trouvée.

## 5.4. STRATÉGIE D'ACCEPTATION

**Algorithme 2 :** Sélection par le receveur $v_*$ du sous-lot parmi le lot d'offre reçu

**Entrées :** $T_*$ le lot d'offre reçu

1 $T_{acc} \leftarrow T_*$;

2 tant que $\delta(T_{acc}, v_i, v_*, \vec{A})$ n'est pas acceptable par l'agent $v_*$ faire

3 $| T_{acc} . \text{pop}|$;

4 fin

5 $\text{Retourner } T_{acc}$;
Selon la **stratégie d'acceptation**, le receveur accepte une délégation qu'il considère acceptable. Dans le cas contraire, il dépile une à une les tâches du lot d'offre $T_*$ (cf. algorithme 2) pour éventuellement en accepter une partie. Quand le sous-lot $T_{acc}$ est vide, le receveur refuse l'offre.

## 5.5. COMPORTEMENT D'AGENT

Dans notre approche, une réallocation bilatérale de tâches est le résultat de négociations entre agents qui adoptent tous le même comportement. Les agents exécutent leur comportement selon leurs connaissances et croyances. Le comportement des agents est spécifié dans [5] par un automate fini déterministe(1). Afin d'éviter les interblocages, les propositions sont associées à des dates butoirs. La base de croyances de l'agent est mise à jour lors de la réception des messages. Aucune proposition n'est soumise tant que l'agent croit que l'allocation est stable. Les comportements des agents leur permettent d'exécuter des négociations concurrentes mais les offres sont traitées de manière séquentielle.

**Exemple 5.2 (Stratégie de négociation).** — Considérons le problème MASTA+ de l'exemple 3.7 et l'allocation initiale $\vec{A}$ (cf. Figure 5.1a) telle que $\vec{B}_1 = (\tau_5, \tau_1)$, $\vec{B}_2 = (\tau_3, \tau_2, \tau_7, \tau_8, \tau_9)$ et $\vec{B}_3 = (\tau_4, \tau_6)$. Le flowtime est $C(\vec{A}) = 7 + 9 + 17 = 33$. On considère ici que les agents ont des croyances à jour. La stratégie d'offre de l'agent $v_2$ sélectionne une délégation de la manière suivante :

(1) il sélectionne le job le plus prioritaire pour lequel il est limitant (cf. équation (5.5)), $J_* = J_3$;

(2) il sélectionne le receveur qui est le moins limitant pour $J_3$ (cf. équation (5.6)). Comme ni $v_1$ ni $v_3$ ne possèdent de tâche de $J_3$, l'agent $v_2$ choisit aléatoirement, $v_* = v_1$;

(3) l'algorithme 1 permet à l'agent $v_2$ de sélectionner son lot d'offre :

(a) les tâches candidates, c'est-à-dire les tâches de $J_3$ ou les précédentes dans son lot de tâches, sont triées par gain de coût décroissant, $T' = [\tau_9, \tau_3, \tau_2, \tau_8, \tau_7]$;

(b) la délégation de la tâche $\tau_9$ améliore la durée de réalisation (cf. figure 5.1b),

$$C^2(\delta([\tau_9], v_2, v_1, \vec{A})) = 11 + 9 + 9 = 29 < 33 \quad (5.7)$$

La tâche $\tau_9$ est ajoutée au lot d'offre, $T_* = [\tau_9]$,

(c) la délégation des tâches $\tau_3$ et $\tau_9$ améliore la durée de réalisation (cf. figure 5.1c),

$$C^2(\delta([\tau_9, \tau_3], v_2, v_1, \vec{A})) = 12 + 9 + 7 = 28 < 29 \quad (5.8)$$

La tâche $\tau_3$ est ajoutée au lot d'offre, $T_* = [\tau_9, \tau_3]$,

<footnote>(1) https://gitlab.univ-lille.fr/maxime.morge/smastaplus/-/tree/master/doc/specification.</footnote>
(d) la délégation des tâches $\tau_2$, $\tau_3$ et $\tau_9$ n'améliore pas la durée de réalisation (cf. figure 5.1c),

$$C^2(\delta([\tau_9, \tau_3, \tau_2], v_2, v_1, \vec{A})) = 15 + 9 + 6 = 30 > 28 \quad (5.9)$$

Le lot d'offre sélectionné est $T_* = [\tau_9, \tau_3]$.

En résumé, l'agent $v_2$ propose à $v_1$ la délégation $\delta([\tau_9, \tau_3], v_2, v_1, \vec{A})$.

<figure><img src="image_8.png" /><figcaption>FIGURE 5.1 – Allocations de l'exemple 5.2</figcaption></figure>

# 6. ÉVALUATION EMPIRIQUE

Après une présentation des conditions expérimentales, nous comparons empiriquement notre approche avec une heuristique classique ainsi qu'avec les techniques d'optimisation distribuée sous contraintes (DCOP). Nous évaluons également notre nouveau critère de rationalité ainsi que les délégations n-aires$^{(2)}$.

## 6.1. CONDITIONS EXPÉRIMENTALES

L'application pratique que nous considérons est le déploiement distribué du patron de conception MapReduce pour le traitement de jeux de données massives sur une

<footnote>$^{(2)}$Ces expérimentations sont reproductibles à partir des instructions suivantes : https://gitlab.univ-lille.fr/maxime.morge/smastaplus/-/tree/master/doc/experiments.</footnote>
grappe de serveurs, comme avec Spark [28]. Nous nous focalisons ici sur la phase *reduce* des jobs MapReduce que nous formalisons par un problème MASTA+ où plusieurs jobs sont soumis de façon concurrente. La fonction de coût est définie telle que :

$$c_i(\tau, v_j) = \sum_{\rho_j \in \mathcal{R}_\tau} c_i(\rho_j, v_j) \text{ avec } c_i(\rho_j, v_j) = \begin{cases} |\rho_j| & \text{si } v_i \in l(\rho_j) \\ \kappa \times |\rho_j| & \text{sinon} \end{cases} \quad (6.1)$$

où nous avons fixé empiriquement $\kappa = 2$ comme une valeur réaliste pour capturer le surcoût induit par la récupération des ressources distantes.

Notre prototype [5] est implémenté avec le langage de programmation Scala et la bibliothèque Akka [19] adaptée aux applications orientées messages, fortement concurrentes, distribuées et robustes. Nous supposons que : (a) le délai de transmission des messages est arbitraire mais non négligeable, (b) l'ordre des messages par paire émetteur-récepteur est préservé, (c) la distribution des messages est garantie. Les expériences ont été réalisées sur une lame munie de 20 CPUs avec 512 Go de RAM.

Ce travail est une première étape dans l'évaluation de nos stratégies, puisque nous comparons ici le calcul d'une réallocation, c'est-à-dire la résolution d'un problème MASTA+, sans les itérations induites par les consommations de tâches, même si la stratégie de consommation est nécessaire pour trier les lots de tâches de chaque agent. Nous considérons des instances de MASTA+ avec $m \in [2; 16]$ nœuds/agents, $\ell = 4$ jobs, $n = 3 \times \ell \times m$ tâches et une ressource par tâche. Chaque ressource $\rho_i$ est répliquée 3 fois et $|\rho_i| \in [0; 100]$. Nous générons 10 instances de MASTA+, et pour chacune nous générons aléatoirement 10 allocations initiales. Nous évaluons les médianes et les déviations standards de trois métriques : (1) la durée moyenne de réalisation (équation (3.8)), (2) le taux de disponibilité locale (équation (3.10)), et (3) le temps de réordonnancement.

## 6.2. HEURISTIQUE CLASSIQUE ET CRITÈRE DE RATIONALITÉ

Les hypothèses que nous voulons tester sont : (1) la durée moyenne de réalisation atteinte par notre stratégie est proche de celle obtenue par l'approche classique ; (2) la décentralisation de notre approche permet d'accélérer le réordonnancement. De plus, contrairement à nos précédents travaux [3] qui utilisaient comme critère de rationalité le *flowtime* local et le *makespan*, nous considérons dans cet article uniquement le *flowtime* global qui suffit à garantir la convergence du processus de négociation. Nous souhaitons également vérifier que ce critère de rationalité permet d'améliorer significativement la qualité de la solution obtenue.

Les figures 6.1a et 6.1b comparent respectivement la durée moyenne de réallocation et le temps de réordonnancement de notre stratégie de délégation unaire avec celle présentée dans [3] ainsi qu'avec un algorithme de montée en gradient qui débutent avec la même allocation initiale générée aléatoirement. À chaque étape, l'algorithme de montée en gradient sélectionne parmi toutes les délégations possibles celle qui minimise la durée moyenne de réalisation.
<figure><img src="image_9.png" /><figcaption>FIGURE 6.1 – Durée moyenne de réalisation et temps de réordonnancement pour notre stratégie, celle proposée dans [3] et l’algorithme de montée en gradient</figcaption></figure>
Dans la figure 6.1a, nous observons que si la qualité des solutions obtenues par la stratégie proposée dans [3] est légèrement inférieure à celle fournie par l’algorithme de montée en gradient, notre stratégie atteint desormais des solutions de qualité similaire. Cette différence s’explique par le fait qu’une réallocation socialement rationnelle vis-à-vis du *flowtime* global ne peut que strictement améliorer la durée moyenne de réalisation, ce qui n’est pas le cas lorsque l’on utilise le *flowtime* local comme critère de rationalité. De plus, le fait que la réduction du *makespan* ne soit plus imposée par le critère de rationalité permet d’élargir le nombre de délégations possibles pouvant améliorer la durée moyenne de réalisation.

Dans la figure 6.1b, nous observons que le temps de réordonnancement pour notre nouvelle stratégie reste approximativement identique et donc largement meilleur que celui de l’algorithme de montée en gradient qui croît exponentiellement avec le nombre de noeuds. Le critère de rationalité proposé dans cet article permet donc d’améliorer significativement la durée moyenne de réalisation avec un temps de réordonnancement similaire. Il est à noter que l’algorithme de montée en gradient n’a été évalué que sur des instances MASTA+ de petites tailles en raison de son temps de réordonnancement rédhibitoire. On peut s’attendre à avoir un temps de réordonnancement plus grand avec une méthode de recherche locale telle que le recuit simulé sans pour autant avoir de garanties sur la qualité du résultat. Par conséquent, même si le nombre d’agents est faible, le gain réalisé sur la durée moyenne de réalisation par réordonnancement via l’algorithme de montée en gradient sera pénalisé et annulé par le surcoût du temps de réordonnancement. Ce surcoût pénalise l’équilibrage en continu des charges dans un système distribué qui devrait s’adapter aux phénomènes perturbateurs (consommation de tâches, libération de jobs, ralentissement des noeuds).

La figure 6.2 compare le taux de disponibilité locale de l’allocation initiale et des allocations obtenues par notre stratégie, par celle proposée dans [3] et par l’algorithme de montée en gradient. On observe que le taux de disponibilité des allocations obtenues par nos stratégies est proche de celui obtenu avec l’algorithme de montée en gradient. Même si, contrairement à ce dernier, notre stratégie n’évalue pas toutes les délégations unaires possibles, elle s’avère efficace en sélectionnant les tâches distantes dont la délégation réduit le coût.

La figure 6.3 compare le temps de réordonnancement de notre stratégie avec un ou plusieurs *threads* d’exécution et celui de l’algorithme de montée en gradient. Comme la version de notre stratégie avec plusieurs *threads* est exécutée sur plusieurs cœurs, nous observons que l’accélération de notre algorithme augmente en fonction du nombre d’agents. Par exemple, avec une durée moyenne de réalisation similaire (si on néglige le non déterminisme observable de leurs exécutions), la version *multi-threads* est 10 fois plus rapide que la version *mono-thread* pour 16 agents.

## 6.3. DÉLÉGATION N-AIRES

Nous souhaitons ici vérifier que les délégations n-aires permettent de réduire le temps de réordonnancement.
<figure><img src="image_10.png" /><figcaption>FIGURE 6.2 – Taux de disponibilité locale de l’allocation initiale et des allocations obtenues par notre stratégie, par celle proposée dans [3] et par l’algorithme de montée en gradient</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>FIGURE 6.3 – Temps de réordonnancement de notre stratégie avec un ou plusieurs threads d’exécution et de l’algorithme de montée en gradient</figcaption></figure>
Les figures 6.4a et 6.4b comparent respectivement la durée moyenne de réallocation et le temps de réordonnancement de notre stratégie de délégation unaire avec celle notre stratégie de délégation *n*-aire. Nous observons que, si la durée moyenne de réalisation atteinte par la stratégie de délégation *n*-aire est légèrement moins bonne que pour la stratégie de délégation unaire, le gain en terme de temps de réordonnancement est en revanche très avantageux.

La figure 6.5 représente l'évolution de la durée moyenne de réalisation de ces deux stratégies de sélection du lot d'offre pour une instance quelconque non équilibrée de problème de réallocation. On observe que la sélection d'une délégation *n*-aire réduit le nombre de délégations (ici 40 plutôt que 66) pour atteindre des allocations stables dont les durées moyennes de réalisation sont similaires. En conséquence, la sélection d'une délégation *n*-aire réduit le temps de réordonnancement (ici 0, 35 seconde plutôt que 1, 8 seconde).

## 6.4. OPTIMISATION DISTRIBUÉE SOUS CONTRaintES

Nous souhaitons ici vérifier que le temps de réordonnancement de notre stratégie de négociation est beaucoup plus faible que celui obtenu par des techniques d'optimisation distribuée sous contraintes (DCOP) et qu'elle permet d'atteindre des durées de réalisation plus faibles.

Trouver l'allocation optimale est un problème d'ordonnancement qui minimise le flowtime de $\ell$ jobs, constitués de $n$ tâches, sur $m$ nœuds indépendants. Il peut être modélisé mathématiquement de la manière suivante :

(1) $n$ variables de décision $x_i$ telles que,

$$x_i = (o-1) \times n + k \quad \text{si } \tau_i \text{ est la } k^{\text{e}} \text{ tâche à partir de la fin sur } v_o \quad (6.2)$$

(2) $n^2$ contraintes pour que chaque tâche soit affectée à une unique position

$$\forall i \in [1, n] \forall j \in [1, n] \setminus \{i\} x_i \neq x_j; \quad (6.3)$$

(3) la fonction objectif à minimiser est $C(\vec{A})$.

$$\begin{align}
C(\vec{A}) &= \sum_{J \in \mathcal{J}} C_J(\vec{A}) \nonumber \\
&= \sum_{J \in \mathcal{J}} \max_{v_i \in N} C_{last}(v_i, J)(\vec{A}) \tag{6.4}
\end{align}$$

où $last(v_i, J)$ est la dernière tâche du job J dans le lot de tâches de $\vec{B}_i$ :

$$last(v_i, J) = \underset{\tau_k \in J \cap B_i}{\operatorname{argmax}} \operatorname{card}(\{\tau \in \vec{B}_i \mid \tau < i \ \tau_k\}) \quad (6.5)$$

Pour résoudre ce problème, nous considérons l'algorithm MGM2 [20] – Maximum Gain Message – comme le plus adapté, car c'est un algorithme distribué de recherche locale qui est approché et asynchrone. Nous avons utilisé la bibliothèque pyDCOP [22, 23]. Nous considérons 100 problèmes de réallocation pour des instances de MASTA+ avec $m = 2$ nœuds, $\ell = 4$ jobs et $n = \ell \times m = 8$ tâches.
<figure><img src="image_12.png" /><figcaption>FIGURE 6.4 – Durée moyenne de réalisation et temps d'ordonnancement pour notre stratégie de délégation unaire et notre stratégie de délégation n-aire</figcaption></figure>
<figure><img src="image_13.png" /><figcaption>(a) Durée moyenne de réalisation des stratégies de délégation unaire et *n*-aire au cours des déléga-
tions</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>(b) Durée moyenne de réalisation de la stratégie de délégation unaire et n-aire au cours du temps</figcaption></figure>

FIGURE 6.5 – Durée moyenne de réalisation des stratégies de délégation unaire et n-aire au cours des délégations (en haut) et du temps (en bas)
La figure 6.6 compare les durées moyennes de réalisation pour des réallocations obtenues par notre stratégie en 55 millisecondes (en moyenne) avec l’algorithme MGM2 dont le *timeout* est respectivement 2, 5 et 10 secondes. On peut noter que l’algorithme MGM2 propose systématique une réallocation quand le *timeout* est de 5 ou 10 secondes mais jamais avec un *timeout* de 2 secondes. Dans ce cas, nous considérons que l’allocation initiale générée de manière pseudo-aléatoire est conservée. Au-delà des temps de réordonnancement qui peuvent s’expliquer par le fait que MGM2 est implémenté en Python et notre stratégie s’exécute sur la machine virtuelle Java [13], nos expériences montrent que même si le *timeout* est de 5 secondes, l’algorithme MGM2 retourne une réallocation où la durée moyenne de réalisation est supérieure à celle obtenue par notre stratégie. Accroître le *timeout* ne permet pas d’améliorer la durée moyenne de réalisation des allocations retournées par MGM2. Notons que l’algorithme MGM2 ne propose jamais de réallocation avec $m = 3$ nœuds, $l = 5$ jobs et $n = 3 \times l \times m = 45$ tâches quand le *timeout* est de 15 minutes. Cet algorithme ne passe pas l’échelle sur ce type de problème.

<figure><img src="image_15.png" /><figcaption>FIGURE 6.6 – Diagrammes en boîte des durées moyennes de réalisation pour les réallocations obtenues par notre stratégie en 55 millisecondes (en moyenne) avec l’algorithme MGM2 dont le *timeout* est respectivement 2, 5 et 10 secondes</figcaption></figure>

## 7. CONCLUSION

Dans cet article, nous avons proposé un système multi-agents pour la réallocation de tâches sur des nœuds en fonction de la localisation des ressources nécessaires afin de réduire la durée moyenne de réalisation de jobs concurrents. Nos expériences montrent que la durée moyenne de réalisation atteinte par notre stratégie est proche de
celle atteinte par l'approche heuristique classique et qu'elle réduit considérablement
le temps de réordonnancement. Cela est dû au fait que le processus de négociation
adapte en continu l'allocation afin d'améliorer l'équilibre des charges en réduisant
les durées de réalisation des jobs pour les nœuds qui sont limitants. D'une part, la
stratégie de consommation consiste à exécuter d'abord les tâches des jobs les moins
coûteux avant celles des jobs les plus coûteux. D'autre part, la stratégie de délégation
consiste à sélectionner un job qui permet de réduire les durées de réalisation du
proposant en choisissant un répondant qui n'est pas limitant pour les jobs impactés et
en choisissant des tâches distantes dont la délégation réduit le coût d'exécution. Nous
avons également comparé notre approche avec les techniques d'optimisation distribuée
sous contraintes (DCOP), en particulier l'algorithme MGM2 pour lequel les temps de
réordonnancement et les durées moyennes de réalisation sont très supérieures.

Une analyse de sensibilité pour étudier l'influence du facteur de réplication va au-delà de la portée de cet article, mais mériterait une étude approfondie. Notre approche passe l'échelle, car elle gère un grand nombre de tâches grâce à des décisions locales des agents à propos de la prochaine tâche à déléguer/exécuter. En outre, le surcoût de la négociation est négligeable par rapport au bénéfice de l'équilibrage des charges, car aucune négociation n'est déclenchée lorsque les agents estiment que l'allocation est stable.

Comme notre cadre de négociation le permet, nous envisageons d'ajouter une
stratégie de contre-proposition pour sélectionner une contre-partie susceptible de dé-
clencher des échanges de tâches afin d'améliorer la durée moyenne de réalisation des
jobs. D'une manière générale, les travaux futurs doivent étendre le processus de réal-
location des tâches vers un processus itératif, dynamique et continu, qui se déroule de
manière concurrente à l'exécution des tâches, pour permettre au système distribué de
s'adapter aux phénomènes perturbateurs (consommation de tâches, libération de jobs,
ralentissement des nœuds).

REMERCIEMENTS

Nous adressons nos remerciements aux relecteurs pour leur travail minutieux et
leurs précieux conseils.

BIBLIOGRAPHIE

[1] Q. BAERT, A.-C. CARON, M. MORGE, J.-C. ROUTIER & K. STATHIS, « An adaptive multi-agent system for task reallocation in a MapReduce job », Journal of Parallel and Distributed Computing 153 (2021), p. 75-88.

[2] E. BEAUPREZ, L. BIGAND, A.-C. CARON, M. MORGE & J.-C. ROUTIER, « Réaffectation de tâches de la théorie à la pratique : état de l'art et retour d'expérience », in *Vingt-neuvièmes journées francophones sur les systèmes multi-agents*, JFSMA 2021, Bordeaux, France, 28-30 juin 2021, JFSMA, Cépaduès, 2021, p. 51-60.

[3] E. BEAUPREZ, A.-C. CARON, M. MORGE & J.-C. ROUTIER, « Une stratégie de négociation multi-agents pour réduire la durée moyenne de réalisation », in *Vingt-neuvièmes journées francophones sur les systèmes multi-agents*, JFSMA 2021, Bordeaux, France, 28-30 juin 2021, JFSMA, Cépaduès, 2021, p. 31-40.
[4] ———, « A Multi-Agent Negotiation Strategy for Reducing the Flowtime », in *Proceedings of the 13th International Conference on Agents and Artificial Intelligence – Volume 1: ICAART*, INSTICC, SciTePress, 2021, p. 58-68.

[5] E. BEAUPREZ & M. MORGE, « Scala implementation of the Extended Multi-agents Situated Task Allocation », https://gitlab.univ-lille.fr/maxime.morge/smastaplus, 2020.

[6] A. BEYNIER, F. CHARPILLET, D. SZER & A.-I. MOUADDIB, « DEC-MDP / DEC-POMDP », in *Markov Decision Processes in Artificial Intelligence* (O. S. Olivier Buffet, éd.), Wiley-ISTE, 2010, p. 277-313.

[7] J. BRUNO, E. G. COFFMAN JR. & R. SETHI, « Scheduling Independent Tasks to Reduce Mean Finishing Time », *Commun. ACM* **17** (1974), n° 7, p. 382-387.

[8] B. CHEN, C. N. POTTS & G. J. WOEGINGER, « A review of machine scheduling: Complexity, algorithms and approximability », in *Handbook of combinatorial optimization* (D.-Z. Du & P. M. Pardalos, éds.), Springer, 1998, p. 1493-1641.

[9] H.-L. CHOI, L. BRUNET & J. P. How, « Consensus-based decentralized auctions for robust task allocation », *IEEE transactions on robotics* **25** (2009), n° 4, p. 912-926.

[10] R. W. CONWAY, W. L. MAXWELL & L. W. MILLER, *Theory of Scheduling*, Addison-Wesley, Reading, MA, 1967.

[11] U. ENDRISS, N. MAUDET, F. SADRI & F. TONI, « Negotiating Socially Optimal Allocations of Resources », *Journal of Artificial Intelligence Research* **25** (2006), p. 315-348.

[12] F. FIORETTO, E. PONTELLI & W. YEOH, « Distributed constraint optimization problems and applications: A survey », *Journal of Artificial Intelligence Research* **61** (2018), p. 623-698.

[13] B. FULGHAM & I. GOUY, « The Computer Language Benchmarks Game », https://benchmarksgame-team.pages.debian.net/benchmarksgame/index.html, 2021.

[14] W. HORN, « Minimizing average flow time with parallel machines », *Operations Research* **21** (1973), n° 3, p. 846-847.

[15] Y. JIANG, « A survey of task allocation and load balancing in distributed systems », *IEEE Transactions on Parallel and Distributed Systems* **27** (2016), n° 2, p. 585-599.

[16] H. W. KUHN, « The Hungarian method for the assignment problem », *Naval research logistics quarterly* **2** (1955), n° 1-2, p. 83-97.

[17] V. LESSER, K. DECKER, T. WAGNER, N. CARVER, A. GARVEY, B. HORLING, D. NEIMAN, R. PODOROZHNY, M. N. PRASAD, A. RAJA, R. VINCENT & X. Q. XUAN, P. ZHANG, « Evolution of the GPGP/TAEMS domain-independent coordination framework », *Autonomous agents and multi-agent systems* **9** (2004), n° 1-2, p. 87-143.

[18] S. LI, R. R. NEGENBORN & G. LODEWIJKS, « A Distributed Constraint Optimization Approach for Vessel Rotation Planning », in *Computational Logistics*, Springer, 2014, p. 61-80.

[19] LIGHTBEND, « Akka is the implementation of the Actor Model on the JVM », http://akka.io, 2020.

[20] R. T. MAHESWARAN, J. P. PEARCE & M. TAMBE, « Distributed Algorithms for DCOP: A Graphical-Game-Based Approach », in *Proceedings of the ISCA 17th International Conference on Parallel and Distributed Computing Systems, September 15-17, 2004, The Canterbury Hotel, San Francisco, California, USA* (D. A. Bader & A. A. Khokhar, éds.), ISCA, 2004, p. 432-439.

[21] A. RUBINSTEIN, « Perfect Equilibrium in a Bargaining Model », *Econometrica* **50** (1982), n° 1, p. 97-109.

[22] P. RUST & G. PICARD, « pyDCOP is a python library for Distributed Constraints Optimization », https://github.com/Orange-OpenSource/pyDcop, 2021.

[23] P. RUST, G. PICARD & F. RAMPARANY, « Mise en place d'une décision collective résiliente sur une infrastructure IoT à l'aide du framework PyDCOP (démonstration) », in *Vingt-sixièmes journées francophones sur les systèmes multi-agents, JFSMA 2018, Métabief, France, 10-12 Octobre 2018*, JFSMA, Cépaduès, 2018, p. 223-224.

[24] A. SCHAERF, Y. SHOHAM & M. TENNENHOLTZ, « Adaptive Load Balancing : A Study in Multi-Agent Learning », *Journal of Artificial Intelligence Research* **2** (1995), p. 475-500.

[25] O. SHEHORY & S. KRAUS, « Methods for task allocation via agent coalition formation », *Artificial Intelligence* **101** (1998), n° 1-2, p. 165-200.

[26] J. TURNER, Q. MENG, G. SCHAEFER & A. SOLTOGGIO, « Distributed Strategy Adaptation with a Prediction Function in Multi-Agent Task Allocation », in *Proc. of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS)*, 2018, p. 739-747.
[27] M. P. WELLMAN, « A market-oriented programming environment and its application to distributed multicommodity flow problems », *Journal of Artificial Intelligence Research* 1 (1993), p. 1-23.

[28] M. ZAHARIA, M. CHOWDHURY, T. DAS, A. DAVE, J. MA, M. McCAULY, M. J. FRANKLIN, S. SHENKER & I. STOICA, « Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing », in *Proc. of the 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI)*; San Jose, CA, USA, 2012, p. 15-28.

**ABSTRACT.** — In this paper, we study the problem of task reallocation for load-balancing in distributed data processing models that tackle vast amount of data. We propose a strategy based on cooperative agents used to optimize the rescheduling of tasks in multiple jobs which must be executed as soon as possible. It allows agents to determine locally the next tasks to process, to delegate, eventually to swap according to their knowledge, their own belief base and their peer modelling. The novelty lies in the ability of agents to identify opportunities and bottleneck agents, and afterwards to reassign some bundles of tasks thanks to concurrent bilateral negotiations. The strategy adopted by the agents allows to warrant a continuous improvement of the flowtime. Our experimentation reveals that our strategy reaches a flowtime which is better than the one reached by a DCOP resolution, close to the one reached by the classical heuristic approach, and significantly reduces the rescheduling time.

**KEYWORDS.** — Multi-Agents Systems, Distributed Problem Solving, Agent-based Negotiation.