62
1 he du plus long chemin dans un réseau. Outil de ges : algorithme de Ford pour la recherche d’un chemin alcul de la durée minimale d’un projet. Méthodes pe rimer la durée d’un projet au moindre coût. La méth durée aléatoire des tâches. Le contrôle des coûts v des délais imposés. Exemples.

1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

Embed Size (px)

Citation preview

Page 1: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

1

Recherche du plus long chemin dans un réseau. Outil de gestion deprojet : algorithme de Ford pour la recherche d’un chemin critiqueet le calcul de la durée minimale d’un projet. Méthodes permettantde comprimer la durée d’un projet au moindre coût. La méthodePERT : durée aléatoire des tâches. Le contrôle des coûts vs lerespect des délais imposés. Exemples.

Page 2: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

2

Introduction

L’instinct et le geste impulsif ont fréquemment cédé le pas à l’actionréfléchie et au geste planifié.

La planification ne date pas de la vie moderne :

la construction de l’Arche de Noé : réussite.

l’édification de la tour de Babel : non menée à terme.

Pour les projets complexes exigeant de grands moyens, faisantintervenir un grand nombre de personnes, et dont le caractère estnon répétitif, on doit penser à :

- préciser l'objectif;- déterminer les opérations ou les tâches nécessaires à réaliser;- estimer la durée et les ressources exigées par chaque tâche;- estimer les risques et prévoir les marges nécessaires pour les pallier;- calculer la durée totale et le coût total du projet;- dresser un calendrier d'échelonnement des tâches.

Page 3: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

3

1er problème

On s’intéresse à la recherche du plus long chemin dans un réseau.

chemin critiqueVoici un exemple d’application :

Une compagnie désire mettre en exploitation un nouveau gisementminier. Les opérations suivantes doivent être réalisées :

a. Obtention d’un permis d’exploitation 180b. Construction d’une piste entre route et site 120c. Installation de deux sondeuses 7d. Érection de baraques provisoires 21e. Asphaltage de la piste 30f. Adduction d’eau 60

Durée (jours)

Dans la planification d’un projet impliquantplusieurs tâches, exigeant chacune un temps d’exécution et reliéesentre elles selon un ordre de précédence, on cherche le tempsminimum d’achèvement du projet.

Page 4: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

4

g. Campagne de sondages 210h. Fonçage et équipement des puits 120i. Installation au fond du matériel d’exploitation 42j. Construction de logements pour le personnel 150k. Traçage et aménagement du fond 330l. Construction d’une laverie 210

Relations d’antériorité :

b doit être précédée de a et suivie des opérations c, d, e, f.

c et d précèdent g.

e, f et g précèdent h et j.

h et j précèdent i, k et l.

Durée (jours)

Page 5: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

5

Construction d’un graphe simple appelé diagramme PERT

Les arcs seront les opérations et les sommets seront des événements(l’achèvement de certaines tâches) liés à ces opérations.

D Fa, 180 b, 120

c, 7d, 21

e, 30

f, 60

g, 210

h, 120

j, 150

i, 42

l, 210

k, 330

D début des opérations F fin des opérations

Note :

Ce diagramme n’est pas un graphe simple à cause des opérationsparallèles c, d et e,f et i, k, l resp.

Graphe simple : graphe tel qu’il n’y a jamais plus d’un arcallant d’un sommet à un autre.

Page 6: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

6

Pourquoi un graphe simple ?Les algorithmes connus pour trouver un chemin critique nécessitentun graphe simple.

Comment convertir ce graphe en un graphe simple ?

Prenons par exemple les opérations parallèles c et d.

Le moyen le plus simple est de créer un événement fictif et uneopération fictive de durée nulle comme ceci :

c

de

f

g0

n opérations parallèles nécessitent n - 1 sommets fictifs etn-1 opérations fictives de durée nulle.

Page 7: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

7

1 12a, 180 b, 120

c, 7

d, 21

e, 30

f, 60

g, 210

h, 120

j, 150

i, 42

l, 210

k, 330

On obtient donc pour le graphe au complet le diagramme PERTsuivant :

2 3

6

0 0

7

8

9

11

0

10

0

5

4

0

Page 8: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

8

Prise en compte de différents types d’opérations :

Opérations composées

Soit une opération a, constituée des 3 opérations élémentairessuccessives a1, a2 et a3 de telle sorte que l’opération c suive a1,d suive a2 et b suive a3.

Sous forme graphique, on obtient :

a1 a2 a3 b

c d

Cela peut arriver lorsqu’on demande que c ne commence qu’unefois le premier tiers de a effectué et que d ne commence qu’unefois les deux premiers tiers de a effectués. De plus, a précède b.

L’opération a est divisée en 3 sous-opérations de durée égale autiers de celle de a.

Page 9: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

9

Opérations dépendantes et indépendantes

Soit,a

b

c

d

c et d sont des opérations dépendantes de a et de b.

Effectuons le changement suivant : c doit succéder à a,d est dépendante de a et b.

Il faut créer un état fictif et une opération fictive de durée nulle :a

b

c

d

Page 10: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

10

Limites de démarrage : 1er cas

Soit le graphe partiel suivant,

D

a b

c

Suite à des imprévus, l’opération c ne pourra commencer avant t0

unités de temps écoulées depuis le début des travaux.

Il faudra donc créer une opération fictive de durée t0 allant dudébut des travaux au début de c.

Puisque b n’est pas astreinte à cette contrainte de démarrage, ondoit introduire un sommet fictif libérant b de cette limite dedémarrage tout en tenant compte du fait que b et c suivent a.

Finalement, on doit prévoir une opération fictive de durée nulleindiquant la dépendance de c envers a.

Page 11: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

11

D

ab

c0

t0

Limites de démarrage : 2ième cas

Pour qu’une tâche i puisse débuter, il est nécessaire que la duréeécoulée depuis le début d’une autre tâche k soit au moins égale àune durée donnée tki.

On doit ajouter l’arc (k, i) représentant une opération fictivede durée tki.

Page 12: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

12

Problème de la recherche du chemin critique(les tâches qui s’y trouvent sont critiques pour la durée du projet)

Il s’agit de trouver la date de réalisation de la fin des travaux i.e.la date la plus proche qui permette que toutes les opérations soientréalisées et la séquence de tâches qui réalise cette durée.

Cela consiste à déterminer le chemin le plus défavorable du débutà la fin des travaux i.e. le chemin de longueur maximale.

2

3

13

67

Exemple :

La fin des travaux aura lieu à la date 9.L’opération (1, 3) aura 2 unités de temps supplémentaires pourêtre réalisée.

Convention : Le temps de début des travaux sera toujours le temps 0.

Page 13: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

13

Résolution du problème de la recherche du chemin critique

Un diagramme PERT est connexe et sans circuit.

Autrement, nous serionsen présence de plusieurs projets.

Une opération ne peut sesuccéder à elle-même.

Considérons une légère adaptation de l’algorithme de Bellman-Kalabasur le diagramme précédent.

Soit ti,j la durée de l’opération qui va du sommet i à j, ti le temps de réalisation au plus tôt ou temps attendu,

(par convention, t1 = 0)

Page 14: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

14

1 12a, 180 b, 120

c, 7

d, 21

e, 30

f, 60

g, 210

h, 120

j, 150

i, 42

l, 210

k, 3302 3

6

0 0

7

8

9

11

0

10

0

5

4

0

t2 = t1 + t1,2 = 180

t3 = t2 + t2,3 = 300

t4 = t3 + t3,4 = 300

Pour le sommet 5, il y a 2 possibilités : t3 + t3,5 = 321 ou t4 + t4,5 = 307.Vu qu’on cherche le chemin le plus long, on prendra : t5 = 321.

Page 15: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

15

t6 = t3 + t3,6 = 300

t7 = max {t3 + t3,7 , t6 + t6,7 , t5 + t5,7} = 531.

Et ainsi de suite, jusqu’à t12 = 1011.

1 12a, 180 b, 120

c, 7

d, 21

e, 30

f, 60

g, 210

h, 120

j, 150

i, 42

l, 210

k, 3302 3

6

0 0

7

8

9

11

0

10

0

5

4

0

0 180 300

300 531 681

681

1011

681531

321

300

temps de réalisation au plus tôt

Page 16: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

16

Notion de chemin critique

Un ensemble d’opérations dites critiques en ce sens qu’on ne peuttolérer aucun retard dans leur mise en exécution et dans leurexécution sans retarder le temps tn de la fin des travaux(ici t12 = 1011).

1 12a, 180 b, 120

c, 7

d, 21

e, 30

f, 60

g, 210

h, 120

j, 150

i, 42

l, 210

k, 3302 3

6

0 0

7

8

9

11

0

10

0

5

4

0

0 180 300

300 531 681

681

1011

681531

321

300

Ex. : (1, 2, 3, 5, 7, 8, 9, 12)

Le chemin critiqueest indiqué en traits doubles.

Page 17: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

17

Temps de réalisation au plus tard ou temps limite

Les opérations non critiques peuvent sans doute être retardées dansleur mise à exécution sans retarder le temps final des travaux.

Soit ti le temps limite de réalisation à laquelle peut se fairel’événement i sans retarder le temps tn de la fin des travaux.

Note : tn = tn ti = ti i dans le chemin critique.et

Comment obtenir les temps de réalisation au plus tard :

ti = tn - le temps minimal nécessaire pour réaliser lesopérations entre i et n

ti = tn - somme des temps opératoires sur le cheminle plus long de i à n.

Cependant, il est possible de les obtenir très rapidement.

Page 18: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

18

1 12a, 180 b, 120

c, 7

d, 21

e, 30

f, 60

g, 210

h, 120

j, 150

i, 42

l, 210

k, 3302 3

6

0 0

7

8

9

11

0

10

0

5

4

0

0 180 300

501 531 801

969

1011

681531

321

314

temps de réalisation au plus tard

t10 = t12 – t10,12 = 969 t11 = t12 – t11,12 = 801

t9 = temps minimal nécessaire= min{ t12 – t9,12, t11 – t9,11, t10 – t9,10} = min{681,801,969} = 681

etc.

Page 19: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

19

Traçons maintenant le chemin critique à partir des ti et des ti:

Le sommet i fait partie du chemin critique si ti = ti.

Si les sommets i et j font partie du chemin critique,l’opération de i à j sera critique si tj - ti,j = ti.

Page 20: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

20

Intervalle de flottement d’un événement i

[ti, ti] est l’intervalle de temps où peut se réaliser l’événement isans retarder le temps de fin des travaux.

Note : Les événements du chemin critique auront unintervalle de flottement réduit à un seul point.

Si l’intervalle de flottement de l’événement k estréduit à un seul point, l’événement k appartiendraà un des chemins critiques (s’il y en a plusieurs).

Exemple : 1 0 2 180 3 300 4 [300, 314]

5 321 6 [300, 501] 7 531 8 531

9 681 10 [681, 962] 11 [681, 801] 12 1011

Page 21: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

21

Marge libre d’une opération de i à j

Le délai qui peut être apporté à la mise à exécution de l’opération(i, j) sans pour autant retarder le temps de réalisation au plus tôt del’événement j.

Il s’agit de : tj - ti,j - ti.

Exemple :

(1,2) (2,3) (3,4) (3,5) (3,6) (3,7) (4,5) (5,7) (6,7) (7,8)

0 0 0 0 0 171 14 0 201 0

(7,9) (9,10) (9,11) (9,12) (10,12) (11,12)

30 0 0 0 281 120

Note : Une opération critique entraîne une marge libre nulle.L’inverse n’est pas vrai.

Ex. : l’arc (3,4) n’est pas une opération critique.

Page 22: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

22

La marge libre est un concept local qui ne tient pas compted’une suite d’opérations non critiques.

Marge totale d’une opération de i à j

Or, ce qui nous importe le plus en général est de ne pas retarderla fin des travaux même si on doit faire des réaménagements surquelques opérations non critiques.

Exemple : On peut retarder le début de l’opération (3, 4)de 14 unités sans retarder la fin des travaux.

La marge totale indique le délai maximal qui peut s’écouler avantle début de l’opération (i, j) sans retarder la fin des travaux maisen retardant peut-être celui de j sans dépasser son temps deréalisation au plus tard :

tj - ti,j - ti.

Page 23: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

23

Exemple :

(1,2) (2,3) (3,4) (3,5) (3,6) (3,7) (4,5) (5,7) (6,7) (7,8)

0 0 14 0 201 171 14 0 201 0

(7,9) (9,10) (9,11) (9,12) (10,12) (11,12)

30 288 120 0 288 120

Page 24: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

24

Diagramme à barres de de Gantt

Construit à l’aide de la marge totale et du diagramme PERT, il nousindique les opérations critiques en 1ière rangée avec l’échéancier àrespecter.

Sous les opérations critiques se placent les opérations non critiquesdans les cases où elles peuvent varier librement.

Exemple :

L’opération c précède l’opération d, toutes 2 non critiques;c peut varier de 10 à 20 étant d’une durée de 3; d peut varier de 17 à 24 étant d’une durée de 4.

10 24

c 3

d 4

2017

Page 25: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

25

Diagramme de Gantt tiré de notre exemple :

0 180

a b

300

d g j k

321 531 681 1011

c 7

f 60

e 30

h 120 i 42

l 210

Cela indique bien visuellement ce qu’on peut faire sans toucher autemps de fin des travaux.

Note : Le diagramme devrait être tracé à l’échelle.

Page 26: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

26

Algorithme de Ford pour calculer les temps au plus tôt ti.

Étape 0. Poser ti = 0 i = 1, 2, …, n.Poser i = 1, j = 2.

Étape 1. Si l’arc (i, j) n’existe pas dans le diagrammealors aller à l’étape 4.

Étape 2. Si tij > tj - ti, faire tj = tij + ti et aller à l’étape 3.

sinon aller à l’étape 4.

Étape 3. Si i > j, faire i = j, j = 2 et aller à l’étape 5

sinon aller à l’étape 4.

Étape 4. Faire j = j + 1.

Étape 5. Si j n aller à l’étape 1

sinon faire j = 2, i = i +1 et aller à l’étape 6.

Étape 6. Si i n aller à l’étape 1

sinon Fin.

Page 27: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

27

Algorithme de Ford pour calculer les temps au plus tard ti.

Il s’agit d’utiliser l’algorithme de Ford précédentoù chaque sommet i a été remplacé par n – i + 1,

chaque arc (i, j) du diagramme est remplacé par (j, i).

Les résultats obtenus sont placés sur le diagramme originalaprès avoir effectué le calcul suivant :

ti = tn - somme des temps opératoires sur le cheminle plus long de i à n.

Page 28: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

28

BREF

Les notions précédentes ont une grande importance :

L’établissement du diagramme PERT permet de préciser ledéroulement des opérations avec les interactions des différentestâches.

La mise en évidence d’un chemin critique détermine lesopérations conditionnant la réalisation du projet.

Elles devront être surveillées attentivement par le gestionnairedu projet.

Les opérations non critiques sont moins rigides et peuventtolérer certains retards quant à leur temps de mise en œuvre(intervalles de flottement, marges libre et totale).

Page 29: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

29

En pratique, les durées tij des opérations sont mal connues et incertaines.

Deux cas se présentent :

A On connaît les distributions des temps d’opérations à partir dedonnées statistiques obtenues dans la réalisation de projetssemblables.

Déterminer le temps moyen et la variance de chaqueopération : tij et 2

ij.

Ce temps moyen de chaque opération servira comme durée del’opération.

La variance interviendra plus tard dans l’estimation du temps defin des travaux.

Page 30: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

30

B On suppose que les temps d’opération sont distribués selon une loiBêta pour des raisons de commodité de calculs.

T ~ Bêta(a, b)

T est une v.a. comprise dans l’intervalle [a, b]où a et b sont des constantes positives.

L’aspect de la distribution Bêta en fonction des paramètresa, b et M est le suivant :

a bM

M désigne la valeur de T où sa fonction de densité est maximale.

Page 31: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

31

Les paramètres de cette fonction de densité sont choisis de telle façon

tij = (aij + 4Mij + bij) / 62

ij = (bij - aij)2 / 36.

Pour déterminer les valeurs de tij et 2ij, il suffit de poser les questions

suivantes aux spécialistes responsables de chaque opération :

À combien estimez-vous la durée minimale de l’opération (i, j) ?

À combien estimez-vous la durée maximale de l’opération (i, j) ?

Quelle est la durée la plus probable de l’opération (i, j) ?

Note : Ces informations fort subjectives doivent être utiliséesavec prudence.

Page 32: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

32

Exemple :

Les opérations fictives demeurent avec des durées nulles.

Page 33: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

33

1 12a, 180 b, 135

c, 6

d, 20

e, 28

f, 61

g, 205

h, 160

j, 140

i, 50

l, 215

k, 3152 3

6

0 0

7

8

9

11

0

10

0

5

4

0

00

180180

315315

315512

540560

700800

700965

10151015

700700

540540

335335

315329

Le chemin critiqueest indiqué en traits doubles.

Le chemin critique est 1, 2, 3, 5, 7, 9, 12 et son espérance mathématiqueest égale à la somme des espérances des opérations qui le composent i.e.E(t12) = 1015.

Page 34: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

34

Si les opérations sont en nombre suffisant et les temps opératoires sontindépendants, le théorème central-limite s’applique.

Page 35: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

35

Sous ces hypothèses, on obtient que :

2t12

= 21,2 + 2

2,3 + 23,5 + 2

5,7 + 27,9 + 2

9,12 = 1300.1111

Calcul de la variance des dates au plus tôt des autres événements :

Il s’agit de considérer le chemin le plus long de 1 à 8 et,

Ex. : E(t8) = 540 = somme des temps moyens sur le chemin le plus long de 1 à 8.

2t8 = 2

1,2 + 22,3 + 2

3,5 + 25,7 + 2

7,8 = 797.3333

Calcul de la variance des dates au plus tard des autres événements :

Il s’agit de considérer le chemin le plus long de 4 à 12 et,

Ex. : E(t4) = 329 = somme des temps moyens sur le chemin le plus long de 4 à 12.

2t4 = 2

4,5 + 25,7 + 2

7,9 + 29,12 = 973.8055

Page 36: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

36

Importance du calcul des variances pour la réalisation d’un projet

Supposons que le contracteur qui réalise les travaux s’est engagé à lesterminer avant 1100 jours et qu’après, il ait à payer des pénalités parjour de retard.

Le contracteur est intéressé à connaître la probabilitéqu’il respecte son engagement.

t12 – 1015 N(0, 1) 36.057

Par conséquent, P(t12 ≤ 1100) = P( t12 – 1015 ≤ 2.36) ≥ 99% 36.057

ce qui laisse une marge de manœuvre suffisante au contracteur.

Note : Si le contracteur s’était engagé à terminer les travaux avant 1040jours, on aurait trouvé P(t12 ≤ 1040) ≥ 75,8% Risque élevé.

Le contracteur augmenterait alors le prix de sa soumission.

Page 37: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

37

Analyse des coûts de réalisation des tâches d’un projet

L’accélération du temps de réalisation d’une tâche se traduit par uneaugmentation de son coût.

Dorénavant, chaque temps opératoire tij peut varier entre deux bornesdij et Dij.

Limite supérieure ou durée normale(temps opérationnel normal)

Limite inférieure ou durée accélérée(temps minimal nécessaire pour réaliser l’opération Pij)

Terminologie :

En optant pour la durée normale (accélérée) de chaqueopération, le problème à résoudre est dit le programme normal(accéléré).

Note : Habituellement, le programme accéléré est trop coûteux etle programme normal trop long.

Page 38: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

38

Coût de réalisation cij de l’opération Pij

La fonction de coût a généralement la forme suivante :

tij

cij

dij Dij

Le coût de l’opération est minimal si sa durée est normale etcroît lorsqu’on s’en éloigne.

Si tij > Dij on ne peut effectuer le travail qu’à des coûts beaucoupplus élevés ce qui correspond habituellement à desmoyens insuffisants en main d’œuvre et matériel.

****

Page 39: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

39

Comment trouver des durées qui représentent un juste milieu entre nospossibilités temporelles et financières ?

1ière approche : Diminution du coût total d’un programme enaugmentant la durée des opérations non critiques.

On suppose ici qu’il nous est impossible de modifier la durée desopérations critiques et donc la date de fin des travaux.

Par contre, on peut modifier la durée des opérations non critiques.

La durée tij de chaque opération Pij est contrainte comme suit :

dij ≤ tij ≤ Dij

Considérons un exemple où les durées tij sont indiquées sur les arcsdans le diagramme PERT suivant :

Page 40: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

40

Exemple :

Page 41: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

41

Exemple (suite) :

L’augmentation des coûts est proportionnelle à la diminution des tempsopératoires, i.e. les fonctions de coût sont linéaires et décroissantes.

Posons cij coût marginal de l’opération Pij ou encore,l’augmentation d’une unité dans la durée del’opération Pij implique une diminution de cij

dans le coût de cette opération.

Dans le tableau suivant, on retrouve :- les durées normales,- les durées accélérées,- les temps opératoires,- les marges libres,- les marges totales,- les couts marginaux,- les coûts opératoires,- le coût total (la somme des coûts de toutes les opérations).

Page 42: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

42

Exemple (suite) :

cij

Coût total : 214,000$

Page 43: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

43

Exemple (suite) :

La durée du programme étant inchangée, il suffit de diminuer lamarge libre des opérations non critiques pour diminuer le coût total.

Les nouvelles durées des opérations non critiques ne pourront êtresupérieures à :

t'ij = tij + min(mlij, Dij - tij)= min(Dij, tij + mlij).

Dans cet exemple, choisissons comme durées ces bornes supérieures.

Page 44: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

44

Exemple (suite) : On obtient le nouveau diagramme PERT suivant :

Cela crée un nouveau chemin critique (1, 2, 5, 3, 6, 8, 9).

4

Page 45: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

45

Exemple (suite) :

Pour chaque opération non critique, la diminution du coût seraégale à : cij (t'ij - tij).

On obtient alors pour les opérations non critiques indiquées,la diminution de coût suivante :

Cela donne une diminution totale de 39, 400$ et le coût totals’établit maintenant à 214, 000 – 39,400 = 174, 600$.

diminution de 18.6% env.

Page 46: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

46

Il ne faut pas croire que l’on soit parvenu pour une date de fin destravaux égale à 31 à un programme de coût minimal.

2

124

On pourrait tenir compte de la marge totale de P24.

Page 47: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

47

On peut augmenter la durée de P24 de 2 unités (économie de 4600$) etlaisser la durée de P45 à 2 unités au lieu de 4. Nous aurions réalisé uneéconomie supplémentaire de 2,700$.

Page 48: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

48

2ième approche : Accélération d’un programme au moindre coût.

Pour réduire le temps total d’exécution d’un programme, il fautréduire la durée d’une ou de plusieurs opérations critiques.

Si nous choisissons l’opération critique qui, pour une mêmediminution de temps, propose la plus faible augmentation des coûts,nous dirons que nous avons accéléré le programme au moindre coût.

Page 49: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

49

Exemple :

g

f

h

d

c

e

i

b

a

Les fonctions de coût des opérations sont de la forme ****.

Ce diagramme PERT représente un programme normal admettantun coût total de 350 millions (voir tableau suivant).

Nous avons aussi un programme accéléré dans ce tableau.

Page 50: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

50

durées(mois) et coûtsde

chaque opération

durées(mois) et coûtsde

chaque opération

Coût total: 350 x 106$ 523 x 106$

Page 51: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

51

Il n’est pas nécessaire d’augmenter la durée des opérations critiques :on dépenserait alors de l’argent inutilement.

Attaquons-nous aux opérations critiques a, b, f et i.

Puisque le coût d’accélération par mois est :

a : 5 millionsb : 19 millionsf : 13 millionsi : 3 millions,

pour accélérer le programme au moindre coût, il s’agit de réduirele temps opératoire de 1 mois sur i ce qui va coûter le moins cher.

Page 52: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

52

g

f

h

d

c

e

i

b

a

Le diagramme PERT devient :

2

35 35

En gagnant 1 mois sur i, nous n’avons pas créé de nouveauxchemins critiques car, autrement, il aurait fallu tenir comptedes nouvelles opérations critiques.

Page 53: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

53

Essayons de gagner un autre mois.

On ne peut le faire sur i puisqu’elle a déjà atteint sa durée accélérée.

Parmi les autres opérations critiques (a, b et f), a coûte le moins cherà accélérer et puisqu’on peut l’accélérer, gagnons un autre mois surl’opération a.

g

f

h

d

c

e

i

b

a2

34 343

9 9

3 3

19 22

32 32

Page 54: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

54

Essayons de gagner un autre mois sur la tâche a, ce qui est possible.

g

f

h

d

c

e

i

b

a2

33 332

8 8

2 2

18 21

31 31

Il n’est maintenant plus possible d’accélérer la tâche i ou la tâche a.

Entre b et f, il faut choisir f.

Page 55: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

55

On peut gagner 3 autres mois sans difficulté.

g

f

d

c

i

b

a2

30 302

8 8

2 2

18 18

28 28h

10

20

ce qui fait apparaître un nouveau chemin critique.

e

Page 56: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

56

Pour réduire la durée totale d’exécution, 3 possibilités s’offrent à nous :

gagner 1 mois sur b : coût de 19 millions,

gagner 1 mois sur f : coût de 13 millions,et 1 mois sur e : coût de 5 millions, d’où un coût de 18.

gagner 1 mois sur f : coût de 13 millions,et 1 mois sur h : coût de 7 millions, d’où un coût de 20.

On choisit donc la 2ième option.

Page 57: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

57

g

f

d

c

i

b

a2

29 292

8 8

2 2

17 17

27 27h

10

19

e 9

On ne peut plus accélérer la tâche e.Il nous reste 2 alternatives :

gagner 1 mois sur b : coût de 19 millions,

gagner 1 mois sur f : coût de 13 millions,et 1 mois sur h : coût de 7 millions, d’où un coût de 20.

Page 58: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

58

g

f

d

c

i

b

a2

28 282

7 7

2 2

16 16

26 26h

10

19

e 9

Gagnons un mois sur b.

5

Finalement, il nous reste une possibilité :

gagner 1 mois sur f : coût de 13 millions,et 1 mois sur h : coût de 7 millions, d’où un coût de 20.

Page 59: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

59

g

f

d

c

i

b

a2

27 272

7 7

2 2

16 16

25 25h

9

18

e 9

5

Il n’est maintenant plus possible d’accélérer la date des travauxdans cet exemple.

Page 60: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

60

En résumé,

Durée du programme

(mois)

Coût

(millions $)

a b c d e f g h i

36 350 4 6 4 12 10 23 7 10 3

35 353 4 6 4 12 10 23 7 10 2

34 358 3 6 4 12 10 23 7 10 2

33 363 2 6 4 12 10 23 7 10 2

32 376 2 6 4 12 10 22 7 10 2

31 389 2 6 4 12 10 21 7 10 2

30 402 2 6 4 12 10 20 7 10 2

29 420 2 6 4 12 9 19 7 10 2

28 439 2 5 4 12 9 19 7 10 2

27 459 2 5 4 12 9 18 7 9 2

Durée des opérations(mois)

C’est au gestionnaire de choisir l’alternative la plus appropriée.

Page 61: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

61

Généralisations possibles du problème :

La fonction de coût avait jusqu’à maintenant la forme suivante :

tij

cij

dij Dij

****

tij

cij

dij Dij

Voici des alternativesoù le problème devientplus difficile :

tij

cij

dij Dijt*

Page 62: 1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford pour la recherche dun chemin critique et le calcul de la

62

Généralisation au programme à coût minimal si les coûts sont desfonctions quelconques des durées :

Posons cij(tij) le coût en fonction de la durée de la tâche Pij,dij la durée accélérée de la tâche Pij,Dij la durée normale de la tâche Pij,dn et Dn les durées accélérée et normale d’exécution,tij la durée de la tâche Pij,t la durée totale d’exécution,U l’ensemble des arcs du programme,on cherche à minimiser le coût total de ce programme.

MIN cij(tij)(i,j) U

Sujet à tij ≤ t chemin allant du sommet 1 au sommet n.(i,j)

dn ≤ t ≤ Dn

dij ≤ tij ≤ Dij tâche Pij