Méthodes approchées et bornes inférieures pour le problème de gestion de projet multi-compétence Odile Bellenguez - Emmanuel Néron – Laurent Magniez Laboratoire

Méthodes approchées et bornes inférieures pour le problème de

gestion de projet multi-compétence

Odile Bellenguez - Emmanuel Néron – Laurent Magniez

Laboratoire d’Informatique de l’Université de Tours,

Département Informatique, Polytech’Tours,

64 avenue Jean Portalis, 37200 Tours

MSPSP - O.Bellenguez - E.Néron - L.Magniez 2

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

– Exemple– Modèle mathématique– Références

• Bornes inférieures– Taches incompatible– Borne préemptive– Approche énergétique

• Borne supérieures– Algorithme Série– Algorithme Parallèle– Une méthode Tabou

• Conclusion


Présentation du MSPSP

Activités:

Personnes:

S1 S2 S3 S4

A1 2 0 1 1

A2 0 1 0 1

A3 0 1 2 0

A4 1 0 1 0

S1 S2 S3 S4

P0 1 1 0 0

P1 0 1 1 0

P2 0 1 0 1

P3 1 1 1 0

P4 1 0 1 1

P5 1 0 1 0

Source Puits

1

2

3

4

2

33

4

4

A1, S1

A1, S4

A1, S1

A1, S3

A2, S4

A2, S2

A4, S1

A4, S4

A3, S3

A3, S3

A3, S2

Cmax = 70 1 2 3 4 5 6P0

P1

P2

P3

P4

P5


Données

• pi : durée de l’exécution de Ai

• bi,k : nombre de personnes exerçant la compétence Sk nécessaire à l’activité Ai pendant son exécution

• Sm,k = 1 si la personne Pm maîtrise Sk, 0 sinon

• A(Pm, t) = 1 si la personne Pm est disponible à la date t, 0 sinon


Contraintes• Précédence:

– une activité ne peut commencer qu’après la fin de ses prédécesseurs

• Ressource/ Affectation: – une personne ne peut exercer qu’une compétence

qu’elle maîtrise

– une personne ne peut répondre qu’à une unité de besoin par unité de temps où elle est disponible

• Objectif: Cmax – minimiser la date d’achèvement totale


Extension aux niveaux de compétences hiérarchiques[Toroslu, 2003]

• Sm,k = h, h {0..H}

• Une personne peut être affectée si elle a au moins le niveau de compétence requis

• On crée une compétence ‘fictive’ pour chaque niveau de compétence de chaque compétence réelle :– Sk correspond à n compétences , h {0,…H}

– Chaque personne a toutes les compétences (fictives) de niveau inférieur ou égal à son niveau de maîtrise :

• = 1, h {0.. H}

hkS

hkmS ,


Modèle mathématique (1/3)

• si Pm commence Ai à t, 0 sinon

• si Pm participe à Sk pour Ai, 0 sinon

n.M.T + n.M.K variables

Contraintes :

• de précédence : (i,j) {1..n} \ Ai Aj,

• de participation :

1,, tmix

1,, kmi

kkj

m ttmj

i

kki

m ttmi

b

txp

b

tx

,

,,

,

,,

t

tmixMmni 1,..,1,,..,1 ,,



• de début :

• de maîtrise :

• Sur le nombre de personnes :

t

kki

h tthi

tmi b

txtxMmni

,

,,

,,,..,1,,..,1

kmkmi SKkMmni ,,,,,..,1,,..,1,,..,1

m t k

kitmi btxni ,,,,,..,1

m

kikmi bni ,,,,,..,1



• de participation maximum

• entre les variables :

• Objectif :

i

t

ptdtmi

i

xMm 1,,..,11

,,

t k

kmitmixMmni ,,,,,...,1,...,1

n

kkn

t mtmn

pb

xC

,

,,

max

Permet de résoudre des problèmes de taille allant jusqu’à 10 activités, 10 personnes, et 3 compétences, à l’aide de Cplex 8.0


Références (1/3)• Cas particulier du RCPSP multi-mode [Sprecher et al, 97], [De Reyck et Herroelen, 97], [Hartmann et Drexl, 98]

- une activité a différents modes d’exécution possiblesEx : faire un trou, M1(3 j) | 3 terrassiers, M2 (1 j) | 1 conducteur

|3 pelles | 1 bulldozer

- un mode correspond à un sous-ensemble de personnesEx: dans un RCPSP multi-mode, l’activité A3 aurait 16 « modes d’exécution»

possibles :

{(P0,P1,P3), (P0,P1,P4), (P0,P1,P5), (P0,P3,P4), (P0,P3,P5), (P0,P4,P5) (P1,P3,P4), (P1,P3,P5) (P1,P4,P5), (P2,P1,P3), (P2,P1,P4), (P2,P1,P5), (P2,P3,P4), (P2,P3,P5), (P2,P4,P5), (P3,P4,P5)}

Augmente très vite avec le nombre de personnes et de compétence

• Jusqu’à 1000 modes par activité dans des ex. de taille normale


Références (2/3)

Toute méthode basée sur l’énumération explicite des

modes est inadaptée :

– Ex : Programme linéaire [Sprecher, 96]

• xj,s,t, = 1 si Aj est achevée en mode s à la fin

de la période t, 0 sinon

• Uj,s,r = quantité de ressource r nécessaire à Aj

en mode s pendant une période t

n.Nbmod.T + n.Nbmod.M variables


Références (3/3)

• Cas particulier du multi-resource shop, [Dauzère-Pérès et

al, 98] :

- une activité a besoin de différentes ressources qui

appartiennent chacune à un groupe de ressources

possibles

Ex: dans un multi-resource shop, l’activité A3 aurait besoin de:

• 1 ressource {P0, P1, P2, P3} (S2)



Bornes inférieures pour le MSPSP


LB1: graphe de compatibilité

S

A3

A2

A1

A5

A6

A7

A4

A9

A8

P

S0 S1 S2

A1 1 2 0

A2 1 1 0

A3 0 3 1

A4 2 1 1

A5 0 0 1

A6 0 2 0

A7 0 2 1

A8 2 1 1

A9 0 1 0

S0 S1 S2

P0 1 0 1

P1 1 1 0

P2 0 1 0

P3 1 1 0

P4 1 0 0

total 4 3 2

S

A3

A2

A1

A5

A6

A7

A4

A9

A8

P

32

3

42

1

3

2

5

iii

i

jiji

up

u

UAAuu

max

1;0

'),(,1

• [Mingozzi et al, 98]


LB2: programmation linéaire simple

• Fixer D, et mettre à jour les di à l’aide du graphe de précédence

• = partie de i exécutée sur [tl , tl+1]

• = temps où Pm exerce

m

lkmki

ili

llkml

km

liil

liil

lili

bxKkLl

ttPmASKkMmLl

xdtsiLlni

xrtsiLlni

pxni

,,,

1,,

,

,1

,

,,...,1,,...,1

),,(,,...,1,,...,1,,...,1

0,,...,1,,...,1

0,,...,1,,...,1

,,...,1

lix ,

lkm,


LB2: programmation linéaire

• S’il existe une solution au programme linéaire :

alors il existe une solution (qui peut-être préemptive)

sinon D + 1 est une borne inférieure valide


LB3: raisonnement énergétique• [Lopez et al, 92], [Baptiste et al, 99]• Fixer D, et mettre à jour les di à l’aide du graphe de précédence

t1, t2 :

t1 t2

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


LB3: raisonnement énergétique

On cherche le flot maximum dans le graphe suivant :

kii

bttiW ,21 ),,( Source Puits

S1

Sk

P1

PM

P2

Si le flot maximum final est inférieur à

ikW(i,t1,t2). bi,k

alors D+1 est une borne inférieure valide

12 tt

A(Pm, t1, t2)


Jeux de données

• 85 instances : - de 15 à 100 tâches ( 27 en moyenne)

- 3 compétences

- 8 à 22 personnes

• Graphes de précédence copiés à partir d’instances classiques du RCPSP

• Tirage aléatoire des compétences : le nombre de tâches susceptibles de s’exécuter en parallèle varie

• NB: Large panel d’instances


Comparaison entre les bornes inférieures

Graphe de compatibilité (exact: PLNE)

Graphe de compatibilité (heur.)

Programma-tion

linéaire

Raisonne-ment énergétique

Meilleure

9.25% 24.65% 6.2% 5.8% 3.75%

0.18 s 0.15 s 12 s 0.5 s

Ecart à la meilleure borne supérieure connue (cf méthodes de résolution):

Méthode de résolution :

Algorithme série


Algorithme série (1/2)

• Adaptation de [Kolish et al, 96], [Klein, 2001] : Serial Schedule Scheme

1. Séquencement des activités selon une liste priorité

2. Pour chaque activité :- fixer sa date de début- Fixer l’ensemble de personnes qui va l’effectuer

Fin Pour


Algorithme série (2/2)

• Règle de séquencement– La liste de priorité est construite à l’aide d’une des règles

classiques (EDD, MST, …) tout en respectant les contraintes de précédence

• Choix de la date de début– plus petite date à laquelle il existe au moins un ensemble de

personnes pouvant répondre aux besoins en compétences. On choisit l’ensemble le moins critique :

– Résolution d’un problème d’affectation à coût minimum


Coût des personnes• Criticité des compétences lors du placement de Ai:

avec Ei = {Aj / ti rj ti+pi}

• Criticité des personnes : CPm = f ( <Sm,k . CSk>k=1..K),

– avec f = somme, moyenne, maximum…

• NB : le calcul peut également être fait sur tout l’horizon du projet (a priori)

ii

i

ij

pt

tt mmkm

EAkj

k

tPAS

b

CS

),(,

,


Affectation à coût minimum

• Modélisation du problème d’affectation sous la forme d’un flot maximum :

Coût unitaire

S1, K

SM, 0

S0, 0

SM, K

1 ; CP1

1 ; CPM

1; CP0

bi, K

bi, 1

bi, 0

S0

S1

SK

P0

P1

PM

PuitsSource

S1, 1

Capacité maxCapacité max

PM-1

1 ; CPM-1

• NB : cela permet de construire directement l’ensemble de personne le moins critique


Résultats

• Testé sur les règles usuelles : EDD, LST, MST…• Permet de déterminer de façon heuristique la

meilleure affectation (au sens de la criticité) pour chaque tâche

En moyenne on est à 7.2% de la meilleure des trois bornes inférieures

Conforme aux résultats attendus



Algorithme parallèle


Algorithme parallèle (1/2)

1. Séquencement des activités identique à la méthode précédente

2. Création de E = {A[1], A[2].. A[i]}, l’ensemble des activités éligibles à t

3. Recherche du flot maximum/ coût min dans le graphe suivant :

b[1],0

Source

A[1]

A[2]

A[i]SK

S0

P0

P1

PM

Puits

b[i],k; 10[i]

b[1],k;10

b[2],k;100

b[1],K

b[2],0

b[2],K

b[i],K

S0,0

S1,0

S0,K

SM,K

1;CP0

1;CP1

1;CPM


Algorithme parallèle (2/2)

• Si le flot maximum = [i] k b[i],k alors on affecte

en parallèle toutes les activités de E• sinon on retire de E, toutes les activités à partir de

la première non satisfaite

Source

A[1]

A[2]

A[4]

SK

S0

P0

P1

PM

Puits

2; 2

4; 43;3

A[3]

5; 4

Capacité

Flot final

=> On place {A[1], A[2]}

.


Une méthode tabou


Méthode Tabou (1/2)

• Inspirée de [Klein, 2000] : Méthode tabou pour le RCPSP

• On construit le voisinage sur la liste de priorité

Un nouveau voisin = échange de deux travaux• L’ordonnancement correspondant est évalué à

l’aide de l’algorithme Série basé sur le flot maximum à coût minimum


Méthode Tabou (2/2)

• Le voisin d’une séquence est construit par permutation de deux activités, sauf si :– l’échange met en jeu deux activités ayant un lien de précédence

– l’échange a déjà été utilisé dans l’itération en cours

– l’échange conduit à une solution tabou

– l’échange ne conduit à aucune modification de la solution courante

• Les solutions sont stockées dans une table de hashage

• La recherche est réinitialisée si trois solutions ont déjà été revisitées


Résultats de la recherche tabou

• En 100 itérations :

- déviation moyenne = 4.55% LB

- temps moyen d’exécution = 44 s• En 2000 itérations :

- déviation moyenne = 4.35% LB

- temps moyen d’exécution = 8 min 40


Conclusion

• Modèle de RCPSP étendu

• Première modélisation des compétences des personnes

• Permet de prendre en compte les indisponibilités des personnes

Perspectives :• Tests sur l’algorithme parallèle seul, puis au sein de la méthode

tabou

• D’autres méthodes en cours de développement : Recovering Beam Search, méthodes exactes, amélioration des bornes inférieures

Documents

Méthodes approchées et bornes inférieures pour le problème de gestion de projet multi-compétence Odile Bellenguez - Emmanuel Néron – Laurent Magniez Laboratoire