Ce cas est parmi une série des Exercices Corrigés études de Cas Gestion de Production.

L’ordonnancement à plusieurs machines est une méthode utilisée pour planifier et organiser les tâches ou les opérations sur plusieurs machines dans un atelier de production. Il existe plusieurs méthodes pour gérer cette complexité en fonction du nombre de machines, de l’ordre des opérations, des priorités des tâches et des objectifs de performance (réduction des temps d’attente, minimisation des retards, maximisation de l’utilisation des machines, etc.).

Voici les principales caractéristiques et méthodes d’ordonnancement à plusieurs machines :

1. Types de Problèmes d’Ordonnancement à Plusieurs Machines

Les problèmes d’ordonnancement à plusieurs machines peuvent être classés en plusieurs catégories, en fonction de la configuration des machines et des opérations :

• Flow Shop (Atelier à flux) : Toutes les tâches passent par les mêmes machines dans le même ordre.
• Job Shop (Atelier à tâches) : Chaque tâche peut avoir un chemin différent à travers les machines. L’ordre dans lequel une tâche passe sur les machines peut varier en fonction des exigences.
• Open Shop (Atelier ouvert) : Les tâches doivent être exécutées sur plusieurs machines, mais l’ordre n’est pas prédéfini.

2. Exemple de Méthode pour un Ordonnancement à Deux Machines : Méthode de Johnson

La méthode de Johnson est une technique bien connue pour ordonnancer les tâches sur deux machines dans un atelier à flux continu. Elle est utilisée lorsque chaque tâche doit passer sur deux machines dans le même ordre (Machine 1 puis Machine 2).

Étapes de la Méthode de Johnson :

1. Identifier les temps de traitement pour chaque tâche sur les deux machines.
2. Rechercher la plus petite durée parmi toutes les tâches, sur les deux machines :

• Si cette plus petite durée concerne la Machine 1, placez cette tâche au début de la séquence.
• Si cette plus petite durée concerne la Machine 2, placez cette tâche à la fin de la séquence.

1. Répéter cette procédure en ignorant les tâches déjà ordonnancées, jusqu’à ce que toutes les tâches soient programmées.
2. Calculez le makespan (le temps total d’exécution) une fois toutes les tâches placées.

Exemple :

Considérons cinq tâches avec les temps de traitement suivants sur deux machines :

Tâche	Machine 1	Machine 2
T1	4	6
T2	5	3
T3	3	7
T4	6	5
T5	2	4

Étapes d’ordonnancement avec la méthode de Johnson :

Rechercher la plus petite durée :

• La plus petite durée est 2 (Machine 1 pour la tâche T5). On place T5 au début de la séquence.

Rechercher la plus petite durée restante :

• La plus petite durée est 3 (Machine 2 pour la tâche T2). On place T2 à la fin de la séquence.

Rechercher la plus petite durée restante :

• La plus petite durée est 3 (Machine 1 pour la tâche T3). On place T3 au début (après T5).

Rechercher la plus petite durée restante :

• La plus petite durée est 4 (Machine 1 pour la tâche T1). On place T1 au début (après T3).

Il ne reste que la tâche T4. Elle est placée dans l’emplacement restant.

Ordonnancement final :
T5 – T3 – T1 – T4 – T2

3. Ordonnancement dans un Job Shop

Dans un Job Shop, chaque tâche peut suivre un chemin différent à travers les machines. L’ordonnancement devient plus complexe et nécessite l’utilisation de techniques plus avancées. Deux approches courantes pour résoudre les problèmes d’ordonnancement dans les Job Shops sont :

a. Heuristiques de Priorité

Ces méthodes attribuent une priorité aux tâches à chaque machine, en fonction de critères comme :

• FIFO (First In, First Out) : La première tâche à arriver est la première à être traitée.
• SPT (Shortest Processing Time) : La tâche avec le plus court temps de traitement est traitée en premier.
• EDD (Earliest Due Date) : La tâche avec la date limite la plus proche est traitée en premier.
• CR (Critical Ratio) : Ratio de la date limite par rapport au temps restant avant l’échéance.

b. Méthodes de Graphe

Les méthodes de graphe représentent les tâches sous forme de réseaux avec des arcs reliant les différentes machines. Chaque nœud représente une tâche, et chaque arc indique l’ordre dans lequel les tâches doivent être effectuées. Des algorithmes d’optimisation, comme l’algorithme de Branch and Bound ou le Simplex, peuvent être utilisés pour trouver le meilleur ordonnancement.

Exemple de Job Shop :

Tâche	Machine 1 (Temps)	Machine 2 (Temps)	Machine 3 (Temps)
T1	2	3	4
T2	4	1	5
T3	3	2	6

Chaque tâche suit un chemin différent à travers les machines. Un algorithme de Branch and Bound pourrait être utilisé pour minimiser le temps total d’achèvement.

4. Ordonnancement en Open Shop

Dans un Open Shop, les tâches peuvent être exécutées sur plusieurs machines dans n’importe quel ordre. L’objectif est généralement de trouver la séquence qui minimise le makespan (temps total de traitement) ou maximise l’utilisation des machines.

Exemple :

Considérons trois tâches qui doivent être traitées sur deux machines, sans ordre imposé.

Tâche	Machine 1 (Temps)	Machine 2 (Temps)
T1	2	3
T2	4	2
T3	3	5

Dans cet exemple, les tâches peuvent être affectées aux machines dans n’importe quel ordre. L’ordonnancement dépend de la disponibilité des machines. Par exemple, T1 pourrait commencer sur Machine 1, tandis que T2 pourrait être traitée sur Machine 2.

5. Objectifs et Critères d’Ordonnancement

Les objectifs de l’ordonnancement à plusieurs machines varient en fonction des besoins de l’entreprise. Voici quelques critères courants :

• Minimisation du makespan : Réduire le temps total d’exécution des tâches.
• Minimisation des retards : Réduire le nombre ou la durée des retards par rapport aux échéances.
• Maximisation de l’utilisation des machines : Minimiser les temps d’inactivité des machines.
• Réduction des en-cours (WIP – Work in Process) : Diminuer le nombre de tâches en attente de traitement dans l’atelier.

👉 L’ordonnancement à plusieurs machines est un outil clé pour optimiser les flux de production dans un atelier. Il s’agit d’une tâche complexe nécessitant des méthodes spécifiques en fonction du type d’atelier (Flow Shop, Job Shop ou Open Shop) et des objectifs de performance. Des techniques comme la méthode de Johnson, les heuristiques de priorité, et des approches de graphe sont couramment utilisées pour ordonnancer les tâches de manière optimale, afin de minimiser les temps d’attente et maximiser l’efficacité des machines.

Voici une série d’exercices corrigés et étude de cas gestion de production sur l’ordonnancement à plusieurs machines. Ces exercices vous permettront de comprendre comment planifier des tâches à travers plusieurs machines en minimisant les temps d’attente et en optimisant l’efficacité globale du système de production.

---

Exercice 1 : Ordonnancement à Deux Machines avec la Méthode de Johnson

Énoncé

Une entreprise doit réaliser cinq tâches sur deux machines (Machine 1 et Machine 2). Chaque tâche doit d’abord être traitée par Machine 1, puis par Machine 2. Les temps de traitement des tâches sur chaque machine sont donnés dans le tableau suivant :

Tâche	Machine 1 (h)	Machine 2 (h)
T1	4	3
T2	2	5
T3	7	6
T4	6	2
T5	5	4

Objectif : Utilisez la méthode de Johnson pour minimiser le temps total de traitement (makespan).

---

Solution

Étape 1 : Identifier les plus petites durées de traitement.

• La plus petite durée dans le tableau est 2 heures pour T2 sur Machine 1 et T4 sur Machine 2.

Étape 2 : Placer les tâches dans la séquence.

• Placez T2 (Machine 1) en première position, car elle a la plus petite durée.
• Placez T4 (Machine 2) en dernière position.

Étape 3 : Rechercher la prochaine plus petite durée.

• La prochaine plus petite durée est 3 heures pour T1 (Machine 2), donc placez T1 juste avant T4.
• Ensuite, la prochaine plus petite durée est 4 heures pour T5 (Machine 1), donc placez T5 après T2.

Étape 4 : Placer la dernière tâche.

• Il ne reste que T3, donc elle est placée dans l’emplacement restant.

Ordonnancement final :
T2 – T5 – T3 – T1 – T4

Étape 5 : Calculer le makespan (temps total).

Tâche	Machine 1 (fin)	Machine 2 (début)	Machine 2 (fin)
T2	2	2	7
T5	7	7	11
T3	14	14	20
T1	18	20	23
T4	24	23	25

Le makespan (temps total d’exécution) est de 25 heures.

---

Exercice 2 : Ordonnancement à Trois Machines

Énoncé

Un atelier doit effectuer quatre tâches, qui passent chacune par trois machines successivement. Les temps de traitement pour chaque tâche et chaque machine sont donnés dans le tableau suivant :

Tâche	Machine 1 (h)	Machine 2 (h)	Machine 3 (h)
T1	3	4	2
T2	2	5	3
T3	4	3	5
T4	5	2	4

Objectif : Ordonnancez les tâches de manière à minimiser le temps total de traitement (makespan).

---

Solution

Étape 1 : Appliquer la méthode de Johnson pour trois machines.

• Pour utiliser la méthode de Johnson, nous devons d’abord transformer ce problème à trois machines en un problème à deux machines :
  • Machine A (combinaison de Machine 1 et Machine 2) = Somme des temps de traitement pour Machine 1 et Machine 2.
  • Machine B (combinaison de Machine 2 et Machine 3) = Somme des temps de traitement pour Machine 2 et Machine 3.

Tâche	Machine A (M1 + M2)	Machine B (M2 + M3)
T1	3 + 4 = 7	4 + 2 = 6
T2	2 + 5 = 7	5 + 3 = 8
T3	4 + 3 = 7	3 + 5 = 8
T4	5 + 2 = 7	2 + 4 = 6

série des Exercices Corrigés études de Cas Gestion de Production – Ordonnancement à Plusieurs Machines

Étape 2 : Appliquer la méthode de Johnson pour ordonnancer les tâches.

• Pour Machine A, la plus petite durée est 7 (égal pour toutes les tâches). Pour Machine B, la plus petite durée est 6 (pour T1 et T4).
• Nous allons placer T1 et T4 aux deux extrémités et laisser les autres tâches au milieu.

Ordonnancement final :
T1 – T2 – T3 – T4

Étape 3 : Calculer le temps total (makespan).

Tâche	Machine 1 (fin)	Machine 2 (début)	Machine 2 (fin)	Machine 3 (début)	Machine 3 (fin)
T1	3	3	7	7	9
T2	5	7	12	12	15
T3	9	12	15	15	20
T4	14	14	16	16	20

Le makespan (temps total d’exécution) est de 20 heures.

---

Exercice 3 : Ordonnancement avec Goulot d’Étranglement

Énoncé

Dans un atelier de production, trois machines (Machine 1, Machine 2, et Machine 3) sont disponibles pour traiter six tâches. Les temps de traitement pour chaque tâche sur chaque machine sont donnés dans le tableau ci-dessous. Cependant, Machine 2 a été identifiée comme un goulot d’étranglement en raison de ses temps de traitement plus longs.

Tâche	Machine 1 (h)	Machine 2 (h)	Machine 3 (h)
T1	2	6	3
T2	1	8	2
T3	3	7	4
T4	4	9	5
T5	2	5	3
T6	3	6	4

Objectif : Ordonnancez les tâches de manière à minimiser les temps d’attente sur Machine 2, en priorisant les tâches ayant le plus court temps de traitement sur cette machine. Utilisez la méthode SPT (Shortest Processing Time) pour Machine 2.

Solution

Étape 1 : Identifier les priorités pour Machine 2 :

• Nous allons ordonnancer les tâches en fonction de leurs temps de traitement sur Machine 2. Le principe de la méthode SPT est de commencer par les tâches ayant le plus court temps de traitement :
  • T5 (5 heures)
  • T1 et T6 (6 heures)
  • T3 (7 heures)
  • T2 (8 heures)
  • T4 (9 heures)

Étape 2 : Appliquer l’ordonnancement en suivant la règle SPT :

• Les tâches sont ordonnancées dans cet ordre : T5 – T1 – T6 – T3 – T2 – T4

Étape 3 : Calculer l’ordonnancement des tâches :

Tâche	Machine 1 (fin)	Machine 2 (début)	Machine 2 (fin)	Machine 3 (début)	Machine 3 (fin)
T5	2	2	7	7	10
T1	4	7	13	13	16
T6	7	13	19	19	23
T3	10	19	26	26	30
T2	11	26	34	34	36
T4	15	34	43	43	48

série des Exercices Corrigés études de Cas Gestion de Production

Calculs détaillés

• Machine 1 :
• T5 démarre à 0, finit à 2.
• T1 démarre à 2, finit à 4.
• T6 démarre à 4, finit à 7.
• T3 démarre à 7, finit à 10.
• T2 démarre à 10, finit à 11.
• T4 démarre à 11, finit à 15.
• Machine 2 (goulot d’étranglement) :
• T5 démarre à 2 (quand T5 est terminé sur Machine 1), finit à 7.
• T1 démarre à 7, finit à 13.
• T6 démarre à 13, finit à 19.
• T3 démarre à 19, finit à 26.
• T2 démarre à 26, finit à 34.
• T4 démarre à 34, finit à 43.
• Machine 3 :
• T5 démarre à 7 (quand T5 est terminé sur Machine 2), finit à 10.
• T1 démarre à 13, finit à 16.
• T6 démarre à 19, finit à 23.
• T3 démarre à 26, finit à 30.
• T2 démarre à 34, finit à 36.
• T4 démarre à 43, finit à 48.

Le makespan (temps total pour terminer toutes les tâches) est de 48 heures.

---

Schéma de l’Ordonnancement

Voici un schéma type représentant l’ordonnancement des tâches sur les trois machines :

Machine 1:  [T5: 0-2]  [T1: 2-4]  [T6: 4-7]  [T3: 7-10]  [T2: 10-11]  [T4: 11-15]
Machine 2:           [T5: 2-7]  [T1: 7-13]  [T6: 13-19]  [T3: 19-26]  [T2: 26-34]  [T4: 34-43]
Machine 3:                     [T5: 7-10]  [T1: 13-16]  [T6: 19-23]  [T3: 26-30]  [T2: 34-36]  [T4: 43-48]

Le goulot d’étranglement est situé sur Machine 2. En utilisant la règle SPT (Shortest Processing Time) pour prioriser les tâches à court temps de traitement sur cette machine, l’atelier optimise le temps total d’exécution (makespan), qui est ici de 48 heures.