View
217
Download
0
Category
Preview:
DESCRIPTION
C3_GestionProjet
Citation preview
Jean-Charles Rgin
Gestion de projet
Licence Informatique 3me anne - MIAGE
Jean-Charles Rgin
Gestion de projet : Ordonnancement
Licence Informatique 3me anne - MIAGE
Remerciements
Michel Minoux
Type de chefs de projets
Petite socit : essentiellement en charge dun projet pour un client
Socit Moyenne : Projet pour un client Rarement projet interne Rarement projet interne Rarement projet financement extrieur (Europe, Gouvernement, priv etc)
Grosse Socit Gros Projets pour client (IBM Watson > $1Million) Projet interne (diteur logiciel) frquent Projet financement extrieur frquent
Gestion de projet : Ordonnancement
Gantt chart
Graphe : dfinitions
Ordonnancement
Graphe Potentiel Tches Graphe Potentiel Tches
Fonction rang dun graphe
Graphe Potentiel Etapes (PERT)
Gantt chart
Dvelopp par Henry L. Gantt, ingnieur amricain, vers 1910.
Le diagramme de Gantt permet
de visualiser dans le temps les diverses tches lies de visualiser dans le temps les diverses tches lies composant un projet
de reprsenter graphiquement l'avancement du projet.
Deux objectifs :
planifier de faon optimale
communiquer sur le planning tabli
Gantt chart
Abscisse : units de tempsOrdonne : diffrentes tches
Permet de :
dterminer les dates de ralisationdterminer les dates de ralisation
identifier les marges existantes
visualiser d'un seul coup d'oeil le retard ou l'avancement des travaux.
Gestion de projet : Ordonnancement
Gantt chart
Graphe : dfinitions
Ordonnancement
Graphe Potentiel Tches Graphe Potentiel Tches
Fonction rang dun graphe
Graphe Potentiel Etapes (PERT)
Graphe : dfinitions
Un Graphe Orient G=(X,U) est dtermin par la donne : dun ensemble de sommets ou nuds X
dun ensemble ordonn U de couples de sommets appels arcs. appels arcs.
Si u=(i,j) est un arc de G alors i est lextrmit initiale de de u et j lextrmit terminale de u.
Les arcs ont un sens. Larc u=(i,j) va de i vers j.
Ils peuvent tre munit dun cot, dune capacit etc
Graphe
Graphe
On note par (i) : lensemble des arcs ayant i comme extrmit
On note par +(i) : lensemble des arcs ayant i comme extrmit initiale = ensemble des arcs sortant de isortant de i
On note par -(i) : lensemble des arcs ayant i comme extrmit terminale = ensemble des arcs entrant dans i
N(i) : ensemble des voisins de i : ensemble des sommets j tels quil existe un arc contenant i et j
Graphe non orient
Un Graphe non orient G=(X,E) est dtermin par la donne :
dun ensemble de sommets ou nuds X
Dun ensemble E de paires de sommets appeles artes Dun ensemble E de paires de sommets appeles artes
Les artes ne sont pas orientes
Graphe non orient
Graphe : dfinitions
Deux sommets sont voisins sils sont relis par un arc ou une arte
Degr entrant dun sommet i : nombre darcs ayant i comme extrmit terminale = nombre darc entrant comme extrmit terminale = nombre darc entrant dans i
Degr sortant dun sommet i : nombre darcs ayant i comme extrmit initiale = nombre darcs sortant de i
Gestion de projet : Ordonnancement
Gantt chart
Graphe : dfinitions
Ordonnancement
Graphe Potentiel Tches Graphe Potentiel Tches
Fonction rang dun graphe
Graphe Potentiel Etapes (PERT)
Graphe : dfinitions
Chemin de longueur q : squence de q arcs {u1,u2,,uq} telle que
u1=(i0,i1)
u2 = (i1,i2) u2 = (i1,i2)
uq=(iq-1,iq)
Chemin : tous les arcs orients dans le mme sens
Circuit : chemin dont les extrmits concident
Ordonnancement
Un problme d'ordonnancement consiste organiser dans le temps la ralisation de tches, compte tenu de contraintes temporelles (dlais, contraintes d'enchanement)
de contraintes portant sur la disponibilit des ressources de contraintes portant sur la disponibilit des ressources requises.
On se limitera aux seules contraintes de succession dans le temps : contraintes de prcdences
Ordonnancement
On suppose que le projet se dcompose en tches
Chaque tches i est caractrise par
Sa dure d(i)
Les contrainte de postriorit ou dantriorit avec les Les contrainte de postriorit ou dantriorit avec les autres tches.
Ordonnancement
La reprsentation par un graphe dun problme dordonnancement permet une bonne apprhension globale du problme
Ltude de ce graphe permet Ltude de ce graphe permet
Didentifier les tches prioritaires
De dtecter les retards et les dpassements ainsi que leur consquences
Gestion de projet : Ordonnancement
Gantt chart
Graphe : dfinitions
Ordonnancement
Graphe Potentiel Tches Graphe Potentiel Tches
Fonction rang dun graphe
Graphe Potentiel Etapes (PERT)
Graphe potentiels-tches
A chaque tche i on associe un sommet du graphe Si la tche i doit prcder la tche j alors on dfinit un arc (i,j) de longueur d(i) (dure de i)
On ajoute deux sommets fictifs On ajoute deux sommets fictifs qui correspond la tche de dbut des travaux (dure 0) qui est antrieure toutes les autres tches
qui correspond la tche de fin des travaux (dure 0) qui est postrieure toutes les autres tches
Pas de circuit dans le graphe : sinon problme i doit suivre j, k doit suivre i et j doit suivre k : blocage
Graphe potentiels-tches
Code de la tche Dure (semaine) Tches antrieures
A Maonnerie 7 -
B Charpente 3 A
C Toiture 1 B
D Installations sanitaires et lec.
8 Asanitaires et lec.
E Faades 2 D,C
F Fentres 1 D,C
G Jardin 1 D,C
H Plafonnage 3 F
J Peinture 2 H
K Emmnagement 1 E,G,J
Graphe potentiels-tches
Ordonnancement
But : trouver un ordonnancement qui minimalise la dure totale du travail, donc la fin de date des travaux
Pour quune tche puisse commencer , il est Pour quune tche puisse commencer , il est ncessaire que toutes les tches qui la prcde (relie la tche dbut) soient ralises
Ordonnancement
Date de dbut au plus tt de la tche i
t(i) = max (t(k) + d(k), avec k prdcesseur de i)
Plus long chemin de i
Dure minimale du projet (t()) = plus long chemin Dure minimale du projet (t()) = plus long chemin de
Ordonnancement
On fixe t() la dure du projet
Date de dbut au plus tard de la tche i
T(i) = min (T(k) - d(i), avec k successeur de i)
T(i) = t() - plus long chemin de i T(i) = t() - plus long chemin de i
Marge de la tche i
Diffrence entre dbut au plus tard et dbut au plus tt
T(i) t(i)
Tche critique : tche dont la marge est nulle
Ordonnancement
Tche critique :
tche dont la marge est nulle
tche sur le plus long chemin de
Gestion de projet : Ordonnancement
Gantt chart
Graphe : dfinitions
Ordonnancement
Graphe Potentiel Tches Graphe Potentiel Tches
Fonction rang dun graphe
Graphe Potentiel Etapes (PERT)
Fonction rang dun graphe
Ordre topologique (un sommet est toujours visit avant ses successeurs)
Associe chaque nud i un nombre positif rang(i) tel que
r(1)=0
R(i) = nombre darcs dans un chemin de cardinalit maximum entre 1 et i (taille (nombre de sommets) du plus grand chemin de prdcesseurs depuis 1)
Se calcule facilement : on limine les sommets sans prdcesseur chaque tape (on pluche le graphe)
Rang dun graphe
Rang dun graphe
TraitementNiveau(Niveau k,R) : Pour chaque lment i de R faire S vide
Rang(i) k
Pour chaque voisin j de i faire Dcrmenter degr(j)
Si degr(j) = 0 alors ajouter j dans S Si degr(j) = 0 alors ajouter j dans S
R S
Algorithme : On dtermine les racines. On les place dans R
Niveau 0
Rpter tant que R nest pas vide TraitementNiveau(Niveau,R)
Incrmenter Niveau
Graphe potentiels-tches
Recherche des dates au plus tt
Poser t() 0
Prendre les sommets k par rang croissant et faire
t(k) = max(t(i) + d(i) avec i prdcesseur de k)t(k) = max(t(i) + d(i) avec i prdcesseur de k)
Graphe potentiels-tches
Recherche des dates au plus tard
Poser T() 0
Prendre les sommets k par rang dcroissant et faire
T(k) = min(T(i) avec i successeur de k) d(k)T(k) = min(T(i) avec i successeur de k) d(k)
Graphe potentiels-tches
Graphe potentiels-tches
Gestion de projet : Ordonnancement
Gantt chart
Graphe : dfinitions
Ordonnancement
Graphe Potentiel Tches Graphe Potentiel Tches
Fonction rang dun graphe
Graphe Potentiel Etapes (PERT)
Graphe potentiels-tapes
PERT : Programme Evaluation and Research Task
Les tches sont les arcs
La longueur de chaque arc = dure de la tche
Le dbut et la fin dune tche sont des tapes du projet Le dbut et la fin dune tche sont des tapes du projet
Chaque tape est dfinie par un nombre de tches ayant dj t effectues
Etape = dernire colonne du tableau
On peut obtenir un multigraphe : plusieurs arcs entre les mmes sommets
Graphe potentiels-tapes
Code de la tche Dure (semaine) Tches antrieures
A Maonnerie 7 -
B Charpente 3 A
C Toiture 1 B
D Installations sanitaires et lec.
8 Asanitaires et lec.
E Faades 2 D,C
F Fentres 1 D,C
G Jardin 1 D,C
H Plafonnage 3 F
J Peinture 2 H
K Emmnagement 1 E,G,J
Etapes : A, B , D et C, F, H , E et G et J
Graphe potentiels-tapes
Modularit
Graphe Potentiels-tches permet une meilleure introduction de contraintes
k commence aprs la moiti de i
k commence c unit aprs i k commence c unit aprs i
k commence au minimum la date b
Avec PERT il faut introduire des nuds intermdiaires
Recommended