Planification de la production : MRP et règles d'ordonnancement
Planification hiérarchique et MRP, optimalité de SPT et d'EDD démontrée par échange, règle de Johnson pour deux machines avec un exemple et optimalité démontrée.
https://www.electronics-engineering.com/fr/planification-de-la-production-mrp-spt-edd-regle-de-johnson/
Une usine doit décider chaque jour quoi produire, en quelles quantités et dans quel ordre sur les machines. La planification de la production traduit les commandes et les prévisions en plans, et l’ordonnancement établit la séquence des travaux. Dans cette leçon, nous regardons la planification hiérarchique et la logique MRP, les règles de séquencement sur une machine avec les démonstrations de l’optimalité de SPT et d’EDD, et la règle de Johnson pour deux machines avec un exemple dont l’optimalité est démontrée.
De la planification au séquencement
La planification procède par niveaux, avec des horizons de plus en plus courts :
- le plan agrégé (mois) : capacité, équipes, niveaux de stock par famille de produits ;
- le programme directeur de production (PDP, semaines) : quels produits finis, combien et quand ;
- la planification des besoins en composants (MRP) : à partir du PDP et de la nomenclature (la liste des composants de chaque produit, niveau par niveau), on calcule pour chaque composant les quantités nettes à produire ou à acheter, en soustrayant les stocks disponibles, avec les dates de lancement des ordres, avancées du délai d’obtention ;
- l’ordonnancement (jours, heures) : la séquence des travaux sur chaque ressource.
Une voiture a des milliers de composants ; une carte électronique des centaines. Calculer les besoins à la main serait impossible : le MRP a été l’une des premières grandes applications des ordinateurs dans l’entreprise, et il est le cœur des systèmes ERP.
Une machine : SPT et EDD
travaux doivent être traités sur une machine, avec des durées
et des dates d’échéance
. Des règles différentes optimisent des objectifs différents.
Théorème (SPT). Traiter les travaux par ordre de durée croissante (shortest processing time) minimise le temps moyen d’achèvement.
Démonstration. C’est le même argument d’échange que pour l’ordonnancement du processeur (leçon de Systèmes d’exploitation sur l’ordonnancement) : si deux travaux consécutifs sont dans l’ordre « long avant court », les échanger avance la fin du court de la durée du long et retarde celle du long de la durée du court, donc la somme diminue ; les autres travaux ne changent pas. L’optimum n’a aucune inversion. ∎
Théorème (EDD). Traiter les travaux par ordre d’échéance croissante (earliest due date) minimise le retard maximal
.
Démonstration. Considérons deux travaux consécutifs
et
avec
et
avant
, commençant à l’instant
et finissant tous deux avant
. Avant l’échange,
finit en
, avec le retard
, le plus grand des deux (parce que
finit avant
et a une échéance plus tardive). Après l’échange,
finit avant
, et
finit en
avec le retard
. Le maximum des deux n’augmente pas, et les autres travaux ne changent pas. En supprimant les inversions une à une, on arrive à l’ordre EDD sans rien perdre. ∎
Aucune des deux règles n’est bonne pour tout : SPT peut faire attendre longtemps les travaux longs ; EDD ignore les durées. Pour minimiser le nombre de travaux en retard, il existe un algorithme dédié (Moore-Hodgson) ; pour des objectifs plus complexes, les problèmes deviennent vite intraitables et l’on utilise des heuristiques.
Deux machines : la règle de Johnson
Chaque travail passe d’abord sur la machine
(durée
) puis sur
(durée
), dans le même ordre. L’objectif est de minimiser le temps total (makespan). Johnson (1954) a donné la règle optimale :
- les travaux avec
passent en premier, par ordre de
croissant ; - les autres passent en dernier, par ordre de
décroissant.
L’idée est de faire travailler
le plus tôt possible (travaux courts sur
au début) et de ne pas lui laisser beaucoup de travail à la fin (travaux courts sur
à la fin).
Exemple. Cinq travaux
: J1 (3, 6), J2 (5, 2), J3 (1, 2), J4 (6, 6), J5 (7, 5). Premier groupe, par
croissant : J3, J1, J4. Deuxième groupe, par
décroissant : J5, J2. Séquence J3, J1, J4, J5, J2.

Sur
, les travaux finissent aux instants 1, 4, 10, 17, 22 ; sur
à 3, 10, 16, 22, 24. Le makespan est 24.
Optimalité dans l’exemple. Toute séquence doit occuper
pendant
, et après le dernier travail sur
il faut encore au moins sa durée sur
, qui vaut au moins
. Aucune séquence ne finit donc avant 24, et la séquence de Johnson atteint la borne. (La démonstration générale utilise encore un échange entre travaux adjacents.)
Avec trois machines ou plus, le problème devient NP-difficile et l’on utilise des heuristiques ; la règle de Johnson reste utile quand deux machines dominent, par exemple un poste d’assemblage suivi d’un essai.






Ciao, sono l'autore di «Programmazione della produzione: MRP e regole di sequenza». Domande, dubbi, segnalazioni di errori o richieste di approfondimento sono benvenuti: scriveteli qui sotto e vi rispondo io. Potete anche votare la pagina con le stelle all'inizio dell'articolo.Hi, I am the author of “Production planning: MRP and sequencing rules”. Questions, doubts, error reports and requests for more detail are all welcome: write them below and I will answer. You can also rate the page with the stars at the top of the article.