Master Académique,

Domaine : Mathématiques et Informatique

Spécialité : Big Data Analytics, BigDataA (ex MIND)

Matière : Théorie de l’ordonnancement (THOR)

(2023/2024)

Chapitre 4 :
Ordonnancement sur machines spécialisées
Nous considérons les problèmes d’ordonnancement où les tâches nécessitent un traitement
sur plusieurs machines spécialisées placées dans un atelier. Une tâche (ou un travail) est ainsi
constituée par un ensemble d’opérations visitant différentes machines de l’atelier.

1
1 Atelier à cheminement unique (flow shop)

Dans ce cas, toute tâche ”doit” visiter chaque machine de l’atelier (les machines sont placées
en série) et l’ordre de passage (sur les machines) est le même pout toutes les tâches (flot unidi-
rectionnel, c’est-à-dire que Les tâches sont enchaı̂nées de manière linéaire suivant une chaı̂ne).
Ce problème se rencontre souvent en pratique. Il correspond à une chaı̂ne de fabrication ou de
montage.

Ti ✲ M1 ✲ M2 ✲ ... ✲ Mm ✲

F IGURE 1 – Atelier à cheminement unique.

2
1.1 Cas de deux machines

1.1.1 Minimisation du makespan

L’un des plus classique algorithme est celui du problème F 2//Cmax du à S.M. Johnson en
1956.

Algorithme (problème F 2//Cmax ) ;

début
1- Construire le sous ensemble de tâches X = {Ti ∈ T /pi1 ≤ pi2} ;
2- Ordonnancer, sur les deux machines, les tâches du sous ensemble X suivant l’ordre
croissant de leurs temps de traitement sur la première machine ;
3- Ordonnancer, sur les deux machines, les tâches du sous ensemble T \ X suivant l’ordre
décroissant de leurs temps de traitement sur la deuxième machine ;
fin

La séquence de tâches est la même sur les deux machines. Ce rangement de tâches est appelé
aussi SPT(1)-LPT(2). Il est clair que cet algorithme est en O(nlogn).

3
Exemple 1 Soit à ordonnancer 5 tâches T1, . . . , T5 dont les temps de traitement sur les deux
machines spécialisées (dans un atelier à cheminement unique) sont donnés dans le tableau
ci-dessous.
Ti T1 T2 T3 T4 T5
pi1 3 5 1 6 7
pi2 6 2 2 6 5

L’algorithme se déroule comme suit :

1- X = {T1, T3, T4} ;
2- Les tâches de l’ensemble X sont ordonnancées dans l’ordre T3, T1, T4 ;
3- Les tâches de l’ensemble T \ X sont ordonnancées dans l’ordre T5, T2 ;
On obtient donc l’ordonnancement de la figure suivante.

M1 T3 T1 T4 T5 T2

M2 T3 T1 T4 T5 T2
✲

0 10 20 24 temps

Cmax = 24.

4
Dans le cas où la séquence des tâches est T1, T2, . . . , Tn, la procédure suivante, de complexité
O(n), calcule les dates de début et de fin de traitement de chaque tâche.

Procédure dates ;
début t11 := 0 ; C11 := p11 ;
t12 := C11 ; C12 := t12 + p12 ;
pour i := 2 haut n
faire ti1 := Ci−1,1 ; Ci1 := ti1 + pi1 ;
ti2 := max{Ci1, Ci−1,2} ; Ci2 := ti2 + pi2 ;
fait ;
Cmax := Cn2
fin ;

tij est la date de début de traitement de la tâche Ti sur la machine Mj .

Cij est la date de fin de traitement de la tâche Ti sur la machine Mj .

Dans le cas d’une permutation arbitraire (soit Tπ(1), Tπ(2), . . . , Tπ(n)), il suffit de remplacer l’in-
dice i par π(i) dans les dates de début et de fin de traitement (remplacer tij par tπ(i)j et Cij par
Cπ(i)j ).

5
1.1.2 Minimisation du temps de séjour moyen

Le problème F 2||C est NP-difficile même pour deux machines. l’heuristique suivante est due
à Gonzalez & Sahni avec un ratio de performances garantie égale à m.

Algorithme F m||C (Gonzalez & Sahni (1978), SPT-rule)

m
P
1- Numéroter les tâches telles que p1 ≤ p2 ≤ . . . ≤ pn où pi = pij .
j=1
2- Construire un ordonnancement de permutation telles que toutes les machines traitent les
opérations selon la permutation (1, 2, . . . , n).

6
Application : considérons l’exemple 1.

10 + 24 + 3 + 16 + 22
Avec l’ordonnancement minimisant le makespan, on obtient C = = 15.
5

Avec l’algorithme précédent, On obtient

Ti T1 T2 T3 T4 T5
pi 9 7 3 12 12

La séquence est donc : T3, T2, T1, T4, T5.

l’ordonnancement est donné à la figure suivante.

M1 T3 T1 T4 T5 T2

M2 T3 T1 T4 T5 T2
✲

0 10 20 25 temps

15 + 8 + 3 + 21 + 27
avec C = = 14.8.
5

7
1.1.3 Autres critères

Le problème F 2||Lmax est NP-difficile ainsi que les problèmes F 2|pij = 1, chains|Cw , F 2|pij =
1, chains|T et F 2|pij = 1, chains|U.

8
1.2 Cas de plusieurs machines (m ≥ 3)

L’algorithme de Johnson peut être étendu à résoudre le cas de 3 machines spécialisées où
min {pi1} ≥ max {pi2} ou min {pi3} ≥ max {pi2}. Dans ce cas le temps de traitement sur
1≤i≤n 1≤i≤n 1≤i≤n 1≤i≤n
la deuxième machine n’est pas important et l’ordonnancement optimal peut être obtenu par
application de l’algorithme précédent aux temps de traitement (pi1 + pi2, pi2 + pi3) (on ramène
le problème à celui de deux machines).

Les deux problèmes F m/pmtn/Cmax et F m//Cmax (pour m ≥ 3) sont NP-difficiles et plu-

sieurs heuristiques et méthodes exactes de type séparation et évaluation sont proposées dans
la littérature.

Une solution optimale pour F 3/prmu/Cmax est aussi optimale pour F 3//Cmax . Jusqu’à trois
machines, un ordonnancement optimal est recherché parmi les ordonnancements de permuta-
tion.

9
Considérons le problème F m|prmu|Cmax . Pour une séquence de tâches (ou permutation)
T1 → T2 → · · · → Tn et une gamme de fabrication M1 → M2 → · · · → Mm, la date de
fin d’une tâche Ti sur une machine Mj est donnée par les expressions récursives :
j

P
c1j = p1k ; j = 1, . . . , m




 k=1
Pi

 ci1 = pk1 ; i = 1, . . . , n

 k=1
cij = max{c(i−1)j , ci(j−1)} + pij ; i = 2, . . . , n ; j = 2, . . . , m


Notons que Cmax = Cnm.

10
La procédure suivante calcule les dates de fin de traitement de chaque opération sur chaque
machine sans dessiner la diagramme de Gantt.

Procédure Cij ;
début C11 := p11 ;
pour j := 2 haut m faire C1j := C1,j−1 + p1j fait ;
pour i := 2 haut n faire Ci1 := Ci−1,1 + pi1 fait ;
pour i := 2 haut n
faire pour j := 2 haut m
faire Cij := max{c(i−1)j , ci(j−1)} + pij ;
fait ;
fait ;
Cmax := Cnm
fin ;

11
1.2.1 Bornes inférieures

Les deux bornes suivantes sont évidentes :

m
P n
P
LB1 = max { pij } et LB2 = max { pij }.
1≤i≤n j=1 1≤j≤m i=1

On peut aussi définir d’autres bornes inférieures plus efficaces.

j−1 n m
j
P P P
LB3 = min { pik } + pij + min { pik }
1≤i≤n k=1 i=1 1≤i≤n k=j+1

qui vient du fait que si on considère une machine quelconque (soit Mj ) :

n
P
(a) Toutes les tâches de cette machine doivent être traitées, on a donc pij ,
i=1
(b) La tâche traitée en première position doit aussi être traitée sur les machines précédentes,
j−1
P
on prend donc min { pik }, et
1≤i≤n k=1
(c) La tâche traitée en dernière position doit aussi être traitée sur les machines suivantes, on
Pm
prend donc min { pik }.
1≤i≤n k=j+1

Nous avons donc, LB3 = max {LB3j } comme meilleure borne inférieure.
1≤j≤m

12
1.2.2 Heuristique pour F m|perm|Cmax

Soit l’exemple suivant.

Exemple 2 Soit une instance à 4 machines et 5 taches avec les durées des opérations données
par la table suivante.

pij T1 T2 T3 T4 T5
M1 1 10 17 12 11
M2 13 12 9 17 3
M3 6 18 13 2 5
M4 2 18 4 6 16

LB1 = max{51, 54, 44, 46} = 54.

LB2 = max{22, 58, 43, 37, 35} = 58.

LB3 = max{51 + 21, 1 + 54 + 8, 14 + 44 + 2, 46 + 19} = max{72, 63, 60, 65} = 72.

Donc, LB = 72.

13
Heuristique CDS

Proposée par H. G. Campbell, R. A. Dudek and M. L. Smith en 1970. Son principe est de
construire m − 1 problèmes à 2 machines, trouver la meilleure séquence en utilisant l’algo-
rithme de Johnson, et ensuite, appliquer cette séquence au problème original à m machines.

Heuristique CDS(F m|perm|Cmax ) ;

début
1. k := 1 ;
k m
p′i1 p′i2
P P
2. Calculer = pij et = pij pour i = 1, . . . , n ;
j=1 j=m−k+1
3. Appliquer l’algorithme de Johnson au problème à 2 machines avec les durées définies
ci-dessus ;
4. Si k < m − 1
alors k := k + 1 ; aller à 2
fsi ;
5. Choisir la séquence donnant le plus petit makespan ;
6. Appliquer cette séquence au problème original à m machines ;
fin.

14
Le déroulement donne :

- k = 1 : Nous avons,
T1 T2 T3 T4 T5
p′i1 1 10 17 12 11
p′i2 2 18 4 6 16

La séquence est T1, T2, T5, T4, T3.

Pour calculer le makespan nous utilisons la procédure Cij, on obtient donc

 
1 11 22 34 51
 14 26 29 51 62 
C=
 20

44 49 59 75 
22 62 78 84 88

Donc, Cmax = 88.

15
- k = 2 : Nous avons,
T1 T2 T3 T4 T5
p′i1 14 22 26 29 14
p′i2 8 36 17 8 21

La séquence est T5, T2, T3, T1, T4.

 
11 21 38 39 51
 14 33 47 60 77 
C=
 19

51 64 70 79 
35 69 73 75 85

Cmax = 85.

- k = 3 : Nous avons,
T1 T2 T3 T4 T5
p′ij 20 40 39 31 19
p′ij 21 48 26 25 24

La séquence est T5, T1, T2, T3, T4.

16
  
11 12 22 39 51
 14 27 39 48 68 
C=
 19

33 57 70 72 
35 37 75 79 85

Cmax = 85

Nous choisissons la troisième séquence. La solution trouvée est donc,

M1 T5 T1 T2 T3 T4
M2 T5 T1 T2 T3 T4
M3 T5 T1 T2 T3 T4
M4 T5 T1 T2 T3 T4
✲

0 10 20 30 40 50 60 70 80 temps

Cmax = 85.

17
Heuristique Gupta

Proposée par J. N. D. Gupta en 1972. Son principe est de ranger les tâches selon un indice à
calculer.

Heuristique Gupta(F m|perm|Cmax ) ;

début

1 si pi1 < pim
1. Calculer ei = pour i = 1, . . . , n ;
-1 si pi1 ≥ pim
ei
2. Calculer si = pour i = 1, . . . , n ;
min {pik + pik+1}
1≤k≤m−1
3. Ranger les tâches selon l’ordre décroissant des si ;
4. Appliquer cette séquence au problème ;
fin.

18
Appliquons l’heuristique à l’exemple précédent.

on obtient,
pi1 + pi2 pi2 + pi3 pi3 + pi4 min ei si
T1 14 19 8 8 1 0.125
T2 22 30 36 22 1 0.045
T3 26 22 17 17 -1 -0.058
T4 29 19 8 8 -1 -0.125
T5 14 8 21 8 1 0.125

La séquence obtenue est T1, T5, T2, T3, T4 et l’ordonnancement est

M1 T1 T5 T2 T3 T4
M2 T1 T5 T2 T3 T4
M3 T1 T5 T2 T3 T4
M4 T1 T5 T2 T3 T4
✲

0 10 20 30 40 50 60 70 80 temps

Cmax = 80.

19
Heuristique NEH

Proposée par M. Nawaz, E. Enscore et I. Ham en 1983. Elle est la meilleure heuristique connue
à ce jour pour le flow shop de permutation. Son principe est de sélectionner la tâche ayant le
plus long temps de traitement global parmi les tâches non encore placées et essaie de l’insérer
dans toutes les positions possibles de la séquence partielle en cours de construction. Elle choisit
enfin la séquence qui augmente le moins le makespan de l’ordonnancement partiel formé par
les tâches déjà placés.

Soit Seq la meilleure séquence de tâches, initialement vide.

20
Heuristique NEH(F m|perm|Cmax ) ;
début
— Soit T1, T2, . . . , Tn la liste de tâches rangées dans l’ordre décroissant de leurs durées
globales.
— Placer la tâche T1 dans la séquence Seq.
— Pour i = 2 à n faire
′
— Cmax = ∞;
— Pour k = 1 à i faire
— Construire une solution partielle en mettant la tâche Ti à la position k dans la
séquence Seq.
— Calculer le makespan Cmax de cette solution partielle.
′
— Si Cmax < Cmax alors
best = k ;
′
Cmax = Cmax
Fsi
Finpour
— Placer la tâche Ti à la position best dans la séquence Seq.
Finpour
— Appliquer cette séquence au problème ;
fin.

21
Appliquons l’heuristique à l’exemple précédent.

Les durées de traitement globales sont

Tâche T1 T2 T3 T4 T5
Durée globale 22 58 43 37 35

ce qui nous donne la liste : T2, T3, T4, T5, T1.

Le déroulement nous donne (les makespans sont calculés en utilisant la procédure Cij).

Seq = T2 ;
Les séquences partielles :
T3 − T2, Cmax = 75 ;
T2 − T3, Cmax = 62 ;
best = 2.

Seq = T2 − T3 ;
Les séquences partielles :
T4 − T2 − T3, Cmax = 81 ;
T2 − T4 − T3, Cmax = 68 ;
T2 − T3 − T4, Cmax = 68 ;
best = 2.
22
Seq = T2 − T4 − T3 ;
Les séquences partielles :
T5 − T2 − T4 − T3, Cmax = 79 ;
T2 − T5 − T4 − T3, Cmax = 84 ;
T2 − T4 − T5 − T3, Cmax = 84 ;
T2 − T4 − T3 − T5, Cmax = 82 ;
best = 1.

Seq = T5 − T2 − T4 − T3 ;
Les séquences partielles :
T1 − T5 − T2 − T4 − T3, Cmax = 80 ;
T5 − T1 − T2 − T4 − T3, Cmax = 87 ;
T5 − T2 − T1 − T4 − T3, Cmax = 92 ;
T5 − T2 − T4 − T1 − T3, Cmax = 89 ;
T5 − T2 − T4 − T3 − T1, Cmax = 81 ;
best = 1.

La meilleure séquence trouvée est donc : T1 − T5 − T2 − T4 − T3.

23
L’ordonnancement est :

M1 T1 T5 T2 T4 T3
M2 T1 T5 T2 T4 T3
M3 T1 T5 T2 T4 T3
M4 T1 T5 T2 T4 T3
✲

0 10 20 30 40 50 60 70 80 temps

avec Cmax = 80.

24