Hosam Hanna

Le Problème de l’Allocation des Tâches (PAT) peut être caractérisé par un ensemble d’agents à ressources limitées qui doivent repartir et exécuter un ensemble de tâches de façon à maximiser le gain du système. Ce problème a été largement abordé pour différents contextes : système centralisé, décentralisé ou par la formation des coalitions. Cependant, ces approches ignorent le comportement incertain des agents. En fait, quand la consommation des ressources est incertaine, l’agent n’est pas sûr de pouvoir exécuter toutes les tâches qui lui sont allouées. Donc, l’allocation d’une tâche à un agent ne représente plus un gain réel pour le système mais un gain espéré. L’objectif des agents est par conséquent d’allouer les tâches de façon à maximiser le gain espéré. Nous focalisons dans cet exposé sur l’utilisation du Processus Décisionnel de Markov (PDM) pour la maximisation du gain espéré. Nous formalisons le PAT en PDM Centralisé (PDMC) et nous montrons qu’une allocation optimale des tâches peut être obtenue une fois le PDMC résolu. Comme la résolution d’un tel PDMC est une opération très coûteuse, nous re-formalisons le PAT en PDMs Distribués (PDMD). Ce dernier est dérivé du PDMC par la distribution de l’espace d’états et de la fonction du gain. L’interaction entre agents leur permettra de coordonner leur PDMds et en obtenir par conséquent une allocation des tâches sans conflits. Nous présentons une démonstration mathématique de l’équivalence entre l’allocation des tâches obtenue d’une façon centralisée et celle obtenue via les PDMDs coordonnés.