C3_GestionProjet

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


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.


Gantt chart

Graphe : dfinitions

Ordonnancement




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


Gantt chart

Graphe : dfinitions

Ordonnancement




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


Gantt chart

Graphe : dfinitions

Ordonnancement




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


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

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


Gantt chart

Graphe : dfinitions

Ordonnancement





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


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)


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)


Gantt chart

Graphe : dfinitions

Ordonnancement




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


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

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

Documents

C3_GestionProjet