Méthodes prédictive et proactive pour un problème de gestion de projet sous contraintes de ressources humaines Laure-Emmanuelle Drezet 27 janvier 2005

Méthodes prédictive et proactive pour un problème de gestion de projet sous contraintes

de ressources humaines

Laure-Emmanuelle Drezet27 janvier 2005

LE Drezet GOThA - 27 janvier 2006 2

Plan

• Problématique

• Approche prédictive – Heuristiques basées sur des règles de priorité– Méthode Tabou– Expérimentations

• Approche proactive – Problématique et mesure de robustesse– Heuristiques basées sur des règles de priorité– Méthode Tabou– Expérimentations

• Conclusions et perspectives


Problématique : Projet

• Eskape est une SSII (Société de service et d’ingénierie informatique)

• Fonctionne en mode projet (ex: développement d’application logicielle)

• Le système fonctionne en discontinu (pas de travail les nuits et les Week-ends)


Problématique : Projet

• Les projets sont découpés en activités, qui utilisent un seul type de ressources : les ressources humaines

• Les activités sont reliées par des contraintes de précédence.

s

1

2 4

3

p


Problématique : Projet et ressources

• Des contraintes légales doivent être respectées par l’emploi du temps de la personne i:

– Ampi : amplitude maximale d’une journée de travail

– Nmini et Nmaxi : durée minimale et maximale d’une journée de travail

• Une limite est fixée sur le nombre maximal de changements d’activité par jour pour chaque employé


Problématique : activités du projet

• Chaque activité j du projet possède:– Une durée pj

– Une date de début au plus tôt rj

– Une date de fin au plus tard dj

– Deux profils de consommation de ressources bminjt et bmaxjt


Problématique : besoins en compétences• Un besoin en compétences est formulé

comme un nombre minimal et maximal de personnes présentes capables de réaliser une activité donnée.

• Des besoins en compétences doivent être satisfaits:– Contrats de maintenance,– Sécurité– …


Problématique : contraintes

• Contraintes « process » :– Besoins des activités (minimaux et maximaux)– Relations de précédence– Compétences des employés

• Contraintes « humaines » :– Contraintes légales– Besoins en compétences


Problématique : Différentes phases

• Tous les mois ou toutes les quinzaines, le planificateur calcule un planning prévisionnel

• Mais, malgré tous les efforts pris pour sa construction, il est quasiment impossible que ce planning prévisionnel puisse être appliqué sans modifications

=> Approches prédictive et proactive


Prédictif, proactif et réactif

• Dans l’approche prédictive, un ordonnancement prévisionnel est construitQualité

• Dans l’approche proactive, un ordonnancement prévisionnel est construit en tenant compte d’informations sur les aléas qui peuvent se produire durant sa mise en œuvre Robustesse


Plan

• Problématique





Description du problème

• Les plannings prévisionnels des employés sont construits en utilisant les activités d’un projet

• L’horizon de planification : la quinzaine/ le mois

• L’objectif : minimiser le retard maximal algébrique du projet

1. Approche prédictive> Heuristiques basées sur des règles de priorité


Besoins en compétences A4

A1r1=0p1=4d1=5

Exemple

s

A1

A2 A4

A3

p

•4 employés 1 journée= 6 per

•Un projet (4 activités)

Contraintes de personnel

Graphe du projet


Nmin

Nmax

Amp

Comp

E1 2 4 6 A1,A4E2 2 2 6 A1,A2,A4E3 2 4 6 A2,A3E4 2 2 6 A1,A2,A3,A

4

A2r2=2p2=3d2=6

A3r3=2p3=2d3=6

A4r4=4p4=4d4=9

E1E2E3E4per. 1 2 3 4 5 6

journée 1A1

A1E1E2E3E4 A2per. 1 2 3 4 5 6

journée 1A1

A1A2

E1E2E3E4 A2 A1per. 1 2 3 4 5 6

journée 1A1

A1A2

E1E2E3E4 A2 A1per. 1 2 3 4 5 6 1 2 3 4 5 6

journée 1

A1A2

A1journée 2

A3A3

E1E2E3E4 A2 A1per. 1 2 3 4 5 6 1 2 3 4 5 6

A2 A3A3

A4A4

journée 1 journée 2A1

A1

Lmax= max(-1,-1,2,1)=2

1 2 3 4 5 6 7 8


Méthode heuristique à règle de priorité

• Minimisation du nombre de contraintes violées (contraintes « humaines ») et du Lmax

• Les contraintes « process » sont toujours respectées

• Nous avons évalué différentes règles de priorité et deux schémas d’heuristiques différents



Algorithme général (1)

U est l’ensemble des activités éligibles

Tant que U n’est pas vide fairePour chaque activité i de U faire

FinPour

FinTantque






P est la liste triée (Wp) des personnes compétentes pour réaliser iGénérer un sous-ensemble A des affectations possibles pour i, en respectant les besoins minimaux de i (|A|≤ n)Calculer le retard de i avec chaque affectation de ABesti est la “meilleure” affectation de i

FinPour

FinTantque






P est la liste triée (Wp) des personnes compétentes pour réaliser iGénérer un sous-ensemble A des affectations possibles pour i, en respectant les besoins minimaux de i (|A|≤ n)Calculer le retard de i avec chaque affectation de ABesti est la “meilleure” affectation de i

FinPourOrdonnancer l’activité i* avec le plus petit Besti*

Mettre à jour UFinTantque


O( Nact2 (Nemp log(Nemp) + n2))


Algorithme général (2)U est l’ensemble des activités éligibles

Tant que U n’est pas vide faireTrier U selon une règle de priorité (Wu), i est la première activité

de UP est la liste triée (Wp) des personnes compétentes pour réaliser i

Générer un sous-ensemble A des affectations possibles pour i, en respectant les besoins minimaux de i (|A|≤ n)

Calculer le retard de i avec chaque affectation de ABesti est la “meilleure” affectation de i

Ordonnancer l’activité i selon l’affectation Besti

Mettre à jour UFinTantque


O( Nact (log(Nact)+Nemp log(Nemp) + n2))


Tri de l’ensemble des activités éligibles• EDD (Earliest Due Date) : les activités sont

triées dans l’ordre croissant de leurs dates dues

• MINSLACK : les activités sont triées dans l’ordre croissant de leurs marges



Tri de l’ensemble des activités éligibles• TOTREQ (Total Requirement) : les activités

sont triées dans l’ordre décroissant de leurs besoins minimaux totaux

TOTREQ1=6


A1r1=0p1=4d1=5

TOTREQ2=3

=> A1<A2 dans U

A2r2=2p2=3d2=6

s

A1

A2 A4

A3

p


Tri de l’ensemble des activités éligibles• NBSUCC (Number of Successors): les activités

sont triées dans l’ordre décroissant de leur nombre de successeurs transitifs

NBSUCC1=2 NBSUCC2=3 => A2<A1 dans

U


s

A1

A2 A4

A3

p


Tri de l’ensemble des activités éligibles• MAXTAIL : les activités sont triées dans

l’ordre décroissant du plus long chemin de l’activité jusqu’au puits

• RANDOM, NBACT (Numéro des activités)

s

1

2 4

3

p

[0,5]4

[2,6]2

[2,6]3

[4,9]4

MAXTAIL1=2 MAXTAIL2=max(2;4)=4

=> A2<A1 dans U



Tri de l’ensemble des personnes candidates

• MinSkill (Minimum Number of Skills): les employés sont triés dans l’ordre croissant de leur nombre de compétences

MinSkill1=2 MinSkill2=3MinSkill3=2MinSkill4=4

=>Pour A4 : P=(E1,E2,E4)


Nmin

Nmax

Amp

Comp

E1 2 4 6 A1,A4E2 2 2 6 A1,A2,A4E3 2 4 6 A2,A3E4 2 2 6 A1,A2,A3,A

4



• MaxSkillReq (Maximal Skill Requirement) : les employés sont triés dans l’ordre décroissant du nombre de besoins en compétences qui peuvent être couverts par leur présence




• Earliest ou FAM (First Available Machine) : les employés sont triés dans l’ordre de leur date de disponibilité au plus tôt. Les trous dans les plannings ne sont pas pris en compte

• Earliest Hole : déclinaison de Earliest avec prise en compte des trous de plannings

• EarliestHoleLegal : déclinaison de Earliest, pour laquelle le respect des contraintes légales est également pris en compte



Exemples

s

A1

A2 A4

A3

p

A5

EarliestHoleLegal

EarliestHole

Earliest


Nmin

Nmax

Amp Comp

E1 2 4 6 A1,A4E2 2 2 6 A1,A2,A4E3 2 4 6 A2,A3E4 2 2 6 A1,A2,A3,A4

E1E2E3E4 A2 A1per. 1 2 3 4 5 6 1 2 3 4 5 6

A2 A3A3

A4A4

journée 1 journée 2A1

A1

E1E2E3E4 A2 A1per. 1 2 3 4 5 6 1 2 3 4 5 6

A3A5

A5A5

A1 A4A2 A3

journée 1 journée 2A1 A4

E1E2E3E4 A2 A1per. 1 2 3 4 5 6 1 2 3 4 5 6

A3

A5A5A5

A1 A4A2 A3

journée 1 journée 2A1 A4

E1E2E3E4 A2 A1per. 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6

A3

A1A2

A4 A5A3 A5

journée 1 journée 2 journée 3A1 A4 A5


Procédure d’affectation

• La liste triée P est utilisée pour générer n affectations pour chaque activité sélectionnée

• Deux types d’affectation :


E1 A1 A1E2E3E4per. 1 2 3 4 5 6

A1A1

Jour 1E1 A1E2 A1 A1E3E4 A1 A1per. 1 2 3 4 5 6

A1

Jour 1

UnitairePar Etage


Amélioration des résultats : méthode Tabou

• Pour améliorer les résultats des heuristiques : méthode Tabou

• La solution initiale est fournie par une heuristique basée sur des règles de priorité

• Approche lexicographique : nombre de contraintes « humaines » violées / Lmax

• Une solution = matrice d’affectation

1. Approche prédictive> Méthode Tabou



• Mouvements autorisés :– Changement de l’affectation d’une personne

pendant une période de temps– Swap de deux personnes pendant une période de

temps– Décalage à gauche ou à droite d’une activité– Swap de deux activités




• Les voisins, qui ne respectent pas les contraintes de précédence ou les contraintes de compétences, ne sont pas générés.

• A chaque itération, un nombre maximal Nv de voisins est généré

• La Liste Tabou est composée des mouvements effectués

• Les mouvements sont tabous pendant un nombre d’itérations fixé



Expérimentations

• Générateur d’instances

• Tests des heuristiques

• Tests de la méthode Tabou

1. Approche prédictive> Expérimentations


Génération des instances pour le prédictif

• Les fichiers sont extraits de la PSPLIB pour le RCPSP [Kolisch et Sprecher, 1996] et sont adaptés à notre problème

• Le personnel est homogène : chacun sait faire 70% des activités

• Les journées sont découpées en 12 périodes de temps

• La durée travaillée par jour minimale de chaque employé est égale à 0.

• La durée travaillée par jour maximale de chaque employé est comprise entre 7 et 10.

• L’amplitude maximale journalière est comprise entre 7 et 12.• Le nombre de changements maximal d’activités est compris entre

4 et 12.



Résultats des heuristiques prédictives• Résultats de tests préliminaires :

– La règle MINSLACK est la plus efficace– Le second schéma d’algorithme est plus efficace

que le premier

• Huit heuristiques sont évaluées :

H8 = lancement multiple de H7, avec toutes les

règles de priorité Wu



Résultat des heuristiques prédictives

Ces résultats moyens sont obtenus sur 110 instances de la PSPLIB adaptée (ensemble J60)

Nombre de contraintes violables ≈15 000


25193,960955264,2130H8

272104,1351516399,2330H7

18869,9401915876,64293H6

272109,5281566364,1321H5

19479,3001069602,14139H4

252140,81441029488,3599H3

277180,3586845427,6355H2

277180,4186845427,9855H1

MaxMoyMinMaxMoyMin

LmaxNb de contraintes violées

Heuristique


Paramétrage Tabou prédictive

• Paramètres de la méthode Tabou prédictive:– Durée maximale d’exécution : 5 minutes– Nombre maximal de voisins générés à chaque itération : 50– Nombre d’itérations avant diversification : 30– Nombre d’itérations maximal : 400

• Ces paramètres sont fixés grâce à des expérimentations préliminaires (meilleurs résultats, stabilité des solutions…)



Résultat de la méthode Tabou prédictive

•Conclusions expérimentales:–Il vaut mieux ne pas utiliser de diversification–L’exploration peut se réduire aux seuls voisins qui respectent les contraintes légales


0,52%93,4493,9642,11%150,88264,21H8

0,63%103,48104,1347,49%198,91399,23H7

0,03%69,9269,9428,47%649,01876,64H6

0,69%108,98109,5247,65%169,69364,13H5

0,31%79,1379,3031,40%430,41602,14H4

2,22%128,04140,8155,09%236,07488,35H3

4,77%172,18180,3556,40%199,55427,98H2

4,69%172,36180,4156,50%199,32427,98H1

GainFinalInitGainFinalInit

LmaxNb de contraintes violéesHeuristique


Plan

• Problématique





Description du problème

• Les plannings prévisionnels des employés sont construits en utilisant les activités d’un projet

• On dispose d’informations sur les aléas qui peuvent se produire durant l’ordonnancement du projet

On veut en tenir compte dans la planification du projet

• L’horizon de planification : la quinzaine/ le mois

• L’objectif : maximiser la robustesse de l’ordonnancement

2. Approche proactive> Présentation du problème et mesure de robustesse


Aléas considérés

• Des aléas peuvent survenir:– Indisponibilité d’un employé

• Travail sur un autre projet• Déplacement

– Modification de la durée d’une activité• Allongement de sa durée

Création de nouveaux besoins de l’activité sur les périodes d’exécution ajoutées



Mesure de robustesse sur les personnes

• A chaque personne i, on associe :– Une probabilité d’indisponibilité : pindi

– Une durée maximale d’indisponibilité : dindi

• Chaque personne i, a une charge de travail chargei

• La mesure de robustesse (à maximiser) d’un ordonnancement S sur les personnes S

P est égale à :



Mesure de robustesse sur les personnes


pind dind chargeE1 0,3 2 2E2 0,5 2 2

1 2 3 4 5 6

d3=4

per.

A1A2

A3

journée 1


1 2 3 4 5 6


1 2 3 4 5 6per.

per.

journée 1

journée 1A1A2

A3

A1A2 A3

sp = min((-4-2)0,3;(-2-2)0,5)= -2

sp = min((-2-2)0,3;(-4-2)0,5)= -3


Mesure de robustesse sur les activités

• A chaque activité j, on associe:– Une probabilité d’allongement : pallj

– Une durée maximale d’allongement: dallj

• Chaque activité j, a une marge margej

• La mesure de robustesse (à maximiser) d’un ordonnancement S sur les activités, S

A, est égale à :



Mesure de robustesse globale

• La mesure de robustesse d’un ordonnancement S est définie par :

(1-) SA + S

P

• Usuellement, la robustesse doit être maximisée

• Nous allons plutôt chercher à minimiser :S =-(1-) S

A – SP



Règles de priorité robustes

• Nouvelle règle de priorité pour les activités :– ROBACT : Les activités sont triées dans l’ordre

décroissant de :(margej – dallj) pallj

• Nouvelle règle de priorité pour les employés:– RobEmp : Les employés sont triés dans l’ordre

décroissant de :-(chargei + dindi) pindi

2. Approche proactive> Heuristique basée sur des règles de priorité



• Inspirée de la méthode Tabou prédictive

• L’évaluation de la qualité de la solution ne tient plus compte du retard, mais de la robustesse.

Approche lexicographique : nombre de contraintes « humaines » violées / Robustesse

2. Approche proactive> Méthode Tabou


Expérimentations

• Les instances utilisées sont générées selon les mêmes principes que les instances « prédictives »

• pindi 0,0.5]

• dindi 1,36]

• pallj 0,0.5]

• dallj 1,pj]

2. Approche proactive> Expérimentations


Résultats des heuristiques proactives

• 24 heuristiques ont été évaluées qui font intervenir la robustesse :– pour le tri des activités seulement (catégorie 2)– pour le tri des employés seulement (catégorie

3)– pour le tri des employés et des activités

(catégorie 4)

• Comparées avec des heuristiques prédictives (catégorie 1)



Résultat des heuristiques proactives

Ces résultats sont obtenus sur 480 instances de la PSPLIB adaptée (ensemble J60), pour chaque catégorie d’heuristiques

Seules les 2 meilleures heuristiques (pour le nombre de contraintes violées) de chaque catégorie sont retenues


25,1096,43315,82H5

24,6477,95190,87H8

Catégorie 4 : robustesse

24,7986,64279,29H5

24,6477,7192,96H8

Catégorie 3 : qualité / robustesse

25,99100,05322,34H5

26,2187,61186,34H8

Catégorie 2 : robustesse / qualité

25,6880,9285,34H5

26,9174,2233,3H8

Catégorie 1 : qualité

sLmaxNb de cont.

violéesHeuristiq

ue


Résultat de la méthode Tabou proactive


• Paramètres de la méthode Tabou proactive:– Durée maximale d’exécution : 5 minutes– Nombre maximal de voisins générés à chaque itération : 50– Nombre d’itérations avant augmentation du voisinage : 30– Nombre d’itérations maximal : 400

4,52%23,5524,640,41%77,5177,9553,04%93,36190,87H8 (robustesse)

5,01%23,4324,640,53%77,1977,7053,70%

92,07192,96

H8 (qualité/robustesse)

GainFinalInitGainFinalInitGainFinalInit

SLmaxNb cont. VioléesHeuristique


Comparaison Prédictif/Proactif

Ces résultats sont obtenus sur les 110 instances de la PSPLIB adaptée (ensemble J60)

Les solutions initiales de la méthode Tabou proactive proviennent de H8 (robustesse)

Les solutions initiales de la méthode Tabou prédictive proviennent de H8 (qualité)


4,03%25,1926,250,24%88,5588,9450,37%128,10247,59Proactive

1,40%28,3028,750,57%85,3385,9455,19%124,43270,91Prédictive

GainFinalInitGainFinalInitGainFinalInit

SLmaxNb de cont. violéesApproche


Conclusions

• Etude d’un problème de gestion de projets avec des spécificités :– Utilisation de ressources humaines

=> Respect des contraintes inhérentes à ce type de ressource

– Demandes des activités variables (comprises entre deux valeurs seuils)

– Besoins en compétences

• Résolution du problème dans la phase prédictive et proactive


Conclusions

• Pour chacune des phases, développement de différentes méthodes de résolution : Algorithmes gloutons Métaheuristiques : méthodes Tabou

• Intégration dans la solution intranet d’Eskape


Perspectives

• Utilisation de nouvelles méthodes de résolution : Proposition d’un ensemble de solutions au décideur

• Extension des méthodes à l’environnement multi-projet

• Version déclinée du problème : RCPSP avec contraintes de ressources humaines


Perspectives

• Définition d’une nouvelle mesure de robustesse Prise en compte des contraintes sur les

ressources dans la mesure de robustesse sur les activités

• Prise en compte d’autres aléas Apparition de nouvelles activités dans le projet Diminution de la durée des activités Modification de la demande des activités


Merci de votre attention

Documents

Méthodes prédictive et proactive pour un problème de gestion de projet sous contraintes de ressources humaines Laure-Emmanuelle Drezet 27 janvier 2005