LES DOMAINES
D’APPLICATION
Problèmes
d’ordonnancement
Ordonnancer ?
Définition
Le problème d’ordonnancement consiste à organiser dans le temps la réalisation
d’un ensemble de tâches, compte tenu de contraintes temporelles (délais,
contraintes d’enchaînements, ...) et de contraintes portant sur l’utilisation et la
disponibilité des ressources requises.
Nous avons :
⚫ Un ensemble de tâches
⚫ Un environnement de ressources pour effectuer les tâches
⚫ Des contraintes sur les tâches et les ressources
⚫ Un critère d’optimisation
==> Déterminer les dates d’execution des tâches?
3
Introduction
➢Les problèmes d'ordonnancement font partie de notre vie quotidienne !
➢Qui ne s'est jamais trouvé avec une liste de "choses à faire" et ne pas savoir par
quel bout les prendre ?
➢Ces problèmes concernent bien évidemment aussi de nombreuses activités des
entreprises.
➢Le problème central de l'ordonnancement consiste à déterminer le calendrier
d'exécution des tâches liées entre elles par des contraintes "temporelles", entre
autres de succession, de manière à minimiser la durée totale.
4
Concepts de base
La réalisation d’un projet nécessite souvent une succession de tâches aux quelles
s’attachent certaines contraintes :
De temps : délais à respecter pour l’exécution des tâches ;
D’antériorité : certaines tâches doivent s’exécuter avant d’autres ;
De production : temps d’occupation du matériel ou des hommes qui l’utilisent..
5
Domaines concernés
Gestion de projets Ateliers de production
… ...
Projets Production
Ordonnancement
Administration Informatique
Gestion des ressources humaines Exécution des programmes
Emplois du temps Optimisation de code
… ...
6
Gestion de projets
Les techniques d’ordonnancement dans le cadre de la gestion d’un
projet ont pour objectif de répondre au mieux aux besoins exprimés
par un client, au meilleur coût et dans les meilleurs délais, en tenant
compte des différentes contraintes.
7
Les étapes de déroulement de l’ordonnancement
La planification : qui vise à déterminer les différentes opérations à réaliser, les dates correspondantes, et
les moyens matériels et humains à y affecter.
L’exécution : qui consiste à la mise en œuvre des différentes opérations définies dans la phase de
planification.
Le contrôle : qui consiste à effectuer une comparaison entre planification et exécution, soit au niveau des
coûts, soit au niveau des dates de réalisation.
Il existe plusieurs méthodes d’ordonnancement : le diagramme de Gantt, la méthode CPM (Critical Path
Method), le PERT ((Program Evaluation and Review Technic) .
8
Méthode de PERT(Program Evaluation
and Review Technic)
Traduit par: Méthode de planification à base de recherche opérationnelle, ou technique
d’établissement et de remise à jour des programmes.
❖Son but est d'organiser les tâches sous la forme d'un réseau afin de faciliter la gestion du projet. Cette
représentation graphique permet d'identifier les connexions entre les différentes tâches, les temps
d'exécution, les interdépendances.
Elle est constituée de 3 étapes
1) Élaboration d'un graphe qui schématise l'organisation des différentes tâches les une par
rapport aux autres,
2) Recherche du chemin critique,
3) Détermination des temps ; de la durée de réalisation du projet et calcule des marges.
9
PERT
1ère étape : Construction du réseau PERT
Définition d'une tâche:
Une tâche constitue l’unité ou l’élément du projet, on peut aussi définir une tâche comme l’activité du
projet.
À chaque tâche on associe: { sa durée d’exécution + une contrainte d'antériorité}
Dans un graphe PERT :
➢Chaque tâche est représenté par un arc, auquel on associe le nom de la tache et un chiffre entre
parenthèses qui représente la durée de cette tâche.
➢Entre les arcs figurent des cercles appelées « sommets » ou « événement » qui marquent l’aboutissement
d’une ou plusieurs tâches. Ces cercles sont numérotées afin de suivre l’ordre de succession des divers
évènements.
10
Exemple illustratif
11
PERT
Antériorité :
(A antérieure à B) <=> (B ne peut commencer avant que A soit achevée)
Tout réseau PERT doit obéir aux conventions suivantes :
1) Deux tâches successives sont représentés par 2 arcs placés l'un à la suite de l'autre
j succède à i
12
PERT
2) Le graphe doit posséder une entrée et une sortie,
3) Chaque tâche correspond un arc et 1 seul,
4) Le graphe ne doit contenir ni boucle ni circuit,
5) Le graphe doit comporté le mois de croisement d'arcs possible,
6) Il est préférable d'orienter les arcs de la gauche vers la droite
13
PERT
Tâche fictive :
c'est une tâche de durée nulle ne mettant en jeux aucun moyen matériel et financier, elle est représenté par
un arc en pointillée (--->) et elle sert à solutionner certaine situations complexes :
Exemple:
k succède à i et j
Tâche fictive
l succède à j
i 1
i(di)
2
k(dk)
5
k
1 0
j(dj)
j l 3 4 l(dl)
6
14
PERT
Tâche fictive :
c'est une tâche de durée nulle ne mettant en jeux aucun moyen matériel et financier, elle est représenté par
un arc en pointillée (--->) et elle sert à solutionner certaine situations complexes :
Exemple:
Nœud fictif
i et j succède à k 3
tâche fictive
l succède à i et j i(di) 0
k(dk) j(dj) l(dl)
k i 1 2 4 5
l
1 2 3 4
j
15
Exemple illustratif
16
PERT
2ème étape : Recherche du chemin critique
Définition : un chemin critique est formé d'une succession de tâche critique au niveau dès qu'elles
tout retards sera interdit,
• le chemin critique représente donc le temps minimum nécessaire à la réalisation du projet.
• Les tâches non critiques laissent une certaine marge de manœuvre dans les déroulement des
travaux.
17
PERT
Date au plus tôt
C'est la date avant la quelle une tâche ne peut démarer ou un évenement ne peut se réaliser,
On initialise la date au plus tôt du premier sommet à 0 :
T 1 = 0 Désigne la date au plus tôt du sommet 1.
T i = Max (T j + Durée T i,j) pour tous les prédécesseurs j de i
18
PERT
Date au plus tard
C'est la date limité de réalisation d'un événement, si l’événement se réalise après cette date le projet en
entier sera retarder,
On initialise la date au plus tard du dernier sommet avec sa date au plus tôt.
T* n = T n ( T* n : désigne la date au plus tard du sommet n)
( T n : désigne la date au plus tôt du sommet n).
T* i = Min ( T* j – Durée T i,j) pour tous les successeurs j de i.
19
PERT
Intervalle de flottement
⚫ c'est la différence entre la date au plus tard et la date au plus tôt d'un même événement, grâce
à cette intervalle il est possible pour le responsable de projet d'augmenter la duré d'une tâche
sans compromettre (toucher) la fin du projet.
⚫ Du point de vue tâche, on dispose des marges qui permettent de détecter certain retard et
d'apporter les corrections nécessaire.
20
PERT
La marge libre
La marge libre sur une tâche est le retard que l’on peut prendre dans la réalisation d’une tâche sans retarder la date de
début au plus tôt de tout autre tâche qui suit.
Si on appelle :
Tj la date au plus tôt de la tâche qui suit la tâche considérée.
Ti La date de début au plus tôt de la tâche i.
Di La durée de la tâche i.
Marge Libre de i = Min (T j – T i – D i,j ) pour tous les successeurs j de i.
Voir l'exemple précédent:
21
PERT
La marge totale
La marge totale sur une tâche est le retard que l’on peut prendre dans la réalisation de cette tâche
sans retarder l’ensemble du projet.
Elle est obtenue , en faisant pour chaque tâche, la différence entre la date au plus tard de début
d’une tâche et la date au plus tôt.
22
PERT
La marge totale
23
Exemple illustratif
24
Graphe correspondant
25
Dates de début au plus tôt
26
Dates de début au plus tard
27
Chemin critique
28
Exercice
29
Solution
30
