Ordonnancement

Chapitre II

 Copyright : Sonia Rebai

1
 Définitions
 L’ordonnancement est la dernière étape de la planification
de la production.
 Il est souvent la seule étape dans les PME.
 Il consiste à déterminer :
 La séquence d’exécution des travaux ou du programme de
production
ou
 La chronologie d’utilisation des ressources de l’entreprise ou
la charge de travail,
 Afin de satisfaire les besoins des clients en termes de
quantité, de qualité, de temps, de lieu et de coûts.

2
 Importance de l’ordonnancement
 Une circulation plus rapide des marchandises à travers
une installation permet :

 Meilleure exploitation
 Meilleure maîtrise des coûts.
 Amélioration de la qualité de service
 Rapidité de la livraison

3
 Exemples
Organisation Ordonnancement
Hôpital Utilisation des salles d’opérations
L’admission des patients
Affectation des infirmiers, des agents de sécurité, du personnel de
maintenance
Traitement des patients externes
Université Salles et équipements audiovisuels
Emplois de temps des étudiants et enseignants
Cours de licences et de mastères
Usine Production de biens
Achat de matériels
Employés
Café Serveurs
Livraison des aliments
Compagnie Aérienne Maintenance des avions
Horaires de départ
Personnel navigant et Personnel de billetterie
Restauration
4
 Modèles d’ordonnancement
 Parmi les modèles d’ordonnancement on distingue :

 Les modèles statiques :

 Une fois par période
 Nouvelle commande signifie nouvel ordonnancement (au
cours de la période considérée, aucune nouvelle tâche non
prévue ne peut être prise en compte dans l’ordonnancement).

 Les modèles dynamiques :

 Toutes les commandes sont considérées au fur et à mesure.
 Techniques plus complexes (files d’attente et simulations)

5
 Les critères les plus utilisés dans
l’ordonnancement
 Minimiser le temps d'exécution;

 Maximiser l'utilisation des installations;

 Minimiser les stocks de produits semi-finis;

 Minimiser le temps d'attente du client.

6
 Charge de travail
 Le document charge de travail décrit la liste des travaux ou
de commandes que les différents postes ou centres
d’exploitation doivent exécuter.
 Deux situations sont possibles:
 Une capacité illimitée ou infinie: un ou plusieurs produits
peuvent être exécutés à la fois.
 Une capacité limitée ou finie: un nombre restreint de produits
en même temps.
 Décider à quel produit donner la priorité d’exécution: Un
produit ne peut être exécuté que si la ressource à utiliser
est disponible et que le produit est passé par toutes les
opérations préalables.

7
 Le diagramme de Gantt
 L’outil le plus simple pour illustrer les charges de travail est le
diagramme de Gantt.
 Il permet de visualiser à la fois :
 L’utilisation dans le temps des moyens productifs
(départements, machines, installations, employés, …).
 L’avancement de l’exécution des tâches. En particulier, il permet
de contrôler les travaux en cours.
 Tous les diagrammes de Gantt doivent être fréquemment
mis à jour pour tenir compte des changements.
 Le diagramme de Gantt se construit en portant en abscisse le
temps et en ordonnée les postes de travail.

8
 Le diagramme de Gantt

Jour Lundi Mardi Mercredi Jeudi Vendredi

Atelier

A1 Tâche A Tâche D

A2 Tâche B Tâche F

A3 Tâche C Tâche E

A4 Tâche F Tâche C Tâche E

Occupé Libre Indisponible

9
 Problème d’affectation
 Le problème d’affectation se pose dans plusieurs situations de prise
de décision.
 Les problèmes d’affectation concernent généralement l’attribution
de :
 tâches aux machines,
 personnel aux tâches
 Commerciaux aux territoires de vente,
 …
 Une caractéristique important du problème d’affectation est qu’une
personne (tâche) est affectée à une seule et unique machine
(projet).
 Plus précisément, on cherche à déterminer la meilleure affectation
qui optimisera un objectif, comme minimiser les coûts, minimiser le
temps d’exécution ou maximiser les profits.
 2 méthodes de résolution des problèmes d’affectation :
 Programmation linéaire avec nombres entiers
 Méthode Hongroise
10
 Problème d’affectation
1. PL en nombres entiers
 Le PL en nombre entiers (traité dans le chapitre 1) est un
outil puissant qui permet de résoudre les problèmes
d’affectation en utilisant des méthodes de calcul
spécifiques.
 On se limitera dans notre cours uniquement à la
formulation des problèmes d’affectation en termes de PL.

11
 Problème d’affectation
1. PL en nombres entiers
 Application :
 Nous avons 4 produits ( à ) à exécuter et nous
disposons de 4 employés (A, B, C et D) capables de les
faire. chacun étant payé 18 dinars l’heure.
 Le tableau ci-dessous résume les temps nécessaires à la
réalisation de chaque produit par chaque employé.
 Formuler le PL qui permet A B C D
de minimiser le salaire versé P1 8 6 2 4
aux employés. P2 6 7 11 10
P3 3 5 7 6
12
P4 5 10 12 9
 Problème d’affectation
1. PL en nombres entiers
 Soit
 Avec et


13
 Problème d’affectation
2. Méthode Hongroise
 L’algorithme d’affectation (appelé méthode Hongroise)

permet d’obtenir l’attribution optimale pour les problèmes

de minimisation (de coûts, de temps …).

 Pour appliquer l’algorithme, il faut s’assurer que:

nombre de colonnes = nombre de lignes.

Autrement, il faut rajouter des lignes ou des colonnes fictives

pour se ramener à une matrice carrée.

14
 Reprenons l’application précédente.
 Problème d’affectation
2. Méthode Hongroise
 Application :
 Nous avons 4 produits ( à ) à exécuter et nous
disposons de 4 employés (A, B, C et D) capables de les
faire. chacun étant payé 18 dinars l’heure.
 Le tableau ci-dessous résume les temps nécessaires à la
réalisation de chaque produit par chaque employé.
 Déterminer l’affectation A B C D
Optimale des employés. P1 8 6 2 4
P2 6 7 11 10
P3 3 5 7 6
15
P4 5 10 12 9
 Problème d’affectation
2. Méthode Hongroise
 Les étapes de l’algorithme sont comme suit:

1. De chaque rangée, soustraire la plus petite valeur

2. De chaque colonne, soustraire la plus petite valeur

3. Recouvrir toutes les valeurs nulles par un minimum de lignes

horizontales ou verticales.

• Si le nombre de lignes tracées est strictement inférieur au

nombre de colonnes, passer à l’étape 4.

• Si le nombre de lignes tracées est égal au nombre de

colonnes passer à l’étape 5.
16
 Problème d’affectation
2. Méthode Hongroise
4. Identifier la plus petite valeur parmi les valeurs non
recouvertes. Puis la soustraire de toutes les valeurs
non recouvertes et l’ajouter aux valeurs se trouvant
aux intersections des droites. Retourner à l’étape 3.

5. Affecter à chaque élément de la colonne des employés

un élément de la ligne des produits correspondant à
une valeur nulle. Commencer par les rangées et/ou les
colonnes ayant un seul zéro.
17
 Problème d’affectation
2. Méthode Hongroise
Minimum
Etape 1 des lignes Etape 2
8 6 2 4 2 6 4 0 2
6 7 11 10 6 0 1 5 4
3 5 7 6 3 0 2 4 3
5 10 12 9 5 0 5 7 4
Minimum des
0 1 0 2
colonnes
Etape 3 6 3 0 0
0 0 5 2
0 1 4 1
0 4 7 2
Moins que 4 lignes sont utilisées pour couvrir tous les zéros
 Problème d’affectation
2. Méthode Hongroise
Etape 4 Etape 5:

7 4 0 0 7 4 0 0
0 0 4 1 0 0 4 1
0 1 3 0 0 1 3 0
0 4 6 1 0 4 6 1
Ainsi:
C à P1 A B C D
B à P2
D à P3
P1 8 6 2 4
A à P4 P2 6 7 11 10
Temps total de réalisation des 4 produits :
P3 3 5 7 6
Coût de réalisation des 4 produits : P4 5 10 12 9
19
 Problème d’affectation
Application :
 Un directeur a 4 subordonnés et 3 projets à étudier.
 Chaque projet doit être affecté à un seul subordonné.
 Chaque subordonné est affecté à au plus un projet.
 Les estimations du directeur pour le temps nécessaire (par
jours) pour l’étude de chaque projet sont résumées dans le
tableau suivant: Projet 1 2 3
Sub
1 10 15 9
2 9 18 5
3 6 14 3
4 12 16 8

1. Formuler le problème qui minimise le temps d’études des

projets.
2. Trouver l’affectation optimale. 20
 Problème d’affectation
Application (correction) :
1. Soit
 Avec et

Chaque subordonné est affecté à au plus un projet.

Chaque projet est affecté à un seul subordonné :

21
 Problème d’affectation
Application (correction) :
2. Affectation optimale avec la méthode Hongroise:
Etape 1 Minimum Etape 2
des lignes
10 15 9 0 0 10 15 9 0
9 18 5 0 0 9 18 5 0
6 14 3 0 0 6 14 3 0
12 16 8 0 0 12 16 8 0
Minimum des
6 14 3 0
colonnes
Etape 3
4 1 6 0
3 4 2 0
0 0 0 0
6 2 5 0
22 Moins que 4 lignes sont utilisées pour couvrir tous les zéros
 Problème d’affectation
Application (correction) :
Etape 4 et retour à l’étape 3 Etape 4 et retour à l’étape 3:

3 0 5 0 2 0 4 0
2 3 1 0 1 3 0 0
0 0 0 1 0 1 0 2
5 1 4 0 4 1 3 0
Etape 5 :
Projet\ 1 2 3
Subordonné
2 0 4 0
1 10 15 9
1 3 0 0
2 9 18 5
0 1 0 2
3 6 14 3
4 1 3 0
4 12 16 8
23
23
Temps d’étude des projets : 15+5+6=26 jours
 Problème d’affectation
Application :
Cinq tâches ; A, B, C, D et E ; doivent être préparées ce soir par cinq
étudiants pour les soumettre le lendemain. Les temps requis, en heures,
pour chacun des étudiants en fonction des différentes tâches sont indiqués
ci-dessous.
Tâches Heure pour se
Étudiants
A B C D E coucher
Ali 2 5 1,5 3 5 22h
Aida 4 2 3 1 4 23h
Salah 1 3 4 2 1,5 21h
Hédi 1,5 2,5 3,5 3 3 22h
Hana 5 4 3,5 2 4 Minuit
Sachant que maintenant il est 19 h et que chaque étudiant doit respecter
l’heure à laquelle il doit dormir (indiquée ci-dessus)
1. Dites quelles sont les restrictions à prendre en considération dans
l’affectation de ces tâches.
2. Aidez les étudiants à trouver la meilleure affectation. 24
 Problème d’affectation
Application : (Correction)
1. Sachant qu’il est maintenant 19h et que chaque étudiant
doit respecter l'heure à laquelle il doit se coucher alors
les conditions suivantes doivent être respectées :
 Les tâches B et E ne doivent pas être affectées à Ali ;
 Les tâches B et C ne doivent pas être affectées à Salah ;
 La tâche C ne doit pas être affectée à Hédi.

25
 Problème d’affectation
Application : (Correction)
1 2
Tâches Tâches
A B C D E Min A B C D E
Ali 2 1,5 3 1,5 Ali 0,5 0 1,5
Aida 4 2 3 1 4 1

Étudiants
Aida 3 1 2 0 3
Étudiants

Salah 1 2 1,5 1 Salah 0 1 0,5

1, 2, Hédi 0 1 1,5 1,5
Hédi 3 3 1,5
5 5 Hana 3 2 1,5 0 2
Hana 5 4 3,5 2 4 2 Min 0 1 0 0 0,5
3
Tâches
A B C D E 4
Ali 0,5 0 1,5 Tâches
Étudiants

Aida 3 0 2 0 2,5 A B C D E
Salah 0 1 0 Ali 0,5 0 1,5
Hédi 0 0 1,5 1
Étudiants

Aida 3 0 2 0 2,5
Hana 3 1 1,5 0 1,5 Salah 0 1 0
Hédi 0 0 1,5 1
26 Hana 3 1 1,5 0 1,5
 Algorithme d’affectation (Correction)

 Ainsi la meilleure affectation serait:

 Ali pour la tâche C,
 Aida pour la tâche B,
 Salah pour la tâche E,
 Hédi pour la tâche A
 Hana pour la tâche D.

27
 Ordonnancement de plusieurs tâches sur une
machine
 Un certain nombre de règles de priorité peuvent être adoptées afin

de décider l’ordre de réalisation de différentes tâches.

 Les règles les plus utilisées sont:

 PEPS (premier entré, premier servi): les biens et services sont exécutés

selon l’ordre d’arrivée.

 TOM (temps opératoire minimum): la priorité est donnée au travail

dont le temps d’exécution est le plus court

 DP (date promise): la priorité est donnée au travail dont la date

promise au client est la plus proche.

28
Ordonnancement de plusieurs tâches sur une
machine
 Des indicateurs de performance permettent d’en mesurer
l’efficacité:
1. Temps (d’achèvement) moyen dans le système:

2. Utilisation effective du système :

3. Retard moyen par tâche:

29
Ordonnancement de plusieurs tâches sur une
machine
Exemple
Considérer les tâches suivantes et appliquer les règles PEPS,
TOM et DP. Puis comparer les différentes approches.

Tâches Temps d’exécution (ti) Échéance (date promise)

A 2 7
B 8 16
C 4 4
D 10 17
E 5 15
F 12 18

30
Ordonnancement de plusieurs tâches sur une
machine
Selon la méthode PEPS, l’ordre des tâches ne change pas A, B, C,
D, E et F

Tâches Début Durée Date d’achèvement Date Retard

Ai promise Ri
A 0 2 2 7 0
B 2 8 10 16 0
C 10 4 14 4 10
D 14 10 24 17 7
E 24 5 29 15 14
F 29 12 41 18 23
Total 41 120 54
31
Ordonnancement de plusieurs tâches sur une
machine
1. Temps d’achèvement moyen dans le système:

2. Utilisation effective du système :

3. Retard moyen par tâche:

32
Ordonnancement de plusieurs tâches sur une
machine
Selon la méthode TOM, l’ordre des tâches sera A, C, E, B, D et F

Tâches Début Durée Achèvement Date promise Retard

Ai Ri
A 0 2 2 7 0
C 2 4 6 4 2
E 6 5 11 15 0
B 11 8 19 16 3
D 19 10 29 17 12
F 29 12 41 18 23
Total 41 108 40

33
Ordonnancement de plusieurs tâches sur une
machine
1. Temps d’achèvement moyen dans le système:

2. Utilisation effective du système :

3. Retard moyen par tâche:

34
Ordonnancement de plusieurs tâches sur une
machine
Selon la méthode DP, l’ordre des tâches sera C, A, E, B, D et F

Tâches Début Durée Achèvement Date promise Retard

Ai Ri
C 0 4 4 4 0
A 4 2 6 7 0
E 6 5 11 15 0
B 11 8 19 16 3
D 19 10 29 17 12
F 29 12 41 18 23
Total 41 110 38

35
Ordonnancement de plusieurs tâches sur une
machine
1. Temps d’achèvement moyen dans le système:

2. Utilisation effective du système :

3. Retard moyen par tâche:

36
Ordonnancement de plusieurs tâches sur une
machine
Les résultats sont résumés dans le tableau suivant:

Temps moyen dans

Utilisation Retard moyen
le système
PEPS 20 34,17 9
TOM 18 37,96 6,67
DP 18,33 37,27 6,33

• TOM est la meilleure en terme des deux premiers indicateurs

• DP est la meilleure en terme de retard moyen

37
Ordonnancement de plusieurs tâches sur une
machine
 Aucune règle n’excelle sur tous les critères.
 TOM est la meilleure dans la minimisation du temps
d’achèvement moyen et en terme d’utilisation du système.
 Mais ! TOM programme les tâches avec le plus long temps
d’exécution en dernier ce qui peut engendrer des clients
insatisfaits.
 PEPS n’est pas particulièrement meilleure que les autres,
mais elle est perçue par les clients comme équitable.
 DP minimise le retard moyen
38
 Limites des règles de priorité
• L'ordonnancement est dynamique c’est pourquoi les règles
de priorité doivent être révisées afin de s'adapter aux
changements éventuels.
• Ces règles ne regardent pas au-delà des échéances: Par
exemple, Deux commandes peuvent avoir la même
échéance. Cependant une des deux commandes est lancée
juste pour alimenter le stock d’un distributeur, alors que
l’autre est conçue pour éviter l’arrêt de fabrication dans une
usine → Les règles appliquées ne permettent pas de choisir
la commande à traiter en urgence

39
Ordonnancement de plusieurs tâches sur 2
machines (2 centres de production)
 Chaque tâche nécessite pour son exécution le passage sur
deux machines : les machines 1 et 2. Soient ti1 et ti2 , les
temps d’exécution de la tâche i sur les machines 1 et 2
respectivement.
 Objectif: Minimisation du temps total d’exécution de tous les
travaux.
 Il faut distinguer deux cas de figures:
 Le cas où toutes les tâches sont à exécuter sur la machine 1
puis sur la machine 2;
 Le cas où toutes les tâches n’ont pas le même ordre de passage
sur les deux machines.
 Remarques: 2 tâches ne peuvent pas utiliser la même
machine au même moment
 Les tâches sont indépendantes.
40
Ordonnancement sur 2 machines
1. Même ordre de passage sur les machines
 Supposons qu’on a cinq tâches à exécuter successivement
sur les machines 1 puis 2. Les temps opératoires (en
secondes) sont repris au tableau suivant:

Tâches (i) A B C D E
Machine 1 5 3 8 10 7
Machine 2 2 6 4 7 12

 On remarque que durant l’exécution de la première tâche sur

la machine 1, la machine 2 est en repos. On a donc intérêt à
mettre en tête la tâche de temps ti1 le plus faible.
 De façon similaire, lors de l’exécution de la dernière tâche sur
la machine 2, la machine 1 est en repos. On a donc intérêt à
mettre à la fin la tâche de durée d’exécution ti2 minimale.
41
Ordonnancement sur 2 machines
1. Même ordre de passage sur les machines
En se basant sur ces deux observations, l’algorithme Johnson
(1954) détermine l’ordonnancement minimisant le temps total
d’exécution des tâches ainsi que le temps d’inactivité des
machines :
1. Énumérer toutes les tâches avec leurs temps d’exécution sur les deux
machines
2. Trouver la tâche dont le temps d’exécution est le plus faible possible. Si
ce temps correspond à la 1ère machine, planifier cette tâche en
premier; cependant, s’il correspond à la 2ème machine, la planifier en
dernier.
3. Éliminer de la liste toute tâche une fois planifiée.
4. S’il reste plus qu’une tâche à planifier, retourner à l’étapes 2.; s’il n’en
reste qu’une, sa position sera automatiquement imposée.
42
Ordonnancement sur 2 machines
1. Même ordre de passage sur les machines

Tâche Machine 1 Machine 2

A 5 2
B 3 6
B E D C A
C 8 4
D 10 7
E 7 12
Ordonnancement sur 2 machines
1. Même ordre de passage sur les machines
 Une fois la séquence est décidée, il reste à établir le
calendrier de production de cette séquence.
Généralement, on utilise le diagramme de Gantt.
Tâche Machine 1 Machine 2
A 5 2
B 3 6 B E D C A
C 8 4
D 10 7
E 7 12

Temps 0 3 10 20 28 33

M1 B E D C A

M2
44
Ordonnancement sur 2 machines
1. Même ordre de passage sur les machines

Tâche Machine 1 Machine 2

A 5 2
B 3 6
B E D C A
C 8 4
D 10 7
E 7 12
Temps 0 3 10 20 28 33

M1 B E D C A

M2 B E D C A

Temps 0 1 3 5 7 9 10 11 12 13 17 19 21 22 23 25 27 29 31 33 35

B E D C A
45
Ordonnancement sur 2 machines
2. Tâches ne s’effectuant pas dans le même ordre

 Exemple:

Tâches à effectuer sur 1 puis 2

Tâches (i) A B C D E F
Machine 1 50 80 10 50 30 70
Machine 2 30 60 30 0 0 0

Tâches à effectuer sur 2 puis 1

Tâches (i) G H I J K
Machine 2 90 20 10 40 10
Machine 1 70 30 100 0 0
46
Ordonnancement sur 2 machines
2. Tâches ne s’effectuant pas dans le même ordre
 L’ordonnancement qui minimise le temps total d’exécution des tâches sur les deux machines
est obtenu par l’algorithme de Jackson (1957) qui est une généralisation de l’algorithme de
Johnson. Il consiste tout simplement à :
1. Répartir l’ensemble des n tâches en 4 sous -ensembles
 L’ensemble 1 des tâches ne passant que sur 1 ; 1 = {D, E, F};
 l’ensemble 2 des tâches ne passant que sur 2 ; 2 = {J, K}
 L’ensemble 1,2 des tâches passant sur 1 puis 2 ; 1,2 = {A, B, C}
 L’ensemble 2,1 des tâches passant sur 2 puis 1 . 2,1 = {G, H, I}
2. Déterminer un ordonnancement optimal pour chaque sous-ensemble :
 Un ordonnancement arbitraire pour 1 (par exemple, TOM); E, D, F;
 Un ordonnancement arbitraire pour 2 (par exemple, TOM). K, J.
 L’ordonnancement optimal pour 1,2 par Johnson; C, B, A;
 L’ordonnancement optimal pour 2,1 par Johnson; I, H, G;
3. Combiner les résultats obtenus dans chaque sous ensemble de la façon suivante :
 Pour la machine 1 : la séquence optimale pour le sous-ensemble 1,2, puis les tâches de 1,
puis la séquence optimale du sous-ensemble 2,1: C, B, A, E, D, F, I, H, G.
 Pour la machine 2: la séquence optimale pour le sous-ensemble 2,1, puis les tâches de 2,
47 puis la séquence optimale du sous-ensemble 1,2: I, H, G, K, J, C, B, A.
Ordonnancement sur 2 machines
2. Tâches ne s’effectuant pas dans le même ordre
Tâches à effectuer sur les Tâches à effectuer sur les
machines 1 puis 2 machines 2 puis 1

Tâche Machine 1 Machine 2 Tâche Machine 2 Machine 1

A 50 30 G 90 70
B 80 60 H 20 30
C 10 30 I 10 100
D 50 0 J 40 0
E 30 0 K 10 0
F 70 0 M1: C, B, A, E, D, F, I, H, G

M2: I, H, G, K, J, C, B, A
Temps 0 10 90 140 170 220 290 390 420 490

M1 C B A E D F I H G

M2 I H G K J C B A 48
Ordonnancement de plusieurs tâches sur 3
machines (ordre identique de passage)
 L’algorithme de Johnson ne s’applique qu’en présence de deux
machines.
 Cependant, le cas de trois machines peut se ramener au cas de
deux machines. C’est la situation où le 2ème centre de
production (celui du milieu) est complètement dominé par
l’un ou l’autre des deux autres centres de production.
 On dit que la machine B est dominée par l’une des deux
autres machines (A ou C) si et seulement si le maximum du
temps d’exécution sur B est plus faible (ou égal) que le
minimum du temps d’exécution observé sur la machine
qui la domine.
49
Ordonnancement sur 3 machines (ordre
identique de passage)

 Si la règle de dominance est vérifiée, on reformule alors le

problème en un problème fictif à deux centres de production
(virtuels):

 Le premier regroupe les machines A et B avec un temps

opératoire ( 𝑖𝐴𝐵 𝑖𝐴 𝑖𝐵 )

 Le second regroupe les machines B et C avec un temps

opératoire ( 𝑖𝐵𝐶 𝑖𝐵 𝑖𝐶 )

50
Ordonnancement sur 3 machines (ordre
identique de passage)

 Planifier ces tâches en utilisant l’algorithme de

Johnson, puis tracer le diagramme de Gantt
correspondant

Tâche 𝒊𝑨 𝒊𝑩 𝒊𝑪

1 7 1 6
2 4 3 2
3 3 2 4
4 8 2 1
5 5 1 3

51
Ordonnancement sur 3 machines (ordre
identique de passage)
 Il est facile de vérifier que la machine B est dominée
par la machine A.
 Le maximum du temps d’exécution sur B = 3
 Le minimum du temps d’exécution observé sur A =3

Tâche 𝒊𝑨 𝒊𝑩 𝒊𝑪 Tâche 𝑖𝐴𝐵 𝑖𝐵𝐶

1 7 1 6 1 8 7
2 4 3 2 2 7 5
3 1 2 5 4
3 3 2 4 3 5 6
4 8 2 1 4 10 3
5 5 1 3 5 6 4
52
Ordonnancement sur 3 machines (ordre
identique de passage)
 Remarques:
 Pour trouver la durée totale d’exécution, on
représente le Diagramme de Gantt avec un axe
contenant les 3 machines: A , B et C.
 Dans le cas où la machine centrale n’est pas
dominée par la première où la troisième machine,
d’autres méthodes permettent de résoudre cette
difficulté, telle que la programmation en nombre
entiers (« Branch and Bound »)...

53
Ordonnancement de plusieurs tâches sur m
machines (ordre identique de passage)
Lorsque l’ordre de passage des tâches est identique et que
le nombre de centres de production ne dépasse pas
quelques dizaines, une solution souvent proche de la
solution optimale peut être trouvée en utilisant l’algorithme
de Johnson sur des groupements de centres de production
successifs, connu sous le nom de l’ Algorithme CDS
(Campbell, Dudek et Smith).

54
Ordonnancement de plusieurs tâches sur m
machines (ordre identique de passage)
 Prenons le cas de 4 centres de productions notés A, B, C et D.
1. Résoudre les 3 problèmes suivants par l’algorithme de Johnson
(ordonnancement optimal) :
 La première et la dernière machine : (A) –(D)
 Les deux premières et les deux dernières machines : (A, B) – (C, D)
 Les trois premières et les trois dernières machines : (A, B, C) – (B, C, D)
2. Déterminer le temps total d’exécution des tâches pour chaque
problème
3. Choisir le meilleur (le plus faible) des temps totaux d’exécution
des tâches ainsi trouvés (T*=min (T1 ;T2 ;T3)). L’ordonnancement
optimal correspond au temps total le plus faible.
 Remarque : si nous avons deux ordonnancements qui donnent le
même temps d’exécution, le choix est arbitraire.
55
Ordonnancement de plusieurs tâches sur m
machines (ordre identique de passage)
 Illustrons ceci sur l’exemple suivant :

Tâches
1 50 43 15 4
2 89 99 95 77
3 7 47 20 98
4 8 64 12 94
5 61 19 65 14
6 1 80 66 78
56
Ordonnancement de plusieurs tâches sur m
machines (ordre identique de passage)
 Le premier problème fictif consiste à ne
considérer que les machines A et D.
 Il conduit à l’ordonnancement suivant
par la méthode de Johnson : 6, 3, 4, 2, 5, Tâches
1 1 50 4
 Avec un temps d’exécution total de 2 89 77
512 heures. 3 7 98
4 8 94
5 61 14

57 6 1 78
Ordonnancement de plusieurs tâches sur m
machines (ordre identique de passage)
 Le deuxième problème fictif
Tâches tiA+tiB tiC+tiD
consiste à considérer les
machines A+B et C+D comme 1 50+43=93 15+4=19
illustré au tableau suivant : 2 89+99=188 95+77=172
3 7+47=54 20+98=118
 Il conduit à l’ordonnancement 4 8+64=72 12+94=106
suivant par la méthode de 5 61+19=80 65+14=79
Johnson : :3, 4, 6, 2, 5, 1 qui 6 1+80=81 66+78=144
donne un temps d’exécution
total de 487 heures.
58
Ordonnancement de plusieurs tâches sur m
machines (ordre identique de passage)
 Le troisième et dernier problème fictif consiste à considérer
A+B+C et B+C+D.
 Il donne la même solution que le problème fictif 2 .
 On a donc trouvé une solution de temps égal à 487 heures
alors que la solution optimale (qui peut être calculée en
faisant une énumération explicite de tous les
ordonnancements possibles) conduit à un temps de 485
heures.
 Remarque : si nous avons deux ordonnancements qui
donnent le même temps d’exécution, le choix est arbitraire.

59
 Application
 Une entreprise de pose de chape et de carrelage a
enregistré pour le mois prochain les 5 commandes
suivantes (la durée, en jours, suppose qu’une équipe
entière soit affectée à une tâche) :
Tâche C1 C2 C3 C4 C5
Chape 2 3 10 1 2,5
Carrelage 5 4 12 3 2
 Il est nécessaire d’avoir 2 jours de séchage entre la fin
de la chape et le début du carrelage. Le séchage est
réalisé avec une machine. L’entreprise ne dispose que
d’une seule machine de séchage.
60
 Application
1. Si l’entreprise dispose d’une équipe de chapistes et d’une
équipe de carreleurs, dans quel ordre doit-elle effectuer
ces contrats pour réaliser les 5 chantiers en un minimum
de temps ?

2. Représentez graphiquement votre solution au moyen

d’un diagramme de Gantt.

3. Combien de jours sont nécessaires pour mener à bien les

cinq chantiers ?
61
 Application (Correction)
1.
Tâche i C1 C2 C3 C4 C5
Chape 2 3 10 1 2,5 C4 C1 C2 C3 C5
Carrelag
e 5 4 12 3 2

2. 2 jours de séchage entre la fin de la chape et le début du

carrelage.
Chape C4 C1 C2 C3 C5 Z

Séchage Z C4 C1 Z C2 Z C3 Z C5 Z

Carrelage Z C4 C1 C2 Z C3 C5
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

3. 32 jours
Autres Applications : (Facultatif)

 Exercice : On a 5 tâches à effectuer sur M1 puis sur M2

(temps en mn)
Tâche (i) A B C D E
M1 7 7 13 9 5
M2 8 4 7 13 6

1. Déterminer l’ordonnancement optimal de façon à

minimiser le temps total d’exécution des tâches.
E/A/D/C/B
2. Tracer le diagramme de Gantt et déterminer le temps
total d’exécution. T=45 min

63
Autres Applications : (Facultatif)

 Exercice : Une entreprise reçoit un certain nombre de

commandes. Chaque commande nécessite le passage sur deux
postes P1 et/ou P2. Les temps des opérations pour les différentes
commandes sont donnés dans le tableau ci-dessous en secondes.

Tâches à effectuer sur P1 puis P2 Tâches à effectuer sur P2 puis P1

Tâches (i) AB C DE F Tâches (i) G H I J K
Machine 1 7 10 12 7 5 9 Machine 2 11 4 3 6 3
Machine 2 5 8 5 0 0 0 Machine 1 9 5 12 0 0

1. Déterminer l’ordonnancement optimal de façon à minimiser le

temps total d’exécution des tâches.
2. Tracer le diagramme de Gantt et déterminer le temps total
d’exécution.
64
Autres Applications : (Facultatif)

Solution :
Ordonnancement optimal:
Machine P1 : B,A,C,D,E,F,I,H,G
Machine P2 : I,H,G,K,J,A,B,C Temps (s)

B A C E D F I H G
P1
10 17 29 34 41 50 62 67 76

I H G K J B A C Z
P2
3 7 18 2127 35 40 45

T = 76 s
Un ordonnancement avec B/C/A donne aussi le même résultat.
65
Autres Applications : (Facultatif)

 Exercice : on a 6 tâches à effectuer sur trois centres

de production, ordre identique de passage

Tâches 1 2 3 4 5 6
C1 9 4 6 5 7 4
C2 3 3 4 4 3 6
C3 7 9 6 8 7 8

1. Déterminer l’ordonnancement optimal.

2. Déterminer le temps total d’exécution.

66
Autres Applications : (Facultatif)

1. Min ti c3 ≥ Max ti c2 donc : c1+c2 et c2+c3

Tâches 1 2 3 4 5 6
C1 + C2 12 7 10 9 10 10
C2 + C3 10 12 10 12 10 14

Ordonnancement 2 4 3 5 6 1
Ou bien 2 4 3 6 5 1
Ou bien 2 4 3 6 1 5
Ou bien 2 4 5 6 1 3
… … …. ….. …... …. ….

Plusieurs ordonnancements qui donnent le même

67 temps: T=52