20
GPA750 – Gestion de Projets Cours # 5

GPA750 – Gestion de Projets Cours # 5. Gestion de Projet Chapitre 4 du livre de Pinedo Ordonnancement des activités (jobs). Modélisation CPM / PERT Compromis

Embed Size (px)

Citation preview

Page 1: GPA750 – Gestion de Projets Cours # 5. Gestion de Projet Chapitre 4 du livre de Pinedo Ordonnancement des activités (jobs). Modélisation CPM / PERT Compromis

GPA750 – Gestion de Projets

Cours # 5

Page 2: GPA750 – Gestion de Projets Cours # 5. Gestion de Projet Chapitre 4 du livre de Pinedo Ordonnancement des activités (jobs). Modélisation CPM / PERT Compromis

Gestion de ProjetChapitre 4 du livre de Pinedo

Ordonnancement des activités (jobs).

• Modélisation

• CPM / PERT

• Compromis durée coût

• Contraintes de ressources

Page 3: GPA750 – Gestion de Projets Cours # 5. Gestion de Projet Chapitre 4 du livre de Pinedo Ordonnancement des activités (jobs). Modélisation CPM / PERT Compromis

4.1. Introduction

• Quand utilise-t-on la gestion de projet?– Exemples de mise en contexte

• Implantation d’un nouveau logiciel;• Construction d’un aéronef, des avions de transport des troupes ou

des sous-marins nucléaires dans l’industrie de la défense, d’un navire, d’un barrage, etc;

• Caractéristiques: – Réseau des activités décrivant les préséances des activités.

• Contraintes : – Ressources limitées ou illimitées.– Budget à respecter.

• Objectif :– Min temps de finition (Cmax).– Respecter une date promise.– Minimiser les coûts.

Page 4: GPA750 – Gestion de Projets Cours # 5. Gestion de Projet Chapitre 4 du livre de Pinedo Ordonnancement des activités (jobs). Modélisation CPM / PERT Compromis

Représentation graphique• Activité sur les arcs: Voir Fig. 4.2-b

– plus pratique mais nécessite des nœuds artificiels et des activités fictives:

• les activités ont les mêmes nœuds de début et de fin;• Pour représenter des contraintes de préséance

• Activité sur les nœuds : Voir Fig. 4.2-a• Exemple :

Activité(job)

Prédécesseursimmédiats

Succésseursimmédiats Durée

1 4 42 5 63 6,7 104 1 6,7 125 2 6 106 3,4,5 8 27 3,4 8 48 6,7 2

Page 5: GPA750 – Gestion de Projets Cours # 5. Gestion de Projet Chapitre 4 du livre de Pinedo Ordonnancement des activités (jobs). Modélisation CPM / PERT Compromis

4.2.1 Méthode du CPM : Calcul des temps au plus tôt

• S’j : temps de début au plus tôt de l’activité j;• C’j : temps de fin au plus tôt de l’activité j;

• C’j = S’j +pj

• {k j} : ensemble des prédécesseurs immédiats de j.• Procédure Avant (Forward):

– Étape 1:• t=0;• Pour chaque activité n’ayant pas de prédécesseurs

– S’j = 0 et C’j = pj

– Étape 2• Calculer de façon inductive pour chaque j

– S’j = Max {k j} C’k,– C’j = S’j + pj ;

– Étape 3• Le temps de finition Cmax = max (C’1, …., C’n)• FIN

Page 6: GPA750 – Gestion de Projets Cours # 5. Gestion de Projet Chapitre 4 du livre de Pinedo Ordonnancement des activités (jobs). Modélisation CPM / PERT Compromis

4.2.2. Méthode du CPM : Calcul des temps au plus tard

• S’’j : temps de début au plus tard de l’activité j;• C’’j : temps de fin au plus tard de l’activité j;• { j k } : ensemble des successeurs immédiats de j.• Procédure Arrière (Backward) : (Cmax connu)

– Étape 1:• t = Cmax;• Pour chaque activité n’ayant pas de successeurs

– C’’j = Cmax et S’’j = Cmax – pj

– Étape 2• Calculer de façon inductive pour chaque j

– C’’j = Min {j k} S’’k,– S’’j = C’’j - pj ;

– Étape 3• Vérifier que 0 = min (S’’1, …., S’’n)• FIN

Page 7: GPA750 – Gestion de Projets Cours # 5. Gestion de Projet Chapitre 4 du livre de Pinedo Ordonnancement des activités (jobs). Modélisation CPM / PERT Compromis

4.2.3. Calcul des marges et du Chemin Critique

Tyes de Marges

début au plus Tôt (S')

Termine au plus Tard (C'')

Prédécesseurs Tôt (C') Libre Totaleterminent Tard (C'') Indépendante sécurité

Successeurs

Page 8: GPA750 – Gestion de Projets Cours # 5. Gestion de Projet Chapitre 4 du livre de Pinedo Ordonnancement des activités (jobs). Modélisation CPM / PERT Compromis

4.3.2.Types de marges• 4 types de Marges (Slack ou Float)

– Marge totale de l’activité (ou tâche) j: • MTj = S’’j – S’j = C’’j – C’j • Les activités critiques ont des marges de 0 et se trouvent sur un chemin critique.• On assume:

– Les activités en amont (prédécesseurs) de j terminent à leurs temps au plus tôt.– Les activités en aval (successeurs) de j terminent à leurs temps au plus tard.

– Marge libre de l’activité j: • MLj = min k { j k } (S’k – C’j)• Mesure le temps qu’une activité peut être retardée sans affecter le début des activités suivantes en

assumant que les activités prédécesseurs terminent à leurs temps au plus tôt.

– Marge de sécurité de l’activité j:• MSj = C’’j – max k Є {k → j} (C’’k + pj)• Mesure le temps qu’une activité peut être retardée sans affecter le temps de finition du projet en

assumant que toutes les activités prédécesseurs terminent à leurs temps le plus tard

– Marge indépendante de l’activité j:• Mesure le temps qu’une activité peut être retardée sans affecter le temps de début des activités

successeurs en assumant que toutes les activités prédécesseurs terminent à leurs temps le plus tard.

0max

min ' (max '' )j k j kk z jz z j

MIS C p

Page 9: GPA750 – Gestion de Projets Cours # 5. Gestion de Projet Chapitre 4 du livre de Pinedo Ordonnancement des activités (jobs). Modélisation CPM / PERT Compromis

4.2. Exemple d’application de la méthode du CPM

Chemin critique: 1 – 3 – 6 – 9- 11 – 12 - 14

Activité 1 2 3 4 5 6 7 8 9 10 11 12 13 14pj 5 6 9 12 7 12 10 6 10 9 7 8 7 5C'j 5 11 14 23 21 26 33 32 36 42 43 51 50 56

S'j 0 5 5 11 14 14 23 26 26 33 36 43 43 51C''j 5 12 14 24 26 26 34 36 36 43 43 51 51 56S''j 0 6 5 12 19 14 24 30 26 34 36 43 44 51

Marge totale 0 1 0 1 5 0 1 4 0 1 0 0 1 0

Libre 0 0 0 0 5 0 0 4 0 1 0 0 1 0

Securité 0 1 0 0 5 0 0 4 0 0 0 0 1 0

Indépendante 0 0 0 0 2 0 0 4 0 0 0 0 1 0

Page 10: GPA750 – Gestion de Projets Cours # 5. Gestion de Projet Chapitre 4 du livre de Pinedo Ordonnancement des activités (jobs). Modélisation CPM / PERT Compromis

4.3. Méthode PERTProgram Review and Evaluation Technique

• Description de l ’algorithme: On suppose que la moyenne j et la variance 2j de

chacune des variables sont connues ou peuvent être estimées.• Les temps de traitement de n activités sont des variables probabilistes

– Distribution de (Beta)• a – temps optimiste• b – temps pessimiste• m – temps le plus probable (temps normal)• Temps moyen d’une opération de j :

• Variance du temps de traitement de l ’activité j :

– Temps de finition moyen du projet :

– Variance associée au chemin critique :

( 4 ) / 6a m bj j j jp p p

2

2

6

b aj j

j

p p

maxˆ ( )

critique

jj J

E C

2max

ˆ`( )critique

jj J

V C

Page 11: GPA750 – Gestion de Projets Cours # 5. Gestion de Projet Chapitre 4 du livre de Pinedo Ordonnancement des activités (jobs). Modélisation CPM / PERT Compromis

4.3.1.Exemple d’application de la méthode PERT: Exemple 4.3.1

Page 12: GPA750 – Gestion de Projets Cours # 5. Gestion de Projet Chapitre 4 du livre de Pinedo Ordonnancement des activités (jobs). Modélisation CPM / PERT Compromis

4.3.2 Méthode PERT: Chemins alternatifs

• Le chemin critique nous donne le temps moyen pour finir le projet;

• Étant donné la variabilité associée aux activités, il devient possible et important de calculer les probabilités de finir avant une date donnée;

• Il est aussi possible qu’il existe d’autres chemins dont la moyenne est inférieure au chemin critique mais avec une variance plus élevée:– Il se peut que ces chemins soient plus critiques!

• Voir exemple 4.3.1 et 4.3.2

Page 13: GPA750 – Gestion de Projets Cours # 5. Gestion de Projet Chapitre 4 du livre de Pinedo Ordonnancement des activités (jobs). Modélisation CPM / PERT Compromis

4.4. Méthode du Compromis durée-coût : Coûts linéaires

• Contexte : Possibilité de réduire le temps d’exécution d ’une activité en allouant des sommes d ’argent supplémentaires.

• Hypothèses : – le budget existe– les durées sont déterministes– mais que la durée d’une activité est une

fonction linéaire du coût• On peut diminuer la durée en investissant

plus de ressources et donc plus d’argent.• pj

min : durée minimale de j pour un coût de cj

a

• pjmax : durée maximale de j pour un coût de

cjb

• cj = coût marginal pour réduire le temps d’opération par une unité de temps

• Coût de traitement de l’activité en pj unités de temps, où pj

min pj pjmax est : cj

b + cj(pj

max – pj)– On assume qu’il y a un coût fixe de c0 par

jour d’opération.

max min

a bj j

jj j

c cc

p p

Page 14: GPA750 – Gestion de Projets Cours # 5. Gestion de Projet Chapitre 4 du livre de Pinedo Ordonnancement des activités (jobs). Modélisation CPM / PERT Compromis

4.4.1 Prétaitement de la méthode du compromis durée-coût

• Prétraitement de l’heuristique 4.4.1:– Ajouter un nœud de début (source), avec un temps

de 0, et un nœud de fin (puit) bau réseau du projet• Gcp est le sous graphe contenant les chemins

critiques :– Gcp contient toujours le nœud de début et le nœud de

fin– Un ensemble de coupe (cut set)

• est un ensemble de nœuds dont l’élimination du sous-graphe Gcp isole le nœud de début du nœud de fin

– Un ensemble de coupe est minimal (minimal cut set) si en mettant n’importe quel nœud dans le graphe Gcp, un chemin est rétabli entre la source et le puit.

Page 15: GPA750 – Gestion de Projets Cours # 5. Gestion de Projet Chapitre 4 du livre de Pinedo Ordonnancement des activités (jobs). Modélisation CPM / PERT Compromis

4.4.2 Méthode du Compromis durée-coût : Heuristique 4.4.1

• Étape 1– Toutes les activités sont à leurs temps max.– Déterminer tous les chemins critiques.– Construire le sous-graphe Gcp des chemins critiques.

• Étape 2– Déterminer tous les ensembles de coupe minimal (minimal cut set) dans Gcp.

– Considérer seulement les ensembles où les temps d’opération sont strictement supérieurs à leurs minimum.

– S’il n’existe pas de tel ensemble: FIN; sinon aller à 3.• Étape 3

– Pour chaque ensemble minimal.• Calculer le coût de réduction des temps d’opération par une unité.

– Pour l’ensemble ayant le coût minimal.• Si le coût est C0 (le coût fixe par jour) aller à 4.• Sinon FIN.

• Étape 4– Réduire la durée des activités de l’ensemble de coupe minimal à coût moindre

par une unité.– Déterminer le nouvel ensemble des chemins critiques.– Réviser le graphe Gcp et aller à 2.

Page 16: GPA750 – Gestion de Projets Cours # 5. Gestion de Projet Chapitre 4 du livre de Pinedo Ordonnancement des activités (jobs). Modélisation CPM / PERT Compromis

4.4.3 Modèles mathématiques: Compromis

durée-coût• Formulation Mathématique : Modèle de

programmation linéaire (voir p. 71).

• Fonction non-linéaire : Modèle de programmation non-linéaire ( voir p. 72, section 4.5).

Page 17: GPA750 – Gestion de Projets Cours # 5. Gestion de Projet Chapitre 4 du livre de Pinedo Ordonnancement des activités (jobs). Modélisation CPM / PERT Compromis

Exemple d’application : méthode du compromis durée-coût (linéaire)

Tableau des coûts et des durées

Réseau initial – Tous les temps sont au max

Chemin critique: 1-3-6-9-11-12-14Temps de finition: 56

• La tâche 12 est l’ensemble minimal à coût moindre• Réduire 12 d’une unité

• + 2$ en coût variable• - 6 $ en coût fixe• Économie: 4

9

Page 18: GPA750 – Gestion de Projets Cours # 5. Gestion de Projet Chapitre 4 du livre de Pinedo Ordonnancement des activités (jobs). Modélisation CPM / PERT Compromis

Exemple d ’application: méthode de compromis durée-coût (suite)

Page 19: GPA750 – Gestion de Projets Cours # 5. Gestion de Projet Chapitre 4 du livre de Pinedo Ordonnancement des activités (jobs). Modélisation CPM / PERT Compromis

4.6. Gestion de projets avec contraintes de ressources

• Pm/prec/Cmax

• Formulation Mathématique : Modèle de programmation en nombres entiers (voir pages 74- 75)

• Traitement de plusieurs projets en parallèle.

Page 20: GPA750 – Gestion de Projets Cours # 5. Gestion de Projet Chapitre 4 du livre de Pinedo Ordonnancement des activités (jobs). Modélisation CPM / PERT Compromis

4.7 Outils informatiques

• MS project.• Les logiciels disponible commercialement pour

des grands projets d’entreprises:– Baan– SAP– JDEdwards

• Outils spécialisés de résolution des programmes linéaires ou en nombres entiers :– WinQSB– Cplex– Mathlab