Théorie des Graphes - THG

CHAPITRE 4 : LE PROBLEME D’ORDONNANCEMENT

Plan
1. Notions préliminaires
2. Les différents types de contraintes
3. Les méthodes de résolution

1. NOTIONS PRELIMINAIRES
Les réalisations importantes telles que la construction de barrages, d’immeubles, … nécessitent une
surveillance permanente et une parfaite considération des différents travaux à effectuer pour éviter
des pertes de temps (souvent couteuses) et respecter les délais. Les problèmes liés à cette
coordination sont appelés problèmes d’ordonnancement.
On dit qu’on a affaire à un problème d’ordonnancement chaque fois que le processus de réalisation
d’un objectif (projet) se décompose en plusieurs tâches (travaux élémentaires) soumises à des
contraintes et dont l’exécution nécessite au préalable l’établissement d’un certain ordre entre ces
multiples tâches.
La représentation d’un problème d’ordonnancement par un graphe (avec l’application de méthodes de
détermination des chemins optimaux) permet d’identifier les tâches prioritaires et de détecter les
retards et/ou les dépassements des moyens à temps pour prendre des mesures correctives.

2. LES DIFFERENTS TYPES DE CONTRAINTES

2.1. Les contraintes de type potentiel

• Les contraintes de localisation temporelle : La tâche u ne doit pas être commencée avant telle date
ou au contraire, doit être achevée à telle date.
• Les contraintes de succession : La tâche ¿ ne peut pas être commencée que lorsque la tâche u est
achevée.

Les tâches u et ¿ ne peuvent pas être réalisées en même temps (par exemple c’est le même ouvrier qui
2.2. Les contraintes de type subjonctif

les réalisent ou c’est la même machine).

2.3. Les contraintes de type cumulatif

Les moyens (humains, financiers, matériels,…) nécessaires à l’exécution d’un certain nombre de tâches

les travaux ne doit pas dépasser une somme ) à l’instant ).

sont à chaque instant limités (par exemple le nombre de camions utilisés est 2, la somme dépensée sur

Dans tout ce qui suit, on tiendra compte seulement des contraintes de succession.

3. LES METHODES DE RESOLUTION

Jusqu’à 1958 il y avait uniquement le "planning à barres" dit diagramme de Gantt et les algorithmes de
Johnson applicable dans des cas bien particuliers.

Exemple 1 : Diagramme de Gantt

0 1 2 3 4 5 6 7 8 Temps

Tâche 1

Tâche 2

Tâche 3

34
Théorie des Graphes - THG
Les segments sont proportionnels à la durée de leur tâche et parallèle à l’axe correspondant au temps.

Après 1958, sont apparues 2 nouvelles méthodes indépendantes fondées sur la théorie des graphes : la
méthode américaine CPM (Critical Path Method) avec sa variante PERT (Program Evaluation and
Review Technique ou Research Task) et la méthode française dite « Méthode des potentiels ».

Ces 2 méthodes permettent :

- d’établir un ordonnancement des tâches composant le projet.
- de déterminer le temps optimal total nécessaire à la réalisation du projet.
- de déterminer le chemin critique et ses tâches critiques (i.e. les tâches dont tout retard
d’exécution sur l’une d’elles, se répercutera sur la durée minimale de la réalisation du projet).

3.1. Le graphe potentiel-tâche

A partir d’un projet donné, on construit le graphe suivant : à chaque tâche u (u allant de 1 à Æ) on lui
Définition

associe un sommet u du graphe. On définira un arc de u vers ¿ de longueur A si la tâche u doit précéder
la tâche ¿ (A est la durée minimale devant s’écouler entre le début de la tâche u et celui de la tâche ¿).

Le graphe ainsi obtenu doit être sans circuit, on lui ajoute alors 2 sommets ® et î correspondant à 2
tâches fictives : ® est la tâche de début des travaux de durée nulle (Aï 0), elle doit être antérieure à

î la tâche de fin des travaux, elle doit être postérieure à toutes les autres tâches (pour cela, il suffit de
toutes les autres tâches (pour cela, il suffit de la relier aux sommets sans prédécesseurs du graphe) et

la relier à tous les sommets sans successeurs du graphe).

Exemple 2 :
Un atelier fabrique 2 pièces P1 et P2 devant être montées sur un appareil. Ces deux pièces sont
obtenues à partir de 2 éléments M1 et M2 qu’il faut commander au magasin central. Les pièces P1 et
P2 nécessitent toutes les deux un tournage et un filetage ; le tournage est effectué sur l’élément M1 et
le filetage sur l’élément M2. La pièce P2 doit être en plus polie après son filetage et son tournage. Les
pièces P1 et P2 entièrement usinées sont ensuite montées sur l’appareil. Sachant que le travail débute
à 8h00, on désire connaître à quel moment l’appareil sera disponible.

Code tâche Désignation de la tâche Durée en minutes Tâches antérieures

∅
∅
A Approvisionnement de M1 20
B Approvisionnement de M2 10
C Tournage de M1 pour P1 20 A
D Filetage de M2 pour P1 10 B
E Tournage de M1 pour P2 20 A
F Filetage de M2 pour P2 10 B
G Polissage de P2 20 E,F
H Montage de P1 10 C,D
I Montage de P2 10 G

® sera relié à N et . (car # (N) = # (.) = ∅), et î succédera à £ et › car ( " (£)
= " (›)
= ∅).

On peut représenter le graphe associé par niveau après avoir calculé sa fonction ordinale (ou rang).

ƾ = {®} Æ = {N , .} Æ = {‘ , • , ’ , Ÿ} Æ% = {£ , } Æ& = {›} Æ' = {î}

Les niveaux :

35
Théorie des Graphes - THG

20 ‘ 20
N £
10
• î
0 20 10

®
’ 20
›
10
10

.
0
20

Ÿ
10
10

Niv. 0 Niv. 1 Niv. 2 Niv. 3 Niv. 4 Niv. 5

Le travail commence à 8h00, on cherche l’heure de fin des travaux.

Méthode de calcul des paramètres

La date au plus tôt : la date au plus tôt de la tâche u est :

(ƒ~ + ó~ )
•
ƒ} áðñ
òa ~∈” (})
C'est-à-dire est égale à la longueur du plus long chemin de ® à u : ℓ(® , u)

La durée minimale du projet ô est donc égale à la longueur du plus long chemin de ® à î.

ô est la durée minimale du projet, la date au plus tard õ de début de

la tâche u est :
• La date au plus tard : si

ö} = áâã ö~ − ó} „÷‚Ð öø = ƒø
~∈”(})
Où õ = ô − ℓ(u , î) avec ℓ(u , î) est la longueur du plus long chemin de u à î.

• La marge : La marge u de la tâche u est la différence entre la date au plus tôt et la date au plus

ù} = ö} − ƒ}
tard :

Les tâches dont leur marge est nulle sont appelées tâches critiques ; elles constituent le chemin
critique. Si un quelconque retard est pris sur une de ces tâches, celui-ci sera répercuté sur la durée min
du projet.

Entre deux tâches u et ¿ telle que ¿ ∈ #

(u), on doit avoir õ − ≥A

La date associée à chaque tâche peut être considérée comme un potentiel d’où l’appellation du
graphe « potentiel-tâches ».

Le graphe étant sans circuit, l’algorithme de recherche du plus long chemin sera celui de la recherche
du chemin minimal, en remplaçant le min par le max.

Algorithme de calcul des dates d’un problème d’ordonnancement par le graphe potentiel-tâches

1. Poser A(®) = 0
• Algorithme de calcul des dates au plus tôt

2. Prendre les sommets u par ordre croissant et calculer :

ƒ} = áðñ (ƒ~ + ó~ )
òa ~∈” (})

36
Théorie des Graphes - THG

0
Exemple 2 (Suite) :
ï
© = max( ï + Aï ) = 0 + 0 = 0
2 = max( ï + Aï ) = 0 + 0 = 0
Õ = max( © + A© ) = 0 + 20 = 20
Ö = max( 2 + A2 ) = 0 + 10 = 10
û = max( © + A© ) = 0 + 20 = 20
ü = max( 2 + A2 ) = 0 + 10 = 10
! = max( û + Aû , ü + Aü ) = max{20 + 20 , 10 + 10} = 40
ý = max( Õ + AÕ , Ö + AÖ ) = max{20 + 20 , 10 + 10} = 40
þ = max( ! + A! ) = max{40 + 20} = 60
ô = max( ý + Aý , þ + Aþ ) = max{40 + 10 , 60 + 10} = 70

ƒø = ÜÛ

• Algorithme de calcul des dates au plus tard

ô étant la durée min du projet.
1. Poser õô = ô
2. Prendre les sommets u par ordre décroissant et calculer :
ö} = áâã ö~ − ó}
~∈”(})

õô = ô = 70
Exemple 2 (Suite) :

õþ = min{õô } − Aþ = 70 − 10 = 60
õý = min{õô } − Aý = 70 − 10 = 60
õ! = min{õþ } − A! = 60 − 20 = 40
õü = min{õ! } − Aü = 40 − 10 = 30
õÖ = min{õý } − AÖ = 60 − 10 = 50
õû = min{õ! } − Aû = 40 − 20 = 20
õÕ = min{õý } − AÕ = 60 − 20 = 40
õ2 = min{õÖ , õü } − A2 = 30 − 10 = 20
õ© = min{õÕ , õû } − A© = 20 − 20 = 0

ù} = ö} − ƒ}
• Calcul des marges

+© = õ© − © = 0 − 0 = 0
Exemple 2 (Suite) :

+2 = õ2 − 2 = 20 − 0 = 20
+Õ = õÕ − Õ = 40 − 20 = 20
+Ö = õÖ − Ö = 50 − 10 = 40
+û = õû − û = 20 − 20 = 0
+ü = õü − ü = 30 − 10 = 20
+! = õ! − ! = 40 − 40 = 0
+ý = õý − ý = 60 − 40 = 20
+þ = õþ − þ = 60 − 60 = 0

Les tâches critiques sont donc : K , ç , “ ‚ƒ

Le chemin critique est : ( , K , ç , “ , , ø)
L’appareil sera disponible à 8h00 + 70’ = 9h10’

37
Théorie des Graphes - THG

‘
(20,40)

( ,õ )
(0,0) 20 20
N £
(40,60)

10
•
(20,20)
î
(70,70)
0 20 10

®
(0,0)

’ 20
›
10
10

.
0 (10,50)
20 (60,60)

Ÿ
(0,20) 10 (40,40)
10
Plus tôt (10,30) Plus tard

3.2. Le graphe potentiel-étapes (PERT)

Dans cette méthode, les tâches représentent les arcs du graphe et les étapes (ou événements) les
sommets du graphe (d’où l’appellation du graphe "potentiel-étapes") :
- Une étape est un début ou une fin de tâche.
- La longueur de chaque arc représente la durée de la tâche correspondante.
- On définit une étape de début du projet, une étape de fin de projet, et un certain nombre

Si une tâche ¿ doit succéder à une tâche u, l’extrémité initiale de l’arc

d’étapes intermédiaires.

tâche ¿) doit être l’extrémité finale de l’arc (correspondant à la tâche u).

- (correspondant à la

- Le graphe ainsi obtenu doit être sans circuit.

La construction d’un tel graphe est un peu complexe car elle nécessite la définition des étapes.
Généralement les étapes peuvent être définies à partir de la colonne du tableau (tâches antérieures).

Les étapes correspondantes sont : {u N, {u ., {u • Ÿ, {u ‘ ’, {u , {u £ ›.

Exemple 3 : (Même énoncé que l’exemple 2)

\
] fin d’approvisionnement de M1 ({u N)
: début des travaux (ou fin de passation des commandes de M1, M2)

^ fin d’approvisionnement de M2 ({u .)

:

A fin du tournage de M1 et filetage de M2 pour P2 ({u • Ÿ)

:

fin du tournage de M1 et filetage de M2 pour P1 ({u ‘ ’)

:

{
:

À fin de montage de P1 et P2 ({u A £ ›)

: fin de polissage pour P2 ({u )
:

A
Nous obtenons le graphe potentiel-étapes suivant :

]
20

{
E 20
G
20 10
10
A F I

\ À
20
B C H
10 10

^ D
10 38
Théorie des Graphes - THG
Date au plus tôt :
- La date au plus tôt | de réalisation de l’étape | est égale à la longueur du plus long chemin
entre l’étape début et l’étape |
- La date au plus tôt de début de chaque tâche issue de l’étape | est alors |
- La durée minimale du projet est donc égale à la longueur du plus long chemin entre l’étape
début et l’étape fin du projet ( étant l’indice de l’étape fin du projet).

Date au plus tard :

|
õ| min õ − A| \œ ^ õ =
- Si est la durée minimale du projet, la date au plus tard de réalisation de l’étape est :
∈

õ| = − ℓ(– , )
Où ℓ(– , ) est la longueur du plus long chemin de – à
Ou bien

- La date au plus tard de début de chaque tâche issue de l’étape | est alors õ| .

- La marge + de l’étape ¿ (la tâche ¿) est : + = õ −

Marge :

- Les étapes dont la marge est nulle sont les étapes critiques qui constituent le chemin critique
de l’étape début à l’étape fin du projet.

= 0, = 20, = 10, = 40, = 40, = 60, = 70

Exemple 3 (suite) :
Calcul des dates au plus tôt : g ¥

õ = = 70
õ¥ = 70 − 10 = 60
Calcul des dates au plus tard :

õ = 70 − 10 = 60
õ = 70 − 30 = 40
õ = 70 − 40 = 30
õg = 70 − 50 = 20
õ = 70 − 70 = 0
+ =0−0=0
+g = õg − g = 20 − 20 = 0
Calcul des marges :

+ = 30 − 10 = 20
+ = 40 − 40 = 0
+ = 60 − 40 = 20
+¥ = 60 − 60 = 0
+ = 70 − 70 = 0
Donc les tâches critiques sont {(\, ]) , (], A) , (A, {) , ({, À)}, Le chemin critique est (\ , ] , A , { , À) de
valeur 70 minutes. L’appareil sera disponible à 8h00 + 70’ = 9h10’

(40,40)

A
(20,20)

]
20
(60,60)

{
E 20
G
20 10
10 (70,70)
(0,0) A F I

\ À
20
B C H
10 10

^ D
10
(10,30) 39
(40,60)