THEME

ORDONNACEMENT DE
LA PRODUCTION
Présenté par :
- FEUMI Patrick Prince
- KENGNE Fodouop Wilfrid
Sous la supervision de: Mr OLEMBE
PLAN:

INTRODUCTION

CLASSIFICATION DES ATELIERS

METHODE DE RESOLUTION STATIQUE

METHODE DE RESOLUTION
DYNAMIQUE
2
Ordonnancement : détermination conjointe des dates
d’exécution d’un ensemble d’opérations et des ressources
mobilisées dans cette exécution

INTRODUCTION
3
CLASSIFICA
TION DES
ATELIERS
SELON LA
CONFIGURATION DES
MACHINES

4
 ATELIER A MACHINE UNIQUE

 Une seule machine assure la production.

 l’existence de files d’attente, de longueur variable au cours du temps, en

amont des différents postes de travail.

5
ATELIER À CHEMINEMENT
UNIQUE(FLOW SHOP)

 Le processus de fabrication est linéaire .

 Dans un ordre précis, le même pour tous les produits
 l’existence de files d’attente, de longueur variable au cours du temps, en

amont des différents postes de travail. 6

ATELIER A CHEMINEMENT
MULTIPLE( JOB FLOW)

 coexistence de très nombreux cheminements des flux de production dans

un même système productif
 Chaque produit a son propre cheminement

7
ATELIER À CHEMINEMENT LIBRE(
OPEN SHOP)

 Aucune contrainte de précédence: l’ordre d’exécution des taches pour un

produit donné importe peu

8
ATELIER À MACHINE
PARRALÈLLE
 Plusieurs machines effectuant les mêmes
opérations
 Classification
 Identiques: lorsque toute les machines ont la
même vitesse de production
 Uniforme : les vitesses sont différentes mais
les même pour deux produits identiques
 Hétérogène : la vitesse varie selon le produit

9
METHODE
DE
RESOLUTIO
N
APPROCHE
STATIQUE

10
ORDONNANCEMENT D’ATELIER À MACHINE UNIQUE
Mise en situation :
Tâche i 1 2 3 4 5
Temps 50 150 80 200 30
opératoire ti (en
minutes)
Remarque: Quel que soit l’ordre dans lequel on effectue ses tâches le temps d’exécution
est le même

Ordre de passage j 1 2 3 4 5
Tâche programmée j 3 4 1 5 2
Temps d »exécution Tj 80 200 50 30 150
Date Aj de fin de la 80 280 330 360 510
tâche j

11
ORDONNANCEMENT D’ATELIER À MACHINE UNIQUE
REGLE DU TEMPS OPERATOIRE MINIMUM
Mise en situation :

Tâche i 1 2 3 4 5
Temps 50 150 80 200 30
opératoire ti (en
minutes)
Remarque:
 5! Ordonnancements possibles
 Temps d’exécution totale invariant suivant l’ordonnancement
 Temps d’attente de chaque tâche dépends de l’ordonnancement
Objectifs:
 Minimiser le temps d’attente moyen des différentes tâches

12
ORDONNANCEMENT D’ATELIER À MACHINE
UNIQUE
REGLE DU TEMPS OPERATOIRE MINIMUM
• Date d’achèvement: Aj=
• Date moyenne d’achèvement

Tâche i 1 2 3 4 5
Temps opératoire ti (en minutes) 50 150 80 200 30
Ordre de passagej 1 2 3 4 5
Tâche programmée j 3 4 1 5 2 =
Temps d’exécution Tj 80 200 50 30 150
Date Aj de fin de la 80 280 330 360 510
tâche j

13
ORDONNANCEMENT D’ATELIER À MACHINE UNIQUE
REGLE DU TEMPS OPERATOIRE MINIMUM
 d’une façon générale:

= =
 minimiser lorsque T1T2 … Tj Tj+1 … Tn
 La règle que l’on notera TOM ou SPT rule,, ou encore SOT rule minimise le temps
d’achèvement moyen.
Elle consiste, comme son nom l’indique, à exécuter immédiatement la
tâche ayant le plus faible temps opératoire.
Application:
Ordre de passage j 1 2 3 4 5

Tâche programmée 5 1 3
Tj 30 50 80

14
 ORDONNANCE D’ATELIER
FLOW
ALGORITHME DE JOHNSON
SHOP
Mise en situation :
Numéro de la 1 2 3 4 5
tâche i
tiA 50 150 80 200 30
tiB 60 50 150 70 20
 Ordre identique de passage des tâches sur les machines A et B. A ensuite B
 Objectif : minimiser le temps total d’exécution des tâches sur les deux
machines
 L’ordonnancement qui minimise le temps d’exécution de tous les travaux se
trouve en utilisant l’algorithme de Johnson (publié en 1954)

15
 ORDONNANCE D’ATELIER
FLOW
ALGORITHME DE JOHNSON
SHOP
 Algorithme de Johnson
 Étape 1þ: Chercher i dont (avec j = A ou B) est minimum
 Étape 2þ:
 Si j = A placer i à la première place disponible
 Si j = B placer i à la dernière place disponible

 • Étape 3þ: Supprimer i des tâches restant à programmer

Numéro de la tâche i 1 2 3 4 5
tiA 50 150 80 200 30
tiB 60 50 150 70 200

rang 2 5 3 4 1

16
 ORDONNANCE D’ATELIER FLOW SHOP
ALGORITHME CDS
 Cas de 3 machines :
 Ordre identique de passage
 Condition d’application de l’algorithme de de Johnson: si max(tiB)tiA) ou max(tiB)
min(tiC)
Création de 2 machines virtuelles:
 Machine virtuelle regroupant A et B: tiAB= tiA+tiB
 Machine virtuelle regroupant B et C: tiBC= tiC+tiB
Tâche tiA tiB tiC Tâche i tiAB tiBC
i 1 8 7
1 7 1 6 2 7 5
2 4 3 2 3 5 6
3 3 2 4
4 10 3
4 8 2 1
5 6 4
5 5 1 3 17
ORDONNANCE D’ATELIER FLOW SHOP
ALGORITHME CDS
• Cas de 3 machines :
• Ordre identique de passage
• (n!)m ordonnancements possibles
algorithme CDS: c’est l’algorithme de Johnson sur des groupes de machines
successives
Temps d’exécution en 1/10ème d’heure
Tâche i tiA tiB tiC tiD
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

Résolution des 3 trois problèmes suivants:[A]-[D];[AB]-[CD].[ABC]-[BCD] 18

ORDONNANCE D’ATELIER FLOW SHOP
ALGORITHME CDS
Exemple
1er problème fictif: [A]-[D]

Ordonnancement obtenu: 6-3-4-2-5-1

Aj=51,2 heures 19
ORDONNANCE D’ATELIER
FLOW SHOP
ALGORITHME CDS
Exemple
2ème problème fictif: [AB]-[CD]
Tâche i ti,A+B ti,C+D
1 93 19
2 188 172
3 54 188
4 72 106
5 80 79
6 81 144

Ce deuxième problème ([AB]-[CD]) donne la solution suivante:3-4-6-2-5-1

Avec cet ordonnancement ; l’ensemble des travaux sera terminé au bout de
48,7heures
20
ORDONNANCE D’ATELIER FLOW SHOP
ALGORITHME CDS
Exemple
3eme problème fictif: [ABC]-[BCD]
Tâche i ti;A+B+C ti;B+C+D
1 108 62
2 283 271
3 74 165
4 84 170
5 145 98
6 147 224

Ce dernier problème ([ABC]-[BCD]) donne la même solution que le deuxième problème

Ordonnancement obtenu: 6-3-4-2-5-1
Aj=51,2 heures

21
ORDONNANCE D’ATELIER
FLOW SHOP
ALGORITHME CDS
Exemple
Solution obtenue:
Tâche i ti,A+B ti;C+D
1 93 19
2 188 172
3 54 188
4 72 106
5 80 79
6 81 144
Ce deuxième problème ([AB]-[CD]) donne la solution suivante:3-4-6-2-5-1
Avec cet ordonnancement; l’ensemble des travaux sera terminé au bout de
48,7 heures
22
 ORDONNANCEMENT EN
ATELIER OPEN SHOP
RÈGLE DU LAPT(LONGEST ALTERNATE PROCESSING TIME)

 objectif: Minimiser la durée d’achèvement de l’ensemble des tâches Aj

exemple de problème
 Cas : ordonnancement à cheminement libre dans 2 centres de
production
Numéro de 1 2 3 4
la tâche i
tiA 50 150 80 200
tiB 60 50 100 70

23
 ORDONNANCEMENT EN
ATELIER OPEN SHOP
RÈGLE DU LAPT(LONGEST ALTERNATE PROCESSING TIME)
 en t = 0, l’opération la plus longue est l’opération A de la tâche 4, on charge donc
l’opération de la tâche 4 à exécuter sur B (date d’achèvement en t = 70) (choisie
arbitrairement parmi les 2 centres libres);
Numéro de la tâche i 1 2 3 4
tiA 50 150 80 200
tiB 60 50 100 70

24
 ORDONNANCEMENT EN
ATELIER OPEN SHOP
RÈGLE DU LAPT(LONGEST ALTERNATE PROCESSING TIME)
 en t = 0, le centre A étant libre, les opérations des tâches 1, 2 et 3 sont donc candidates;
l’opération la plus longue sur le centre B parmi ces candidats est celle de la tâche 3 (100),
ce qui conduit à charger l’opération A de la tâche 3 (date d’achèvement en t = 80);

Numéro de 1 2 3 4
la tâche i
tiA 50 150 80 200
tiB 60 50 100 70

25
 ORDONNANCEMENT EN
ATELIER OPEN SHOP
RÈGLE DU LAPT(LONGEST ALTERNATE PROCESSING TIME)
 en t = 70, le centre B se libère, les opérations des tâches 1 et 2 sont donc candidates (3
étant en cours); l’opération la plus longue sur A de ces candidats est celle de la tâche 2
(150); on charge donc l’opération B de la tâche 2 (date d’achèvement en t = 70 + 50 = 120);

Numéro de 1 2 3 4
la tâche i
tiA 50 150 80 200
tiB 60 50 100 70

26
 ORDONNANCEMENT EN
ATELIER OPEN SHOP
RÈGLE DU LAPT(LONGEST ALTERNATE PROCESSING TIME)

 en t = 80, le centre A se libère, les opérations des tâches 1 et 4 sont donc

candidates; l’opération de la tâche 1 (qui n’a encore aucune réalisation de tâche) est
plus prioritaire que celle de la tâche 4 (qui a déjà une opération réalisée); on charge
donc l’opération A de la tâche 1 (date d’achèvement en t = 80+50 = 130);

Numéro de la 1 2 3 4
tâche i
tiA 50 150 80 200
tiB 60 50 100 70

27
 ORDONNANCEMENT EN
ATELIER OPEN SHOP
RÈGLE DU LAPT(LONGEST ALTERNATE PROCESSING TIME)

 en t = 120, le centre B se libère, l’opération de la tâche 3 est candidate unique (1 étant en

cours); on charge donc l’opération B de la tâche 3 (date d’achèvement en t = 120 + 100 =
220);

Numéro de 1 2 3 4
la tâche i
tiA 50 150 80 200
tiB 60 50 100 70

28
 ORDONNANCEMENT EN
ATELIER OPEN SHOP
RÈGLE DU LAPT(LONGEST ALTERNATE PROCESSING TIME)
 en t = 130, le centre A se libère, sont donc candidates les opérations des
tâches 2 et 4 qui ont déjà toutes deux une opération exécutée sur B; elles sont
équivalentes et on charge arbitrairement l’opération A de la tâche 2 (date
d’achèvement en t = 130 + 150 = 280.
Numéro de 1 2 3 4
la tâche i
tiA 50 150 80 200
tiB 60 50 100 70

29
ORDONNANCEMENT EN
ATELIER OPEN SHOP
RÈGLE DU LAPT(LONGEST ALTERNATE PROCESSING TIME)
 puis l’opération A de la tâche 4 (date d’achèvement en t = 280 + 200 =
480) qui est la dernière opération à exécuter sur ce centre;

Numéro de 1 2 3 4
la tâche i
tiA 50 150 80 200
tiB 60 50 100 70

30
ORDONNANCEMENT EN
ATELIER OPEN SHOP
RÈGLE DU LAPT(LONGEST ALTERNATE PROCESSING TIME)
 en t = 220, le centre B se libère, on charge donc l’opération B de la
tâche 1 (date d’achèvement en (t=220+60 = 280) qui est la dernière à
réaliser.
Numéro de 1 2 3 4
la tâche i
tiA 50 150 80 200
tiB 60 50 100 70

31
ORDONNANCEMENT EN
ATELIER OPEN SHOP
HEURISTIQUE : règle MWR
 Lorsqu’il y a plus de 2 centres de production, on peut utiliser
des heuristiques,
 Les travaux effectués montrent qu’en général la meilleure
règle est la règle MWR (Most Work Remaining) qui privilégie la
tâche candidate dont la durée cumulée des opérations non
encore traitées est maximale.
 Aucune garantie d’optimalité ,En général on espère
simplement obtenir rapidement une «bonne» solution.

32
ORDONNANCEMENT EN
ATELIER JOB
CAS DE 2 CENTRES SHOP
D’OPERATION
 Il faut tout d’abord effectuer une partition de l’ensemble initial des n
tâches en quatre sous-ensembles:
 l’ensemble {A} : les tâches qui ne nécessitent que l’intervention sur A;
 l’ensemble {B} : comprend toutes les tâches qui ne nécessitent que
l’intervention sur B
 l’ensemble {AB} : Tâches intervenantes en A puis en B
 l’ensemble {BA}:Tâches intervenantes en B puis en A

 ordonnancement optimal sur le sous-ensemble {AB} à l’aide de

l’algorithme de Johnson.
Idem pour le sous-ensemble {BA}.
 Pour les sous-ensembles {A} et {B} l’ordre de passage des tâches n’est
pas importante .
33
ORDONNANCEMENT EN
ATELIER JOB SHOP
CAS DE 2 CENTRES D’OPERATIONS
On combine les résultats obtenus dans chaque sous-ensemble
de la façon suivante:
centre de production A:
o séquence optimale du sous-ensemble {AB},
o tâches du sous-ensemble {A},
o séquence optimale du sous-ensemble {BA}
centre de production B:
o séquence optimale du sous-ensemble {BA}
o tâches du sous-ensemble {B}
o séquence optimale du sous-ensemble{AB}

34
ORDONNANCEMENT EN
ATELIER JOB
CAS DE N CENTRES SHOP
D’OPERATIONS
 Aucun résultat analytique n’est disponible pour résoudre cette classe de
problèmes.
 On peut utiliser la programmation mathématique, mais la résolution
numérique optimale de problèmes d’une certaine dimension, est le plus
souvent hors de portée.
 On cherchera à les résoudre plutôt à l’aide d’approches simulatrices
s’appuyant sur des méthodes heuristiques
 On examinera cependant ici le problème statique de l’ordonnancement en
cas d’existence d’un goulot d’étranglement, c’est-à-dire de centre de
production plus sollicité que les autres au point de conditionner le débit
global de production du système productif étudié

35
ORDONNANCEMENT EN
ATELIER JOB SHOP
ORDONNANCEMENT BASÉ SUR LE GOULOT D’ETRANGLEMENT
1 2 3 4 5
Machin durée Machin duré Machine duré Machine durée Machin durée
e e e e e
A 5 A C C 8 B 5 D 7
C 7 B A A 4 D 4 C 15
D 9 C B B 3 C 6 A 4
- - D - - - B 7 - -
 Détermination du goulot d’étranglement : la machine C
 Hypothèse: considère qu’en amont et en aval de ce goulot, on est à capacité
infinie

36
ORDONNANCEMENT EN
ATELIER JOB SHOP
ORDONNANCEMENT BASÉ SUR LE GOULOT D’ETRANGLEMENT
 Transformation du problème de job shop autour de la machine critique C
 En aval le travail s’effectue sur une machine fictive, pour une durée égale à la
somme des durées
 En aval le travail s’effectue sur une machine fictive, pour une durée égale à la
somme des durées

1 2 3 4 5
Machin durée Machin duré Machine duré Machine durée Machin durée
e e e e e
Avant C 5 Avant C 8 Avant C 0 Avant C 9 Avant C 7
C 7 C 10 C 8 C 6 C 15
Après C 9 Après C 4 Après C 7 Après C 7 Après C 4

37
ORDONNANCEMENT EN
ATELIER JOB SHOP
ORDONNANCEMENT BASÉ SUR LE GOULOT D’ETRANGLEMENT
 Ordonnancement sur la machine C:utilisation de la règle de TOM
 Autre règle possibles

Date Tâches disponibles Ordonnancement

T=0 3(durée 8) 3 (durée 8)
T=8 5(durée 15), 1 durée(7) 1 (durée 7)
T = 15 5(durée 15), 2(durée10), 4 ( durée 6)
4( durée 6)
T = 21 5(durée 15), 2(durée10) 2(durée10)
T = 31 5(durée 15), 5(durée 15),
 Ordonnancement des opérations en aval en prenant comme date de livraison
la date d’arrivée au goulot d’étranglement.(règles S/OP,

38
ORDONNANCEMENT EN
ATELIER JOB SHOP
ORDONNANCEMENT BASÉ SUR LE GOULOT D’ETRANGLEMENT

 Illustration de l’ordonnancement final obtenu

39
METHODE
DE
RESOLUTIO  APPROCHE PAR LA THEORIE DE FILE

N
APPROCHE
DYNAMIQUE
D’ATTENTE

 APPROCHE SIMULATOIRE

40
APPROCHE PAR FILES
D’ATTENTE
 Théorie de la fil d’attente
 Temps d’arrive = V.A suivant une
loi de probabilité p
 étudier l'existence ou non d'un
régime stationnaire, le risque de
saturation du service, la discipline
optimale par rapport au temps de
résidence
 pluLe bon fonctionnement du
système est jugé à travers un ou
plusieurs critères

41
APPROCHE PAR SIMULATION
 Monte-Carlo pour obtenir info pour systèmes complexes,
éventuellement perturbés •
 La simulation de systèmes réels : Recherche de règles de
décision générales (tables de décision) ou contingente (pb
spécifique) • Supériorité de règle: contingente, attention à
généralisations abusives
 La simulation de systèmes fictifs : Hypothèses précises:
nombre de CP, gammes, durées, arrivées, lotissement, temps
de trans fert, perturbations…

42
APPROCHE PAR SIMULATION
 Comparaison des règles.
 Simulation d’un jeu de 8700 tâches, SP à 9 C, 25 règles de priorité
 Travaux de Conway, Maxwell et Miller

Règle Rando FCFS TOM LWK WINQ SOPN

m R
Nbre moyen instantanée de 59,42 58,57 23,25 47,52 40,43 D.I.
tâche en attentes
Temps t 74,70 74,43 33,04 D.I. 66,10
sigma D.I. 41,06 53,65 16,31

43
MERCI POUR VOTRE
ATTENTION

44