L’Ordonnancement

EL Hassani Ibtissam
Introduction à l’ordonnancement
Lien entre moyen terme et court terme :

À la fin de la méthode de MRP, on dispose d’un échéancier en besoin net

de familles de produits ou composants. Les limites de capacité prise
éventuellement en compte concernant les familles de machines ou de
centres de production et les informations sont les volumes à produire par
période de moyen terme (1 mois, 1 semaine).
Au niveau des CT : Organiser des fabrications pour la première période .
du MT, en considérant cette fois-ci les donnée détaillées, c-à-d qu’on
s’interresse au produits à fabriquer réellement et aux machines qui
effectueront effectivement les opérations.
1. Caractéristiques de
l’ordonnancement des ateliers
1.Loi d’arrivée des tâches (opérations) (aspect statique ou dynamiques);
2.Nombre et la variétés des machines dans l’atelier (n taches, m machines
 ordonnancements possibles ?);
3.Nombre d’ouvriers dans l’ateliers (machines et ouvriers détermine la
capacité du système);
4.Définition des flux (ordre des opérations dans une séquence donnée)
5.Evaluation des règles d’ordonnancement.

Les critères 1. et 3. visent à satisfaire le client, 2., 4., 5. et 6. visent une

haute efficacité des installation.
2. Objectifs de gestion d’Atelier

1. Rencontrer les dates promise ;

2. Minimiser les en-cours ;
3. Minimiser le temps moyen de passage à travers le système (atelier) ;
4. Minimiser les temps d’arrêts ;
5. Réduire les temps de mise en place ;
6. Minimiser les coûts (production est M.O) …
3. Terminologie générale
• Atelier séquentiel (Ateliers à cheminement unique) flowshop : les
taches doivent s’executer sur les mêmes machines dans le même
ordre et une seule fois.
3. Terminologie générale
• Atelier générale (Ateliers à cheminements multiples) jobshop : aucune
séquence d’opération n’est fixe, aucune durée d’opération n’est fixe, et
une pièce peut circuler plusieurs fois sur la même machine pour des
taches différentes.
3. Terminologie générale
• Traitement séquentiel : machines différentes, caractéristiques
différentes.
• Traitement parallèle : une tâche donnée peut être exécuté sur plus d’un
poste. Plusieurs postes ayant des capacités identiques sont
disponibles.
3. Terminologie générale
• Temps de circulation (flowtime) : c’est le temps qu’une pièce donnée
passe par le système depuis son démarrage sur la première machine
jusqu’à sa sortie du système.
• Temps moyen de traitement : Il est calculé comme étant la moyenne
arithmétique des temps de circulation pour n jobs.
• Temps global (makespan): c’est le temps nécessaire pour compléter
l’ensemble de toutes les n tâches.
• Retard (tardiness): La différence positive entre la date promise d’une
tâche et la date des fin des opérations.
• Avance (earliness) : La différence négative entre la date promise d’une
tâche et la date des fin des opérations.
• Délai (lateness) : La différence négative entre la date promise d’une
tâche et la date des fin des opérations.
4. Les règles d’ordonnancement
Ceux sont des règles comme sur les tâches d’ordonnancement :
• Premier arrivé premier servi (PAPS = FIFO) : les tâches sont traitées
dans l’ordre d’arrivée sans aucune exeption.
• Temps de traitement le plus court (shortest processing time) : les
tâches sont effectuée selon leurs durées en débutant par la plus
courte.
• La date promise la plus tôt (eurliest due date) : les tâches sont
effectuées dans l’ordre promis de livraison en débutant par la plus tôt à
livrer.
• Ratio critique (critical ratio) : on calcule le ratio du temps de traitement
d’une tâche sur le temps restant avant la date promise. Les tâches
seront effectuées dans l’ordre décroissant du ratio.
• …
Exemple
Exemple
Exemple
• Un centre d’usinage a 5 tâches à réaliser, décider l’heuristique optimal
en calculant le retard moyen, le nombre de tâches en retard et le temps
moyen dans le système.

Tâche Temps de Date promise

traitement
1 11 61
2 29 45
3 31 31
4 1 33
5 2 32
Exemple : PAPS

Tâche Temps de Date Date de fin Df-Dp

traitement promise
1 11 61 11 -50
2 29 45 40 -5
3 31 31 71 40
4 1 33 72 39
5 2 32 74 42

Retard moyen : (40+39+42)/5 = 24.2

Temps moyen dans le système : (11+40+71+72+74)/5 = 53.6
Nombre de tache en retard : 3
Exemple : Temps de traitement le plus
court (shortest processing time)

Tâche Temps de Date Date de fin Df-Dp

traitement promise
4 1 33 1 -32
5 2 32 3 -29
1 11 61 14 -47
2 29 45 43 -2
3 31 31 74 43

Retard moyen : 43/5= 8.6

Temps moyen dans le système : (1+3+14+43+74)/5 = 27
Nombre de tache en retard : 1
Exemple : La date promise la plus tôt
(eurliest due date)

Tâche Temps de Date Date de fin Df-Dp

traitement promise
3 31 31 31 0
5 2 32 33 1
4 1 33 34 1
2 29 45 63 18
1 11 61 74 13

Retard moyen (1+1+18+13)/5= 6.6

Temps moyen dans le système (31+33+34+63+74)/5= 47
Nombre de tache en retard :4
 Exemple : Ratio critique
Nous sommes à t= 0 :
Tâche Temps de Date promise Tps restant Ratio critique
traitement =
1 11 61 61 – 0 = 61 11/61=0.18
2 29 45 45 29/45 =0.64
3 31 31 31 31/31 =1
4 1 33 33 1/33 =0.03
5 2 32 32 2/32 =0.0625
Itération t = t+ T4
Tâche Temps de Date promise Tps restant Ratio critique
traitement =
1 11 61 61 – 1 = 60 11/60=0.183
2 29 45 44 29/44 =0.659
3 31 31 30 31/30 =1.03
5 2 32 31 2/31 = 0.0645
Exemple : Ratio critique

Tâche Temps de Date Date de fin Df-Dp

traitement promise
4 1 33 1 -32
5 2 32 3 -29
1 11 61 14 -47
2 29 45 43 -2
3 31 31 74 43

Retard moyen : 43/5= 8.6

Temps moyen dans le système : (1+3+14+43+74)/5 = 27
Nombre de tache en retard : 1
Exemple

Méthode Critère 1 Critère 2 Critère 3

(RM) (TMS) (Nb R)
A. Premier arrivé premier servi 24.2 53.6 3
B. Temps de traitement le plus 27 8.6 1
court
C. La date promise la plus tôt 47 6.6 4
D. Ratio critique 27 8.6 1
A - (B,D) - C C - (B,D) - A (B,D) - A - C
5. Qu’est ce que l’ordonnancement ?
Ordonnancement : la détermination de l’ordre de traitement des
commandes en indiquant pour chaque tâche à exécuter où et à quel
moment elle sera effectuée.
Le jalonnement: détermination de la séquence selon laquelle les tâches
seront effectuées par un poste de travail.
Etapes :
1. L’affectation: distribution des tâches aux postes de travail
2. Détermination d’un ordre de passage: détermination de la séquence
de traitement des commandes à chaque poste de travail: jalonnement
3. Calendrier de fabrication: date et heure de lancement des opérations
à chaque poste de travail
4. Lancement: démarrage des opérations selon le calendrier.
5. Suivi: supervision de l’exécution et vérification de l’adéquation avec la
planification
6.Relance: ajustements en fonction des imprévus.
6. Généralisation : Ordonnancement sur
une seule machine
• La règle de TOM
Aj : le temps d’achèvement de la tâche programmée à la position j.
Ti: le temps opératoire de la tâche i

• Aj= Ʃ Ti = T1+T2+…+Tj
• A = moy (Aj) = 1/n . Ʃ Aj = 1/n . Ʃ (n+1-j)Tj

• Il s’agit d’une somme pondérée des temps opératoires. Chaque temps

opératoire étant pondéré par rapport à un facteur de temps plus grand
qui se trouve exécuté plus tôt dans l’ordo. La règle qui minimise le
temps d’achèvement moyen est celle du Temps Opératoire Minimum
.
• Il s’agit de ‘exécuter les tâches par ordre croissant de TO.
7. Ordonnancement sur deux machines
• Chaque tâche nécessite pour son exécution le passage sur deux
machine A et B. Soit tiA et tiB les temps d’exécution de la tâche i sur la
machine A et B respectivement. On va utiliser comme critère l’ordo la
minimisation du temps total d’exécution des tâches sur les deux
machines.

• 1/ Cas où toutes les tâches sont à exécuter sur A puis sur B.

• 2/ Le cas où toutes les tâches n’ont pas le même ordre de passage sur
les deux machines.
7.1 Cas 1 - toutes les tâches sont
exécutées sur A puis B

Algorithme de Johnson
• 1.Rechercher la tâche i de temps d’exécution tij minimal
• 2. Si j = A placer cette tâche à la première place disponible
Si j = B placer cette tâche à la dernière place disponible
• 3. Supprimer la tâche i des tâches encore à programmer.
Retour en 1.

Exemple
7.1 Cas 2 - les tâches ne s’exécutent
pas dans le même ordre (openshop)
Algorithme de Jackson (1957)
1. Faire une partition de l’ensemble des n tâches en :
• L’ensemble A des tâches ne nécessitant que le passage sur la
machine A
• L’ensemble B des tâches ne nécessitant que le passage sur la
machine B
• L’ensemble AB des tâches nécessitant le passage sur A puis B
• L’ensemble BA des tâches nécessitant le passage sur B puis A
2. Calculer un ordo pour chaque sous ensemble AB, A , BA,B
AB et BA par l’algorithme de Jonhson, A et B par un ordonnancement (par
exemple TOM)
3. Pour la machine A : AB, A, BA
Pour la machine B : BA, B, AB
8. Ordonnancement sur 3 machines
• A B  C
L’algorithme de Johnson ne s’applique que dans le cas de deux machines.
Cependant, le cas de 3 machines peut se ramener au cas de deux
machines si la machine B est complètement dominée par la machine A ou
C, c-à-d c’est où on trouve :
– min tiA >= max tiB
– Min tiC >= max tiB
On peut reformuler le problème en un problème à 2 machines (AB) et
(BC), et on applique l’algorithme de Johnson.
Tâche 1 2 3 4 5 6 7
• Exemple :
Assemblage 20 12 19 16 14 12 17
Inspection 4 1 9 12 5 7 8
Expédition 7 11 4 18 18 3 6
• 5–4–7–3–2–1–6
Algorithme de tâche promise la plus tôt
amélioré
Le même algorithme de la tâche promise sauf que :
• si la tâche n'est pas en retard je l'affecte
• et si la tâche est en retad je la laisse en dernier
Exemple :
Tâche Temps de Date Date de fin Df-Dp
traitement promise
3 31 31 31 0
5 2 32 33 1
4 1 33 34 1
2 29 45 63 18
1 11 61 74 13
3-4-1-5-2
L'objectif ici est de minimiser le nombre des tâches en retard.
Exercice
Soit le produit A constitué de (1X, 3Y) l'objectif est de planifier les 3OF :
– OF1 : 150A dans une semaine
– OF2 : 1500Y (dont 450 sont nécessaires pour l'OF1)
– OF3 : 500X (dont 150 sont nécessaires pour l'OF2)
• Les ressources
– La ressource "MONT" pour obtenir le produit fini A, Capacité = 120h/semaine. (3 équipes)
– La ressource "INJE" pour fabriquer X et Y de capacité 40h/semaine.
– La ressource "TAMP" pour fabriquer X et Y de capacité 40h/semaine.
• Gamme de fabrication
Produit Phase Ressources Tps de Tps unitaire
réglage
A 10 MONT 1 0.2

X 10 INJE 1.5 0.005

20 TAMP 1 0.01

Y 10 INJE 1 0.01

20 TAMP 1 0.01

• Calculer les durées des OF

• Reproduire un ordonnancement faisable
Exemple 2
Une petite entreprise manufacturière produit
des pièces qui nécessitent deux opérations: le
sablage et la perforation. Ces opérations
doivent toujours être effectuées dans le même
ordre, soit la sablage avant la perforation.
La compagnie reçoit 5 commandes. Le tableau
fournit, pour chaque commande et chaque
opération, le temps d’opération en minutes.
Exemple 2 (suite)
Commandes Sablage Perforation
1 4 5
2 4 1
3 10 4
4 6 10
5 2 3

Déterminez la séquence de traitement des

commandes de façon à minimiser le temps total
de traitement.
Dites à quel moment seront terminées toutes
les commandes.
Exemple 3
Commandes C1 C2 C3 C4 C5 C6

Temps d’op. poste D04 2 7 9 10 8 11

Temps d’op. poste D07 6 8 4 1 3 7

Délai de livraison 25 19 30 26 16 55

Établir les séquences de traitement des commandes selon:

1- le temps d’opération le plus court au département D04;

2- le temps d’opération le plus court au département D07;
3- le délai de livraison le plus rapproché;
4- le temps total d’achèvement des commandes.
Les systèmes d’ordonnancement
informatisés
Facteurs à considérer pour bien implanter un système
d’ordonnancement informatisé:

1) Exactitude des données: exige un contrôle constant.

2) Processus: doit être bien connu et bien étudié pour éviter des
difficultés d’implantation.
3) Milieu de travail: acceptation des changements.
4) Formation du personnel.
5) Savoir quel objectif on désire atteindre.
EL Hassani Ibtissam