Chapitre : Les problèmes d’ordonnancement
I) Généralités
1) Introduction
L’ordonnancement consiste à prévoir un calendrier de réalisation qui tient
compte de toutes les contraintes et de l’un des objectifs suivants :
Minimisation de la durée totale de réalisation
Minimisation du coût total
Utilisation optimale des ressources
Maximisation de la sécurité etc.
L’ordonnancement est particulièrement utilisé pour l’étude de la réalisation
des projets de grandes importances économique (projet d’investissement,
construction d’ouvrages, processus de production industrielle…). Mais il exige une
certaine succession et/ou un agencement séquentiel des tâches entrant dans
l’exécution du projet. En Recherche Opérationnelle ce processus scientifique est
matérialisé par la théorie des graphes.
2) Notion de projet :
a) Caractéristique d’un projet :
Les projets peuvent être variés : la construction d’une usine ou d’une école,
étude et lancement d’une nouvelle activité, entretien d’un forage, élaboration d’un
emploi du temps… mais ils ont 3 caractéristiques communes :
- L’unicité
- La limitation dans le temps
- La convergence des actions vers un grand but.
b) Phase d’analyse préalable d’un projet :
Les phases sont les suivants :
- Définir de manière très précise le projet ;
- Définir un responsable de projet, auquel on rendra compte et qui prendra les
décisions importantes ;
- Analyser le projet par grand groupe de tâches, puis détailler certaines tâches
si besoin est ;
- Évaluer la durée, le coût, les moyens nécessaires à la réalisation de chaque
tâche ;
- Repérer les contraintes pesant sur ces tâches. On peut distinguer 3 grands
types des contraintes :
Les contraintes potentielles, qui se décomposent en :
Contraintes de succession ou contraintes d’antériorité : deux cas sont possibles.
o cas de deux tâches dépendantes (A et B) dont l’une (B) ne peut débuter que
si la tâche précédente (A) est terminée.
o cas de deux tâches dépendantes (A et B) dont l’une (B) ne peut débuter que
si la tâche précédente (A) non achevée, a débuté depuis un certain temps. il y
a succession avec recouvrement.
Contraintes de date. Dans ce cas une tâche (A) quelconque ne peut débuter avant
une date précise. On parle aussi de contraintes de localisation temporelle.
Les contraintes disjonctives : Deux tâches A et B utilisent une même
ressource. La quantité de la ressource étant de 1, les tâches A et B ne
RO, Chapitre : Ordonnancement, Par M. Karim Page 1 sur 11
peuvent être exécutée simultanément. On parle alors de contrainte
disjonctive.
Les contraintes cumulatives : Si l’on veut impérativement exécuter tout
ou partie de A et B en même temps, il y aurait besoin de cumuler
(augmenter) la quantité de la ressource. Cet engagement d’exécution
simultanée crée une contrainte cumulative qui est de pouvoir disposer
d’une quantité de ressource supplémentaire. La quantité finale de la
ressource (cumul) ne pourra excéder les capacités disponibles au moment
considéré.
3) Détermination du niveau et des ascendants directes
Pour construire le diagramme il faut d’abord déterminer les ascendants directs de
chaque tâche et le niveau d’ordonnancement.
Exemple : Soit un projet ayant les caractéristiques suivantes :
Tâche à réaliser Tâches antérieures Durée (en semaines)
A I, G, P 3
B A, C, D, G, H, I, P 5
C G 2
D 4
E D, I, P 8
F A, G, I, P 1
G 7
H G, I, P 5
I 5
J A, G, I, P 6
K D, E, G, I, M, N, O 3
L A, D, E, F, G, K, I, M, N, O 4
M D, E, G, I, P 7
N G, I, P 1
O D, E, G, I, P 2
P G 6
Déterminer les niveaux et les ascendants directs de chaque tâche.
Méthode du tableau :
Tâches Tâches Ascendant
à antérieures s directs
réaliser
A G, I, P P ___ I, P
B A, C, D, G, H, I, P A, C, H, P A, H ___ A, C, H
C G ____ G
D ___
E G, I, P P ___ I, P
F A, G, I, P A, P A ___ A
G ___
H G, I, P P ___ I, P
I ___
J A, G, I, P A, P A ___ A
K D, E, G, I, M, N, O E,M, N, O E,M, N, O M, O ___ M, N, O
RO, Chapitre : Ordonnancement, Par M. Karim Page 2 sur 11
L A, D, E, F, G, K, A, E, F, K, A, E, F, K, F, K, K ___ F, K
I, M, N, O M, N, O M, N, O M, O
M D, E, G, I, P E, P E ___ D, E
N G, I, P P ___ I, P
O E, G, I, P E, P E ___ E
P G ____ G
Niveau N0 = {D, G, I} N1={C, P} N2={A,E,N N3={B,F N4= N5=
,H} ,J,O,M} {K} {L}
Au niveau 0 : Nous avons les tâches qui n’ont pas des précédents : {D, G, I}
Au niveau 1 : On supprime les tâches de niveau 0 partout où elles figurent dans la
colonne tâches antérieures, les tâches n’ayant plus de précédents font parties du
niveau 1. On continue cette procédure jusqu’au moment où toutes les tâches seront
classés par niveau.
Les ascendants directs d’une tâche sont les tâches qui précédent immédiatement
celle-ci.
4) Le réseau d’ordonnancement :
Il est la représentation graphique de l’ensemble des tâches concourant à la
réalisation du programme envisagé, articulées entre elles par l’intermédiaire des
étapes. Deux types de représentation graphique sont généralement utilisés en
Recherche Opérationnelle selon les méthodes : PERT (Program Evaluation and
Review Technique) et MPM (méthode des potentiels mettra), suivies par le
diagramme de Gantt.
II) Méthode PERT :
PERT (Program Evaluation and Review Technique – Technique d’élaboration et
de mise à jour de programme) a été créée en 1958, aux USA pour la planification du
programme spatial POLARIS. Le délai initial de ce programme qui a fait intervenir
9000 sous-traitants, était de 6 ans. L’application de la technique de PERT a permis
de réduire ce délai à 2,5 ans.
PERT est " une méthode consistant à mettre en ordre sous forme de réseau
plusieurs tâches qui, grâce à leur dépendance et à leur chronologie, concourent
toutes à l'obtention d'un produit fini ". La méthode PERT est le plus souvent
synonyme de gestion de projets importants et à long terme. C'est pourquoi, plusieurs
actions sont nécessaires pour réussir sa mise en œuvre.
Le graphe PERT est composé des tâches et des étapes. Les tâches sont
représentées par des arcs. Chaque tâche comporte une étape « début » et une
étape « fin ». Les étapes sont représentées par des sommets.
1) Construction du réseau:
Pour construire le graphe on placera les tâches de gauche vers la droite en
fonction de leur niveau en commençant par le niveau 0 et en les reliant à leurs
ascendants directs. A un même niveau on disposera les tâches de façon à limiter le
nombre d’intersections entre les arcs.
RO, Chapitre : Ordonnancement, Par M. Karim Page 3 sur 11
2) Mise en évidence du chemin critique :
Après avoir tracé le graphe il faut déterminer les dates (temps) au plutôt et au plus
tard de chaque sommet encadrant une ou des tâches.
a) Les dates de début au plutôt :
La date de début au plutôt d’un sommet est la date à la quelle toutes les tâches
précédentes sont terminées. On prend la date maximale en allant du début à la fin
du programme. On inscrit les dates au plutôt dans chaque sommet à gauche.
Pour un sommet Ei dont un ascendant direct est Eh la date de début au plutôt que
nous noterons ti est définie par :
ti = max [th + thi ] pour toute les arcs qui précédent le sommet Ei où :
th est la date de début au plutôt d’un sommet qui précède Ei avec t1 = 0
thi est la durée de l’opération définie par l’arc encadre par les sommets Eh et Ei
Après avoir calculé la date de début au plutôt du projet (32 semaines dans notre
exemple), on part de cette durée totale pour déterminer les dates de fin au plus tard
de chaque sommet.
b) Les dates de fin au plus tard :
C’est la date limite de réalisation de l’opération en tenant compte de toutes les
contraintes. En pratique on inscrit les dates au plus tard dans chaque sommet à
RO, Chapitre : Ordonnancement, Par M. Karim Page 4 sur 11
droite. On prend la date minimale en remontant le graphe de la fin au début du
projet.
Pour un sommet Ei qui est un ascendant direct de Ej la date de fin au plus tard
que nous noterons ti* est définie par :
ti* = min [tj* - tij ] pour toute les arcs qui quittent le sommet Ei où :
tj* est la date de fin au plus tard d’un sommet que précède Ei avec t1 = 0
tij est la durée de l’opération définie par l’arc encadre par les sommets Ei et Ej.
c) Détermination du chemin critique :
Une activité est dite critique quand un retard dans son commencement entraîne
un retard dans l’accomplissement entier du projet. Un chemin critique est défini par
une chaîne d’activités critiques qui lient le début et la fin du projet.
Pour une activité critique on a ti = ti*, tj = tj*, tj – ti = tj* - ti* =tij.
3) Calcule des marges :
On calcule d’abord les dates de début au plus tard Dij et de fin au plutôt Dij*avec :
Dij* = ti + tij et Dij = tj* - tij
Ensuite on calcule la marge totale (pour les tâches de marge totale non nulle on
peut les retarder de cette marge et le retard aura un incident sur tous les
descendants sans que soit modifiée pour autant, la date finale). Mt = Dij – ti.
La marge libre Ml est l’intervalle de temps à l’intervalle de temps à l’intérieure
duquel on peut commencer une tâche tout en respectant les dates de début au
plutôt de ses descendants. Ml = tj – Dij*
NB : Pour les tâches critiques les marges sont nulles.
Les calcules sont résumés dans le tableau suivant :
Tâche Durée Début Fin au Début Fin Tj Marge Marge Remarque
(i, j) tij au plutôt au au 6 total libre
1 plutôt Dij* plus plus Mt Ml
ti 3=1+2 tard Dij tard 7=4- 2 8=6- 3
2 4= 5 - tj*
1 5
A 3 13 16 27 30 1 14 0 Non critiq
6
B 5 18 10 30 35 3 12 12 Non critiq
5
C 2 7 9 28 30 1 21 9 Non critiq
8
D 4 0 4 17 21 2 17 17 Non critiq
1
E 8 13 21 13 21 2 0 0 Critique
1
F 1 16 17 30 31 3 14 14 Non critiq
1
G 7 0 7 0 7 7 0 0 Critique
H 5 13 18 25 30 1 12 0 Non critiq
8
I 5 0 5 8 13 1 8 8 Non critiq
3
J 6 16 22 29 35 3 13 13 Non critiq
5
RO, Chapitre : Ordonnancement, Par M. Karim Page 5 sur 11
K 3 28 31 28 31 3 0 0 Critique
1
L 4 31 35 31 35 3 0 0 Critique
5
M 7 21 28 21 28 2 0 0 Critique
8
N 1 13 14 27 28 2 14 14 Non critiq
8
O 2 21 23 26 28 2 4 4 Non critiq
8
P 6 7 13 13 13 1 0 0 Critique
3
RO, Chapitre : Ordonnancement, Par M. Karim Page 6 sur 11
III) Méthode des potentiels metra
La Méthode des Potentiels et antécédents Métra (MPM) est une méthode
d’ordonnancement basée sur la théorie des graphes, et visant à optimiser la
planification des tâches d'un projet. Semblable au PERT, les principales différences
entre les deux méthodes reposent essentiellement dans la construction du graphe.
Elle a été développée par le chercheur français Bernard Roy, en 1958.
Le graph MPM se présente tel qu’il suit :
- Chaque tâche est représentée par un sommet,
- Les arcs entre les sommets traduisent uniquement les relations d'antériorité
des tâches ;
- la représentation des relations d'antériorité d'une tâche partageant avec une
autre certains de ses antécédents ne nécessite pas, comme dans le PERT, le
recours à des "tâches fictives" ;
- chaque tâche (ou sommet) est renseignée sur la date à laquelle elle peut
commencer au plus tôt (date de début au plus tôt) et terminer au plus tard
(date de fin au plus tard) pour respecter le délai optimal de réalisation du
projet ;
- A chaque arc est associée une valeur numérique qui représente soit une
durée d’opération, soit un délai ;
- La longueur des arcs n’est pas proportionnelle à cette durée ;
- le graphe commence et termine sur 2 sommets, respectivement appelés «
Début » et « Fin » symbolisant les début et fin des opérations. Ces deux
sommets ne correspondent pas une tâche ;
- Le graphe se lit de gauche à droite (du sommet "DÉBUT" à celui de "FIN").
Tâche Opérations préalables Durée (en seconde)
s
A 3
B A 30
C A, B 600
D 3
E 300
F D, E 30
G D, E, F 120
H D, E, F, G 10
I A, B, C 10
J A, B, C, D, E, F, G, I, H 10
1) Construction du graphe
On procède de la même façon qu’avec la méthode PERT en déterminant les
niveaux.
Tâche Opérations Ascendants
s préalables directs
A
B A __ A
C A, B B __ B
D
E
RO, Chapitre : Ordonnancement, Par M. Karim Page 7 sur 11
F D, E __ D, E
G D, E, F F __ _ F
H D, E, F, G F, G G __ G
I A, B, C B, C C __ C
J A, B, C, D, E, B, C, F, G, C, G, I, H I, H I, H
F, G, I, H I, H
Niveau N0 = {A,D,E} N1 = {B, F} N2={C, G} N3={I, H } N4={J}
2) Détermination du chemin critique
Pour chaque tache, nous allons rajouter 2 nombres : à gauche "la date de début", à
droite "la date de fin". Les dates au plus tôt sont au dessus et les dates au plus tard
en dessous de chaque tâche. La procédure des calculs est identique à celle de la
méthode PERT.
Une activité est critique si ses dates "au plus tôt" et ses dates "au plus tard"
coïncident. Ici se sont les tâches : A, C, D, F, G
RO, Chapitre : Ordonnancement, Par M. Karim Page 8 sur 11
IV) Diagramme de Gantt
Le diagramme de Gantt, couramment utilisé en gestion de projet, est l'un des outils
les plus efficaces pour représenter visuellement l'état d'avancement des différentes
activités (tâches) qui constituent un projet.
Le premier diagramme de ce type (appelé Harmonogram Adamieckiego) fut réalisé
par l'ingénieur polonais Karol Adamiecki en 1896. Il l'a décrit en 1931, mais la langue
de publication n'a pas permis la reconnaissance internationale de son idée. Pour
cette raison, le concept a été nommé d'après Henry L. Gantt, ingénieur américain
collaborateur de Frederick Winslow Taylor, qui a publié la description du diagramme
en 1910.
Le diagramme de Gantt est un outil utilisé (souvent en complément d'un réseau
PERT) en ordonnancement et en gestion de projet et permettant de visualiser dans
le temps les diverses tâches composant un projet. PERT permet d'analyser toutes
les relations qui existent entre les activités, de dégager les séquences d'activités,
d'identifier le chemin critique et les dates de début et de fin (au plus tôt et au plus
tard) de chaque activité. Le diagramme de Gantt permet de choisir les dates qui
seront effectivement retenues pour réaliser les activités et, éventuellement, de
montrer les relations entre les activités et donc les incidences en termes de retard.
Une différence essentielle entre les deux outils est aussi le lien qui existe entre la
durée des tâches et l'espace utilisé pour les représenter dans les diagrammes. Dans
un Gantt, l'espace est directement proportionnel à la durée alors que dans un PERT,
la durée n'est pas gérée graphiquement, toutes les activités ayant la même taille
dans le diagramme, quelle que soit leur durée. Ces différences font que le
diagramme PERT est plus complexe à utiliser, car il est moins proche de la réalité.
Etant donné la relative facilitée de lecture des diagrammes GANTT, cet outil est
utilisé par la quasi-totalité des chefs de projet dans tous les secteurs. Le diagramme
GANTT représente un outil pour le chef de projet, permettant de représenter
graphiquement l'avancement du projet, mais c'est également un bon moyen de
communication entre les différents acteurs d'un projet. Ce type de modélisation est
particulièrement facile à mettre en œuvre avec un simple tableur mais il existe des
outils spécialisés dont le plus connu est Microsoft Project.
Dans un diagramme de Gantt, la colonne de gauche du diagramme énumère toutes
les tâches à effectuer, tandis que la ligne d'en-tête représente les unités de temps
les plus adaptées au projet (jours, semaines, mois etc.). Chaque tâche est
matérialisée par une barre horizontale, dont la position et la longueur représentent la
date de début, la durée et la date de fin. Ce diagramme permet donc de visualiser
d'un seul coup d'œil :
- Les différentes tâches à envisager
- La date de début et la date de fin de chaque tâche
- La durée escomptée de chaque tâche
- Le chevauchement éventuel des tâches, et la durée de ce chevauchement
- La date de début et la date de fin du projet dans son ensemble
Il est possible de faire apparaître sur le planning des événements importants autre
que les tâches elles-mêmes, constituant des points d'accroche pour le projet : il
RO, Chapitre : Ordonnancement, Par M. Karim Page 9 sur 11
s'agit des tâches jalons (en anglais milestones). Les jalons permettent de scinder le
projet en phases clairement identifiées, évitant ainsi d'avoir une fin de projet à trop
longue échéance. Un jalon peut être la production d'un document, la tenue d'une
réunion ou bien encore un livrable du projet. Les jalons sont des tâches de durée
nulle, représentées sur le diagramme par un symbole particulier, la plupart du temps
un triangle à l'envers ou un losange.
Exemple : Représenter le diagramme de Gantt de l’exemple précédant
V) Considération du coût dans la programmation d’un projet
L’aspect coût est inclus dans la programmation d’un projet en définissant la
relation coût-durée de chaque activité dans le projet. La figure suivante montre une
relation le plus suivant utilisé dans les projets.
Coût
Cr Point réduit
Cn Point normal
Dr Dn Durée
Le point (Dn ; Cn) représente la durée Dn et son coût Cn, si l’activité est exécutée
dans les conditions normales. La durée Dn peut être réduite en augmentant les
ressources allouées. Il existe une limite, appelé durée réduite, au-delà de la quelle
aucune autre réduction dans la durée ne peut être possible. À ce point, toute
augmentation des ressources augmentera le coût sans réduire la durée.
La détermination du chemin critique est effectuée en considérant le coût normal.
L’étape suivante est la réduction de la durée du projet. Comme une telle réduction
ne sera possible que si la durée des activités critiques est réduite, une attention
particulière sera accordée à ces activités. Pour avoir une réduction dans la durée
avec le moindre coût possible, on doit compresser autant que possible l’activité
RO, Chapitre : Ordonnancement, Par M. Karim Page 10 sur 11
critique avec la plus petite déviation coût- durée. Le montant par le quel une activité
peut être compressé est limité par le temps de réduction, mais aussi d’autres limites
doivent aussi être considérées avant la détermination du montant de la compression.
Exemple : Soit le réseau PERT suivant :
2 10
8
2 5
1
4 5
3 5 4
Le point normal et réduit de chaque activité sont donnés dans le tableau suivant
Activité (i ;j) Normal Réduit
durée Coû durée Coût
t
(1 ; 2) 8 100 6 200
(1 ; 3) 4 150 2 350
(2 ; 4) 2 50 1 90
(2 ; 5) 10 100 5 400
(3 ; 4) 5 100 1 200
(4 ; 5) 3 80 1 100
La première étape est de considérer que toutes les activités se déroulent
normalement.
(8 ; 8)
2 10
(0 ; 0) 8
2 5 (18 ; 18)
1 ML = 0
4 (4 ; 10) 5
ML = 5
3 5 4 (10 ; 15)
ML = 0
ML = 1
Les activités (1 ; 2) et (2 ; 5) constituent le chemin critique. La durée du projet est
de 18 et le coût associé est de 520.
On calcule la déviation d = (Cr – Cn)/(Dn – Dr)
Activité (1 ; 2) (1 ; 3) (2 ; 4) (2 ; 5) (3 ; 4) (4 ; 5)
déviation 50 100 40 60 25 10
La deuxième étape consiste à réduire la durée du projet en compressant (le plus
possible) les activités critiques. L’activité (1 ; 2) est choisi pour être compressée car
elle a la plus petite déviation. La durée de la compression dépend de la limite de
réduction de l’activité mais aussi de la marge libre des activités non critiques.
Limite de compression = min {2 ; 1} = 1 ; car l’activité non critique qui a la plus
petite marge est l’activité (3 ; 4).
RO, Chapitre : Ordonnancement, Par M. Karim Page 11 sur 11