Aller au contenu
ELECTRONICS ENGINEERINGelectronics-engineering.com
Gestion d'entreprise

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/

Pas encore de vote : soyez le premier à noter cette page.

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 :

  1. le plan agrégé (mois) : capacité, équipes, niveaux de stock par famille de produits ;
  2. le programme directeur de production (PDP, semaines) : quels produits finis, combien et quand ;
  3. 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 ;
  4. 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

n travaux doivent être traités sur une machine, avec des durées p_j et des dates d’échéance d_j. 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 L_{max} = \max_j(C_j - d_j).

Démonstration. Considérons deux travaux consécutifs i et j avec d_i \gt  d_j et i avant j, commençant à l’instant t et finissant tous deux avant T = t + p_i + p_j. Avant l’échange, j finit en T, avec le retard T - d_j, le plus grand des deux (parce que i finit avant T et a une échéance plus tardive). Après l’échange, j finit avant T, et i finit en T avec le retard T - d_i \lt  T - d_j. 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 M_1 (durée a_j) puis sur M_2 (durée b_j), dans le même ordre. L’objectif est de minimiser le temps total (makespan). Johnson (1954) a donné la règle optimale :

  1. les travaux avec a_j \le b_j passent en premier, par ordre de a_j croissant ;
  2. les autres passent en dernier, par ordre de b_j décroissant.

L’idée est de faire travailler M_2 le plus tôt possible (travaux courts sur M_1 au début) et de ne pas lui laisser beaucoup de travail à la fin (travaux courts sur M_2 à la fin).

Exemple. Cinq travaux (a_j, b_j) : J1 (3, 6), J2 (5, 2), J3 (1, 2), J4 (6, 6), J5 (7, 5). Premier groupe, par a croissant : J3, J1, J4. Deuxième groupe, par b décroissant : J5, J2. Séquence J3, J1, J4, J5, J2.

Séquence de Johnson sur deux machines
Sur la machine M 1, les travaux J3, J1, J4, J5, J2 se suivent sans temps mort jusqu’à l’instant 22. Sur la machine M 2, chaque travail commence quand il a fini sur M 1 et que M 2 est libre ; le dernier, J2, finit à l’instant 24.

Sur M_1, les travaux finissent aux instants 1, 4, 10, 17, 22 ; sur M_2 à 3, 10, 16, 22, 24. Le makespan est 24.

Optimalité dans l’exemple. Toute séquence doit occuper M_1 pendant \sum a_j = 22, et après le dernier travail sur M_1 il faut encore au moins sa durée sur M_2, qui vaut au moins \min_jb_j = 2. 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.

S’abonner
Notifier de
guest
1 commentaire
Le plus ancien
Plus récent Les plus votés
1
0
Vous avez apprécié cet article ? Merci de laisser un commentaire.x