Le problème Rm||Cmax consiste à allouer un ensemble de tâches à $m$ agents de sorte à minimiser le makespan de l'allocation, c'est-à-dire le temps d'exécution de l'ensemble des tâches. Ce problème est connu pour être NP-dur dès que les tâches sont allouées à deux agents ou plus (m <= 2). De plus, il est souvent admis que le coût d'une tâche est précisément estimé pour un agent et que ce coût ne varie pas au cours de l'exécution des tâches. Dans cette thèse, je propose une approche décentralisée et dynamique pour l'amélioration d'une allocation de tâches. Ainsi, à partir d'une allocation initiale et pendant qu'ils exécutent les tâches, les agents collaboratifs initient de multiples enchères pour réallouer les tâches qui restent à exécuter. Ces réallocations sont socialement rationnelles, c'est-à-dire qu'un agent accepte de prendre en charge une tâche initialement allouée à un autre agent si la délégation de cette tâche bénéficie à l'ensemble du système en faisant décroître le makespan. De plus, le dynamisme du procédé permet d'améliorer une allocation malgré une fonction de coût peu précise et malgré les variations de performances qui peuvent survenir lors de l'exécution des tâches. Cette thèse offre un cadre formel pour la modélisation et la résolution multi-agents d'un problème de réallocation de tâches situées. Dans un tel problème, la localité des ressources nécessaires à l'exécution d'une tâche influe sur son coût pour chaque agent du système. À partir de ce cadre, je présente le protocole d'interaction des agents et je propose plusieurs stratégies pour que les choix des agents aient le plus d'impact sur le makespan de l'allocation courante. Dans le cadre applicatif de cette thèse, je propose d'utiliser ce processus de réallocation de tâches pour améliorer le patron de conception MapReduce. Très utilisé pour le traitement distribué de données massives, MapReduce possède néanmoins des biais que la réallocation dynamique des tâches peut aider à contrer. J'ai donc implémenté un prototype distribué qui s'inscrit dans le cadre formel et implémente le patron de conception MapReduce. Grâce à ce prototype, je suis en mesure d'évaluer l'apport du processus de réallocation et l'impact des différentes stratégies d'agent.
Composition du jury proposé M. Jean-Christophe ROUTIER Université de Lille Directeur de thèse Mme Amal EL FALLAH SEGHROUCHNI Paris Sorbonne Rapporteur M. Laurent VERCOUTER INSA Rouen Rapporteur Mme Anne-Cécile CARON Université de Lille Co-directeur de thèse M. Maxime MORGE Université de Lille Co-directeur de thèse Mme Salima HASSAS UCB Lyon 1 Examinateur M. Nicolas MAUDET Paris Sorbonne Examinateur
Thèse de l'équipe SMAC soutenue le 13/09/2019
français
English