Cours

Ingénierie des Systèmes Industriels

( Planification & Ordonnancement)

BENAISSA Mounir

Docteur Ing. : Génie Industriel

 Le Plan du cours….

 Chapitre 1: Modèles de Files d’attente

 Chapitre 2: Planification de la production

 Chapitre 3: Ordonnancement de la production

 Chapitre 1: MODELES DE FILES
D’ATTENTE

1.INTRODUCTION
2. MESURES DE PERFERMANCE
3. PROCESSUS DE POISSON
4. DISTRIBUTION EXPONENTIELLE
5. NOTATION DE KENDALL
6. PROCESSUS DE NAISSANCE ET DE MORT: CAS GENERAL
7. PROCESSUS DE NAISSANCE ET DE MORT: CAS PARTICULIERS
 1. MODELES DE FILES D’ATTENTE:
INTRODUCTION

 La théorie des files d'attente s’attache à modéliser et à

analyser de nombreuses situations très diverses:
• Des clients arrivent à intervalles aléatoires dans un système
comportant plusieurs serveurs auxquels ils vont adresser une
requête. La durée du service auprès de chaque serveur est elle-
même aléatoire. Après avoir été servis (ce qui suppose un arrêt
chez un ou plusieurs serveurs selon le cas), les clients quittent le
système.
 Le but de l'analyse est de caractériser le degré de
performance du système en répondant à des questions
du type suivant:
• en moyenne, combien de temps attend un client avant d'être servi?
• quel est le nombre moyen de clients dans le système?
• quel est le taux d'utilisation moyen des serveurs?
 1.Structure générale d’un système
de files d’attente

Arrivées Départs
Clients Clients
 1. Exemple d’un système
de files d’attente

 Agence bancaire
Ici, les serveurs sont les guichets de l'agence. Typiquement,
tous les guichets offrent le même service, et chaque client
ne devra donc visiter qu'un seul guichet.
 Atelier de production
Les ‘clients’ sont les ordres de fabrication à exécuter, et les
'serveurs' sont les machines nécessaires à l'exécution de
chaque ordre de fabrication.
 Parking
Les 'clients' sont les véhicules qui cherchent à stationner.
Les 'serveurs' sont les emplacements de parking, et la
'durée de service' est la durée pendant laquelle chaque
véhicule reste stationné.
 1.Les différents Types d’un système
de files d’attente

 Les systèmes à serveurs parallèles: où chaque client ne

réclame le service que d'un seul serveur et tous les
serveurs sont capables de fournir ce service.
Arrivées Départs

 Les systèmes à serveurs en série, où chaque client doit

visiter plusieurs serveurs successifs dans un ordre fixe pour
recevoir satisfaction.

Arrivées Départs
 1.Caractéristiques d’un système
de files d’attente

 Les arrivées de clients peuvent être groupées ou individuelles; de

même pour le service par chaque serveur.
 Les clients forment une ou plusieurs files d'attente, éventuellement
caractérisées par des priorités différentes. Au sein de chaque file, le
prochain client à servir est sélectionné sur base d'une règle
prédéterminée, appelée discipline de service. Les disciplines de service
les plus courantes sont: premier arrivé premier servi (First In First Out,
First Come First Served) , temps de service le plus court d'abord (utilisé
dans les ateliers de production), dernier arrivé premier servi, sélection
aléatoire, etc.
 La capacité du système, c’est-à-dire le nombre de clients pouvant être
simultanément présents dans le système, est limitée ou non. Dans le
premier cas, on suppose que les clients qui arrivent lorsque le système
est déjà saturé le quittent immédiatement sans obtenir le service désiré.
On dit que ces clients sont perdus. Dans le cas d'un système à
capacité illimitée, bien sûr, aucun client n'est perdu (mais la longueur
des files d'attente peut grandir indéfiniment !).
 1. Hypothèses

 Dans ce cours, nous nous limiterons à

l'étude de systèmes
• à serveurs parallèles
• à arrivées et service individuels.
 Nous supposerons également que tous les
clients demandent le même service et que
les serveurs sont identiques.
 Chapitre 1: MODELES DE FILES
D’ATTENTE

1.INTRODUCTION
2. MESURES DE PERFERMANCE
3. PROCESSUS DE POISSON
4. DISTRIBUTION EXPONENTIELLE
5. NOTATION DE KENDALL
6. PROCESSUS DE NAISSANCE ET DE MORT: CAS GENERAL
7. PROCESSUS DE NAISSANCE ET DE MORT: CAS PARTICULIERS
 2. Mesures de performance -
Comportement à long terme
 Nous appelons état d'un système à l'instant t le nombre n(t) de clients présents
dans le système à cet instant (un client est « présent dans le système » si il est
en file d’attente ou en cours de service).

 Les quantités fondamentales auxquelles s'intéresse l'analyste dans le cadre des

modèles de files d'attente sont les probabilités d'état, que nous définissons de la
façon suivante: pour n = 0, 1, 2, ... et t ≥0,

• pn(t) = probabilité de l'état n à l'instant t (1)

• probabilité que n clients soient présents dans le système à
l'instant t
 Sous certaines conditions, les probabilités à long terme ou probabilités
stationnaires p =
n limp (t )
t →∞
n (2)
existent pour n = 0, 1, 2, ... et définissent effectivement une mesure de probabilité :
∞

∑p
n =0
n =1
 2. Mesures de performance -
Comportement à long terme

Lorsque les probabilités (1) et/ou (2) sont connues, il est

possible de calculer de nombreuses mesures de performance du
système de files d’attente à étudier. Parmi les plus importantes, on
considérera les mesures à long terme suivantes:
Ls = nombre espéré de clients dans le système (à un instant
quelconque dans le long terme)
Lq = nombre espéré de clients dans la file d'attente (à un instant
quelconque dans le long terme)
Ws = temps espéré passé par chaque client dans le système (dans le
long terme)
Wq = temps espéré passé par chaque client dans la file d'attente
(dans le long terme).
 2.Mesures de performance -
Comportement à long terme
Par définition, on a:
∞
Ls = ∑ npn (3)
n =0

De plus, si le système comporte c serveurs parallèles, alors

∞
Lq = ∑ (n − c) p
n = c +1
n (4)
 2. Mesures de performance -
Comportement à long terme

• λeff = taux d'entrée moyen des clients dans le système (nombre

moyen de clients entrant dans le système par unité de temps).
• L’équation suivante, désignée sous le nom de loi de Little, lie les
paramètres Ls, Ws et λeff et permet donc de calculer l’une de ces
quantités lorsque les deux autres sont connues:
Proposition 1. (Loi de Little) Pour tout système de files d’attente,
Ls = Ws × λeff (5)
De même
Lq = Wq × λeff (6)
 Notons que:
• La durée moyenne du service, par client = Ws - Wq (7)
• Le nombre moyen de serveurs occupés = Ls - Lq (8)
 EXEMPLE 1

Le gestionnaire d'un petit atelier enregistre en moyenne 5

commandes par jour. Les 6 ouvriers employés dans l’atelier sont
très polyvalents, si bien que chaque commande peut être réalisée
par n’importe lequel d’entre eux. Néanmoins, le gestionnaire est
inquiet car il constate que les ouvriers sont occupés en
permanence et que son carnet de commandes contient, en
moyenne, une vingtaine de commandes en cours (enregistrées,
mais non satisfaites). Pour mieux comprendre la situation, le
gestionnaire aimerait estimer le temps moyen consacré par les
ouvriers à chaque commande. Il voudrai également pouvoir
annoncer à ses clients, au moment de la passation de commande,
un délai de livraison attendu.
 Chapitre 1: MODELES DE FILES
D’ATTENTE

1.INTRODUCTION
2. MESURES DE PERFERMANCE
3. PROCESSUS DE POISSON
4. DISTRIBUTION EXPONENTIELLE
5. NOTATION DE KENDALL
6. PROCESSUS DE NAISSANCE ET DE MORT: CAS GENERAL
7. PROCESSUS DE NAISSANCE ET DE MORT: CAS PARTICULIERS
 3. PROCESSUS DE POISSON

 Nous notons N(t) le nombre d'arrivées de clients survenues dans

l'intervalle de temps [0, t), pour t ≥ 0. La quantité N(a+t) - N(a)
représente alors le nombre d’arrivées enregistrées entre les instants a
et a+t, pour tout a ≥0 et t ≥0.

Le processus d'arrivée peut bien sûr présenter des caractéristiques

variées en fonction de la situation modélisée. Mais il est fréquent
dans la pratique que ce processus soit (du moins en première
approximation) un processus de Poisson, ce qui signifie qu'il existe
un paramètre λ> 0 (appelé taux du processus) tel que:
 3. PROCESSUS DE POISSON

(i) le nombre d'arrivées dans tout intervalle [a,a+t) de longueur t suit

une loi de Poisson de moyenneλt , c'est-à-dire: pour a, t≥0 et n =
0, 1, 2, ...
( λ t ) n
Pr[ N (a + t ) − N (a ) = n] = e −λt
n!
(ii) si [a,b) et [c,d) sont des intervalles de temps disjoints, alors le
nombre d'arrivées dans [a,b) est indépendant du nombre d'arrivées
dans [c,d).

(iii) N(0) = 0.
 3. PROCESSUS DE POISSON

Pour un intervalle de longueur t fixée, disons [0,t), le nombre

espéré d'arrivées se calcule comme suit:
∞
E[ N (t )] = ∑ n Pr[ N (t ) = n]
n =0
∞
(λt ) n ∞
( λ t ) n −1
= ∑ ne −λt = λte −λt ∑
n =0 n! n =1 ( n − 1)!
∞ n
( x )
Si l'on se souvient que ex = ∑ , on obtient
n = 0 n!

E[ N (t )] = λte − λt e λt = λt
 Chapitre 1: MODELES DE FILES
D’ATTENTE

1.INTRODUCTION
2. MESURES DE PERFERMANCE
3. PROCESSUS DE POISSON
4. DISTRIBUTION EXPONENTIELLE
5. NOTATION DE KENDALL
6. PROCESSUS DE NAISSANCE ET DE MORT: CAS GENERAL
7. PROCESSUS DE NAISSANCE ET DE MORT: CAS PARTICULIERS
 4. DISTRIBUTION EXPONENTIELLE
 il existe deux façons de décrire le processus selon lequel les
arrivées de clients surviennent dans un système: on peut en effet
vouloir placer l’accent sur:
• le nombre de clients qui arrivent dans un intervalle de
temps donné (par exemple, 10 clients par heure), ou sur
• l’intervalle de temps écoulé entre deux arrivées successives
(par exemple, une arrivée toutes les 6 minutes).
 Dans l'hypothèse où le processus d'arrivée considéré est
poissonnien, on peut aisément passer d’un type de description à
l’autre. En effet, supposons qu'une arrivée d’un processus
poissonnien se produise à l'époque a, et indiquons par X le temps
écoulé jusqu’à l'arrivée suivante. Calculons la loi de probabilité
qui régit l'intervalle de temps écoulé entre ces deux arrivées
successives.
 4. DISTRIBUTION EXPONENTIELLE

Pour tout t ≥ 0, on à:
Pr[ X > t ] = probabilité qu’aucune arrivée ne soit enregistrée entre a et a+t
= Pr[ N (a + t ) − N (a ) = 0] = e − λt
Par définition, on dit que la variable aléatoire X suit une distribution
exponentielle de paramètre λ.

Proposition 2. Un processus d'arrivée est un processus de Poisson

de taux λ si et seulement si les durées entre arrivées successives sont
indépendantes et suivent toutes une loi exponentielle de paramètre λ.
 4. DISTRIBUTION EXPONENTIELLE

Mentionnons encore que, si X suit une loi exponentielle de

paramètre λ , alors E[X] = λ
1 1
et Var[X] = λ . 2

puisque λ est le nombre moyen de clients arrivant par unité

de temps, l'intervalle de temps
1
moyen séparant deux arrivées
successives doit valoir λ .

Proposition 3. Pour t, s ≥ 0, Pr [X > t + s | X > s] = Pr [X > t ].

 Exemple 2

A Sfax, les trains arrivent à la gare selon un

processus de Poisson, à raison de 2 trains par heure en
moyenne. Ali arrive à la gare, où un employé lui signale
que le dernier train est passé il y a une heure déjà. Quelle
est la probabilité que Ali doive attendre plus de 10
minutes avant de voir arriver le train suivant?
 Chapitre 1: MODELES DE FILES
D’ATTENTE

1.INTRODUCTION
2. MESURES DE PERFERMANCE
3. PROCESSUS DE POISSON
4. DISTRIBUTION EXPONENTIELLE
5. NOTATION DE KENDALL
6. PROCESSUS DE NAISSANCE ET DE MORT: CAS GENERAL
7. PROCESSUS DE NAISSANCE ET DE MORT: CAS PARTICULIERS
 5. NOTATION DE KENDALL

Suivant une suggestion de Kendall, on décrit souvent les caractéristiques

essentielles d'un système de files d'attente par une notation abrégée de la forme
a/b/c/N, où
a ∈ {M ,G....} précise le processus d'arrivée: M (Markovien) pour un processus
de Poisson, G (général) pour un processus quelconque non précisé, ...;
b ∈ {M ,G....}précise la distribution des durées de service: M (Markovien) pour
des durées indépendantes et distribuées exponentiellement avec moyenne
identique pour chaque serveur, G pour des durées quelconques, ...;
c ∈ {1,2,...., ∞} indique le nombre de serveurs;
N ∈ {1,2,...., ∞} précise la capacité du système, c'est-à-dire le nombre de
clients qui peuvent simultanément s'y trouver.
 5. NOTATION DE KENDALL

Le paramètre N est souvent omis lorsqu’il vaut +∞. Ainsi, on

parlera de systèmes M/M/1, M/M/5/8, M/G/1, etc. Par ailleurs, la
notation a/b/c/N est parfois complétée par des champs
supplémentaires indiquant par exemple la discipline de service
(FIFO, aléatoire, ...), le nombre de clients existant dans l'univers
considéré, etc.

Dans la suite, nous nous limiterons à l’étude des systèmes de type

M/M/c/N (systèmes de file d'attente à arrivées poissonniennes et à
durées de service exponentielles)
 Chapitre 1: MODELES DE FILES
D’ATTENTE

1.INTRODUCTION
2. MESURES DE PERFERMANCE
3. PROCESSUS DE POISSON
4. DISTRIBUTION EXPONENTIELLE
5. NOTATION DE KENDALL
6. PROCESSUS DE NAISSANCE ET DE MORT: CAS GENERAL
7. PROCESSUS DE NAISSANCE ET DE MORT: CAS PARTICULIERS
6. PROCESSUS DE NAISSANCE ET DE MORT :LE
CAS GENERAL

 Définition: Le processus d’état stochastique {n(t): t ≥ 0} est un

processus de naissance et de mort si, pour chaque n = 0, 1, 2, ..., il
existe des paramètres λn et µ n (avec µ 0= 0) tels que, lorsque le
système est dans l'état n, le processus d'arrivée est poissonnien de
taux λn et le processus de sortie est poissonnien de taux µ n .
 6.1 Processus de naissance pur

 Dans un processus de naissance pur, λn = λ et µ n = 0 pour

n = 0, 1, ... Donc, les arrivées ont lieu à taux constant et il
n'y a pas de départs. Pour un tel processus, le nombre de
clients dans le système est évidemment égal au nombre
d’arrivées enregistrées pour un processus de Poisson
classique, si bien que
 pn (t) = probabilité que l'état du système à l'époque t soit
égal à n.
− λt ( λ t ) n

= e (n=0,1,2,…..)
n!
 6.2 Processus de mort pur
Dans un processus de mort pur, l’ensemble des états possibles du système
est {0,1,...,N} et
λn =0 pour n = 0, 1, ..., N
µ ={n
0 si n = 0
µ si n=1,2…N
l'état initial d’un tel système vaut N, il n'y a pas d'arrivées et les départs se
produisent à taux (moyen) constant jusqu'à ce que le système soit vide. En
interprétant les départs comme des « arrivées à l'extérieur du système », on
conclut facilement que:
 Pn(t) = probabilité que N-n départs se produisent dans l'intervalle [0, t)
( µt ) N − n
e − µt
=
( N − n)! (n = 0, 1, ..., N)

Soit P0(t) = probabilité Nque N départs au moins se produisent dans

l’intervalle [0, t) = 1 − ∑ pn (t )
n =1
 6.3 Système M/M/1

Un système M/M/1 définit un processus de naissance et

de mort caractérisé par les paramètres d’arrivée λn = λ pour
n = 0, 1, ..., et les paramètres de sortie µ 0 = 0 et µ n = µ pour
n = 1, 2, ...
 6.4 Système M/M/c

On obtient une description d’un système M/M/c en posant λn= λ

pour n = 0, 1, ..., et
nµ si n ≤ c
µn = 
cµ si n ≥ c
En effet, lorsque le nombre de clients présents dans le système est inférieur au
nombre de serveurs, alors les n serveurs occupés donnent lieu à un processus de
départ poissonnien de taux n µ si le nombre de clients présents excède c, alors le
µ
taux du processus de départ reste limité à c , comme illustré par la figure ci-
dessous.
µ cµ
λ
µ
µ
 6.5 Système M/M/c/N

Dans un système de file d’attente dont la capacité est finie (égale

à N), les états possibles du système sont n = 0, 1, ..., N, et
λ si n < N
λn 
0 si n = N
nµ si n ≤ c
µn 
cµ si n ≥ c

puisque aucun client n'a accès au système lorsque n = N.

 6.6 Probabilités à long terme

Proposition 4. Lorsqu’elles existent, les probabilités à long terme

Pn (n = 0, 1, ...) d'un processus de naissance et de mort satisfont aux
équations d'équilibre
λ0 p0 = µ1 p1 (9)
λn pn = µ n +1 pn +1 (10) ∞
et à l’équation de normalisation ∑p
n =0
n =1 (11)

considérons le graphe de transition associé à un processus de

naissance et de mort arbitraire.
 6.6 Probabilités à long terme

 Dans ce graphe, les sommets correspondent aux états possibles du système, et

chaque arc indique une transition possible d'un état vers un autre
 Lorsque le système est dans l’état n, il passe à l’état n+1 au taux moyen λn .
Cette valeur se retrouve sur l’arc (n,n+1) du graphe de transition. Puisque pn est
la proportion du temps pendant laquelle le système se trouve dans l'état n, on en
déduit:
λn pn = taux espéré auquel le système passe de l'état n à l’état n+1.
De même:
µ n +1 pn +1 = taux espéré auquel le système passe de l'état n+1 à l’état n.
 6.6 Probabilités à long terme

 Lorsque µ n > 0 pour n = 1, 2, ... (ce qui est par exemple le cas pour
tout système M/M/c/N avec µ > 0), les équations d'équilibres
peuvent être facilement résolues en terme de p0. En effet, on
obtient successivement: p = λ0 p
1
µ1 0
λ λλ
p2 = 1 p1 = 0 1 p0
µ2 µ1µ 2
et, plus généralement:
λ0 λ1....λn −1
pn = p0 Pour n=1,2….. (11)
µ1µ 2 ....µ n
 Chapitre 1: MODELES DE FILES
D’ATTENTE

1.INTRODUCTION
2. MESURES DE PERFERMANCE
3. PROCESSUS DE POISSON
4. DISTRIBUTION EXPONENTIELLE
5. NOTATION DE KENDALL
6. PROCESSUS DE NAISSANCE ET DE MORT: CAS GENERAL
7. PROCESSUS DE NAISSANCE ET DE MORT: CAS PARTICULIERS
 7. 1 Processus de naissance pur

Si λn = λ > 0 et µ n = 0 pour n = 0, 1, 2, ..., alors les équations

d'équilibre deviennent:
λpn = 0 n = 0 1 2 ( , , ,...).

Ce système a pour unique solution: Pn = 0 pour n = 0, 1, 2, ...,

 7.2 Processus de mort pur

donc pn = 0 pour n = 1, 2, ..., N. En substituant ces valeurs dans l'équation de

normalisation (10), on obtient les probabilités stationnaires:
.
7.3 Système M/M/1

(12)

(13)
7.3 Système M/M/1

(5)
7.3 Système M/M/1
7.4 Système M/M/c
7.4 Système M/M/c

(14)

(15)
 Exemple 3

 Ahmed est directeur de l'agence de banque à Sfax. Les clients se

présentent à l'agence au rythme moyen de 10 clients par heure. Ils y
sont servis par l'unique employé de l'agence, auprès duquel chaque
client passe 5 minutes en moyenne. Selon les L'agence peut donc être
vue comme un système M/M/1;
 EXEMPLE 3 (suite)

Ahmed juge que ces 30 minutes passées (en moyenne) par chaque
client dans le système sont inacceptablement longues et envisage
différentes façons de remédier au problème.
 Option a: Ahmed pourrait engager un second employé de qualifications
similaires à celles de l'employé actuel et laisser chaque client s'adresser
au premier employé disponible.
 Option b: Dans cette variante de l'option a, l'employé actuel (qui se
trouve être un Géant) se limiterait à servir les clients Géants et Julien
engagerait un Nain pour servir les clients Nains. Cette option paraît
raisonnable dans la mesure où la clientèle de l'agence compte 50% de
Géants et 50% de Nains, et où les clients pourraient y voir une
personnalisation du service offert.
 Option c: Ahmed envisage également la possibilité de licencier son
employé et de le remplacer par un employé plus qualifié, deux fois plus
rapide que l’employé actuel.
Comparons les trois options considérées sur base du temps
moyen passé par les clients dans l'agence.
FIN CHAPITRE 1
 Chapitre 2
Planification de la production
Le Plan du cours….
2

 P1: Introduction

 P2: Le pilotage par le flux poussé

 P3: Pilotage par le juste à Temps JAT

 P4: Pilotage par les contraintes OPT

Le Plan du cours….
3

 P1: Introduction

 P2: Le pilotage par le flux poussé

 P3: Pilotage par le juste à Temps JAT

 P4: Pilotage par les contraintes OPT

lntroduction
 La Planification de la production
5

Elle consiste à répartir les ressources

d’une entreprise en tenant compte de
ses objectifs stratégiques, des
contraintes spécifiques et de la
demande prévue.
 Répartition des ressources de l’entreprise

Équipements
Main-d’œuvre Espaces d’entreposage

Ressources financières Sous-traitants

Tenir compte de ses objectifs stratégiques

 Niveler la production pour garder stable

l’utilisation de la main-d’œuvre.

 Synchroniser la production avec la demande

pour minimiser les coûts de maintien en
inventaire.

 Gestion classique ou JàT.

Tenir compte des contraintes existantes

 Le nombre d’employés
 La convention de travail (pour les embauches,
mises à pied, salaires, etc.)
 Le coût du temps supplémentaire
 Le coût de la sous-traitance
 Les capacités de production des différents types
d’équipements
 Les coûts de maintien en inventaire et les coûts de
pénurie
 Les temps de mise en course
Tenir compte de la demande prévue

 Les prévisions

 Les commandes

 Les urgences
LES ÉTAPES DE LA PLANIFIACTION DES OPÉRATIONS

10

Quel produit
Est-ce que et en quelle
nous devons Est-ce que nous quantité? Dans quel
ajouter de la devons Quand et ordre et sur
capacité ou embaucher ? combien quelle machine
adopter une Planifier de la commander traiter mes
nouvelle sous-traitance ? de matières commandes ?
technologie ? premières ?

Horizon Horizon Horizon Horizon Le jour

de d’une de d’une de la
3 ans année 6 mois semaine production

Horizon de la Planification
LES ÉTAPES DE LA PLANIFIACTION DES OPÉRATIONS

11

Plan Stratégique
FAMILLES Prévisions
commerciales
-Commerciales
Plan Industriel et Commercial
-Technologiques

BESOINS Programme Directeur de Production Calcul des

Besoins Nets
-Indépendants
(PDP) Manufacturing Resource Planning
-Dépendants Ordonnancement
(MRP)
Kanban

OPT Gestion / pilotage d’atelier

Plan Industriel et
Commercial (PIC)
 Plan Industriel et Commercial (PIC)
13

Le PIC est un contrat global entre le service Production

et le service Commercial.

La démarche qu’il propose repose sur l’établissement de

prévisions de vente et de production.

Remarque: les prévisions portent sur des familles plutôt

que sur des produits et des périodes relativement
longues..
 Plan Industriel et Commercial (PIC)
14

Le document du PIC comporte trois tableaux : Ventes, Production et Stocks.

Échéancier du PIC
Famille : Unité : Date :

VENTE M-3 M-2 M-1 M M+1 M+2 M+3 M+4

Prévisionnel
Réel
Écart
Écart en %

PRODUCTION M-3 M-2 M-1 M M+1 M+2 M+3 M+4

Prévisionnel
Réel
Écart
Écart en %
 Plan Industriel et Commercial (PIC)
15

STOCK M-3 M-2 M-1 M M+1 M+2 M+3 M+4

Prévisionnel
Réel
Écart
Écart en %

-------------
Objectif de stock : --------------
--------------
 Plan Industriel et Commercial (PIC)
16
Le document du PIC comporte trois tableaux : Ventes, Production et Stocks.
Échéancier du PIC
Famille : A Unité : K€ Date : 2 Avril

VENTE jan Fev Mar Avril Mai Juin Juillet Aout

Prévisionnel 500 500 500 500 500 510 510 520

Réel 510 510 510
Écart 10 10 10
Écart en % 2 2 2

510 – 500 = 10 soit 10/500 = 2 %

La production a dépassée ses prévisions

 Plan Industriel et Commercial (PIC)
17
Le document du PIC comporte trois tableaux : Ventes, Production et Stocks.
Échéancier du PIC
Famille : A Unité : K€ Date : 2 Avril

PRODUCTION jan Fev Mar Avril Mai Juin Juillet

Prévisionnel 490 500 510 520 520 520 520

Réel 480 490 490
Écart -10 -10 -20
Écart en % -2 -2 -4

490 – 510 = -20 soit -20/510 = - 4 %

La production n’a pas atteint ses prévisions

 Plan Directeur de Production (PIC)
18

STOCK jan Fev Mar Avril Mai Juin Juillet Aout

Prévisionnel 250 230 210 210 230 240 250 250

Réel 230 210 190
Écart -20 -20 -20
% d’objectif 92 84 76

Smar = Sfév + Pmar – Vmar = 210 + 490 – 510 = 190

190/250 = 76 % de l’objectif de stock
Le stock est actuellement tombé en dessous de la fourchette prévue
300
Objectif de stock : 250
200
Plan Directeur de
Production (PDP)
 Plan Directeur de Production (PDP)
20

Il établit une passerelle entre le Plan industriel et commercial et le Calcul

des besoins. C’est un contrat qui définit de façon précise l’échéancier des
quantités à produire pour chaque produit fini.
Les principales fonctions du PDP :
Il dirige le calcul des besoins en donnant les ordres de fabrication
pour les produits finis,
il induit l’explosion du calcul des besoins à travers les
nomenclatures.
Il concrétise le plan industriel puisqu’il traduit en produits finis réels
chaque famille du PIC.
Il met à disposition du service Commercial le disponible à vendre
 Il permet enfin de mesurer l’évolution du stock
 Plan Directeur de Production (PDP)
21
Le PDP est composé de deux zones :
 l’une est dite ferme, ou parfois gelée, à l’intérieur de laquelle les valeurs ne
sont pas modifiables, sauf intervention directe du gestionnaire de la production.
 l’autre zone est dite libre : en s’éloignant de la période actuelle, les valeurs
sont de moins en moins sûres et peuvent être remises en cause sans perturber la
production.
PDP Produit X Zone ferme Zone libre
Semaines 12 13 14 15 16 17 18 19 20
Ventes prévues
Commandes fermes
Livraisons attendues
(en début de semaine)
Stock
(en fin de semaine)
Besoins Nets

Ordres de fabrication :
– ordres fermes
– ordres suggérés
DAV (en début de sem.)
 Plan Directeur de Production (PDP)
22

PDP Produit X Zone ferme Zone libre

Semaines 12 13 14 15 16 17 18 19 20
Ventes prévues 0 0 10 30 30 50 40 60
Commandes fermes 60 40 40 30 10
Exemple

Livraisons attendues 100

(en début de semaine)
Stock
80
(en fin de semaine)
Besoins Nets

Ordres de fabrication :
– ordres fermes
– ordres suggérés
DAV (en début de sem.)
LES OF DOIVENT ETRE PAR LOT DE 100 SOUS 2 SEMAINES
 Plan Directeur de Production (PDP)
23

PDP Produit X Zone ferme Zone libre

Semaines 12 13 14 15 16 17 18 19 20
Ventes prévues 0 0 10 30 30 50 40 60
Commandes fermes 60 40 40 30 10
Exemple

Livraisons attendues 100 100 100 100

(en début de semaine)
Stock 80 120 80 30 70 30 80 40 80
(en fin de semaine)
Besoins Nets 30 20 20

Ordres de fabrication :
100 100 100
– ordres fermes
– ordres suggérés
DAV (en début de sem.)
 Plan Directeur de Production (PDP)
24

 Le PDP est souvent complété par une ligne supplémentaire,

appelée disponible à vendre ou DAV.
 Il correspond au nombre maximum de produits qui peut être
promis à un client sans impliquer une révision du PDP.
 Le DAV est calculé en début de période, et à chaque fois
qu’un OF est mis en stock.
 Le DAV s’obtient en réduisant du stock initial (auquel
s’ajoute une livraison attendue) le montant des commandes
fermes jusqu’à la prochaine livraison.
 Plan Directeur de Production (PDP)
25

PDP Produit X Zone ferme Zone libre

Semaines 12 13 14 15 16 17 18 19 20
Ventes prévues 0 0 10 30 30 50 40 60
Commandes fermes 60 40 40 30 10
Exemple

Livraisons attendues 100 100 100 100

(en début de semaine)
Stock 80 120 80 30 70 30 80 40 80
(en fin de semaine)
Besoins Nets 30 20 20

Ordres de fabrication :
100 100 100
– ordres fermes
– ordres suggérés
DAV (en début de sem.) 40 60 100
 Planification des Besoins-Matières
Material Requirements Planning (MRP)
LES DIFFERENTS BESOINS (rappel)
CLIENT CONSTRUCTEUR

Besoins indépendants Besoins dépendants

Prévus Calcul des besoins nets Calculés

27
 LE Calcul des Besoins Nets
28
Niveau 0 = produit fini
Besoins bruts Besoins bruts = Prévisions de
Niveau N ventes
et/ou en-commande
Affectation des stocks
et des en-cours

Besoins nets Ordre de fabrication / d’achats

Niveau N Niveau N

Eclatement
selon nomenclature

Besoins bruts
Niveau N+1
Affectation des stocks
et des en-cours N+1
Ordre de fabrication /
Besoins nets d’achats
Niveau N+1 Niveau N+1
Eclatement
selon nomenclature N+1
 MRP-OBJECTIF
29

Le Calcul des Besoins a pour

objectif de définir les besoins en
composants pour satisfaire la
consommation, sur une période
donnée, de produits finis
rassemblant ces composants.
 MRP-DESIGNATIONS SIMILAIRES
30

 M R P pour Material Requirements Planning

 Programmation des besoins en composants (P B C)
 Planification des Besoins-Matières (P B M)
 M R P 2 pour Manufacturing Ressource Planning
 Management des ressources de la production
 MRP-ORIGINE
31

C'est l'américain Joseph ORLIKY

qui, en 1965, décrivait le premier la
méthode du calcul des besoins qui est
la base de tous les logiciels MRP. Il
s'agissait du système de gestion des
nomenclatures développé par IBM et
connu sous l'appellation BOMP pour
Bill Of Material Processor.
 Élaboration d’un MRP : Intrants
32

● Les principaux intrants à la planification des besoins

matières sont :

– Le plan directeur de production (PDP)

– Les nomenclatures des produits

– Le fichier informatif sur l’état des stocks

 Élaboration d’un MRP : La nomenclature
33

Nomenclature : « Liste indiquant de façon hiérarchique et

exhaustive, le type et la quantité de matières premières et
d’autres composants nécessaires à fabrication du produit».

Signification de
cette nomenclature:
Niveau 0 X
Pour chaque x3 x2
produit X, il faut 3 Niveau 1
articles Y et 2
articles Z. Y Z
Pour chaque article Niveau 2 x2 x1
Z, il faut 2 articles W Y
W et 1 article Y.
Élaboration d’un MRP : La nomenclature
34

Produit fini

Traverses
Pieds avant

Barreau
Siège
Barreau
Pieds
arrières
 TABLEAU MRP

Rp Ni Cm
Période
BB
AD
BN
OP
 MRP-LEGENDES

BB : Besoin Brut ;
AD : Article Disponible ;
BN : Besoin Net ;
OP : Ordre Prévisionnel;
Rp : Repère de l'article ;
Ni : niveau de nomenclature;
Cm : Coefficient de montage avec indication de l'article
générateur du besoin;
D : Délai d'obtention de l'article;
 Les TABLEAUX MRP COMPRENNENT
37
 Besoin Brut: Demande
 Articles Disponibles: Quantité
disponible en stock
 Besoins Nets: Demande ajustée en
fonction de stocks
 Ordre Prévisionnels: On doit décider à
quel moment et en quelle quantité on
doit lancer les commandes d’achat ou
de fabrication de chacun des articles.
 MRP: METHODOLOGIE
38

1- Collecter les données :

 nomenclatures arborescentes (dites cascadées)
 plan directeur de production et / ou carnet de commandes
et si besoin,
 articles disponibles et en-cours non attribués
 délais d'obtention des articles
2- A chaque niveau de nomenclature depuis le niveau
supérieur,
POUR CHAQUE ARTICLE, A CHAQUE PERIODE CONSIDEREE,
1°/ Calcul du besoin brut,
2°/ Calcul du besoin net,
3°/ Définition de l'ordre prévisionnel (O.P.) envisagé
 pour satisfaire le besoin net exprimé et indiquant :
 la quantité d'unités de l'article
 la date de lancement.
 Exemple
39

A(1)
X1 X3

B(2) C(1)
X2 X1 X2 X1

D(1) E(1) B(2) F(1)

X2 X1 X1 X2

D(1) E(1) D(1) G(2)

Les commandes fermes à ce jour pour les machines A et le sous-ensemble B
sont les suivantes
Janvier Février Mars Avril Mai Juin
A 0 3 1 6 10 7
B 0 0 0 0 50 0
La capacité en place de permet que 100 unités par mois pour l’article D
 Le fournisseur de G exige de le vendre dans des de 100 unités.
Différentes techniques de lotissement
40

 Lot pour lot :

- On fabrique ou achète exactement la
quantité requise
- Évite d’avoir des produits en stock mais
néglige les coûts de commande

 Lot de taille fixe « X » : La

quantité fabriquée ou achetée est X
ou un multiple de X (ex.: douzaine,
caisse, palette, etc.)
Différentes techniques de lotissement

 Lot de taille minimale « X » : La

quantité fabriquée ou achetée est au
minimum X ; si le besoin net est
supérieur à X, on commande exactement
la quantité requise.

 Lot économique :
- On commande ou fabrique moins souvent, mais
de plus grandes quantités.
- Permet d’équilibrer les coûts de stockage et de
commande.
Le Plan du chapitre….
42

 P1: introduction

 P2: Pilotage par le flux Poussé

 P3: Pilotage par le juste à Temps JAT

 P4: Pilotage par les contraintes OPT

Le Juste à Temps
 JAT - La philosophie Juste à temps
44

 La philosophie du JAT remonte aux milieu

des années 50 où Ohno Taiichi, cadre chez
Toyota, eut l’idée de faire la superposition du
comportement d’un client d’un supermarché
américain sur leur planché de production à
l’usine.

 Sa vision s’est traduit par : « produire

seulement ce dont le clients a besoin au
moment voulu ».
 JAT - La philosophie Juste à temps
45

Le principe est le suivant : rendre le

traitement aussi court que possible en
utilisant les ressources de façon optimale.
 Éliminer les perturbations
 Rendre le système flexible
 Réduire les temps de mise en route
 Réduire les stocks au minimum
 Éliminer les pertes et les rejets
JAT - La philosophie Juste à temps
46
Pour atteindre les objectifs mentionnés, le
JAT doit répondre aux exigences suivantes :

une conception adéquate du produit

une conception de processus en conséquence

une gestion adaptative des ressources humaines

une planification et un contrôle de la production flexible

 JAT - DÉFINITION
47

Produire en juste à temps, c’est vouloir

travailler en flux tirés et parvenir à une
production orchestrée par la demande en
aval, c’est-à-dire par les livraisons à effectuer.

 Produits finis prêts juste à temps

pour être livrés;
 Sous-ensembles livrés juste à
temps à l’interne.
 Composantes fabriquées en J.A.T.
 Matières premières achetées et
livrées en J.A.T.
 JAT- FLUX POUSSE VS FLUX TIRE

48

PILOTAGE PAR LES

FLUX POUSSE FABRICATION PROGRAMMES

Prévisions
MRP
OA OF
Poste Poste Poste
FOURNISSEUR 1 2 3 CLIENT

PILOTAGE PAR LA
DEMANDE FABRICATION FLUX TIRE

Commande Kanban Kanban Demande

Poste Poste Poste

FOURNISSEUR 1 2 3 CLIENT
 FLUX TENDU ET JUSTE A TEMPS

49

REDUCTION
FLUX TENDU DES DELAIS DE CHASSE AUX
FABRICATION GASPILLAGE

SYNCHRONISATION DE LA
PRODUCTION AVEC LE MARCHE
POUR LE
POUR LE CLIENT
PROCESSUS
Fabriquer les
C’est organiser la
produits dont il a
production de telle
besoin (QUOI),
PRODUCTION EN JUSTE A manière que le client
quand il a besoin
TEMPS n’est pas besoin
(QUAND), dans les
d’attendre et que, pour
quantités exactes
le satisfaire, nous
demandées
n’ayons pas besoin de
(COMBIEN)
stocks
 Flux tendus (JAT): METHODES
50

 Ordonnancement à cours terme visant à limiter les stocks en

réglant la cadence de production par la consommation avale (flux
tirés)

 Atelier constitué de machines affectées à des lots répétitifs : le

flux est tiré en réglant la cadence de production d’une machine
amont par la demande provenant de l’aval.
 Méthode KANBAN
 Atelier constitué de machines indépendantes travaillant sur des
lots non répétitifs : le flux tiré se traduit par un flux de
lancement adapté à la cadence des machines les plus lentes
 Méthode OPT : gestion par les contraintes
 51

LA METHODE KANBAN
 KANBAN
52
 Le Kanban est une fiche ou une carte qui
accompagne chaque lot de pièces. C’est un
système de contrôle de fabrication. Il s’agit à la
fois d’une indication de fabrication et d’un ordre de
transport.
 Ce simple morceau de papier (ou sous autre
forme) est un important instrument de la
productivité d’une entreprise telle que Toyota.

* Le Kanban peut être représenté sous plusieurs moyen de

communication: fax, bar code, électronique, carte de plastique, etc.
 Étiquette KANBAN
53
• Informations minimales :
– référence de l’article fabriqué,
– capacité du container donc la quantité à produire,
– destination du container plein (poste aval ou stockage),
– provenance du container c.a.d. planning où doit être recyclé le ticket
(poste amont).

• Informations complémentaires :
– désignation de l’article fabriqué,
– nombre de containers du lot traité,
– emplacement sur le lieu de stockage du poste aval,
– trajet complet de l’article dans l’unité de production,
–position de l’index vert lors du lancement,
– position de l’index rouge lors du lancement,
– code à barre de l’article.
 PRINCIPE DE FONCTIONNEMENT
Je fabrique un conteneur,
j’y attache une carte 54

FLUX PHYSIQUE
Containers avec Kanban
FOURNISSEUR CLIENT

J’accumule les cartes sur J’ai vidé un conteneur, je

un tableau. C’est mon renvoie sa carte. C’est
carnet de commandes mon bon de commande

A B C

A B C
FLUX D’INFORMATION
A B C Etiquette Kanban
 LE Tableau d’Ordonnancement de la Production
55

TOP machine XXX Nombre total de Kanban

-Index Noir: Encours mini

Nombre minimum de
B
Kanbans
B Index Rouge: Le Lancement devient
obligatoire la pile atteint l’index rouge car
B
on risque une rupture d’approvisionnement
B C au poste aval.
A B C Lot mini de fabrication
A B C
Index Vert: Le lancement est interdit
A B C
lorsque la pile de kanbans rangés sur le
Produit Produit Produit planning n’atteint pas l’index vert.
A B C
 NOMBRE DE CARTE KANBAN
56
Nombre de Carte Kanban (K) – Production:

K = D (TA+ TB ) * ( 1 + SS ) / Q
OÙ :
D = Demande journalière moyenne durant le mois pour la pièce, déterminée
par horaire uniforme;
TB = Temps de production, incluant mise en course pour un contenant de
pièce, en jour de travail;
TA = Temps d’attente au centre de travail pour la carte d’aller et retour,
temps de transport, temps d’attente et temps de transfert, en jour de travail;
SS = Stock sécurité, pas plus de 10% de la demande journalière exprimée en
nombre de contenant ou, si le niveau de service demandé est de x % donc,
SS = ((1 / x) - 1 );
Q = Quantité d’unités dans un contenant, pas plus que 10% de la demande
journalière.
EXEMPLE 1 – NOMBRE DE KANBAN

 Une entreprise fabrique de façon régulière les

produits A,B,C,D et achète F.

A B C

X1 X1 X2
X2

C F D
C

• Cette entreprise, souhaitant fabriquer ces produits en ligne de

production pilotée par KANBAN,organise ses machines de la
façon suivante:
M3
M1 M2
M4
EXEMPLE 1– NOMBRE DE KANBAN

L’entreprise devant produire 20 produits A et 30 produits B par

jour, on vous demande alors de définir le nombre de kanbans à
mettre en place pour piloter la production entre le poste M1 et
M2.
La phase d’analyse a relevé les informations suivantes:
Le durée journalière de travail est de 8 heures.
Le Poste M1 fabrique les pièces D.
Le Poste M2 fabrique les pièces C.
Le Poste M3 fabrique les pièces A.
Le Poste M4 fabrique les pièces B.
EXEMPLE 1 – NOMBRE DE KANBAN

La fabrication de la pièce D nécessite 0.5 heure pour le

réglage du poste et 0.08 heure pour la fabrication unitaire.
Le transfert d’un Kanban peut se faire entre M1 et M2 en 5
minutes et les containers sont conçus pour contenir 10 pièces.
Le Temps de Transport des containers (Temps de transports
et d’attente) effectué par un chariot automoteur entre les postes
M1 et M2 est 15 minutes.
Le Taux de service est 92%, ce qui se traduit par un
coefficient de sécurité de (1/0.92 -1)
Calculer le nombre nécessaire de Kanbans de production
entre le poste M1 et M2.
Présenter le flux de production sous forme d’un schéma
 EXEMPLE 1 ( Solution)

A B C

X1 X1 X2
X2

C F D
C

20 A/Jour
M3
140 D/Jour 40 C/Jour Produit A
M1 M2
Produit D Produit C
30 B/Jour
30 C/Jour M4
Produit B

flux de production F
30 F/Jour
Le Plan du chapitre….
61

 P1: Introduction

 P2: Pilotage par le flux Poussé

 P3: Pilotage par le juste à Temps JAT

 P4: Pilotage par les contraintes OPT

 LA METHODE OPT
(Optimized Production
Technology)
 HISTORIQUE DE LA METHODE

63
- GOLDRATT (Le but - 1979)

- OBJECTIF : PROPOSER UNE NOUVELLE APPROCHE DE LA PLANIFICATION

ET DE L’ORDONNANCEMENT COMME UNE ALTERNATIVE
AUX METHODES :

 MRP (Positionne des OF sur des centres de charges mais ne

considère pas l’ordonnancement)

 KANBAN (Ordonnance les flux sans tenir compte des contraintes

globales du système de production)

PRINCIPE MAJEUR DE L’OPT TRAVAILLER SUR LES POSTES GOULETS CAR

CE SONT EUX QUI LIMITENT LA PRODUCTION
 QU’EST CE QU’UN GOULET ?

Matière Poste 1 Poste 2 Poste 3 Poste 4 Pièces

première Capacité Capacité Capacité Capacité finies
200 p/h 180 p/h 50 p/h 150 p/h

BESOIN CLIENT = 50 PIECES PAR

HEURES
BESOIN CLIENT = 100 PIECES PAR
HEURES
BESOIN CLIENT = 170 PIECES PAR
HEURES

GOULET = UNE RESSOURCE DE PRODUCTION

DONT LA CAPACITE NE PERMET PAS DE REPONDRE AUX

BESOINS DU MARCHE

64
 COMMENT DETECTER UN GOULET ?

E5 E1 E3 E4

E6 P1 E2 P2 P3 E6 P4

E7 E4 E6 E7
S S
RETARD A L’HEURE A L’HEURE RETARD

P1 et P4 ne sont jamais livrés à l’heure, ou est le goulet ?

E6 et E7 commun à P1 et P4.
E6 également commun à P3 jamais GOULET = E7
livré en retard
E7 uniquement commun à P1 et P4

STOCKS IMPORTANTS = GOULET POTENTIEL

65
 REGLE N°1 Equilibrer les flux et non les capacités

Equilibre des capacités

Poste 2.1
Capacité
50 p/h
Matière Poste 1 Poste 2 Poste 3 Pièce
Capacité Capacité Capacité
première 100 p/h 50 p/h 100 p/h s
Poste 2.2
Capacité finies
50 p/h

Stock 120 Stock 100

pièces pièces
SUR UNE JOURNEE DE 8H DE TRAVAIL, QUE SE
PASSE-T-IL SI :
1. Le poste 3 tombe en panne LES SOLUTIONS ?
pendant 1h ?
2. Le poste 2.2 ne produit que 70% de sa
capacité ?

UTILISER LES RESSOURCES TELLES QU’ELLES SONT

ADAPTER LE FLUX A LA DEMANDE PAR LA POLYVALENCE, LES HORAIRES…

66
 REGLE N°2 Le niveau d’utilisation d’un non goulet n’est
pas déterminé par son propre potentiel mais
par d’autres contraintes du système

Poste A Poste B
Capacité Capacité
Matière 100 p/h 120 p/h Pièces
première Production Production finies
100 p/h ?100 p/h

PRODUCTION
LIMITEE

67
 REGLE N°3
Utilisation et plein emploi d’une ressource ne
doivent pas être synonymes

Poste A Poste B Poste C Poste D

Matière Pièces
Capacité Capacité Capacité Capacité
première finies
200 p/h 120 p/h 100 p/h 150 p/h
Production Production Production Production
200p/h 120p/h 100p/h 100p/h
100
p/h
20 12 10
0 80 0 20 0

PRODUCTION
LIMITEE

Si l’on sature les ressources de production pendant 1 heure, que ce

passe-t-il ?

68
 REGLE N°4 Une heure perdue sur un goulet est une
heure perdue pour tout le système

Matière Poste A Poste B Poste C Poste D

Pièces
première Capacité Capacité Capacité Capacité
finies
200 p/h 120 p/h 100 p/h 150 p/h

Production Production Production Production

200p 120p 100p 100p
90 p 90 p

20 12 10
0 80 0 20 0

RUPTURE
D’APPROVISIONNEMENT
PRODUCTION LIMITEE
Si il y a une rupture dans l’approvisionnement de la ressource goulet, que ce
passe-t-il ?
69
 REGLE N°5 Une heure gagnée sur un non goulet n’est
qu’un leurre

Matière Poste A Poste B Poste C Poste D

Capacité Capacité Capacité Capacité Pièces
première 200 p/h 120 p/h 100 p/h 150 p/h
finies
Réglage Réglage
Réglage Réglage
Réglage Réglage
1h 2h
1h 0,5h
1h 1h

Production Production Production Production

1400 p 720 p 750pp
700 750pp
700
700 p

1400 720 700

680 840 20

140
SMED SUR
POSTE B
SUR UNE JOURNEE DE 8H DE TRAVAIL :
1. Combien produit-on de pièces sans changer les paramètres d’origine ?

2. Combien produit-on de pièces en gagnant 1h de réglage sur le poste B ?

3. Combien produit-on de pièces en gagnant 0,5h de réglage sur le poste
goulet ?
70
 REGLE N°6
Les goulets déterminent à la fois le débit de
sortie et les niveaux de stocks

Capacité
A
STOCKS
120
p/h
STOCKS B
120
p/h
C
STOCKS
80 p/h

80 p/h

PRODUCTION
LIMITEE
71
 Souvent le lot de transfert ne doit pas être
REGLE N°7 égal au lot de production

Matière Poste A Poste B Poste C Poste D Pièces

première Capacité Capacité Capacité Capacité finies
210 p/h 140 p/h 70 p/h 140 p/h

1. Lot de production = 140 pièces Lot de transfert = 140

pièces
Poste A
Poste B
Poste C
Poste D
2. Lot de production = 140 pièces Lot de transfert = 35
pièces
Poste A
Poste B
Poste C
Gain
Poste D
72
Réglage
 EN CONCLUSION

Il est impératif d’établir les programmes en

REGLE N°8 prenant en compte toutes les contraintes
simultanément

Les délais de fabrication (à ne pas confondre

avec les délais de livraison) sont le résultat
REGLE N°9 d’un programme et ne peuvent donc pas être
pré-déterminés²

73
 74

FIN CHAPITRE 2
 Chapitre 3
Ordonnancement de la
production
Le Plan du chapitre….
2

 P1: Introduction

 P2: Ordonnancement des Projets

 P3: Ordonnancement des Ateliers spécialisés

1. Introduction
 Qu’est ce que l’ordonnancement ?
4

 C’est la planification de l’exécution de la

production à très court terme.

 C’est la détermination de l’ordre de passage de

l’ensemble des travaux à réaliser pour la
production d’un bien ou d’un service.

 C’est 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.
 Qu’est ce que l’ordonnancement ?

L’ordonnancement est la dernière étape de la

planification de la production. Elle est
souvent la seule étape dans les PME.
Les étapes de l’ordonnancement

Planification
Contrôle

Affectation des tâches

Suivi
Détermination d’un ordre de
Relance
passage
Calendrier de fabrication

Exécution

Lancement
Les étapes de l’ordonnancement

 Affectation: répartition des commandes aux

divers postes de travail: qui fait quoi?
 Détermination d’un ordre de passage:
détermination de la séquence de traitement
des commandes à chaque poste de travail:
jalonnement

 Calendrier de fabrication: date et heure de

lancement des opérations à chaque poste de
travail.
Les étapes de l’ordonnancement

 Lancement: démarrage des opérations

selon le calendrier.

 Suivi: supervision de l’exécution et

vérification de l’adéquation avec la
planification.

 Relance: ajustements en fonction des

imprévus.
Le jalonnement

Pour faire le jalonnement (ou la séquence de

traitement), il faut deux choses:

1 . Des objectifs (critères de performance)

2. Des règles de décision (règles de priorité)

Critères de performance les plus utilisés

1. Le coût total de mise en route

2. La quantité de produits en cours
3. Le taux d’utilisation des équipements
4. Le retard moyen des commandes
5. Le % de commandes en retard
6. Le temps total de production

Les critères de performance servent à

établir dans quelle mesure le jalonnement
est efficace.
Les règles de priorité
C’est une façon d’établir un ordre de passage des commandes en attribuant une
valeur relative (priorité) à chacune des commandes afin de les classer par ordre
croissant ou décroissant de valeur.
PODA :Par Ordre D’Arrivée ALE: prise de manière Aléatoire

TOC: par ordre du Temps RC: ayant le Ratio Critique le plus faible (le
d’Opération (le plus Court en nombre de jours jusqu’à la date d’exigibilité
premier) divisé par le nombre de jours de traitement)
MTO: nécessitant le Moins de
Temps d’Opération pour être
terminée.
DLR : par ordre de Livraison; la FDAC: dont la File D’Attente pour
Date la plus Rapprochée en l’opération est la plus Courte
premier ( Date de Livraison
Minimale : DLM)
MLM: Marge Libre Minimale COTE: dont le ratio suivant est le plus élevé
(nombre de jours jusqu’à la date pour une opération donnée: le COût du
d’exigibilité moins le temps délai divisé par le TEmps requis
opératoire d’une commande)
2. Ordonnancement des
projets
La production par Projet
13

Dans le cas de la production par projet, le produit est unique. Des exemples en
sont l’organisation des Jeux Olympiques ou la construction d’un barrage. Le
processus de production y est unique et ne se renouvelle pas.
 La quantité produite est faible, souvent unitaire.
 Le délai de fabrication est généralement impératif et son non respect peut
entraîner des pénalités de retard.
 Le projet est constitué d'un grand nombre d'opérations exécutées en
séquence ou en parallèle, mais qui sont souvent interdépendantes
(antériorités entre elles).
 Les ressources humaines et matérielles sont souvent hétérogènes car
elles proviennent d'entreprises ou de services différents.
 Un projet a un début et une fin.
La production par Projet
14

Production par projet

Les Méthodes
15

Il existe trois méthodes d’ordonnancement :

La méthode de Gantt

La méthode MPM (Méthode des Potentiels Métra)

La méthode PERT (Program Research Technic).

3. ORDONNANCEMENT EN ATELIERS
SPÉCIALISÉS
3.1 ATELIERS SPÉCIALISÉS: TERMINOLOGIES
17

On parle d’ateliers spécialisés lorsque l’ensemble des

équipements nécessaires pour assurer une fonction
déterminée sont rassemblés dans un même atelier.

flow Job Open

shop shop shop
3.1 ATELIERS SPÉCIALISÉS: TERMINOLOGIES
18

Flow shop: Lorsque l’ordre de passage d’un ensemble de tâches sur un

même ensemble de centres de production est toujours le même. On parle
encore de structure de type « flux unidirectionnel» en ce sens que, sur
tous les centres de production, l’ordre d’exécution reste le même; on trouve
encore, dans la littérature française le terme d’atelier à cheminement
unique.
.

Flow shop
3.1 ATELIERS SPÉCIALISÉS: TERMINOLOGIES
19

Dans un flow shop , le temps opératoire de certaines opérations pouvant

être nul, on peut alors décrire un flow shop quelconque à m centres de
production:
- Les entrées directes sur un centre de production de rang supérieur à 1
s’expliquent par des temps opératoires nuls sur tous les centres de
production précédents;
- Les sorties directes antérieurement au dernier centre de production
s’expliquent par des temps opératoires nuls sur tous les centres de
production suivants;
- Un temps opératoire nul entre le centre de production d’entrée et celui de
sortie conduit, en pratique, à «sauter» ce centre de production.
3.1 ATELIERS SPÉCIALISÉS: TERMINOLOGIES
20

Ce tableau fournit un exemple de données d’un problème de flow shop

avec dix OF (ordre de fabrication): l’OF 5 commence directement sur la
machine C; l’OF 7 sort de l’atelier après exécution de l’opération sur la
machine C; la machine B est «sautée» par les OF 9 et 10.
3.1 ATELIERS SPÉCIALISÉS: TERMINOLOGIES
21
Job shop: On réserve le terme de job shop pour le cas général d’une coexistence
de très nombreux cheminements des flux de production dans un même système
productif. On trouve encore, dans la littérature française, le terme d’atelier à
cheminements multiples.

In A B
Out
P1
P2
P3
D P1 goes: A->B->C->D Out
P4 C
P2 goes: B->C->B->D Out
P3 goes: A->C->D->B Out
P4 goes: A->B->B->C Out
3.1 ATELIERS SPÉCIALISÉS: TERMINOLOGIES
22
Open shop: atelier à cheminements libres dans lesquels les opérations des
tâches à exécuter sur un ensemble de centres de production différents peuvent
l’être dans un ordre quelconque.

J1 M1 M2 M3 OUT

J2 M1 M2 M3 OUT

J3 M3 M2 M1 OUT

J4 M2 M1 M3 OUT
3.1 ATELIERS SPÉCIALISÉS: TERMENOLOGIES
23

Résoudre un problème d’ordonnancement, c’est définir où et

à quel moment précis un certain nombre de tâches doivent
être réalisées.

Chaque tâche se décompose en un certain nombre

d’opérations dans des centres de production. Selon le
problème examiné, un centre de production peut être aussi
bien une usine, un département de production, un atelier,
un groupe de machines ou une machine.
3.1 ATELIERS SPÉCIALISÉS: TERMENOLOGIES
24

Parmi les modèles d’ordonnancement en ateliers spécialisés,

on distingue

Statique Dynamique
- toutes les commandes sont
- se fait une fois par période considérées au fur et à
mesure.
- nouvelle commande = - nécessite techniques +
changement de complexes (file d’attente et
l’ordonnancement simulation)
3.2 MODÈLES STATIQUES D’ORDONNANCEMENT
25

 3.2.1 Modèles statiques : Cas des coûts de lancement indépendants de

l’ordonnancement retenu

 3.2.2 Modèles statiques: cas du coût de lancement total variable avec

l’ordonnancement retenu
3.2.1 Modèles statiques : Cas des coûts de lancement indépendants de
l’ordonnancement retenu
26

 Les coûts de lancement sont indépendants de

l’ordonnancement retenu.

 Le problème général est à n tâches et m centres de production.

Hypothèses :
o L’ordre technique de passage des tâches sur les centres de
production est intangible.

o Les temps de transport et de lancement sont nuls

o Les temps opératoires sont certains, une opération ne peut

commencer que si la précédente est terminée.
3.2.1 Modèles statiques : Cas des coûts de lancement indépendants de
l’ordonnancement retenu
27
3.2.1.1 Ordonnancement de n tâches nécessitant l’intervention d’un seul
centre de production

3.2.1.2 Ordonnancement de n tâches nécessitant l’intervention de 2

centres de production

3.2.1.3 Ordonnancement de 2 tâches nécessitant l’intervention de m

centres de production

3.2.1.4 Ordonnancement de n tâches nécessitant l’intervention de m

centres de production

3.2.1.5 Ordonnancement de n tâches nécessitant l’intervention de m

centres de production (cheminement libre – open shop)

3.2.1.6 Ordonnancement de n tâches nécessitant l’intervention de m

centres de production (ordre de passage quelconque)
3.2.1.1 Ordonnancement de n tâches nécessitant l’intervention d’un seul centre de
production

28

 Ce cas de figure est simple.

 Quel que soit l’ordonnancement choisi, le temps
nécessaire pour réaliser les n tâches est le même.

On examinera donc les conséquences de

plusieurs règles d’ordonnancement sur certains
indicateurs permettant de juger la qualité de
l’ordonnancement choisi, dans une optique donnée.
3.2.1.1 Ordonnancement de n tâches nécessitant l’intervention d’un seul centre de
production

29
A) L’ordonnancement suivant la règle du Temps Opératoire Minimum (TOM)
Supposons que pour la période à venir, 5 tâches, toutes disponibles, soient à
exécuter sur le centre de production A. Le centre de production est réputé
disponible le temps nécessaire.

 Supposons que l’ordonnancement retenu soit le suivant: tâche 3, puis tâche 4,

puis tâche 1, puis tâche 5, puis tâche 2.
 On notera j le numéro d’ordre de passage du travail ;
A) L’ordonnancement suivant la règle du Temps Opératoire Minimum (TOM)

30

Si l’exécution des 5 tâches nécessite 510 centièmes d’heures quel que soit
l’ordonnancement retenu, l’ordre de passage de ces tâches a des
conséquences sur le moment à partir duquel chaque tâche est terminée.
Notons Aj, le moment à partir duquel la tâche programmée en jème
position est terminée.
A) L’ordonnancement suivant la règle du Temps Opératoire Minimum (règle TOM)

31
A) L’ordonnancement suivant la règle du Temps Opératoire Minimum (règle TOM)

32
B) L’ordonnancement suivant la règle du Temps Opératoire Minimum (TOM) pondéré

33

 Dans la pratique, les travaux à effectuer peuvent ne pas tous présenter le

même intérêt (articles en rupture de stock, commandes urgentes, etc.). On peut
alors introduire un coefficient ui (ui ≥ 1) traduisant la priorité accordée à la
tâche i. On cherche alors à minimiser le temps d’attente moyen pondéré.
 Le temps d’attente moyen pondéré est obtenu en donnant la priorité la plus
forte à la tâche qui a le plus faible quotient du temps opératoire au coefficient de
pondération. Cette règle récurrente, que l’on désignera sous le nom de règle
TOM pondéré, (règle de Smith) est donc:
B) L’ordonnancement suivant la règle du Temps Opératoire Minimum (TOM) pondéré

34

Calcul du temps d’attente moyen pondéré

Tj
C) Ordonnancement suivant la règle de la date de livraison minimale

35

 Un cas fréquent dans la pratique est celui d’une date maximale souhaitée pour
la fin de l’exécution d’une ou de plusieurs tâches.
 Le plus souvent, aucun ordonnancement ne permet de satisfaire
simultanément toutes ces dates de livraison et un arbitrage doit être effectué.
C) Ordonnancement suivant la règle de la date de livraison minimale

36
Calculons les conséquences de l’ordonnancement TOM sur les retards de
livraison, avant de présenter d’autres règles d’ordonnancement.
C) Ordonnancement suivant la règle de la date de livraison minimale

37

si on adopte l’ordonnancement programmant les tâches selon les dates

croissantes de livraison (règle de Jackson).

Cet ordonnancement minimise le plus grand retard possible, mais il ne

minimise pas le retard moyen
D) Ordonnancement suivant la règle de la marge minimale

38
Elle consiste à programmer les tâches par valeurs croissantes de leurs marges
(di – ti), les tâches ayant la plus faible marge étant supposées offrir le plus grand
risque d’être en retard.

Un tel ordonnancement ne conduit ni à une minimisation du retard moyen

ni à une minimisation du retard maximum.
3.2.1.2 Ordonnancement de n tâches nécessitant l’intervention de 2 centres de
production

39
 Chaque tâche comporte maintenant deux opérations distinctes
effectuées par 2 centres de production différents.

 Il faut distinguer deux cas de figure: celui où l’ordre de passage des

tâches est le même sur les 2 centres de production, et celui où l’ordre
technologique diffère selon les travaux.

Le seul critère que l’on retiendra pour juger de la performance de

l’ordonnancement est celui de la minimisation du temps total d’exécution de
tous les travaux.
A) Cas du même ordre de passage sur les centres de production A et B

40

 Le problème traité ici est un problème de flow shop à 2 centres de production.

 Supposons que cinq tâches soient à exécuter successivement sur les centres de
production A et B.

L’ordonnancement qui minimise le temps d’exécution de tous les travaux se

trouve en utilisant l’algorithme de Johnson
A) Cas du même ordre de passage sur les centres de production A et B

41
- Étape 1 : rechercher la tâche i dont le temps d’exécution tij (avec j = A ou B)
est le plus faible possible.
- Étape 2 : si j = A placer cette tâche à la première place disponible en début
de la séquence d’ordonnancement; si j = B placer cette tâche à la dernière
place disponible.
- Étape 3 : supprimer la tâche i des tâches restant à programmer; s’il reste
plus d’une tâche à programmer, revenir en étape 1 ; s’il n’en reste qu’une, sa
position est imposée puisqu’il ne reste plus dans le tableau d’affectation qu’une
seule place à prendre.
A) Cas du même ordre de passage sur les centres de production A et B

42

L’ordonnancement optimal permet de gagner 20/100 d’heure sur la date

de fin d’exécution de tous les travaux, ce qui correspond à l’économie de
temps réalisée sur l’utilisation du centre de production B.
B) Cas de la non-unicité de l’ordre de passage sur les centres de production A et B

43

Algorithme de Jackson
B) Cas de la non-unicité de l’ordre de passage sur les centres de production A et B

44
3.2.1.3 Ordonnancement de 2 tâches nécessitant l’intervention de
m centres de production

45

 Ce cas concerne 2 tâches ne suivant pas la même séquence d’opérations

(problème de job shop), mais utilisant le même nombre de centres de production.
Supposons que 5 centres de production, repérés par les lettres A à E, soient
nécessaires pour réaliser la tâche 1 (dans l’ordre suivant: D, B, E, A, C) et la
tâche 2 (dans l’ordre technique suivant A, B, C, D, E).
3.2.1.3 Ordonnancement de 2 tâches nécessitant l’intervention de
m centres de production

46
On établit un graphique sur les axes duquel le montant cumulé du travail
accompli de chacune des tâches (l’axe vertical pour la tâche l et l’axe horizontal
pour la tâche 2, ou l’inverse) est repéré. On commence par placer sur ces axes
les temps passés sur chaque centre de production, dans l’ordre imposé
techniquement.
Dans cet espace à 2 dimensions, on représente par des rectangles rouges les
incompatibilités liées à la demande simultanée d’un même centre de production
par les 2 tâches à effectuer.
3.2.1.3 Ordonnancement de 2 tâches nécessitant l’intervention de
m centres de production

47
Une programmation réalisable se visualise par une ligne brisée partant de
l’origine 0 des axes, au point 0’ (repérant la fin simultanée des 2 travaux), et ne
comportant que:
- des segments verticaux (seule la tâche 1 est en cours d’exécution),
- des segments horizontaux (seule la tâche 2 est en cours d’exécution)
- et des segments à 45° avec les axes (exécution simultanée des 2 tâches).
3.2.1.4 Ordonnancement de n tâches nécessitant l’intervention de m centres de
production

48
A) Ordonnancement de n tâches nécessitant l’intervention de 3 centres de production
(ordre identique de passage)
 Dans certains cas particuliers un problème d’ordonnancement sur 3 centres de
production se ramène à un problème d’ordonnancement sur 2 centres de
production. C’est le cas où le centre de production B, qui, techniquement, doit
intervenir avant le centre de production C et après le centre de production A, est
complètement dominé par l’un ou l’autre de ces 2 centres de production, c’est-à-
dire que le plus grand temps d’exécution tiB est plus faible (ou égal) que le plus
petit temps d’exécution observé sur le centre de production qui le domine.

Lorsque ce cas se produit, on reformule le problème en un problème à 2

centres fictifs de production, le premier groupant les centres de production A et B
en un centre de production virtuel noté {AB} (avec un temps opératoire tiAB = tiA
+ tiB) et le second groupant les centres de production B et C en un centre de
production virtuel noté {BC} (avec un temps opératoire tiBC = tiB + tiC).
3.2.1.4 Ordonnancement de n tâches nécessitant l’intervention de m centres de
production

49
A) Ordonnancement de n tâches nécessitant l’intervention de 3 centres de production
(ordre identique de passage)

L’application de l’algorithme de Johnson sur les données permet de

déterminer l’ordonnancement optimal sur les 3 centres de production: tâches
3, 1, 2, 5 et 4;
3.2.1.4 Ordonnancement de n tâches nécessitant l’intervention de m centres de
production

50
A) Ordonnancement de n tâches nécessitant l’intervention de 3 centres de production
(ordre identique de passage)
3.2.1.4 Ordonnancement de n tâches nécessitant l’intervention de m centres de
production
A) Ordonnancement de n tâches nécessitant l’intervention de 3 centres de production
(ordre identique de passage)
51

 Lorsque les conditions imposées pour se ramener au cas de 2 centres

de production ne sont pas exactement satisfaites, la solution optimale ou
une solution à performance voisine peut être trouvée en utilisant cette
procédure.

L’algorithme de Johnson reste optimal si quelle que soit la tâche i, on a

tiB ≤ tiA et tiB ≤ tiC.

 Le cas général du problème à 3 centres de production a toutefois une

solution optimale en appliquant l’un des algorithmes utilisés en
programmation linéaire en nombres entiers, et qui est connu sous le nom
de branch and bound ;
B) Ordonnancement de n tâches nécessitant l’intervention de m centres de production
(ordre identique de passage identique)

52

B-1: Le modèle de base

B-2: Ordonnancement de n tâches nécessitant l’intervention de

m centres de production (ordre identique de passage –sans
attente )
B-1: Le modèle de base
53

 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).

 Prenons le cas de 5 centres de production repérés dans leur ordre

d’intervention par les lettres A à E, il faut résoudre les 4 problèmes suivants
: {A} – {E};{AB} – {DE};{ABC} – {CDE};{ABCD} – {BCDE}.
B-1: Le modèle de base
54
B-1: Le modèle de base
55
Le premier problème fictif (machines A et D) conduit à l’ordre 6 – 3 – 4 – 2 – 5 – 1.
 B-2: Ordonnancement de n tâches nécessitant l’intervention de
m centres de production (ordre identique de passage –sans
attente )
56
Dans certaines industries (industries alimentaires notamment), les opérations de
chaque tâche doivent s’enchaîner sans attente et tous les centres de production
sont utilisés (autrement dit, il n’y a pas de temps opératoire nul).

Si l’on considère deux tâches i et j programmé l’une après l’autre au plus tôt, il est
évident qu’une fois programmé i de telle sorte que ses opérations s’enchaînent
sans attente, il convient, pour que toutes les opérations de la tâche J s’enchaînent
également sans attente et que cette tâche s’achève au plus tôt.
B-2: Ordonnancement de n tâches nécessitant l’intervention de
m centres de production (ordre identique de passage –sans
attente )
57
B-2: Ordonnancement de n tâches nécessitant l’intervention de
m centres de production (ordre identique de passage –sans
attente )
58

La durée d’exécution totale des tâches dans une programmation au plus tôt sans
attente (43) est la somme des opérations (2 + 3 + 4 = 9) de la dernière tâche (5) et
des décalages successifs de la séquence de tâches antérieurement programmées
({4 + 10} + {3 + 0} + {5 + 3} + {2 + 7} = 34).

Ce type de problème trouve une solution avec l’algorithme de Little

Le problème d’ordonnancement posé pouvait être considéré comme équivalent à

un problème de création d’une tournée de voyageur de commerce qui doit visiter
chaque ville d’un ensemble, une fois et une seule, et revenir dans la ville de
départ, qui peut être quelconque ; Il faut alors, en gardant cette analogie:
B-2: Ordonnancement de n tâches nécessitant l’intervention de
m centres de production (ordre identique de passage –sans
attente )
59
- Créer une ville fictive de départ Alpha avec une distance nulle avec chacune des
villes j et une interdiction de se rendre dans la ville Alpha; ceci correspond à la
création d’une tâche fictive α avec les décalages minimaux suivants avec les
autres tâches:

- Créer une ville fictive Oméga de destination finale, distante de chaque ville i
mais avec interdiction de partir d’Oméga vers une ville autre qu’Alpha; ceci
correspond à la création d’une tâche fictive ω avec un décalage minimal avec
une tâche i, autre que la tâche α, égal au cumul décalage minimaux par rapport à
i dans les m centres de production :

- La distance entre deux villes quelconques autres qu’Alpha et Oméga est

égale au décalage minimal cij.
B-2: Ordonnancement de n tâches nécessitant l’intervention de
m centres de production (ordre identique de passage –sans
attente )
60

La solution optimale étant α→4→1→3→2→5→ω, pour une durée totale de 33

3.2.1.5 Ordonnancement de n tâches nécessitant l’intervention de m
centres de production (cheminement libre – open shop)

61
Si deux centres de production seulement sont mobilisés, on démontre que
l’ordonnancement minimisant la durée d’achèvement de l’ensemble des tâches est
obtenu en appliquant la règle LAPT (Longest Alternate Processing Time first)
qui consiste à sélectionner, sur le centre de production libre, l’opération de plus
grande durée sur l’autre centre. Dans l’application de cette règle, les tâches dont
une opération a été réalisée ont la même priorité, la plus faible, et, lorsque ces
dernières sont considérées, elles le sont de manière arbitraire.
3.2.1.5 Ordonnancement de n tâches nécessitant l’intervention de m
centres de production (cheminement libre – open shop)

62

L’application de la règle LAPT conduit aux étapes suivantes:

-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 centre
libres);

-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);

- 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);
3.2.1.5 Ordonnancement de n tâches nécessitant l’intervention de m
centres de production (cheminement libre – open shop)

63

- 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);
-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);
- 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), 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;
-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. Le travail est donc achevé en t = 480.
3.2.1.5 Ordonnancement de n tâches nécessitant l’intervention de m
centres de production (cheminement libre – open shop)

64

Lorsqu’il y a plus de 2 centres de production, on peut

utiliser des heuristiques, lesquelles ne garantissent
pas l’optimum. 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.
3.2.1.6 Ordonnancement de n tâches nécessitant l’intervention de m
centres de production (ordre de passage quelconque)

65

Ce cas général que l’on a qualifié de problème de job shop, se

caractérise par le fait que l’ordre de passage entre les centres de
production varie d’une tâche à l’autre et que, pour une même tâche,
certains centres de production peuvent être utilisés plusieurs fois et
d’autres pas.

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é.

On présentera ici une démarche heuristique donnant de bons résultats

3.2.1.6 Ordonnancement de n tâches nécessitant l’intervention de m
centres de production (ordre de passage quelconque)

66

 On commence par détecter le centre de production qui constitue un goulot

d’étranglement. (dans notre exemple, c’est la machine C).
 On considère qu’en amont et en aval de ce goulot, on est à capacité infinie,
ce qui revient à dire que les opérations de chacune des tâches peuvent
s’exécuter au plus tôt, aucun conflit dans l’utilisation d’une même machine
n’étant censé arriver. Ceci revient à considérer que:
3.2.1.6 Ordonnancement de n tâches nécessitant l’intervention de m
centres de production (ordre de passage quelconque)

67
 Avant le goulot, le travail s’effectue sur une machine fictive sur laquelle sont
réalisées toutes les opérations antérieures, pour une durée égale à la somme
des durées.

 Après le goulot, le travail s’effectue sur une machine fictive sur laquelle sont
réalisées toutes les opérations postérieures, pour une durée égale à la somme
des durées.

Les tâches qui n’utilisent pas ce centre critique peuvent être fusionnées dans
cet ensemble ou traitées à part, une fois réalisé l’ordonnancement des tâches
utilisant ce goulot d’étranglement;
3.2.1.6 Ordonnancement de n tâches nécessitant l’intervention de m
centres de production (ordre de passage quelconque)

68

 On cherche alors à résoudre le problème du goulot d’étranglement, en partant

des dates d’arrivées qui viennent d’être calculées et, le cas échéant, en tenant
compte des dates de livraison rectifiées comme on vient de l’indiquer. Ce
problème à résoudre porte sur une machine unique. La règle TOM peut être
utilisée ;
3.2.1.6 Ordonnancement de n tâches nécessitant l’intervention de m
centres de production (ordre de passage quelconque)

69

• en T = 0: chargement de la tâche 3 immédiatement disponible (durée

8);
• en T = 5: arrivée de la tâche 1 (durée 7);
• en T = 7: arrivée de la tâche 5 (durée 15);
• en T = 8: fin de la tâche 3, libération de la machine C; arrivée de 2
(durée 10); chargement de 1 (en application de la règle TOM, les
tâches 1 et 5 étant candidates);
• en T = 9: arrivée de 4 (durée 6);
• en T = 15: fin de la tâche 1, libération de la machine C; chargement
de la tâche 4 (en application de la règle TOM, les tâches 4 et 5 étant
candidates);
• en T = 21: fin de 4, libération de la machine C; chargement de la
tâche 2 (en application de la règle TOM, les tâches 2 et 5 étant
candidates);
• en T = 31: fin de la tâche 2, libération de la machine C; chargement
de la tâche 5 (candidat unique);
• en T = 46: fin de la tâche 5.
3.2.1.6 Ordonnancement de n tâches nécessitant l’intervention de m
centres de production (ordre de passage quelconque)

70

On cherche ensuite à résoudre le problème des centres situés en

amont du goulot, en prenant comme dates de livraison celles retenues
pour définir les arrivées dans le goulot (autrement dit, celles reposant
sur l’hypothèse de la capacité infinie du «système productif amont»).
Là encore, plusieurs règles sont possibles (notamment la règle
S/OPN), en cas de conflit dans la mobilisation d’une ressource, la
tâche devant débuter le plus tôt sur le goulot (critère de la date de
livraison minimale).

S/OPN: La règle d’ordonnancement du quotient de la marge (=

temps restant avant la livraison, diminué du cumul des temps
opératoires restant à réaliser) par le nombre d’opérations restant à
exécuter, est plus connue sous son sigle anglosaxon S/OPN (pour
Slack/Operation) ; elle préconise de sélectionner la commande
ayant la valeur la plus faible de ce ratio.
3.2.1.6 Ordonnancement de n tâches nécessitant l’intervention de m
centres de production (ordre de passage quelconque)

71
Les dates de fin des tâches sur le goulot sont ensuite considérées comme les
dates d’arrivées dans le système-aval; un ordonnancement est alors calculé en
utilisant des règles de priorité. Si certaines machines se retrouvent
simultanément en amont et en aval du goulot (dans notre exemple, c’est le cas
de la machine B, à cause de la tâche 4), il convient de considérer comme non
révisable la programmation décidée en amont du goulot (sauf acceptation d’une
nouvelle itération).
3.2.2 Modèles statiques : cas du coût de lancement total variable avec
l’ordonnancement retenu
72
Nous n’examinerons ici que le cas de n tâches nécessitant l’intervention d’un seul
centre de production (m = 1) et pour lequel l’ordre de passage influe sur les coûts
de lancement. Prenons l’exemple d’une usine de peinture : différentes couleurs de
peinture sont produites en séquence sur le même équipement, lequel doit être
soigneusement nettoyé lorsque l’on change de couleur.
3.2.2 Modèles statiques : cas du coût de lancement total variable avec
l’ordonnancement retenu
73
Le problème posé revient à trouver l’ordre de passage qui minimise le temps total
de nettoyage. On peut, bien sûr, trouver une solution à ce problème en explicitant
toutes les combinaisons possibles au nombre de (n – 1) ! = 3! = 6

Mais cette technique n’est envisageable que si le nombre m de tâches est faible:
pour 6 couleurs seulement, le dénombrement conduit à 120 comparaisons du
résultat de 6 additions.
3.2.2 Modèles statiques : cas du coût de lancement total variable avec
l’ordonnancement retenu
74
 Pour résoudre ce problème, une analogie pourrais être faite avec celui du
voyageur de commerce pour lequel un algorithme de résolution efficace a été
trouvé (Algorithme de Little) . Dans ce problème, le voyageur de commerce quitte
une ville de départ et doit visiter au cours d’une tournée, m – 1 villes différentes,
en n’y passant qu’une fois, avant de retourner à la ville de départ, et cherche à
minimiser son coût de transport. Ce coût de transport Cij entre une ville i et une
ville j est de même nature que le coût de lancement de la tâche j lorsque celle-ci
succède à la tâche i.
 Sur le plan formel, le problème du voyageur de commerce peut se formuler
sous la forme du programme linéaire suivant, où xij est une variable susceptible
de prendre seulement les valeurs 0 ou 1, la valeur 0 signifiant que le voyageur de
commerce ne part pas de la ville i pour se rendre à la ville j, la valeur l ayant la
signification contraire.
3.2.2 Modèles statiques : cas du coût de lancement total variable avec
l’ordonnancement retenu
75
L’algorithme de résolution d’un programme linéaire en nombres entiers le plus
utilisé pour cette classe de problèmes est sans aucun doute celui connu du
branch and bound
3.2.2 Modèles statiques : cas du coût de lancement total variable avec
l’ordonnancement retenu
76
3.2.2 Modèles statiques : cas du coût de lancement total variable avec
l’ordonnancement retenu
77
3.2.2 Modèles statiques : cas du coût de lancement total variable avec
l’ordonnancement retenu
78
3.2.2 Modèles statiques : cas du coût de lancement total variable avec
l’ordonnancement retenu
79
3.2.2 Modèles statiques : cas du coût de lancement total variable avec
l’ordonnancement retenu
80
3.2.2 Modèles statiques : cas du coût de lancement total variable avec
l’ordonnancement retenu
81
3.2.2 Modèles statiques : cas du coût de lancement total variable avec
l’ordonnancement retenu
82
3.2.2 Modèles statiques : cas du coût de lancement total variable avec
l’ordonnancement retenu
83
3.2.2 Modèles statiques : cas du coût de lancement total variable avec
l’ordonnancement retenu
84
3.2.2 Modèles statiques : cas du coût de lancement total variable avec
l’ordonnancement retenu
85

Analyse des décisions prises à la sixième itération

 86

FIN CHAPITRE 3