Ordonnancement multiprojet à contraintes de ressources partagées par plusieurs agents Meya Haroune, Cheikh Dhib, Emmanuel Neron, Ameur Soukhal, Hafedh Mohamed Babou, Mohamedade Nanne To cite this version: Meya Haroune, Cheikh Dhib, Emmanuel Neron, Ameur Soukhal, Hafedh Mohamed Babou, et al.. Ordonnancement multiprojet à contraintes de ressources partagées par plusieurs agents. Recherche Opérationnelle et d’Aide à la Décision (ROADEF), Feb 2020, Montpellier, France. ฀hal-02559669฀ HAL Id: hal-02559669 https://hal.archives-ouvertes.fr/hal-02559669 Submitted on 30 Apr 2020 HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published 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. Ordonnancement multiprojet à contraintes de ressources partagées par plusieurs agents Meya HAROUNE1,2 , Cheikh DHIB2 , Emmanuel NERON1 , Ameur SOUKHAL1 , Hafedh MOHAMED BABOU2 , Mohamedade NANNE2 1 Université de Tours, Laboratoire d’Informatique Fondamentale et Appliquée de Tours LIFAT ROOT ERL-CNRS 7002, France(2) meya.haroune@etu.univ-tours.fr,{emmanuel.neron, ameur.soukhal}@univ-tours.fr 2 Université de Nouakchott, Unité de recherche Documents Numériques et Interaction de l’Université de Nouakchott, Mauritanie dhib.cheikh@iscae.mr, hafedh.mohamed-babou@esp.mr, farouk@una.mr Mots-clés : Planification de projets, Ordonnancement multiagent, Programmation linéaire, Heuristiques, Recherche Tabou. 1 Introduction et description du problème Dans cette étude, plusieurs chefs de projet, chacun gérant un ou plusieurs projets, sont en concurrence pour obtenir les ressources humaines nécessaires à l’exécution de leurs projets. L’affectation des personnes pour l’ordonnancement des activités doit permettre d’optimiser une fonction objectif propre à chaque chef de projets. Il s’agit donc d’un problème d’ordonnancement ou chacun a son propre ensemble d’activités à réaliser. La fonction objectif d’un chef de projets dépend uniquement de l’ordonnancement de ses propres activités. Nous cherchons alors une bonne solution de compromis. Il s’agit d’un problème d’ordonnancement multiagent dans un contexte de gestion de projets [1]. Dans [1], les auteurs ont identifié quatre scénarios de problèmes d’ordonnancement multiagent : Symétrique, Compétition, Interférant et Non-Disjoint. Ces différents cas sont classés selon la relation des sous-ensembles des activités des agents (s’ils partagent ou non certaines activités). Dans cette étude, nous considérons le scénario ”Compétition”, i.e. un problème d’ordonnancement de projet multiagents où les sous-ensembles des activités de chaque agent sont disjoints. La démarche développée dans ce résumé, est valable pour un nombre d’agents quelconque, mais pour faciliter la lecture, elle est illustrée pour 2 agents (chefs de projets), A et B. Les l projets sont donc répartis en deux sous-ensembles indépendants et doivent être planifiés sur un horizon de temps fixé, exprimé en nombre de semaines. Chaque semaine est décomposée en 10 demi-journées. Nous supposons que les {1, ..., lA } (resp. {lA + 1, ..., l}) premiers (resp. derniers) projets sont ceux de l’agent A (resp. B). Un projet l est constitué d’un ensemble de phases. Chaque phase k d’un projet l est définie par un ensemble d’activités préemptives et indépendantes et doit être réalisée avant une date de fin souhaitée dlk (numéro de semaine). Dans cette étude, une seule phase par projet est considérée. Pour simplifier l’écriture, nous notons par dl la semaine échue commune des activités du même projet. Sans perte de généralité, nous supposons que {J1 , . . . , JnA } (resp. {JnA + 1, . . . , Jn }) est l’ensemble des nA (resp. n − nA ) activités de l’agent A (resp. B) à réaliser. Pour chaque activité Ji , nous avons donc : une charge estimée pi en jour.homme, une date de début au plus tôt ri , une date échue commune aux activités du même projet dl et une pénalité de retard wi . Les périodes de disponibilité des personnes par semaine sont connues. A un instant t donné, une personne Mj ne peut traiter qu’une seule activité à la fois. Chaque personne dispose d’un niveau d’efficacité pour la réalisation d’une activité qu’elle maîtrise (i.e. compétence 6= 0). Ainsi, la charge nominale d’une activité est calculée en fonction de l’efficacité de la personne en charge de son traitement. On définit la charge de l’activité Ji affectée à la personne Mj comme suit : pi,j = (2 − vi,j )pi , où vi,j est le niveau d’efficacité de la ressource Mj dans l’exercice de l’activité Ji , 0 ≤ vi,j ≤ 1. Le nombre d’activités affectées à une personne durant la même semaine est borné par une valeur donnée bj . Ainsi, une charge minimale et une autre maximale par activité sont définies permettant d’encadrer les quantités de sa réalisation par semaine. Une activité est affectée à une seule personne tout au long de sa réalisation. Une solution à ce problème consiste à trouver une affectation des personnes aux différentes activités des projets en définissant par personne une quotité allouée à chaque projet, i.e. définir le taux de participation d’une personne à chaque projet. Par cette affectation, nous cherchons une solution de meilleur compromis minimisant P A la somme P pondérée des retards des activités de chaque agent A et B, notées : f A = ni=1 wi Ti et f B = ni=nA +1 wi Ti . Noter qu’une activité d’un projet l en retard d’une unité de temps (Ti = 1) peut se terminer en début ou en fin de la semaine dl + 1. Ce problème est N P-difficile, car le cas particulier où nous cherchons l’affectation des personnes aux projets selon des quotités fixées a été montré N P-difficile [2]. 2 Approches de résolution : exactes et approchées Pour calculer une solution de Pareto strictement non-dominée, deux approches de résolution sont considérées : combinaison linéaire des critères et ε-contrainte. Lorsque la combinaison linéaire des critères est considérée, par la réécriture de la fonction objectif, nous montrons que le problème étudié est équivalent au cas monocritère, où l’objectif est la minimisation de la somme pondérée des retards des activités. Cette réécriture permet de définir les nouveaux poids de chaque activité à ordonnancer en fonction des coefficients de la combinaison linéaire choisis. Ainsi, les méthodes de résolution exactes et approchées développées dans [2] peuvent donc être appliquées. Lorsque l’approche ε-contrainte est considérée, le problème consiste à trouver une solution minimisant la somme pondérée des retards des activités de l’agent A (M ininimserf A ) sous-contrainte f B ≤ QB . Nous proposons d’adapter les méthodes développées dans le cas monocritère au problème étudié. En effet, pour chercher une solution de Pareto optimale avec une valeur QB donnée, nous procédons comme suit. (i) Résoudre par le PLNE le problème en minimisant f A sous contrainte f B ≤ QB . La solution trouvée est optimale pour le critère A, notée (f ∗A , QB ). (ii) Résoudre une deuxième fois le problème en minimisant f B sous contrainte (f A ≤ f ∗A ). La solution ainsi obtenue est optimal au sens de Pareto strict. Pour résoudre des instances de grande taille, des heuristiques à deux-phase sont développées : (i) déterminer l’affectation des activités aux personnes selon une des règles de priorité considérées ; (ii) A partir de cette affectation, calculer un ordonnancement pour minimiser le retard des activités de chaque agent. Pour cette deuxième phase, nous développons une heuristique basée sur la recherche de flot maximum à coût minimum. Une méthode de type recherche tabou est également proposée où la solution initiale est générée en appliquant l’heuristique à 2-phase avec les meilleures paramètres. L’analyse des performances des méthodes proposées est en cours et sera donc présentée lors de la conférence. Références [1] A. Agnetis, J.-C. Billaut, S. Gawiejnowicz, D. Pacciarelli, and A. Soukhal. Multiagent Scheduling, Models and Algorithms. Springer-Verlag, Berlin Heildelberg New York, 2014. [2] Meya Haroune, Cheikh Dhib, Emmanuel Néron, Ameur Soukha, Hafed Babou, Mohameddade Nanne. Ordonnancement multi-projets à contraintes de ressources partagées multicompétences. 20ème congrès annuel de la société Française de Recherche Opérationnelle et d’Aide à la Décision, Le Havre, 2019.