Méthodes de résolution pour un problème de gestion de projet avec prise en compte de compétence

Méthodes de résolution pour un problème de gestion de projet

avec prise en compte de compétence

Odile Bellenguez-MorineauLaboratoire d’Informatique (EA 2101)Dépt. Informatique - Polytech’Tours

Université François-Rabelais de Tours - France

Méthodes de résolution pour un problème de gestion de projet avec prise en compte de compétence

Odile Bellenguez-Morineau 26 avril 2007 2

Problème d’ordonnancement

• « Ordonnancer c’est programmer l’exécution d’une réalisation en attribuant des ressources aux tâches et en fixant leurs dates d’exécution » [Carlier & Chrétienne, 88]

• Projet : réalisation unique à objectifs définis. Un projet est découpé en activités qui doivent être accomplies à l’aide des ressources allouées pour que le projet aboutisse.

• Ressource renouvelable : disponible en quantité limitée sur chaque période de temps



Problème de gestion de projet

• Classiquement, les projets se modélisent à l’aide d’un graphe de précédence :

A1

A2

A3

A4

2

A0 A5

0

03

3

4

4

• Ressources disponibles en quantité connue• Les besoins des activités sont exprimés en terme de quantité requise de chaque ressource existante



Origines du problème de gestion de projet multi-compétence

• Problème à l’origine de notre réflexion :– Développement de projets industriels

Réaliser un ensembles d’activités (étapes du projet) à l’aide des ressources allouées (équipe de projet)

Lors de la phase de négociation, il est nécessaire de s’engager sur des délais de livraison (durée du projet)



Origines du problème de gestion de projet multi-compétence

• Dans ce cas : Les ressources sont des ressources humaines, maîtrisant des compétences

[Pepiot et al., 04] : « … habilité à mobiliser d’une manière efficace des ressources non-matérielles dont la structuration peut se réaliser de multiples façons et des ressources matérielles dans le but de répondre à une activité »

• besoins définis en terme de compétences

De nombreuses affectations possibles pour une même activité



Le problème de gestion de projet multi-compétence

Activités Personnes

A1 A2 A3 A4 P0 P1 P2 P3 P4

S0 1 - 2 1 1 1 1 1 -

S1 2 1 - 1 1 1 - 1 1

S2 - 1 1 - 1 - - - 1

2

A0 A5

A1

A2

A3

A4

0

03

3

4

4

A1, S1

A1, S0

A1, S1

A2, S1

A2, S2 A4, S1

A4, S0

A3, S0

A3, S2

A3, S0

Cmax = 6

P0

P1

P2

P3

P4

2 40

Sous-ensembles possibles : {(P0,P1,P3), (P0,P1,P4), (P0,P3,P4), (P1,P3,P4), (P2,P0,P1), (P2,P0,P3), (P2,P0,P4), (P2,P1,P3), (P2,P1,P4), (P2,P3,P4), … }



Plan

1. Problème de gestion de projet multi-compétence 2. Des bornes inférieures3. Des méthodes approchées4. Une méthode exacte5. Extension et problèmes industriels traités6. Conclusion et perspectives scientifiques



Plan

1. Problème de gestion de projet multi-compétence – Notations– Complexité

2. Des bornes inférieures3. Des méthodes approchées4. Une méthode exacte5. Extension et problèmes industriels traités 6. Conclusion et perspectives scientifiques




• Données : – Compétences Sk, k {0,…,K-1}– Activité Ai, i {0,…,n} : précédence, durée pi, besoins bi,k

– Ressource Pm, m {0,…,M-1}: compétences (MSm,k {0,1}), disponibilité (Disp(Pm, t) {0,1})

• Contraintes :– Capacité des ressources– Compétences – Disponibilité– Précédence– Pas de préemption

Minimiser la durée du projet




• Complexité : NP-difficile au sens fort

• Si chaque personne ne maîtrise qu’une compétence RCPSP classique [Blazewicz et al., 83]

• Si les dates de début des activités sont fixées Fixed Job Scheduling Problem [Kolen & Kroon, 91]

• Si les affectations des personnes aux activités sont fixées

Multiprocessor job-shop [Garey et al., 76]



Plan

1. Problème de gestion de projet multi-compétence 2. Des bornes inférieures

– Raisonnement énergétique– Graphe de compatibilité

3. Des méthodes approchées4. Une méthode exacte5. Extension et problèmes industriels traités6. Conclusion et perspectives scientifiques



Des bornes inférieures

• [Bellenguez & Néron, 05]

• Les bornes présentées sont destructives : on fixe D comme date de fin impérative du projet

la propagation sur le graphe de précédence permet de déterminer les fenêtres d’exécution des activités [ri,di(D)]

Si une infaisabilité est détectée, alors D+1 est une borne inférieure valide

On effectue une recherche dichotomique sur D entre la borne inférieure donnée par le chemin critique et une borne supérieure valide

~



Borne inférieure : raisonnement énergétique

• [Lopez et al, 92], [Baptiste et al, 99] pour le RCPSP

• Partie obligatoire W(i,t1,t2) d’une activité Ai sur [t1; t2]:

W(i,t1,t2) = min(max(0,ri+pi-t1), max(0,t2-(di(D)-pi)), pi, t2-t1)

ri di(D)~

~

t1 t2




• Sur un intervalle [t1;t2], on a un problème d’affectation simple à résoudre

• on cherche le flot maximum dans G:Un nœud par compétence

Un arc si MSm,k = 1

Un nœud par

personne

Sourcepuits

SK-1

P0

PM-1

P1

t2t1 Disp(PM, t)

|t2-t1|

i

W(i,t1,t2)bi,0

i

W(i,t1,t2)bi,K

t2t1 Disp(P1, t)S0




• Si [t1;t2] t.q. le flot maximum calculé est inférieur à la somme des besoins, alors les besoins ne peuvent pas être satisfaits

D+1 est une borne inférieure valide

• On teste tous les intervalles [t1;t2], t1<t2

t1 {ri, ri+pi, di(D)-pi, i {0,…,n} }

t2 {ri+pi, di(D)- pi, di(D), i {0,…,n} }

~

~~



Borne inférieure : graphe de compatibilité

• Inspiré de [Mingozzi et al, 98] pour le RCPSP

• Pour chaque couple (Ai, Aj) :– Déterminer si les activités peuvent être exécutées en

parallèle Un nœud par compétence

Un arc si MSm,k = 1

Un nœud par personne

Un nœud par activité

Source Puits

Ai

Aj

S0

Sk

SK-1

P0

PM-1

k bi,k

bj,K

1

1

1

k bj,k

bi,1

bi,K

bj,k

1

11

11




Graphe de compatibilité G(U,V’): (Ai, Aj) V’, si Ai et Aj peuvent être en cours d’exécution en même temps

S

A3

A2

A1

A5

A6

A7

A4

A9

A8

P

S

A3

A2

A1

A5

A6

A7

A4

A9

A8

P

32

3

4

2

1

3

2

5

Graphe de précédence G(U,V):

Poids = durée de l’activité

3

3

3

2

2

2

1

5

4




• On recherche un stable de poids maximum sur G(U,V’): (NP-difficile au sens fort)

Max i ui.pi

ui {0,1}

ui = 1 si Ai est dans le stable, 0 sinon

s.c. (Ai,Aj) G(U,V’) ui + uj ≤ 1

• Si le poids de ce stable maximum est supérieur à D, D+1 est une borne inférieure valide



Bornes inférieures : Résultats

• Complémentarité des deux bornes

Raisonnement énergétique

Graphe de compatibilité

#best(strict)

Déviation

moyenne

Temps moyen

(s)

#best(strict)

Déviation

moyenne

Temps moyen(

s)

A(185)

126 (81)

9,68 0,153 104 (59) 23,30 0,007

B(174)

168 (26)

5,00 1,008 48 (6) 20,85 0,024

C(198)

197 (93)

4,35 0,075 105 (1) 23,21 0,009

D(195)

164 (148)

8,78 1,712 47 (31)

18,04 0,025



Plan

1. Problème de gestion de projet multi-compétence 2. Des bornes inférieures3. Des méthodes approchées

– Placement série– Méthode tabou

4. Une méthode exacte5. Extension et problèmes industriels traités6. Conclusion et perspectives scientifiques



Méthodes approchées : algorithme série

• Adaptation de [Kelley, 63] pour le RCPSP

• L : liste de priorité respectant les contraintes de précédence

• Ai est calée à gauche, i.e., placée à la plus petite date ti ≥ ri qui respecte les contraintes de ressources

• À cette date il peut exister plusieurs sous-ensembles de personnes pouvant satisfaire Ai

on les départage à l’aide de la criticité (indicateur heuristique)

Permet de construire des ordonnancements actifs




• La criticité d’une compétence : besoin total/ressource disponible

• La criticité d’une personne : somme des criticités des compétences maîtrisées

1

0, .

K

kkkmm CSMSCP

1

0max,

1

1,

),0,(.

.

M

mmkm

n

iiki

k

TPDispMS

pb

CS




• On recherche un flot maximum à coût minimum :

Source Puits

S0

SK-1

P0

PM-1

bi,k2, 0

bi,k1, 01, 0

1, 0

1, 0

1, 0

1, CP0

1, CPM-1

• Si le flot est égal à la somme des besoins alors Ai est placée à la date t, sinon on incrémente t jusqu’à ce qu’une nouvelle ressource soit libre

Capacité maximum, coût

S1 P1




• Exécution pour 8 règles de priorité classiques : – MTS, EST, EFT, LFT, LST, MST, GRD, GR

• Résultats pour la meilleure règle de priorité :

#OPTDéviation moyenne

Temps moyen (s)

A(185) 15 17,73 < 0,01

B(174) 12 14,65 < 0,01

C(198) 52 10,30 < 0,01

D(195) 1 18,75 < 0,01



Plan

1. Problème de gestion de projet multi-compétence 2. Des bornes inférieures3. Des méthodes approchées

– Placement série– Méthode tabou

4. Une méthode exacte5. Extension et problèmes industriels traités6. Conclusion et perspectives scientifiques



Méthodes approchées : méthode tabou

• Inspiré de [Klein, 2000] pour le RCPSP

• L = {A[i]} : liste de priorité respectant les contraintes de précédence

• Une solution est basée sur une liste de priorité• La solution associée est obtenue par la méthode de

placement série • L’ est voisine de L si elle peut être obtenue par un

échange– On interdit les échanges d’activité liées par une contrainte de

précédence– On interdit les échanges qui ne modifieront pas les dates de

début des activités




• A chaque itération on évalue un nombre limité de voisins, choisis aléatoirement parmi ceux valides

• On conserve le meilleur comme point de départ de l’itération suivante

• Liste tabou– Les solutions visitées sont stockées dans une table de

hashage– Un enregistrement = la liste de priorité, le nombre de visites

nv, indice de l’itération où a eu lieu la dernière visite lv– Une solution est tabou à une itération ir si ir – lv < v, avec v

la période tabou




• Intensification– Le nombre de voisins visités est augmenté

• Diversification – Le nombre de voisins visités est diminué– Si le nombre de revisites est supérieur à 3, on réinitialise la

recherche (règles de priorité classiques, puis une génération aléatoire)

• Condition d’arrêt– Après ∆ itérations sans amélioration de la meilleure solution

atteinte (∆=250)




• Résultats

Tabou + série

#OPTDéviationmoyenne

Temps moyen (s)

A(185) 60 5,01 6,50

B(174) 71 0,08 23,84

C(198) 165 0,46 2,60

D(195) 7 5,28 43,03



Plan

1. Problème de gestion de projet multi-compétence 2. Des bornes inférieures3. Des méthodes approchées4. Une méthode exacte

– Condition coupe– Traitement d’une feuille

5. Extension et problèmes industriels traités6. Conclusion et perspectives scientifiques



Méthode exacte

• Inspiré de [Carlier & Latapie, 91] pour le RCPSP

Ai [ri; di(UB)]~

Ai [ri + mi/2; di(UB)]Ai [ri; di(UB) - mi/2]~ ~

mi =di(UB)- ri -pi~

• Schéma de branchement basé sur les marges des activités

- Une activité est choisie et sa marge est réduite de moitié- Propagation sur les successeurs et prédécesseurs

• Borne supérieure UB déterminée par la méthode série

- Bornes inférieures présentées précédemment- Recherche dichotomique à la racine- Dans un nœud on teste uniquement UB-1



Plan






Méthode exacte : condition de coupe

• Partie centrale obligatoire

• Permet de définir une activité « fictive » à date de début fixée– Durée d’autant plus importante que la fenêtre d’exécution est

serrée – Problème traité comme une feuille Si ce problème n’admet pas de solution, alors le nœud peut

être coupé

ri di(D)~

pipi



Plan






Méthode exacte : traitement d’une feuille

• Une feuille = problème à dates de début fixées NP-difficile au sens fort [Kolen & Kroon, 91]

A1(S1)

A1(S1)

A2(S0)

A2(S2)

A4(S3)

A3(S3)

A3(S0)

A5(S1) A6(2S1)

A6(2S1)

A1(2S1)A3(S0,S3)

A6(2S1)

A5(S1)A2(S0,S2)

A4(S3)

0 2 4 6

P0(S0,S2,S3)

P1(S1,S3)

P2(S0,S1)

P3(S1)

P4(S1,S2,S3)

2 40 6




• Appel à une heuristique de placement– Inspiré du placement série

• Décomposition en sous-problèmes de plus petite taille– Décomposition temporelle– Décomposition par groupes de compétences indépendants

• Résolution : appel à un Programme Linéaire en Nombres Entiers




• Décomposition temporelle :– Point de coupure t

– Sous-problèmes indépendants– Résolution plus rapide– Coupures fréquentes dues aux contraintes de précédence

A3

A1A5

A7

A8

A9

A6A2

A4

t




• Décomposition par groupes de compétences indépendants– Groupes indépendants

– Sous-problèmes indépendants– Résolution plus rapide– Coupure peu fréquente due aux nombres de compétences

maîtrisées

A1 A2 A3 A4 P0 P1

P2

P3

P4

S0 1 - 2 1 - 1 - 1 -

S1 2 1 - 1 1 - - - 1

S2 - 1 1 - 1 - 1 - 1



Méthode exacte : résultats

• Obtenus en branchant sur l’activité de marge maximum

#OPTDéviationmoyenne

Temps moyen (s)

A(185) 25 (15)11,79 (17,73)

505,99

B(174) 19 (12)15,86 (14,65)

567,36

C(198) 84 (52) 5,00 (10,30) 350,71

D(195) 1 (1)16,39 (18,75)

600,00

• Tronquée en 10 minutes



Plan




Extension et problèmes industriels traités

• Problème de planification de formation de télé-opérateurs (société Vitalicom)– Formations initiales pour les arrivants (turnover important)– Plusieurs formations continues pour chaque télé-opérateur– Formateurs multi-compétents, avec fenêtres de disponibilité et

préférence– Formations par groupe de 20 télé-opérateurs (entre 5 et 15

groupes par session) en modules soumis à des contriantes de précédence

– Faire un planning lissé des formations sur 15 jours – Minimiser les modifications d’emploi du temps des télé-

opérateurs

Proposition d’une méthode heuristique Jusqu’à 400 modules de formations planifiés avec une charge

équitable entre les opérateurs




• Problème planification d’un service de maintenance d’un progiciel bancaire (société Delta Informatique)– Employés multi-compétents avec différents niveaux de

maîtrise– Couvrir les créneaux horaires d’ouverture de la hotline (équipe

de 2 personnes sur chaque créneau)– Composé des équipes complémentaires non-figées

– Maximiser le lissage de l’emploi du temps de chacun– Maximiser l’équité et la satisfaction des souhaits

Modèle mathématique + proposition d’une méthode heuristique permettant de gérer 40 employés




• Problème de changement de série dans un système de production (société SKF)– Opérateurs multi-compétents (avec vitesse moyenne)– Lignes de production série/parallèle – Certaines machines sont prioritaires

– Effectuer les changements d’outils et les réglages nécessaires à la nouvelle production

– Minimiser la perte de production

Algorithme génétique + descente locale permettant de gagner entre 10 et 50% de productivité




• Problème de planification des opérations de maintenance d’un système de production (société SKF)

– Opérateurs multi-compétents (avec vitesse moyenne)– Précédence ou disjonction entre certaines opérations de

maintenance

– Minimiser la durée d’immobilisation des machines à entretenir– Permettre aux opérateurs de s’entrainer sur tous les types de

réparation

Adaptation de la PSE en cours



Plan




Conclusion

• Prise en compte de compétences des ressources dans le cadre de la gestion de projet

• Définition d’un modèle pour ce problème• Mise au point de méthodes d’évaluation par défaut et

de méthodes de résolution efficaces• Permet de modéliser différents cas pratiques :

– Formations internes nécessitant des formateurs multi-compétents (Vitalicom), planification d’activités de maintenance (SKF)…

• Ces travaux ont donné lieu à 1 participation à un ouvrage, 3 acceptations en revues internationales et 14 présentations en conférences.



Perspectives

• Amélioration de la PSE, notamment dans le traitement des feuilles (problèmes à dates de début fixées)

• Intégration dans un outil de gestion de projet

• Prise en compte de critères supplémentaires : – Coût des personnes, dimensionnement de l’équipe

• Méthodes réactives prenant en compte les aléas– Réagir aux absences imprévues en minimisant le retard

engendré, les modifications d’emploi du temps



Merci de votre attention…

[email protected]

Documents

Méthodes de résolution pour un problème de gestion de projet avec prise en compte de compétence