Groupes indépendants avec points communs

Gian · November 2020

Bonsoir à tous,

Ce problème me donne du fil à retordre !
J'ai un groupe d'individu : A,B,C,D,E,F, ....
Qui travaille sur des projets : P1, P2,P3,P4,P5,P6, ....

Je peux avoir :
A travaille sur P1,P2
B travaille sur P1,P3
C travaille sur P1,P4
D travaille sur P2,P3,P5
E travaille sur P5,P6

Chaque Projets Px doit être passé en revue par toutes les équipes travaillant dessus.
Si je passe en revue séquentiellement P1 puis P2 puis P3, P4, P5, P6, Px cela crée de l'attente sur les projets à venir et aussi sur les équipe qui attendent leur tour de parole.
C'est le même problème si je passe en revue par équipe A puis B puis C...

Mon objectif est déterminer des groupes de travail qui concernent des équipes et des projets en communs.
Idéalement, chaque groupe est indépendant l'un de l'autre ce qui permet de paralléliser la revue des projets.
Finalement l'objectif est de passer en revue le plus vite possible tous les projets.

J'ai commencé à réfléchir à une matrice symétrique Px/Px.
Par exemple l'intersection de P5,P6 me donne E,D car ce sont les équipes qui travaillent sur P5 et P6.
Ceci n'est qu'un exemple, j'ai en realité 54 projets et 50 équipes.

Il faut donc trouver la démarche algorithmique, puis je coderai en VBA sous excel une macro qui analyse un tableau et créer les groupes en sortie.

EN Pj

Gian · November 2020

Bonjour à tous,

Personne n'aurait une idée ?

Merci à vous

Sylviel · November 2020

Bonjour,

ce n'est pas vraiment des statistiques, c'est plutôt de la combinatoire.

On peut écrire le problème comme un problème en nombre entier et demander à un solveur de le résoudre.

Si le problème est de petite taille tu peux aussi faire une exploration brutale (par recursivité) :
Soit L la liste des projets à évaluer.
temps(L) est une fonction qui renvoie le nombre de slots nécessaires pour traiter la liste L.

Si L ne contient qu'un seul projet temps(L) renvoie 1

Si $L=\{L_1,...,L_n\}$ contient au moins deux projets :
temps(L) considère qu'on traite $L_1$ à ce tour, puis regarde si d'autres projet sont traitable en même temps
et retourne 1 + min { temps(L') tel que L' est la liste des projets restant}.

[Je suis à 90% convaincu qu'il n'y a pas de perte d'optimalité à supposer qu'on va forcément traiter le premier élément de la liste ce tour ci, car il faudra bien le traiter en même temps qu'un sous-set de L, mais il faudrait le vérifier proprement]

Dernier point : l'écriture recursive n'est peut-être pas l'implémentation la plus efficace car tu vas recalculer temps(L') pour une même liste de nombreuse fois. Il faudrait maintenir un dictionnaire global qui à chaque liste (non-ordonnée) associe son temps. Si la liste a déjà été traitée il suffit de lire la valeur dans le dictionnaire, sinon il faudra l'ajouter au dictionnaire dans la procédure ci-dessus.

Gian · November 2020

Bonjour Sylviel,

Merci pour ton aide !
En réalité j'ai environ 50 équipes et 50 projets.
Dans ta méthode, je ne suis pas sur d'avoir compris. Si je l'applique à mon exemple :
L = {P1,P2,P3,P4,P5,P6}
L1 = P1
L' = {P2,P3,P4,P5,P6}
temps(L) = 1 + min temps(L') avec min temps(L') le projet que je peux traiter en même temps

Est-ce que tu pourrais illustrer par un exemple concret ?
Equipe Projet
E1 P1
E2 P1
E3 P2
E3 P3

Sylviel · November 2020

Ton exemple est un peu simple car il n'y a aucun choix à faire.

P1 : (E1,E2)
P2 : (E3,E4)
P3 : (E4)
P4 : (E1,E3)

Au départ L = {P1, P2, P3, P4}
On va traiter P1, ce qui immobilisé E1 et E2.
Tu peux donc traiter en parallèle : P2 ou P3.
Tu as donc comme L' possible : {P3,P4} et {P2,P4}.

Donc temps(L) doit renvoyer 1 + min [ temps( {P3,P4}), temps({P2,P4}) ].

Groupes indépendants avec points communs

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 31