2 Atelier à cheminement libre (open shop)

Dans ce cas, l’ordre de passage des opérations sur les machines n’est pas imposé ; les opérations
d’une tâches peuvent être exécutées dans n’importe quel ordre. C’est par exemple le cas pour
la réparation ou la maintenance d’engins mécaniques, ou encore la tenue d’examens médicaux
pour des patients hospitalisés.

25
2.1 Cas de deux machines

Considérons le problème O2//Cmax.

n
P n
P
Nous avons : Cmax = max{ max {pi1 + pi2}, pi1, pi2}.
1≤i≤n i=1 i=1

T. Gonzalez & S. Sahni (1976) ont proposé le premier algorithme en O(n).

M.L. Pinedo (2008), propose la règle de priorité LAPT (Longest Alternate Processing Time
first) qui résout le problème en O(n log n).

N. Babou, D. Rebaine & M. Boudhar (2021) proposent la règle GARD (Greatest And then
RanDom) qui résout le problème en O(n).

26
2.1.1 Règle LAPT

L’idée principale est de ”traiter la tâche ayant le plus long temps de traitement sur l’autre
machine”.

Pour construire une solution optimale, on procède comme suit :

1- Sur la première machine libre traiter la tâche ayant le plus long temps de traitement sur
l’autre machine et la supprimer de la liste.

2- Répéter cette étape jusqu’à ce que toutes les tâches soient traitées.

3- Ensuite, répéter l’ordre des tâches de chaque machine, trouvé à l’étape précédente, sur
l’autre machine.

27
Exemple 3 Soit à ordonnancer 5 tâches T1, . . . , T5 dont les temps de traitement sur les deux
machines spécialisées (dans un atelier à cheminement libre) 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

En appliquant la règle LAPT on obtient : A t = 0, on place les tâches T1 et T5 respectivement

sur les machines M1 et M2. La prochaine machine libre est M1 (t = 3). On sélectionne la tâche
T4. On place ensuite successivement, à t = 5, la tâche T2 et la tâche T3 sur M2. A t = 9, une
opération de chaque tâche a déjà été réalisée. On place alors les opérations restantes sur leurs
machines correspondantes. On obtient donc la solution suivante.

M1 T1 T4 T5 T2 T3

M2 T5 T2 T3 T1 T4
✲

0 5 10 15 20 22 temps

28
2.1.2 Règle GARD

L’idée principale est de ” traiter l’opération la plus longue d’abbord, ensuite les autres dans un
ordre arbitraire”.

Pour construire une solution optimale, on procède comme suit :

1- Trouvée l’opération ayant le plus long temps de traitement (soit Okh) et traiter la tâche
Th sur l’autre machine (c’est-à-dire, la machine M3−h) à t = 0.

2- Traiter les autres tâches, une à une, dans un ordre arbitraire, sur la première machine
libre.

3- Traiter l’opération Okh (sur la machine Mh) le plus tôt possible.

4- Traiter les opérations restantes, le plus tôt possible, dans un ordre arbitraire, sur la ma-
chine correspondante.

29
Algorithme Greatest And then RanDom (GARD) ;
début 1- Soit pkh = max{pij : i = 1, . . . , n; j = 1, 2} ;
2- Traiter Tk sur la machine M3−h ;
3- Pour i = 1 à n, i 6= k faire
Traiter Ti sur la première machine libre
fait ;
4- Traiter Tk , le plutôt possible, sur la machine Mh ;
5- Pour i = 1 à n ; i 6= k faire
Traiter l’opération restante de Ti le plutôt possible sur la machine correspondante
fait ;
fin.

Pour l’exemple précédent, nous avons k = 5 et h = 1 (p51 = 7). L’ordonnancement obtenu

est :

M1 T1 T2 T5 T3 T4

M2 T5 T3 T4 T1 T2
✲

0 5 10 15 20 22 temps

30
2.2 Autres critères

Les problèmes O2//ΣCi et O2//Lmax sont NP-difficiles.

31
2.3 Cas de plusieurs machines

Le problème devient NP-difficile si le nombre de machines passe à 3 (O3//Cmax).

Une borne inférieure pour le problème Om//Cmax est

Xn Xm
LB = max{ max { pij }, max { pij }}
1≤j≤m 1≤i≤n
i=1 j=1

Si on ajoute la préemption des tâches, le problème O/pmtn/Cmax devient polynomial avec

Cmax = LB.

32
Cas particulier Om/pij = 1/Cmax

Il n’est pas difficile de construire un ordonnancement optimal pour le problème Om/pij =

1/Cmax avec Cmax = max{m, n}.

Les deux diagrammes suivants montre :

(a) un ordonnancement optimal pour 7 tâches et 4 machines.
(b) un ordonnancement optimal pour 3 tâches et 4 machines.

(a) m = 4 et n = 7 (b) m = 4 et n = 3

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

0 1 2 3 4 5 6 7 temps 0 1 2 3 4 temps

33
La procédure suivante, de complexité O(mn), calcule les dates de début et de fin de traitement
de chaque tâche.

Procédure dates ;
début Cmax = max{m, n} ;
pour i := 1 haut n
faire pour j := 1 haut m
faire tij = reste(i + j − 2, Cmax ) ;
Cij = tij + 1
fait
fait
fin ;

On peut remplacer tij = reste(i + j − 2, Cmax) par

Si i + j − 1 ≤ Cmax
alors tij = i + j − 1
sinon tij = i + j − 1 − Cmax
fsi

34
Heuristique

Nous allons étudier une heuristique basée sur la règle LAPT.

Considérons l’instance suivante avec 4 machines et 5 taches dont les durées des opérations
sont 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

Nous avons :

LB = max{max{50, 54, 44, 46}, max{22, 58, 43, 37, 35}} = max{54, 58} = 58

35
Heuristique

Cette heuristique est divisée en trois étapes :

Etape 1 : (Généralisation de la règle LAPT à m > 2 machines) à chaque l’instant t, commencer

par t = 0, si une machine est libre, lui affecter la tâche ayant le plus long temps de traitement
sur les autres machines. S’il y a plusieurs machines disponibles, choisir celle ayant le plus
petit indice et s’il y a plusieurs tâches candidates, choisir celle ayant le plus petit indice. Ne
pas prendre une tâche si elle est déjà affectée.

Etape 2 : Après l’étape 1, nous avons, pour chaque machine Mj , une séquence de tâches Sj
qui lui sont affectées en première position. Avec ces séquences partielles, nous formons les m
cycles possibles à partir de la permutation S1, S2, . . . , Sm en faisant des décalages à gauche.

Ainsi, à chaque machine Mj est affectée la permutation (ou la séquence) de tâches n° j

dénommée Seqj .

36
Un exemple pour 4 machines :
M1 : Seq1 = S1 − S2 − S3 − S4
M2 : Seq2 = S2 − S3 − S4 − S1
M3 : Seq3 = S3 − S4 − S1 − S2
M4 : Seq4 = S4 − S1 − S2 − S3

Etape 3 : (ordonnancement des tâches sur les machines) Prendre la première machine libre et
lui affectée la première tâche libre de sa séquence.

Algorithme MLS (Multi List Scheduling) ;

début
1- t = 0.
2- Tantque il existe une opération non encore affectée faire
- Soit Mj la première machine disponible.
- Prendre la première opération de la séquence Seqj et l’ordonnancer le plus tôt possible.
(cette opération est donc supprimée de la séquence)
- t = la plus petite date disponible.
fait
fin.

37
Le déroulement de la méthode sur l’exemple précédent donne :

Les séquences partielles sont : S1 = T2, S2 = T3, S3 = T4 − T5 et S4 = T1.

Ainsi,
Seq1 = T2 − T3 − T4 − T5 − T1,
Seq2 = T3 − T4 − T5 − T1 − T2,
Seq3 = T4 − T5 − T1 − T2 − T3, et
Seq4 = T1 − T2 − T3 − T4 − T5.

L’ordonnancement obtenu est donné ci-dessous

M1 T2 T3 T4 T5 T1

M2 T3 T4 T5 T1 T2

M3 T4 T5 T1 T2 T3

M4 T1 T2 T3 T4 T5
✲

0 10 20 30 40 50 60 temps

avec Cmax = 66.

38