Ordonnancement Des Tâches

Ordonnancement des Tâches
La méthode PERT
Par Dr GUESSOUM Souad
[email protected]
Ordonnancement des Tâches par Dr S. Guessoum 1

Contexte
Nous allons traiter dans ce chapitre :
➢ Un certain type particulier de problème
➢ Ordonnancement des Tâches

Contexte
Dans ce contexte :
➢ Nous avons un projet particulier qui doit se réaliser
➢ Nous connaissons les différentes Tâches qui composent ce

projet
➢ Nous savons que toutes les Tâches doivent être réalisées

pour terminer le projet
➢ Ces Tâches ont des Durées connues
➢ Et surtout ces Tâches ont des Contraintes d’Antériorité

Quel Objectif ??
Notre travail consiste à :
➢ Planifier la réalisation de toutes les Tâches pour réaliser le projet.
➢ Planifier c’est mettre un PLAN ou
➢ Mettre de l’ORDRE dans l’exécution des tâches
➢ En prenant en considération leurs Durées et surtout
➢ Leur Contraintes d’Antériorité

Méthodes d’Ordonnancements
Deux grandes méthodes sont utilisées dans les
problèmes d’ordonnancement :
➢ La méthode Américaine PERT (Program

Evaluation and Review Technique)
➢ La méthode Française MPM (Metra

Potentiels Methode

La méthode PERT
Elle consiste à représenter :
un Problème d’Ordonnancement de projet
Par
un Graphe appelé :
Réseau PERT
Diagramme Evènement-Tâche
Composants d’un Graphe PERT
De quoi est composé un Graphe PERT ??
Un graphe PERT est un triplet R=(X, U, d)
➢ X : un ensemble d’Etapes
➢ U : un ensemble de Tâches
➢ d : un ensemble de valeurs qui représentent
les Durées des Tâches

Composants d’un Graphe PERT – La Tâche
La Tâche ….
➢ est un élément de base dans un graphe PERT
➢ Elle signifie le déroulement d’une opération dans le temps
➢ Elle est représentée par une flèche.
➢ Elle doit avoir un nom (code) et une durée connue
➢ Le nom et la durée sont mentionnés sur la flèche
➢ Elle doit être délimitée obligatoirement par une étape

antérieure et une étape postérieure
Exemple : A;6
2 tâches peuvent être :

➢ Successives : elles s’exécutent l’une après l’autre
A;6 B; 3
1 2 3
➢ Simultanées : elles s’exécutent en parallèle et elles ont la

même étape antérieure
A;6 3
1
2
B; 3

➢ Convergentes : elles arrivent sur la même étape postérieure
1 A;6
3
B; 3
2

La tâche Fictive …
❑ Elle n’existe pas en réalité,

A’ ; 0
❑ Elle est représentée par une flèche en pointillés
❑ Elle a une durée nulle
❑ On l’utilise pour certaines raisons d’organisation du graphe PERT
❑ Elle Indique les contraintes d’enchaînement entre certaines

étapes

Composants d’un Graphe PERT – L’Etape
L’ Etape…
➢ On l’appelle aussi : nœuds… évènement… sommet
➢ Un autre élément de base aussi dans un graphe PERT
➢ Elle représente le début ou la fin d’une tâche
➢ Elle n’a pas de durée
➢ Chaque tâche possède une étape de début et une étape de fin

➢ Elle est représentée généralement par un cercle

1
➢ En haut du cercle on mentionne le n° de l’étape
➢ chaque tâche doit obligatoirement être précédée et suivie

par une étape
A;6 4
3
La tâche A commence après l’étape 3 et se termine à l’étape 4

➢ En bas à gauche du cercle la date (durée) au plutôt,
➢ et à droite la date (durée) au plus tard de la tâche

Date au plus tard Date au plus tard

du commencement De Fin de la tâche A
de la tâche A
A;6
Date au plus tôt Date au plus tôt

du commencement De Fin de la tâche A
de la tâche A

➢ Date au plus tôt de l’étape Début = 0
➢ Date au plus tôt de l’étape 1 = date au plus tôt de l’étape Début + durée de A
A;6 B;3
0 6
Date au plus tôt Date au plus tard

du commencement du commencement
de la tâche B de la tâche B

Exemple d’un Graphe PERT

Les Etapes de Construction d’un PERT
Les différentes étapes pour la construction d’un graphe PERT
1. Trouver les différents Niveaux du Graphe Pert à partir du tableau

d’Antériorité (qui est donné)
2. Trouver le tableau de Postériorité
3. Dessiner les Etapes du graphes (les sommets)
4. Dessiner les Tâches
5. Calculer les dates au plus tôt des Tâches
6. Calculer les dates au plus tard des Tâches
7. Calculer les marges

La méthode PERT - Application
Soit un projet composé de 6 tâches dont les durées de réalisation et les
contraintes d’Antériorités sont données dans le tableau suivant (Tableau
d’Antériorité) :
Tâches Durées Antériorités

A 6 -
B 3 -
C 1 B, A
D 2 A
E 4 D
F 1 C

La méthode PERT - Application
A 6 -
B 3 -
C 1 B, A
D 2 A
E 4 D
F 1 C
Le problème est de trouver un calendrier ou un plan de

déroulement des tâches avec les dates de démarrage
de chaque tâche de façon à minimiser la durée totale
de réalisation du projet

Exemple
Objectif : Tracer le réseau PERT
Tâches Antériorités NIVEAUX

A -
B -
C B, A
D A
E D
F C

Exemple
Tâches pouvant bien s’exécuter dès le début du projet
Tâches Tâches précédentes Les NIVEAUX

A - 1 (0)
B - 1 (0)
C B, A
D A
E D
F C

Exemple
Tâches qui n’ont plus de tâches antérieures

A - 1
B - 1
C B, A 2
D A 2
E D
F C
Barrer les Tâches de niveau 1 dans toute la colonne d’Antériorité

Exemple
Tâches qui n’ont plus de tâches antérieures

A - 1
B - 1
C B, A 2
D A 2
E D 3
F C 3
Niveau 1 = {A, B}
Niveau 2 = {C, D}
Niveau 3 = {E, F}
La méthode PERT
Le calendrier des « Suivants »
Tâche X Antériorité P(X) Postériorité S(X)

A - C, D
B -
C B, A
D A
E D
F C

La méthode PERT

A - C, D
B - C
C B, A
D A
E D
F C

La méthode PERT

A - C,D
B - C
C B, A F
D A
E D
F C

La méthode PERT

A - C, D
B - C
C B, A F
D A E
E D
F C

La méthode PERT

A - C, D
B - C
C B, A F
D A E
E D -
F C -

La méthode PERT

A - C, D
B - C
C B, A F
D A E
E D -
F C -

La méthode PERT
Maintenant on peut tracer le graphe PERT
D, 2 4
2
A, 6 E, 4
Début Fin
B,3 3 5 F, 1
C, 1
Un graphe PERT commence obligatoirement par une seule étape (0, 1, Début)
Et se termine par une seule étape également (Fin)
La méthode PERT
Calculons maintenant les dates au plus tôt des évènements
D, 2 4
2
A, 6 E, 4
Début Fin
B,3 3 5 F, 1
C, 1
Les dates au plus tôt traduisent :

la date de début au plus tôt soit la date de fin au plus tôt .Tout
dépends comment on se place par rapport à la tâche
La méthode PERT
Les dates au plus tôt traduisent :
➢ la date de début au plus tôt, soit
➢ la date de fin au plus tôt
Tout dépends comment on se place par rapport à la tâche

La méthode PERT – Dates au plus tôt
Calculons maintenant les dates au plus tôt des évènements
D, 2 4
2
A, 6 8 E, 4
6
Début Fin
0 12
B,3 3 5 F, 1
6 7
C, 1
Point de départ du projet
Date au plus tôt de l’étape 2 = date au plus tôt de l’étape Début +

durée de la tâche A = 0 + 6 = 6
La méthode PERT
Calculons maintenant les dates au plus tard des évènements
D, 2 4
2
A, 6 8 8 E, 4
6 6
Début Fin
0 0 12 12
B,3 3 5 F, 1
6 10 7 11
C, 1
Ceci est le réseau PERT complet de notre projet

La méthode PERT --- EXERCICE revoir
A 2 -
B 3 -
C 4 A
D 2 B
E 1 C, D

La méthode PERT --- EXERCICE

La méthode PERT --- EXERCICE

Le calcul des marges
➢ Une marge est un délai dont on dispose

dans chacune des tâches pour absorber un
éventuel retard
➢ Attention : toutes les tâches n’ont pas

obligatoirement une marge

➢ L’avantage des marges : absorber des

éventuels retards, des évènements
inattendus…
➢ L’absorption de ces retard ne se fera pas

au détriment de la durée totale du projet

Pour calculer la marge de la tâche A,

on prendra
les 2 étapes qui l’encadrent,

On va utiliser :
➢ la date au plus tard de l’étape qui suit la

tâche A,
➢ La durée de la tâche A
➢ La date au plus tôt de l’étape qui précède
la tâche A

Marge d’une tâche =
date au plus tard (étape suivante)

- durée de la tâche
- date au plus tôt (étape précédente)

• Marge de la tâche A = 6 – 6 – 0 = 0
• La tâche A n’a pas de marge, tout retard dans

sa réalisation entrainera automatiquement un
retard global du projet

• Marge (A)=0
• Marge de la tâche B = 10 – 3 – 0 = 7
• Marge (C)= 4
• Marge (D) = 0
• Marge (E) = 0
• Marge de (F) = 4

Le chemin critique
Seulement les tâches qui ont une marge non

nulle peuvent se permettre des retards sans
retarder le projet global
Les chemin critique : La succession des tâches

dont les marges sont nulles

Ordonnancement Des Tâches - Cours

Transféré par

Droits d'auteur :

Formats disponibles

Ordonnancement Des Tâches - Cours

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Ordonnancement Des Tâches - Cours

Transféré par

Droits d'auteur :

Formats disponibles

Ordonnancement des Tâches par Dr S. Guessoum 1

➢ Un certain type particulier de problème

➢ Ordonnancement des Tâches

Ordonnancement des Tâches par Dr S. Guessoum 2

➢ Nous avons un projet particulier qui doit se réaliser

➢ Nous connaissons les différentes Tâches qui composent ce

➢ Nous savons que toutes les Tâches doivent être réalisées

➢ Ces Tâches ont des Durées connues

➢ Et surtout ces Tâches ont des Contraintes d’Antériorité

Ordonnancement des Tâches par Dr S. Guessoum 3

Notre travail consiste à :

➢ Planifier la réalisation de toutes les Tâches pour réaliser le projet.

➢ Planifier c’est mettre un PLAN ou

➢ Mettre de l’ORDRE dans l’exécution des tâches

➢ En prenant en considération leurs Durées et surtout

➢ Leur Contraintes d’Antériorité

Ordonnancement des Tâches par Dr S. Guessoum 4

➢ La méthode Américaine PERT (Program

➢ La méthode Française MPM (Metra

Ordonnancement des Tâches par Dr S. Guessoum 5

un Problème d’Ordonnancement de projet

Un graphe PERT est un triplet R=(X, U, d)

Ordonnancement des Tâches par Dr S. Guessoum 7

➢ Elle signifie le déroulement d’une opération dans le temps

➢ Elle est représentée par une flèche.

➢ Elle doit avoir un nom (code) et une durée connue

➢ Le nom et la durée sont mentionnés sur la flèche

➢ Elle doit être délimitée obligatoirement par une étape

2 tâches peuvent être :

➢ Simultanées : elles s’exécutent en parallèle et elles ont la

Ordonnancement des Tâches par Dr S. Guessoum 9

➢ Convergentes : elles arrivent sur la même étape postérieure

Ordonnancement des Tâches par Dr S. Guessoum 10

❑ Elle n’existe pas en réalité,

❑ Elle a une durée nulle

❑ On l’utilise pour certaines raisons d’organisation du graphe PERT

❑ Elle Indique les contraintes d’enchaînement entre certaines

Ordonnancement des Tâches par Dr S. Guessoum 11

➢ On l’appelle aussi : nœuds… évènement… sommet

➢ Un autre élément de base aussi dans un graphe PERT

➢ Elle représente le début ou la fin d’une tâche

➢ Elle n’a pas de durée

➢ Chaque tâche possède une étape de début et une étape de fin

Ordonnancement des Tâches par Dr S. Guessoum 12

➢ Elle est représentée généralement par un cercle

➢ En haut du cercle on mentionne le n° de l’étape

➢ chaque tâche doit obligatoirement être précédée et suivie

La tâche A commence après l’étape 3 et se termine à l’étape 4

Ordonnancement des Tâches par Dr S. Guessoum 13

➢ En bas à gauche du cercle la date (durée) au plutôt,

➢ et à droite la date (durée) au plus tard de la tâche

Ordonnancement des Tâches par Dr S. Guessoum 14

Date au plus tard Date au plus tard

Date au plus tôt Date au plus tôt

Ordonnancement des Tâches par Dr S. Guessoum 15

Date au plus tôt Date au plus tard

Ordonnancement des Tâches par Dr S. Guessoum 16

Ordonnancement des Tâches par Dr S. Guessoum 17