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 bilatérales concurrentes. 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.
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.
Accepté le :
Publié le :
Keywords: Multi-Agents Systems, Distributed Problem Solving, Agent-based Negotiation.
Ellie Beauprez 1 ; Anne-Cécile Caron 1 ; Maxime Morge 1 ; Jean-Christophe Routier 1
CC-BY 4.0
@article{ROIA_2023__4_2_193_0,
author = {Ellie Beauprez and Anne-C\'ecile Caron and Maxime Morge and Jean-Christophe Routier},
title = {D\'el\'egation de lots de t\^aches pour la r\'eduction de la dur\'ee moyenne de r\'ealisation},
journal = {Revue Ouverte d'Intelligence Artificielle},
pages = {193--221},
publisher = {Association pour la diffusion de la recherche francophone en intelligence artificielle},
volume = {4},
number = {2},
year = {2023},
doi = {10.5802/roia.62},
language = {fr},
url = {https://roia.centre-mersenne.org/articles/10.5802/roia.62/}
}
TY - JOUR AU - Ellie Beauprez AU - Anne-Cécile Caron AU - Maxime Morge AU - Jean-Christophe Routier TI - Délégation de lots de tâches pour la réduction de la durée moyenne de réalisation JO - Revue Ouverte d'Intelligence Artificielle PY - 2023 SP - 193 EP - 221 VL - 4 IS - 2 PB - Association pour la diffusion de la recherche francophone en intelligence artificielle UR - https://roia.centre-mersenne.org/articles/10.5802/roia.62/ DO - 10.5802/roia.62 LA - fr ID - ROIA_2023__4_2_193_0 ER -
%0 Journal Article %A Ellie Beauprez %A Anne-Cécile Caron %A Maxime Morge %A Jean-Christophe Routier %T Délégation de lots de tâches pour la réduction de la durée moyenne de réalisation %J Revue Ouverte d'Intelligence Artificielle %D 2023 %P 193-221 %V 4 %N 2 %I Association pour la diffusion de la recherche francophone en intelligence artificielle %U https://roia.centre-mersenne.org/articles/10.5802/roia.62/ %R 10.5802/roia.62 %G fr %F ROIA_2023__4_2_193_0
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, Post-actes des Journées Francophones sur les Systèmes Multi-Agents (JFSMA 2021), Volume 4 (2023) no. 2, pp. 193-221. doi : 10.5802/roia.62. https://roia.centre-mersenne.org/articles/10.5802/roia.62/
[1] An adaptive multi-agent system for task reallocation in a MapReduce job, Journal of Parallel and Distributed Computing, Volume 153 (2021), pp. 75-88 | DOI
[2] Réaffectation de tâches de la théorie à la pratique : état de l’art et retour d’expérience, 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), pp. 51-60
[3] Une stratégie de négociation multi-agents pour réduire la durée moyenne de réalisation, 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), pp. 31-40
[4] A Multi-Agent Negotiation Strategy for Reducing the Flowtime, Proceedings of the 13th International Conference on Agents and Artificial Intelligence – Volume 1 : ICAART,, SciTePress, INSTICC (2021), pp. 58-68 | DOI
[5] Scala implementation of the Extended Multi-agents Situated Task Allocation (2020) (https://gitlab.univ-lille.fr/maxime.morge/smastaplus)
[6] DEC-MDP / DEC-POMDP, Markov Decision Processes in Artificial Intelligence (Olivier Sigaud Olivier Buffet, ed.), Wiley-ISTE, 2010, pp. 277-313
[7] Scheduling Independent Tasks to Reduce Mean Finishing Time, Commun. ACM, Volume 17 (1974) no. 7, pp. 382-387 | DOI | MR | Zbl
[8] A review of machine scheduling : Complexity, algorithms and approximability, Handbook of combinatorial optimization (Ding-Zhu Du; Panos M. Pardalos, eds.), Springer, 1998, pp. 1493-1641 | DOI
[9] Consensus-based decentralized auctions for robust task allocation, IEEE transactions on robotics, Volume 25 (2009) no. 4, pp. 912-926 | DOI
[10] Theory of Scheduling, Addison- Wesley, Reading, MA, 1967
[11] Negotiating Socially Optimal Allocations of Resources, Journal of Artificial Intelligence Research, Volume 25 (2006), pp. 315-348 | DOI | MR
[12] Distributed constraint optimization problems and applications : A survey, Journal of Artificial Intelligence Research, Volume 61 (2018), pp. 623-698 | DOI | MR | Zbl
[13] The Computer Language Benchmarks Game (2021) (Accessed April 22, 2021 https://benchmarksgame-team.pages.debian.net/benchmarksgame/index.html)
[14] Minimizing average flow time with parallel machines, Operations Research, Volume 21 (1973) no. 3, pp. 846-847 | DOI | Zbl
[15] A survey of task allocation and load balancing in distributed systems, IEEE Transactions on Parallel and Distributed Systems, Volume 27 (2016) no. 2, pp. 585-599 | DOI
[16] The Hungarian method for the assignment problem, Naval research logistics quarterly, Volume 2 (1955) no. 1-2, pp. 83-97 | DOI | MR | Zbl
[17] Evolution of the GPGP/TAEMS domain-independent coordination framework, Autonomous agents and multi-agent systems, Volume 9 (2004) no. 1-2, pp. 87-143 | DOI
[18] A Distributed Constraint Optimization Approach for Vessel Rotation Planning, Computational Logistics, Springer (2014), pp. 61-80 | DOI
[19] Akka is the implementation of the Actor Model on the JVM (2020) (http://akka.io)
[20] Distributed Algorithms for DCOP : A Graphical-Game-Based Approach, Proceedings of the ISCA 17th International Conference on Parallel and Distributed Computing Systems, September 15-17, 2004, The Canterbury Hotel, San Francisco, California, USA (David A. Bader; Ashfaq A. Khokhar, eds.), ISCA (2004), pp. 432-439
[21] Perfect Equilibrium in a Bargaining Model, Econometrica, Volume 50 (1982) no. 1, pp. 97-109 | DOI | MR | Zbl
[22] pyDCOP is a python library for Distributed Constraints Optimization (2021) (https://github.com/Orange-OpenSource/pyDcop)
[23] Mise en place d’une décision collective résiliente sur une infrastructure IoT à l’aide du framework PyDCOP (démonstration), 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), pp. 223-224
[24] Adaptive Load Balancing : A Study in Multi-Agent Learning, Journal of Artificial Intelligence Research, Volume 2 (1995), pp. 475-500 | DOI | Zbl
[25] Methods for task allocation via agent coalition formation, Artificial Intelligence, Volume 101 (1998) no. 1-2, pp. 165-200 | DOI | MR | Zbl
[26] Distributed Strategy Adaptation with a Prediction Function in Multi-Agent Task Allocation, Proc. of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS) (2018), pp. 739-747
[27] A market-oriented programming environment and its application to distributed multicommodity flow problems, Journal of Artificial Intelligence Research, Volume 1 (1993), pp. 1-23 | DOI | Zbl
[28] Resilient Distributed Datasets : A Fault-Tolerant Abstraction for In-Memory Cluster Computing, Proc. of the 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI) ; San Jose, CA, USA (2012), pp. 15-28
Cité par Sources :