Chapitre 1

L'ordonnancement de projet

Présentation
Un problème d'ordonnancement de projet (PSP : Projet Scheduling Problem) consiste à
gérer et contrôler la mise en ÷uvre d'un projet comportant de nombreuses tâches dont
il faut planier l'exécution en respectant diverses contraintes. Ces projets concernent gé-
néralement la réalisation d'un produit unitaire complexe : construction d'un bâtiment,
d'une usine ; élaboration d'un ouvrage d'art ; mise en place d'un chantier industriel ; fa-
brication d'une machine spécique sur commande ; organisation d'un grand événement ;
etc.
D'un point de vue historique, ce domaine est un des premiers de la Recherche Opéra-
tionnelle. A la n des années 50, la nécessité de développer des méthodes pour résoudre
des problèmes PSP est apparu simultanément aux États Unis et en Europe :
 en 1957, des sociétés américaines mettent au point la méthode du chemin critique
CPM (Critical Path Method) ou encore méthode PERT (Programming Evaluation
and Review Technics)  nom initialement utilisé pour la situation de durée aléatoire
des tâches , notamment à l'occasion de lancement de fusées Polaris et des premiers
satellites,
 en 1958, la société française SemaMetra introduit la méthode MPM (Méthode des
Potentiels Metra) en vue de résoudre les problèmes posés par la construction du pa-
quebot France et celle de centrales électriques de la société EDF.
Grâce à leur simplicité et leur ecacité, ces méthodes ont été ensuite appliquées dans
de nombreux domaines industriels (chimie, pétrole, construction, etc.).
L'objectif des méthodes CPM  PERT et MPM est de minimiser la durée d'exécution
d'un projet tout en satisfaisant des contraintes temporelles entre les tâches. Ces mé-
thodes fournissent également les éléments nécessaires pour assurer le suivi et le contrôle
de l'exécution du projet ou pour réagir à des événements impondérables durant celle-ci.
Par la suite, diverses extensions ont été proposées :
 L'analyse des ressources
Souvent la réalisation des tâches nécessite l'utilisation de ressources et il convient
de respecter des contraintes de limitation des ressources donnant lieu aux problèmes
RCPSP (Resource Constrained Project Scheduling Problem).
6 CHAPITRE 1. L'ORDONNANCEMENT DE PROJET
 L'analyse des coûts
La durée d'exécution des tâches peut être diminuée moyennant un coût supplémentaire
et l'on peut donc étudier l'interaction de la durée d'exécution du projet avec le coût
de celui-ci.

Ce chapitre comprendra trois paragraphes.

Le Ÿ 1.1 traitera du problème PSP de base relatif à la minimisation de la durée d'exécution
du projet sous des contraintes temporelles entre les tâches. Nous y décrirons, dans le cas
de durée déterministe, la méthode CPM (Ÿ 1.1.1) qui utilise une représentation graphe-
événements et la méthode MPM (Ÿ 1.1.2) qui utilise une représentation graphe-tâches.
Ces deux méthodes seront comparées au Ÿ 1.1.3, mettant en évidence leurs avantages et
inconvénients. Le cas de durée aléatoire des tâches sera analysé au Ÿ1.1.4 avec la méthode
PERT.
L'analyse des ressources sera l'objet du Ÿ 1.2. La modélisation générale sous forme de pro-
blème linéaire en variables mixtes (MILP) sera formulée au Ÿ 1.2.1. Ensuite, seront décrits
des algorithmes heuristiques, tant pour la situation de ressources renouvelables (rene-
wal) du type machines, main d'÷uvre, etc., c'est-à-dire des moyens qui restent dispo-
nibles après chaque utilisation (Ÿ 1.2.2), que pour la situation de ressources consommables
ou non-renouvelables (non-renewal) du type matières premières, moyens nanciers, etc.,
c'est-à-dire des moyens diminuant au fur et à mesure de leur utilisation (Ÿ 1.2.3).
Le Ÿ 1.3 s'intéresse à l'analyse des coûts. Nous traiterons principalement
 de la dénition et de la formulation du problème général (Ÿ 1.3.1)
 de la diminution du coût total d'un ordonnancement sans variation de sa durée
(Ÿ 1.3.2)
 de la diminution de la durée d'un ordonnancement au moindre coût (Ÿ 1.3.3)
Quelques exercices et applications clôtureront cette partie au Ÿ 1.4.
De nombreux ouvrages spécialisés traitent plus en détail de l'ordonnancement de projet :
en particulier des ouvrages précurseurs tels [8], [12] et des ouvrages plus récents [13], [14],
[2], [10] ou un ouvrage orienté vers les exercices [1].

1.1 Minimisation du délai d'exécution d'un projet

Dans ce paragraphe, nous considérons un projet qui n'est soumis qu'à des contraintes
temporelles (temporal project scheduling).
L'objectif est d'ordonnancer  c'est-à-dire de planier dans le temps  les diérentes
tâches du projet de façon à réaliser le projet en le moins de temps possible, tout en
respectant bien sûr les contraintes temporelles entre les tâches.
L'application concrète d'une méthode d'ordonnancement nécessite un travail préliminaire
d'information et de recueil des données du cas étudié. Il convient
 de décomposer le projet en ses diérentes tâches ;
 de dénir les contraintes temporelles liant ces tâches ;
 d'estimer le plus précisément ces contraintes, ainsi que les durées des tâches.
C'est donc un travail minutieux dont il ne faut pas sous estimer la diculté . . . et que
nous supposerons accompli pour les diérents exemples envisagés.
1.1. MINIMISATION DU DÉLAI D'EXÉCUTION D'UN PROJET 7

1.1.1 La méthode CP M (ou P ERT )

Soit un projet dont les tâches sont soumises uniquement à des contraintes de postériorité
stricte (precedence constraints) du type la tâche j ne peut débuter que si la tâche i est
terminée.
Si xi représente l'instant de début d'une tâche i et di sa durée, une contrainte de posté-
riorité stricte s'écrit
xj ≥ xi + di
Dans la méthode du chemin critique ( CM P ) les données sont représentées sous forme
d'un graphe-événements (dénommé en anglais AOA (Activity-on-arc) network) ;
 les sommets représentent des étapes (ou événements ou instants), notés m, n, . . ..
On introduit un sommet initial (DEB ou O) et un sommet nal (F IN ou N ).
 les arcs représentent les tâches et les valeurs portées sur les arcs indiquent les durées
des tâches.
Une tâche i est donc représentée par la gure 1.1
et une contrainte de postériorité stricte par la gure 1.2

i di

Figure 1.1  Tâche dans un graphe-événements

i j

Figure 1.2  Contrainte de postériorité stricte dans un graphe-événements

Avec les notations classiques de la théorie des graphes (voir partie VI du tome 1)

Γ−1 (m) Γ(m)

Figure 1.3  Ensemble des prédécesseurs et successeurs directs d'un sommet

 Γ−1 (m) désigne l'ensemble des sommets précédents directs du sommet m

 Γ(m) désigne l'ensemble des sommets suivants directs du sommet m
Nous imposerons que chaque couple de sommets soit relié par au plus un arc ,
de sorte que l'on peut parler de la tâche (m, n), qui relie le sommet m au sommet n, de
durée d(mn) .
8 CHAPITRE 1. L'ORDONNANCEMENT DE PROJET
Remarque
Pour satisfaire cette convention, il peut être nécessaire d'introduire des tâches ctives de
durée nulle.
C'est le cas si plusieurs tâches sont simultanées comme indiqué à la gure 1.4.a) bien
qu'il soit aussi possible de ne retenir que la tâche de durée la plus longue, comme indiqué
à la gure 1.4.b).
a)
10
a 0

b 15

c 0
12

b) a

b 15

Figure 1.4  Tâches a,b,c simultanées

Toutefois l'introduction de tâches ctives de durée nulle est parfois une nécessité. Ce sera
par exemple le cas (voir gure 1.5) pour représenter la situation où
 la tâche c ne peut débuter que si les tâches a et b sont terminées,
 la tâche d ne peut débuter que si la tâche a est terminée.
b c

a d

Figure 1.5  Introduction d'une tâche ctive de durée nulle

Si le problème est bien posé, à l'évidence ce graphe-événements ne comporte pas de

circuit.
Il convient donc d'être attentif à bien exprimer les diérents contraintes de précédence
entre les tâches dans l'élaboration du graphe-événements.
Étant donné cette absence de circuit, il est possible de numéroter les sommets du graphe-
événements selon l'ordre croissant des rangs. (voir dénition 19.11 du tome 1).
Rappelons
 qu'un sommet sans prédécesseurs (ici DEB ) est de rang 0 ;
 qu'un sommet est de rang k si tous ses prédécesseurs sont de rang inférieur à k .
Les sommets de même rang sont numérotés dans un ordre quelconque et la procédure
est appliquée jusqu'à numéroter le sommet F IN (soit sommet N ).
1.1. MINIMISATION DU DÉLAI D'EXÉCUTION D'UN PROJET 9

Remarque
Bien évidemment pour un projet comprenant de très nombreuses tâches, il est dicile
de représenter le graphe-événements. Comme nous l'indiquerons pour l'illustration 1.1,
il est toutefois possible, une fois obtenue la numérotation des événements, de représenter
les données sous forme d'une matrice D de dimension (N + 1 × N + 1) dont l'élémént
(m, n) avec m < n, vaut la durée d(mn) = di de la tâche i = (m, n).

A. Dates des étapes

Dénition 1.1 Date au plus tôt de l'étape m : tm
C'est la date représentant le premier instant auquel on peut s'attendre à la n de l'exé-
cution de toutes les tâches qui précèdent cette étape. Cette date au plus tôt de l'étape m
est notée tm et correspond à la longueur du chemin le plus long pour aller du sommet
initial DEB au sommet m.
Pour calculer ces dates au plus tôt, nous pouvons donc appliquer l'algorithme de Dijkstra
utilisant de manière élémentaire la programmation dynamique pour calculer la longueur
des chemins les plus longs du sommet DEB aux diérents sommets m (voir Ÿ 20.1.1 du
tome 1). En posant initialement t0 = 0, les dates tm sont donc déterminées par la formule
récurrente de m = 0 à m = N .

tDEB (= t0 ) = 0
tm = max −1
(tl + d(lm) ) (1.1)
l∈Γ (m)

Dénition 1.2 Durée minimale d'exécution du projet

La date au plus tôt tN du sommet FIN correspond à la durée minimale d'exécution du
projet.
Dénition 1.3 Date au plus tard de l'étape m : tm
C'est le dernier instant auquel doit se terminer toutes les tâches qui précèdent cette étape
sous peine d'allonger la durée d'exécution minimale tN du projet.
Cette date au plus tard de l'étape m est notée tm et correspond à la diérence entre la
durée minimale du projet (= tN ) et la longueur du chemin le plus long pour aller du
sommet m au sommet F IN .
An de respecter la durée minimale du projet, on pose d'abord

tN = tN

Ensuite, l'algorithme de Dijkstra est à nouveau appliqué pour calculer la longueur des
chemins les plus longs des diérents sommets m au sommet F IN et ces valeurs sont
soustraites de tN . Les dates tm sont donc déterminées par la formule récurrente de m = N
à m = 0.

tN = tN
tm = min (tp − d(mp) ) (1.2)
p∈Γ(m)

Ces deux dates tm et tm de l'étape m peuvent également être calculées sur la matrice
D associée au graphe : pour les formules (1.1), les sommets l ∈ Γ−1 (m) sont ceux situés
10 CHAPITRE 1. L'ORDONNANCEMENT DE PROJET
dans la colonne m avec une valeur positive d(lm) tandis que pour les formules (1.2), les
sommets p ∈ Γ(m) sont ceux situés dans la ligne m avec une valeur positive d(mp) (voir
table 1.2 de l'illustration 1.1).

Remarque
La numérotation m d'un sommet , et ses dates au plus tôt tm et au plus tard tm , sont
indiquées de la façon suivante sur le graphe

m
tm tm

B. Dates des tâches

Soit une tâche i allant du sommet m au sommet n telle que représentée à la gure 1.6

m n
i di
tm t
m tn t
n

Figure 1.6  Tâche i allant de l'événement m à l'événement n

A chaque tâche i, on associe quatre dates :

Dénition 1.4 Début au plus tôt de la tâche i : ES(i)
C'est la date la plus proche, notée ES(i) (Earliest Starting date) à laquelle il est possible
de commencer la tâche i :
ES(i) = tm (1.3)
Dénition 1.5 Fin au plus tôt de la tâche i : EF (i)
C'est la date la plus proche, notée EF (i) (Earliest Final date) à laquelle il est possible
de terminer la tâche i :
EF (i) = ES(i) + di (1.4)

Dénition 1.6 Fin au plus tard de la tâche i : LF (i)

C'est la date la plus éloignée, notée LF (i) (Latest Final date) à laquelle la tâche i doit
se terminer sous peine d'allonger la durée d'exécution minimale du projet :
LF (i) = tn (1.5)

Dénition 1.7 Début au plus tard de la tâche i : LS(i)

C'est la date la plus éloignée, notée LS(i) (Latest Starting date) à laquelle la tâche i
doit commencer sous peine d'allonger la durée d'exécution minimale du projet :
LS(i) = LF (i) − di = tn − d(mn) (1.6)

Ces quatre dates fournissent pour chaque tâche i


 un intervalle de début : [ES(i), LS(i)]
 un intervalle de n : [EF (i), LF (i)]
1.1. MINIMISATION DU DÉLAI D'EXÉCUTION D'UN PROJET 11

Dénition 1.8 Ordonnancement au plus tôt et au plus tard

On parle d'ordonnancement au plus tôt lorsque toutes les tâches sont planiées le plus
tôt possible, (c'est-à-dire débutent en les ES(i) et se terminent en les EF (i)).
On parle d'ordonnancement au plus tard lorsque toutes les tâches sont planiées le plus
tard possible, (c'est-à-dire débutent en les LS(i) et se terminent en les LF (i)), sous
entendu de façon à respecter la durée d'exécution du projet.
L'ordonnancement au plus tard est donc relatif à une date de n prévue du projet, qui
sans autre précision, est la date minimale de n du projet.

C. Marges totales ; tâches critiques ; marges libres

Dénition 1.9 Marge totale d'une tâche
La marge totale (total oat) d'une tâche i  notée M T (i)  représente le retard que peut
subir cette tâche par rapport à son exécution au plus tôt, sans allonger la durée totale du
projet.
C'est donc la largeur commune des intervalles de début et de n de tâche :

M T (i) = LF (i) − EF (i) = LS(i) − ES(i) = tn − (tm + d(mn) ) (1.7)

Si une tâche subit un retard inférieur ou égal à sa marge totale, il est possible qu'il soit
nécessaire de replanier des tâches suivantes mais cela peut se faire sans remettre en
cause la date prévue pour la n du projet.
Dénition 1.10 Tâche critique et chemin critique
Une tâche critique est une tâche pour laquelle M T (i) = 0 :
tout retard apporté à l'exécution d'une telle tâche retarde l'échéance nale pour le projet.
Un chemin critique est un chemin allant du sommet DÉBUT au sommet FIN et composé
de tâches critiques.
Il existe toujours au moins un chemin critique mais il n'est pas nécessairement unique.
La durée d'exécution minimale tN du projet est égale à la longueur commune des chemins
critiques qui sont les chemins les plus longs allant du sommet DÉBUT au sommet FIN.
Dénition 1.11 Marge libre d'une tâche
La marge libre (free oat) d'une tâche i  notée M L(i)  représente le retard que peut
subir cette tâche par rapport à son exécution au plus tôt, sans retarder l'exécution d'une
tâche suivante.
Elle est donc déterminée par la relation
M L(i) = tn − (tm + d(mn) ) (1.8)

Si une tâche subit un retard inférieur ou égal à sa marge libre, il n'est donc pas nécessaire
de remanier l'ordonnancement prévu.
Propriété 1.1 Relation entre les marges totale et libre
0 ≤ M L(i) ≤ M T (i)
12 CHAPITRE 1. L'ORDONNANCEMENT DE PROJET
Par conséquent, la marge libre d'une tâche critique est nulle.
Propriété 1.2 Détermination de la marge libre à l'aide des marges totales
⎡
M L(i) = M T (i) − min M T (j)
⎢ j∈Γ(i)
⎣ où Γ(i) représente l'ensemble des tâches qui suivent directement la tâche i
(voir gure 1.7).

m n
i
tm t
m tn t
n

j ∈ Γ(i) p ∈ Γ(n)

Figure 1.7  Ensemble Γ(i) des tâches qui suivent directement la tâche i

Démonstration
M L(i) = tn − (tm + d(mn) )
= tn − (tm + d(mn) ) − (tn − tn ) 
= M T (i) − min (tp − d(np) ) − tn
p∈Γ(n)
= M T (i) − min (tp − (tn + d(np) ))
p∈Γ(n)

Par conséquent M L(i) = M T (i) − min M T (j) 

j∈Γ(i)
Cette propriété fournit donc un autre moyen de calcul  indépendant des dates des étapes
 de la marge libre qui peut s'avérer plus aisé.
Illustration 1.1
Considérons le problème d'ordonnancement de projet déni par les trois premières co-
lonnes de la table 1.1 :

 la première colonne indique le nom des 21 tâches i, appelées de a à u,

 seules des contraintes de postériorité stricte sont considérées et la deuxième colonne
indique l'ensemble des tâches, noté Γ−1 (i), qui doivent être terminées avant que la
tâche i puisse débuter,
 la troisième colonne indique la durée d(i) de la tâche i.