Fiches techniques

LISTE DES FICHES TECHNIQUES

Article

A COMPLETER

Cellule

A COMPLETER

Kanban

Tableau Kanban



Il est utilisé pour stocker temporairement et visuellement toutes les étiquettes Kanban en attente de fabrication. Il sert non seulement de stockage, mais d'outil d'aide au choix des productions à effectuer (ordonnancement des travaux).

Principe:

À chaque produit correspond une colonne. Cette colonne reçoit les étiquettes au fur et à mesure de leur retour (les kanbans en attente de fabrication).

L'exemple suivant est pris dans une entreprise commerçant ce type de tableau.



Pris de http://www.shop.org-sys.de/


Bien que ce ne soit pas systématique, chaque colone a souvent 3 zones :

  • verte : les kanbans peuvent s'accumuler dans cette zone, si la machine est libre, on peut les faire, mais il n'y a pas urgence
  • orange : si des kanbans s'accumulent dans cette zone, dès que la machine se libère, les produits correspondant doivent être mis en fabrication
  • rouge : les kanbans qui s'accumulent dans une zone rouge coivent préempter la machine (on arrête la fabrication en cours et on traite ces kanbans).

On peut s'interroger sur la qualité de cette approche puisque rien n'empêche plusieurs produits d'arriver simultanément dans la zone orange, voire dans la zone rouge. Mais ce type de gestion visuelle permet à l'opérateur de faire des choix intelligents. Ses degrés de liberté sont :

  • faire quelque chose ou ne rien faire
  • si il décide de faire, choisir le produits prioritaire
  • pour ce produit, choisir la taille du lot (un, plusieurs ou tous les kanbans en attente)

Ces degrés de liberté lui permettent de gérer correctement les conflits et de les anticiper.

Références:

http://chohmann.free.fr/lean/top.htm

http://www.magnatag.com/page/KANBAN-LEAN/category.asp





Kanban de Transfert



Principe:

Le site de production utilise un lot de production. Dans ce cas, si chaque site de consommation est traité comme un kanban normal, le délais de mise à disposition (ou temps de réaction) va prendre en compte ce fonctionnement en lot deux fois.

Dans ce premier schéma (cas A), les deux consommateurs gèrent leur Kanban indépendamment l'un de l'autre. Le nombre total de Kanbans, NA est la somme des deux boucles.





Les temps de réaction vérifient :

  • C1=C'1+C3
  • C2=C'2+C3

Dans le second cas (Cas B), deux boucles (Kankans de transfert) servent entre un stock intermédiaire et le lieu de consommation. Un Kanban de production permet de réalimenter ce stock. Il faut évidemment que les deux boucles de transfert effectuent les transferts Kanban par Kanban.





Dans le second cas, le nombre [math]N_B[/math] de Kanbans est la somme des trois boucles. On remarque cependant que la somme des trois nouvelles boucles est inférieure à la somme des deux précédentes.

[math]N_B=\displaystyle\frac {D_1 + D_2}{k}C_3 + \left(\displaystyle\frac{Q}{k}-1 \right)+ \displaystyle\frac{D_1}{k}\times C_2^' + \displaystyle\frac{D_2}{k}\times C_1^'[/math]


[math]N_A = N_1 + N_2 = \displaystyle\frac {D_1}{k}(C_1' + C_3) + \displaystyle\frac {D_1}{k}(C_2' + C_3) + 2\left(\displaystyle\frac{q}{k} - 1 \right) [/math]



[math]N_A = \displaystyle\frac {D_1 + D_2}{k}C_3 + \left(\displaystyle\frac{q}{k} - 1 \right) + \displaystyle\frac {D_1}{k}C_1 + \displaystyle\frac {D_2}{k}C_2 + \left(\displaystyle\frac{q}{k} - 1 \right) = N_B + \left(\displaystyle\frac{q}{k} - 1 \right) [/math]

Exemple:
Considérons ici une entreprise d'assemblage qui utilise pour ses composant un approvisionnement par Kanban. Un opérateur fait régulièrement une tournée durant laquelle il collecte les Kanbans (étiquettes) des produits consommés et dépose les Kanbans (et les produits correspondants) approvisionnés. La tournée de collecte/dépose dure 15 minutes.
La fin de la tournée ets au quai d'ou un camion part pour aller approvisionner les kanbans au centre de production. Il faut 20 minutes pour s'y rendre. Les caisses sont de 100 produits, la consommation de 2 produits à la minute.

Question 1 : Combien faut il de Kanbans:

Demande :2/ minutes
contenant: 100 produits
Temps de mise à disposition = 15+15+20+20=70 minutes

[math]N= arrondi \left( \displaystyle\frac {2}{100} \times 70 \right) = 2 [/math]

Remarque 1: Il faut effectivement que le Kanban parte dès que la consommation commence. Sinon, on risque la rupture car la consommation d'une caisse dure 50 minutes et le temps que les nouvelles pièces arrive, il faut 70 minutes.
Remarque 2: il est dommage d'avoir des caisses aussi grosses. Avec des caisses de 30, on aurait 5 caisses, soit un stock maximal de 150, contre 200 avec les caisses de 100

Question 2
L'entreprise produit en fait ces pièces, avec une durée assez rapide mais des lôts de 550 pièces. Quel est le nombre de Kanbans dans une boucle simple ?
La dure devient 70+15, et on rajoute des kanbans pour le lot

[math]N= arrondi \left(\displaystyle\frac {2}{100} \times 85 \right)+ arrondi \left(\displaystyle\frac {550}{100} -1 \right) = 7 [/math]

Question 3 Il y a en fait 5 ateliers travaillant avec le même composant et la même demande. Quel est le nombre de kanbans avec et sans boucle de transfert ?

Sans boucle de transfert :

[math]N= 5 \times 7 = 35 [/math]

Avec boucle de transfert :
Pour la boucle de production, la demande est de 10 pièces minutes et un temps de production de 15 minutes:
[math] N= arrondi \left( \displaystyle\frac {10}{100}*15+ \right) + arrondi\left( \displaystyle\frac {550}{100} -1 \right) = 7 [/math]

Pour chaque boucle de transfert, on est dans le cas de la question 1, soit 2. Le total est 17 kanbans.
Références:
A COMPLETER



Correction de prévisions



Objectif : Le responsable de la production d’une entreprise planifie sa production pour l’an prochain. Il ressort l’historique des ventes 2008, et il cherche une méthode pour établir des prévisions pour l’année 2009. Son objectif est d’atteindre une précision de 3% maximum. Il demande à un stagiaire d’étudier le problème.

Le stagiaire lui revient avec l’historique mensuel des ventes de 2008, (feuille « données mensuelles » du fichier nettoyagedonnees.xls). Sachant que 3% de la demande moyenne mensuelle représente 200 produits environ, et que la consommation de l’année 2008 a évoluée entre 3767 et 4551, le stagiaire l’informe que bien sur, il voit une certaine tendance à l’augmentation, mais qu’il ne lui semble pas possible d’établir des prévisions fiables à moins de 5%. Son raisonnement est le suivant :

La demande moyenne est de 4065, avec un écart type de 244. Une prévision à 3%, soit plus ou moins 120 suppose de prédire 12 valeurs consécutives en deçà de 0.9 écart type. Or la probabilité qu’un phénomène suivant une loi normale soit compris entre la moyenne plus ou moins 0.9 écart type est de 0.63 seulement. Donc la probabilité d’avoir 12 fois une valeur dans cet intervalle est de 0.004 environ. Même si quelque chose nous échappe, ce n’est quand même pas très probable.

En allant plus loin, le stagiaire propose de tenir compte de la tendance et il calcule avec Excel la droite de régression. La mesure de l’écart des valeurs à la droite est presque toujours supérieure à 3%, avec une pointe à -10% pour le mois d’aout. Ceci confirme sa première conclusion.

Le responsable de production demande alors qu’on lui sorte les données journalières de l’année 2008 (feuille données jour). Il constate qu’il y a beaucoup de bruit dans le signal… Il refait alors un tableau (feuille « données jour complètes ») avec le jour de l’année, le mois et le jour de la semaine.

Il fait alors un tableau croisé dynamique (feuille Analyse 1) sur lequel il sélectionne la moyenne des ventes par jour et il s’aperçoit d’une grande diversité, entre le lundi qui compte comme 0.29 jour moyen et le samedi qui compte pour 2.2. Il décide alors de pondérer les mois par la somme pondérée des jours qui les compose. Donc pour chaque mois, il compte le nombre de lundi, de mardi, etc… et il calcule le coefficient total du mois (la somme des coefficients des 12 mois est donc 366 jours (années bissextile). Ensuite, il calcule la consommation moyenne d’un jour type par mois (division de la vente réelle par la somme des coefficients des jours du mois). Moyenne 133,8, écart type de 3.54. Ceci lui donne espoir car rien qu’avec ces chiffres, il y a 94% d’être en deçà des 3%, et presque 50% de chance d’être en deçà 12 fois de suite.

Confiant, le responsable de production calcule avec Excel la droite de régression et mesure les écarts entre le modèle avec tendance (la droite de régression) et la réalité. Toujours inférieur à 1.7%. Le responsable de production en conclut que contrairement à ce que le stagiaire disait, il peut sans aucune difficulté prévoir la production avec moins de 3% d’erreur. Il lui suffit d’appliquer mois par mois le modèle de régression, puis de pondérer par le poids du mois donné par son « profil » en jour. Chaque mois il peut mettre à jour les poids des mois ainsi que les coefficients de la régression.




fichier a consulter


Le coin des technologies de production et d'assemblage

L'automobile

L'automobile est l'une des principales industries du monde moderne. Les technologie de fabrication et d'assemblage des automobiles sont maintenant bien connues et bien rodée.
Il y a au moins 4 niveaux de production qui s'enchaine :

  • obtention des matériaux bruts,
  • fabrication des pièces élémentaires,
  • Assemblage des sous-ensembles,
  • assemblage final.

Ligne d'assemblage dans l'automobile

La ligne d'assemblage automobile est elle-même séparée en 5 lignes successives, disposant entres-elles de stocks tampon.

  • L'emboutissage (fabrication des tôles),
  • Le Ferrage (fabrication de l'armature en montant les tôles sur le châssis),
  • La peinture (des châssis complet, incluant les portes),
  • Le montage final (incluant le démontage des portes qui sont finis sur des lignes secondaires et remontées en fin de ligne),
  • Le contrôle final.

Une vision globale est présentée ici
De même, donne une idée de la fabrication d'un moteur .
Finalement, donne une idée de l'assemblage d'une BMW sedan .

Un esprits un peu "vintage, l'assemblage manuel dans les années 1936"

Emboutissage


Le problème de l'emboutissage est souvent la taille des lots. Les presses sont souvent très longues à régler, les moules très longs à changer, et on essaye de faire des séries le plus longue possible, au risque d'engendrer de gros stocks. Ce sont sur ces équipement que les Japonais ont introduit le SMED.
Notons aussi que les moules sont long à mettre au point et que souvent la fabrication des moules est sur le chemin critique du délais de mise au marché (durée entre le début de la conception et la mise sur le marché des première voiture).
L'utilisation de polymère peut amener cet atelier à évoluer considérablement.
Exemple à PSA :

Ferrage


Le ferrage consiste à monter les éléments de la carrosserie sur le châssis de la voiture. Les technologie utilisées sont essentiellement les robots de manutention et les robots de soudure. Le problème de gestion de fabrication consiste à faire la séquence d'assemblage (en fonction des besoins) et gérer l'alimentation en composant. Soit on est en flux poussé, soit on est en flux tiré à partir du stock intermédiaire. Les carcasses ainsi construites sont généralement stockées dans un stock vertical, composés de "N" petites lignes gérées en FIFO (on entre les carcasses par un des cotés du stockage, on les ressort par le coté opposé): lorsqu'une carcasse est faites, on choisie une des lignes (plan XZ) dans laquelle il reste une place, en on rentre la carcasse dans cette ligne. Comme chaque ligne est une FIFO, on ne pourra accéder à cette carcasse en peinture que lorsque toutes les voitures rentrée avant elle dans cette lignes seront sortie.
La logique du ferrage est de faire des lots de carcasses identiques (pour minimiser les setup, même si avec les robots, les setups sont souvent nuls) alors que la logique en peinture sera de regrouper par couleur.
La gestion des emplacements de ce stockage est important puisqu'il conditionne la possibilité de produire la séquence de carcasses voulue en peinture avec la séquence de carcasses produite en ferrage.
Exemple à PSA

Peinture


Les lignes de peinture prennent les produits dans le stock de sorti de ferrage et finisse dans le stock fin de peinture. Les deux système de stockages sont gérés de la même manière. Les cabines de peintures sont très longues à nettoyer et on essaye donc de faire des lots de carcasses de couleur identique, en mêlant des carcasses de type différent. Les portes sont montés sur la carcasses pour des raisons d'homogénéité de couleur.
La peinture demande aussi souvent des retouches ce qui perturbe le séquencement de la ligne. Les retouches introduisent des inversions d'ordre qui peuvent remettre en cause al possibilité de faire le séquencement de la ligne d'assemblage finale.
Exemple à PSA

Assemblage final


La première opération consiste souvent à démonter les portes. Celle ci vont suivre une ligne d'assemblage particulière (vitre, garnitures, etc.) et rejoindre la voiture en fin de ligne.
Sur la ligne elle-même, les technologie utilisée sont les robots de manutention, de soudures, de collage, les assemblages manuels. Certains modèles sont plus complexe à assembler que d'autre. Il faut trouver une séquence de voitures qui simultanément remplisse la demande (souvent la ligne d'assemblage est "make to order" donc il faut satisfaire le client) et qui équilibre les charges aux différents postes (alternance de véhicule complexes et simple sur chaque poste. Cette opération s'appelle le "Car sequencing " problème.

l'approvisionnement de la ligne d'assemblage

L'approvisionnement des lignes d'assemblage est un gros problème. Le volume de composants est énorme et la gestion de ce flux est délicate.

La nature de l'approvisionnement va dépendre essentiellement de l'encombrement des composants. Dans les lignes automobiles,il y a trois types d'approvisionnement:

  • pour les petites pièces,
  • l'approvisionnement se fait par gestion de stock, sur point de commande, avec une consolidation (synchronisation) en cas de fournisseur alimentant plusieurs composant. Il y a un sur-stock sur la ligne, mais peu encombrant étant donné la taille des composants. Typiquement, un contenant par type de produit, approvisionnement rare.
  • Pièces moyennes
  • L'approvisionnement se fait en réunissant dans un contenant tous les composants nécessaires pendant une période de temps donnée (typiquement, une heure de production). L'approvisionnement doit donc connaitre a priori la quantité consommée sur cette période, qui peut varier. Typiquement, un contenant par produit, approvisionnement périodique en quantité exacte.
  • Gros composants
  • Approvisionnement d'une séquence de composants dans l'ordre exacte ou ils seront utilisés. Typiquement, un contenant peut contenir plusieurs produits différents (évidement du mêm etype et rendant la mêm efonction, comme des moteurs différents par exemple), mais dans un ordre lié à la ligne. Ceci permet de diminuer le nombre de contenants en bord de ligne et de faciliter la gestion.

Évidement, pour faire un flux synchrone, il faut disposer d'un entrepôt voisin de la ligne d'assemblage, ou aller jusqu'à demander au fournisseur de livrer (voire de produire) dans l'ordre de la ligne. Ce point est abordé dans l'article de Vincent Giard et Gisèle Mendy, Le passage de l’approvisionnement synchrone à la production synchrone dans la chaîne logistique

Méthodes de planification

Plan de production

Cet exemple porte sur une entreprise qui établie un plan de production pour 2009, pour fabriquer 4 familles de produits différentes (a, B, C et D).
Les données pour cet exemple se trouvent là:
La feuille "pourcalculercout" donne les données de l'an dernier, les quantités, le nombre d'heures de travail pour effectuer un produit (20, 100, 50, 60). Cette feuille permet de calculer le coût "d'une heure de travail" en incluant les coûts de matière: 40$ environ.
Le calcul du nombre de jours ouvrables est donné par la feuille "Jours 2009".
La feuille "donnees de depart" donne les demandes estimées pour les mois de janvier à décembre. Ces données ont été élaborées en coopération avec les différents services de la compagnie. Certaines colonnes peuvent être masquées.
Il est assumé que le stock de sécurité est à 34400 heures, et le stock maximum de 70000 heures.
Sur cette feuille, la figure donne trois courbes :

  • la demande cumulée,
  • La demande plus le stock de sécurité, qui représente les exigences cumulée,
  • le stock maximum.

Ensuite, deux plans sont proposés, l'un avec 116 personnes en permanence, l'autre avec un nombre variant de 108 à 122. Le calcul du coût payé (dernière colonne) est fait avec l'hypothèse d'un coût à l'heure.
Ces feuilles sont en fait des simulateurs qui permettent de calculer différents scenarii. On peut calculer un coût avec des coûts liés aux variations du nombre d'opérateurs.

Opérations spéciales

Le but ici est de répertorier quelques types d'opération connues pour poser problème lors de leurs modélisation

opération de traitement thermique


Un traitement thermique consiste à introduire les pièces dans un four, à porter le four à une certaine température. Ce qui caractérise cette opération, c'est que la durée de l'opération est indépendant du nombre de pièces enfournée. Le calcul de la durée peut donc s'avérer difficile :
On utilise alors le mode de calcul :

LISTE

Ce mode de calcul permet de calculer la durée de l'opération du point de vue de la gamme de production, mai spas du point de vue de l'atelier.

Exemple :
Soit une opération de traitement thermique dans un four. Le four peut contenir 100 pièces, et la durée est de 1 heure. Ces informations permettent de calculer la durée du point de vue de la gamme, en fonction du nombre de pièces de l'ordre de fabrication:

Taille du lot Durée de production (h)
501
801
1502
8509

En revanche du coté atelier, les choses peuvent être plus complexes. En effet, si l'ordre de fabrication est de 50 produits, mais qu'il y a un autre de fabrication pour un autre produit, utilisant la même température et la même durée, et d'un volume de 30 pièces par exemple, les deux seront effectués en même temps. La durée total sera donc de 1+1=1 heures...

opération de traitement de surface

La caractéristique des opérations de traitement de surface par électrolyse, c'est que le courant dépend de la surface. La durée opératoire dépend donc de la surface du produit. Lorsqu'il y a plusieurs produit, la durée de l'opération est donc une fonction linéaire du nombre de produits traités simultanément.
Mais dans l'atelier, on peut traiter deux ordres simultanément. La surface est donc la somme des surfaces, et la durée la somme des durées. On a cependant intérêt à coupler les deux ordres de fabrication sur le même support car cela permet de diminuer les temps morts (chargement et déchargement de la cuve de traitement).

opération de mécano-soudage

Parmi les opérations de chaudronnerie, les opérations d'assemblage par soudage en 3 dimensions sont connues pour être très techniques et avoir des durées variant avec l'opérateur, et même variable un même opérateur. Il est très difficile de leur attribuer une durée.

le casse tête des opérations de réglage


Les opérations de réglages sont généralement classées en deux catégories :

Par exemple, les temps de réglage dépendant de la séquence classique sont :

histoire vraie

Une entreprise de fabrication ce confiture faisait chaque semaine une séquence fixe de confiture allant du plus clair au plus noir (par exemple pomme-poire-orange-fraise-framboise-cassis). La ligne était nettoyée en fin de semaine. Au moment du changement de référence, la couleur dominante était bien la nouvelle, mais il y avait un mélange de gout (la première confiture se mélait à la seconde). On commençait donc par fabriquer des "sous marques". Une fois que la ligne de production était bien "purgée" du premier produit, on fabriquait les marques plus "dispendieuses". Ce système permettait d'économiser un grand nombre de nettoyages.

Mais il existe des cas encore plus pervers. Notons le cas des magasins d'outils de certaines machines à commande numérique.

Centre d'usinage avec magasin d'outils automatique

Soit une machine dont le magasin d'outils peut contenir N outils (par exemple, N=10). Tout changement d'outil dans le magasin entraine un temps ''t'' de réglage de cet outil.


Pour passer de A à B, on doit donc enlever certains outils pour que tous les outils de O(B) soient installés.








configuration pour usiner A nombre de réglages cause
a,b,c,d,e,f,g,h,i,j3 il faut faire de la place pour x, y, et z
a,b,c,d,e,f,g,x,y,m1un seul changement pour mettre z
a,b,c,d,e,f,g,x,y,z0x, y, et z sont déjà en place

Le temps de réglage pour passer de A à B est donc non seulement dépendant du couple (A, B), mais aussi de l'état de la machine au moment ou la pièce A est faite.
Dans ce cas, on a pratiquement toujours intérêt à négliger cela et à mettre un temps de réglage moyen. Le modèle est approximatif, mais tellement plus simple.

Prévisions



Si la chronique suit une tendance, on peut l’approximer par :


[math]y(t)=a \times t+b+e(t)[/math]



Le lissage par la moyenne mobile donne :


[math] \displaystyle \overline {y(t)} = \frac 1n \sum_{i=0}^{n-1} y(t-i) = \frac 1n \sum_{i=0}^{n-1} \left( a(t-i) + b + e(t-i) \right) [/math]



[math] \displaystyle \overline {y(t)} = \frac 1n \sum_{i=0}^{n-1} a(t-i) + \frac 1n \sum_{i=0}^{n-1} b + \frac 1n \sum_{i=0}^{n-1} e(t-i)[/math]



[math] \displaystyle \overline {y(t)} = \frac an nt - \frac an \sum_{i=0}^{n-1} i + b + \frac 1n \sum_{i=0}^{n-1} e(t-i)[/math]



[math] \displaystyle \overline {y(t)} = \frac an nt - \frac an \left( \frac {(n(n-1))}{2} \right) + b + \frac 1n \sum_{i=0}^{n-1} e(t-i)[/math]



Comme le terme e(t) est un bruit de moyenne nulle,


[math] \displaystyle \overline {y(t)} = at - a \frac {(n-1)}{2} + b = a \left[ t - \frac {n-1}{2} \right] [/math]



Donc le lissage utilisant une moyenne mobile centrée de n+1 éléments, (n impaire) introduit un retard de [math] \frac {n-1}{2} [/math].


_______________________________________________________________
Si la chronique suit une tendance, on peut l’approximer par :


[math]y(t)=a \times t+b+e(t) [/math]



Le lissage par une moyenne mobile centrée d’ordre 2 donne


[math] \displaystyle \overline {\overline {y(t)}} = \frac 1n \sum_{i=0}^{n-1} \overline {y(t-i)} = \frac 1n \sum_{i=0}^{n-1} \frac 1n \sum_{k=0}^{n-1} y(t-k-i) [/math]



[math] \displaystyle \overline {\overline {y(t)}} = \frac 1n \sum_{i=0}^{n-1} \overline {y(t-i)} = \frac {1}{n^2} \sum_{i=0}^{n-1} \sum_{k=0}^{n-1} \left[ a(t-k-i) + b + e(t-k-i) \right] [/math]



[math] \displaystyle \overline {\overline {y(t)}} = \frac {1}{n^2} \sum_{i=0}^{n-1} \sum_{k=0}^{n-1} \left[ at + b - a(k+i) + e(t-k-i) \right] [/math]



[math] \displaystyle \overline {\overline {y(t)}} = at + b - \frac {a}{n^2} \sum_{i=0}^{n-1} \sum_{k=0}^{n-1} (k+i) + \frac {a}{n^2} \sum_{i=0}^{n-1} \sum_{k=0}^{n-1} e(t-k-i) [/math]



[math] \displaystyle \overline {\overline {y(t)}} = at + b - \frac {a}{n^2} \sum_{i=0}^{n-1} ni + \sum_{k=0}^{n-1}(k) [/math]



_______________________________________________________________

Si la chronique suit une tendance, on peut l’approximer par :


[math]y(t)=a \times t+b+e(t)[/math]



Le lissage exponentiel donne :


[math] \displaystyle y'(t)= \alpha \sum_{i=0}^{ \infty } (1- \alpha)^i y(t) = \alpha \sum_{i=0}^{ \infty } (1- \alpha)^i \left( a (t-i) + b + e(t-i) \right)[/math]



[math] \displaystyle y'(t)= \alpha \sum_{i=0}^{ \infty } (1- \alpha)^i \left( at - ai + b + e(t-i) \right) [/math]



[math] \displaystyle y'(t)= (at + b) - \alpha a \sum_{i=0}^{ \infty } (1- \alpha)^i i + \alpha \sum_{i=0}^{ \infty }(1- \alpha)^i e(t-i)[/math]



Comme le terme e(t) est un bruit de moyenne nulle, et comme


[math] \displaystyle \sum_{i=0}^{ \infty } (1-x)^i = \frac 1x[/math]



Et que


[math] \displaystyle \sum_{i=0}^{ \infty } i(1-x)^{i-1} = x^{-2}[/math]



Alors


[math] \displaystyle y'(t)= (at+b) - \alpha (1- \alpha) a \sum_{i=0}^{ \infty } (1- \alpha)^{i-1} i = (at+b) - \frac {(1- \alpha)a}{ \alpha} [/math]



[math] \displaystyle y'(t)= a \left(t - \frac {(1- \alpha)}{\alpha} \right) + b = y \left[t - \frac {(1- \alpha)}{ \alpha} \right][/math]



Donc le lissage exponentiel simple introduit un retard de [math] \frac {(1- \alpha)}{\alpha} [/math]

exemple de prévision avec la moyenne

Soit une chronique corrigée et filtrée, dont les 20 derniers éléments sont les suivants :

59,58,62,60,63,64,62,65,64,65,65,66,63,67,68,68,69,69,66,70

La moyenne mobile (de 5 valeurs) peut être calculée pour les date t=5 à 20

-; -; -; -; 60,4;61,4;62,2;62,8;63,6;64;64,2;65;64,6;65,2;65,8;66,4;67;68,2;68; 68,4

Approche 1

La moyenne des moyennes peut être calculée pour les 10 dernières valeurs:
62,08; 62,8; 63,36; 63,92; 64,28; 64,6; 64,96; 65,4; 65,8; 66,52; 67,08; 67,6

LA prévision est donc donné par l'équation :

avec a = 1/2*(68,4-67,6)=0,4 (mais la moyenne des 10 valeurs est 0,5)

et b = 2*68,4-67,6 = 69,2

Les 3 prévisions suivantes sont donc de 69,7; 70,2; 70,7 (en prenant a=0,5)

Approche 2

La moyenne fourni une chronique des [math]\overline{a(t)} = \overline{y(t)} - \overline{y(t-1)} [/math] pour les 14 dernières valeurs:

1; 0,8; 0,6; 0,8; 0,4; 0,2; 0,8; -0,4; 0,6; 0,6; 0,6; 0,6; 1,2; -0,2; 0,4;

La moyenne de ces 14 valeurs est 0,53. La moyenne des 5 dernières valeurs et 0,52. On peut faire les prévisions avec la formule :

[math] \hat Y (t+i)= \overline{y(t)}+ 0,52 * \left( i+\displaystyle\frac {5-1}{2}\right) = \overline{y(t)}+ 0,52 * (2+1) [/math]

Les 3 prévisions suivantes sont donc de 69,96; 70,48; 71


exemple de prévision avec le lissage exponetiel

Soit une chronique corrigée et filtrée (la même que pour la moyenne), dont les 20 derniers éléments sont les suivants :

59,58,62,60,63,64,62,65,64,65,65,66,63,67,68,68,69,69,66,70

Avec un lissage exponentiel de paramètre 0,2, ou trouve les valeurs lissées suivantes :

59; 58,8; 59,44; 59,55; 60,24; 60,99; 61,19; 61,96; 62,36; 62,89; 63,31; 63,85; 63,68; 64,34; 65,08; 65,66; 66,33; 66,86; 66,69; 67,35;

Approche 1

Le lissage exponentiel d'ordre 2 donne les valeurs suivantes :
59; 58,96; 59,06; 59,16; 59,37; 59,7; 60; 60,39; 60,78; 61,21; 61,63; 62,07; 62,39; 62,78; 63,24; 63,73; 64,25; 64,77; 65,15; 65,59;

La prévision est donc donnée par l'équation :

avec a = (1-0,2)/0,2*(67,35-65,59)=0,43 (mais la moyenne des 10 valeurs est 0,5433)

et b = 2*67,35-65,59 = 69,11

Les 3 prévisions suivantes sont donc de 69,54; 69,97; 70,41 (en prenant a=0,5)

Approche 2


Le lissage fourni une chronique des [math]\overline{a(t)} = \overline{y(t)} - \overline{y(t-1)} [/math] pour les 20 valeurs. Les 11 dernières sont:

0,53; 0,42; 0,54; -0,17; 0,66; 0,73; 0,58; 0,67; 0,53; -0,17; 0,66

La moyenne de ces 11 valeurs est 0,45. On peut faire les prévisions avec la formule :

[math] \hat Y (t+i)= \overline{y(t)}+ 0,45 * \left( i+\displaystyle \frac {1- \alpha}{\alpha}\right) = \overline{y(t)}+ 0,45 * (4+i) [/math]

Les 3 prévisions suivantes sont donc de 67,84, 68,29; 68,74


méthodes d'approvisionnement en flux poussé

Dans cette partie, le même exemple va être comparé avec différentes méthodes de réapprovisionnent en flux poussé. Le vecteur des besoins identifiés aux périodes suivantes est :


semaine12345678910111213
demande 01520102015251020510520
Le coût de stockage est estimé à 1 \$ par produit et par période
Le coût de commande (coût de lancement, coût de passation de commande) est de 100 $

Exemple lot pour lot

Exemple


Cette politique est triviale puisqu'il s'agit simplement de commander chaque semaine pour la semaine suivante. Le coût de stockage est minimal :
[math]\displaystyle \sum_{i=1}^{12}{}\displaystyle \frac {d_i}{2}=87.5[/math]
En revanche, il y a 12 lancements, soit 1200\$
Le total est de 1287.5\$

Exemple avec période de réapprovisionnement fixe de 4 semaines.

Rappel


Cette méthode triviale consiste à créer un ordre de fabrication régulièrement pour combler une période de durée constante. Dans ce cas, on peut par exemple s'en tenir à 4 semaines.
Commande 1 : 65, coût stockage = 132.5
Commande 2 : 70, coût stockage = 140
Commande 3 : 40, coût de stockage = 100

Coût total : [math]3 \times 100 + 372.5 = 672.5 [/math]

Exemple avec une quantité économique

Rappel

La quantité économique peut se calculer avec les formules de Wilson.

  • Demande moyenne = 16
  • Coût de stockage par unité de temps = 1
  • Coût de lancement = 100
  • Q*=56 produits, arrondis à 55.

Calcul du coût

semaine12345678910111213
demande 01520102015251020510520
Ordres5500 5500550000550
stock debut 0 55402065 4530605030251565
coût stockage 0 47.5301555 37.517.5554027.52012.555

Donc le coût total de cette politique est :
[math]4\times 100+412.5=812[/math]\$

exemple avec équilibrage de périodes

Rappel


Dans cette approche, on cherche à commander pour un nombre de semaines tel que le coût de lancement soit le plus proche possible du coût de stockage.

Premier ordre de fabrication


La première commande :
1 semaine: coût stockage = [math]\displaystyle \frac {15}{2}=7.5[/math]
2 semaines : coût de stockage = [math]\displaystyle \frac {15}{2} + \displaystyle \frac {20 \times 3}{2}=37.5[/math]
3 semaines : coût de stockage = [math]\displaystyle \frac {15}{2} + \displaystyle \frac {20 \times 3}{2}+\displaystyle \frac {10 \times 5}{2}=62.5[/math]
4 semaines : coût de stockage = [math]\displaystyle \frac {15}{2} + \displaystyle \frac {20 \times 3}{2}+\displaystyle \frac {10 \times 5}{2}+\displaystyle \frac {20 \times 7}{2}=132.5[/math]

Solution retenue : 4 semaines. En effet [math] |100-62.5|=37.5 > |132.5-100|=32.5[/math]

Second ordre de fabrication


Différents choix :
1 semaine: coût stockage = [math]\displaystyle \frac {15}{2}=7.5[/math]
2 semaines : coût de stockage = [math]\displaystyle \frac {15}{2} + \displaystyle \frac {25 \times 3}{2}= 45 [/math]
3 semaines : coût de stockage = [math]\displaystyle \frac {15}{2} + \displaystyle \frac {25 \times 3}{2}+\displaystyle \frac {10 \times 5}{2}=70[/math]
4 semaines : coût de stockage = [math]\displaystyle \frac {15}{2} + \displaystyle \frac {25 \times 3}{2}+\displaystyle \frac {10 \times 5}{2}+\displaystyle \frac {20 \times 7}{2}=140[/math]

Solution retenue : 3 semaines. En effet [math] |100-70|=30 < |140-100|=40[/math]

Troisième ordre de fabrication


Différents choix :
1 semaine: coût stockage = [math]\displaystyle \frac {20}{2}=10[/math]
2 semaines : coût de stockage = [math]\displaystyle \frac {20}{2} + \displaystyle \frac {5 \times 3}{2}= 17.5 [/math]
3 semaines : coût de stockage = [math]\displaystyle \frac {20}{2} + \displaystyle \frac {5 \times 3}{2}+\displaystyle \frac {10 \times 5}{2}=42.5 [/math]
4 semaines : coût de stockage = [math]\displaystyle \frac {1
20}{2} + \displaystyle \frac {5 \times 3}{2}+\displaystyle \frac {10 \times 5}{2}+\displaystyle \frac {5 \times 7}{2}= 60[/math]
5 semaines : coût de stockage = [math]\displaystyle \frac {1
20}{2} + \displaystyle \frac {5 \times 3}{2}+\displaystyle \frac {10 \times 5}{2}+\displaystyle \frac {5 \times 7}{2}+\displaystyle \frac {20 \times 9}{2}= 150[/math]
Solution retenue : 4 semaines. En effet [math] |100-60|=40 < |150-100|=50[/math]

Synthèse


Il y aura donc 4 ordres de fabrication (le dernier de 20 produits en attendant de savoir de quoi le futur sera fait). Le coût total de la politique est donc de :
[math] 4\times 100+ 132.5+70+60+10 = 672.5 [/math]\$

Exemple d'optimisation avec l'algorithme de Within etWagner

Rappel


Le principe de cette méthode, c'est que :
[math] Z_k = Min_{0 <=j< k }\left( Z_j+C_{j,k} \right) [/math]

avec [math] C_{j,k}[/math] qui est le coût pour couvrir les périodes de j+1 à k, avec une fabrication en période j (livrée en j+1)

calcul de [math] Z_{2}[/math]


[math] Z_2=Z_1+C_{1,2}[/math] avec [math] C_{1,2}[/math] qui consiste à fabriquer en période 1 pour couvrir le besoin de la période 2.
Les produits de la période 2 ( 15 unités en l'occurrence) sont donc stockés en moyenne [math] 1/2[/math] période, à 1 \$ par produit et par période.

[math] Z_2 = \displaystyle \frac {15}{2}+100 = 107,5 [/math]

Calcul de [math] Z_{3}[/math]

[math] Z_3 = Min\left( Z_2+C_{2,3}; C_{1,3} \right) [/math] avec [math] C_{1,3} [/math] qui consiste à faire en semaine 1 la production des périodes 2 et 3.

[math] C_{2,3} = 100+\displaystyle \frac {20}{2}= 110[/math]
[math] C_{1,3} = 100+\displaystyle \frac {15}{2}+\displaystyle \frac {20 \times 3}{2}=137,5[/math]
[math] Z_{3} = Min \left( 110+117.5, 137.5\right)= 137.5[/math]

Calcul de [math] Z_{4}[/math]


[math] Z_4 = Min\left( Z_3+C_{3,4}; Z_2+C_{2,4};C_{1,4}; \right) [/math]
avec
[math] C_{3,4} = 100+\displaystyle \frac {10}{2}= 105 [/math]
[math] C_{2,4} = 100+\displaystyle \frac {20}{2}+\displaystyle \frac {10 \times 3}{2}=125[/math]
[math] C_{1,4} = 100+\displaystyle \frac {15}{2}+\displaystyle \frac {20 \times 3}{2}+\displaystyle \frac {10 \times 5}{2}=162.5[/math]

Et donc
[math] Z_{4} = Min \left( 137.5+105; 107.5+125; 162.5 \right)= 162.5[/math]

Calcul de [math] Z_{5}[/math]


[math] Z_5 = Min\left( Z_4+C_{4,5}; Z_3+C_{3,5}; Z_2+C_{2,5};C_{1,5}; \right) [/math]
avec
[math] C_{4,5} = 100+\displaystyle \frac {20}{2}= 110 [/math]
[math] C_{3,5} = 100+\displaystyle \frac {10}{2}+\displaystyle \frac {20 \times 3}{2}=135[/math]
[math] C_{2,5} = 100+\displaystyle \frac {20}{2}+\displaystyle \frac {10 \times 3}{2}+\displaystyle \frac {20 \times 5}{2}= 175[/math]
[math] C_{1,5} = 100+\displaystyle \frac {15}{2}+\displaystyle \frac {20 \times 3}{2}+\displaystyle \frac {10 \times 5}{2} +\displaystyle \frac {20 \times 7}{2}= 232.5[/math]

Et donc
[math] Z_{5} = Min \left( 162.5+ 110; 137.5+ 135; 107.5+175 ; 232.5 \right)= 232.5[/math]

Calcul de [math] Z_{6}[/math]


[math] Z_6 = Min\left( Z_5+C(5,6);Z_4+C_{4,6}; Z_3+C_{3,6}; Z_2+C_{2,6};C_{1,6}; \right) [/math]
avec
[math] C_{5,6} = 100+\displaystyle \frac {15}{2}= 107.5 [/math]
[math] C_{4,6} = 100+\displaystyle \frac {20}{2}+\displaystyle \frac {15 \times 3}{2}=132.5[/math]
[math] C_{3,6} = 100+\displaystyle \frac {10}{2}+\displaystyle \frac {20 \times 3}{2}+\displaystyle \frac {15 \times 5}{2}= 165[/math]
[math] C_{1,5} = 100+\displaystyle \frac {20}{2}+\displaystyle \frac {10 \times 3}{2}+\displaystyle \frac {20 \times 5}{2} +\displaystyle \frac {15 \times 7}{2}= 237.5[/math]
[math] C_{1,6} = 100+\displaystyle \frac {15}{2}+\displaystyle \frac {20 \times 3}{2}+\displaystyle \frac {10 \times 5}{2} +\displaystyle \frac {20 \times 7}{2} +\displaystyle \frac {15 \times 9}{2} = 300[/math]

Et donc
[math] Z_{6} = Min \left( 232.5+ 107.5; 162.5+ 132.5; 137.5+ 165; 107.5+237.5 ; 300 \right)= 295[/math]

Calcul de [math] Z_{7}[/math]


[math] Z_7 = Min\left( Z_6+C_(6,7);Z_5+C_{5,7}; Z_4+C_{4,7}; Z_3+C_{3,7};Z_2+C_{2,7};C_{1,7}; \right) [/math]
Nous pouvons nous limiter à
[math] Z_7 = Min\left(Z_5+C_{5,7}; Z_4+C_{4,7}; Z_3+C_{3,7}\right) [/math]
avec
[math] C_{5,7} = 100+\displaystyle \frac {15}{2}+\displaystyle \frac {25 \times 3}{2}=145[/math]
[math] C_{4,7} = 100+\displaystyle \frac {20}{2}+\displaystyle \frac {15 \times 3}{2}+\displaystyle \frac {25 \times 5}{2}= 195[/math]
[math] C_{3,7} = 100+\displaystyle \frac {10}{2}+\displaystyle \frac {20 \times 3}{2}+\displaystyle \frac {15 \times 5}{2} +\displaystyle \frac {25 \times 7}{2}= 252.5 [/math]

Et donc
[math] Z_{6} = Min \left(232.5+ 145; 162.5+ 195; 137.5+252.5 \right)= 357.5 [/math]

Calcul de [math] Z_{8}[/math]


[math] Z_8 = Min\left( Z_7+C_(7,8);Z_6+C_{6,8}; Z_5+C_{5,8}; Z_4+C_{4,8};Z_3+C_{3,8};Z_2+C_{2,8};C_{1,8}; \right) [/math]
Nous pouvons nous limiter à
[math] Z_7 = Min\left(Z_6+C_{6,8}; Z_5+C_{5,8}; Z_4+C_{4,8}; Z_3+C_{3,8}\right) [/math]
avec
[math] C_{6,8} = 100+\displaystyle \frac {25}{2}+\displaystyle \frac {10 \times 3}{2}=127.5[/math]
[math] C_{5,8} = 100+\displaystyle \frac {15}{2}+\displaystyle \frac {25 \times 3}{2}+\displaystyle \frac {10 \times 5}{2}= 170[/math]
[math] C_{4,8} = 100+\displaystyle \frac {20}{2}+\displaystyle \frac {15 \times 3}{2}+\displaystyle \frac {25 \times 5}{2} +\displaystyle \frac {10 \times 7}{2}= 230 [/math]
[math] C_{3,8} = 100+\displaystyle \frac {10}{2}+\displaystyle \frac {20 \times 3}{2}+\displaystyle \frac {15 \times 5}{2} +\displaystyle \frac {25 \times 7}{2} +\displaystyle \frac {10 \times 9}{2} = 297.5[/math]

Et donc
[math] Z_{6} = Min \left(195+127.5; 232.5+170; 162.5+ 230 ;137.5+197,5 \right)= 392.5 [/math]

Calcul de [math] Z_{9}[/math]


[math] Z_9 = Min\left( Z_8+C_(8,9);Z_7+C_{7,9}; Z_6+C_{6,9}; Z_5+C_{5,9};Z_4+C_{4,9}; Z_3+C_{3,9}; Z_2+C_{2,9}; C_{1,9}; \right) [/math]
Nous pouvons nous limiter à
[math] Z_7 = Min\left(Z_7+C_{7,9}; Z_6+C_{6,9}; Z_5+C_{5,9};Z_4+C_{4,9}\right) [/math]
avec
[math] C_{7,9} = 100+\displaystyle \frac {10}{2}+\displaystyle \frac {20 \times 3}{2}=135[/math]
[math] C_{5,8} = 100+\displaystyle \frac {25}{2}+\displaystyle \frac {15 \times 3}{2}+\displaystyle \frac {20 \times 5}{2}= 177.5[/math]
[math] C_{4,8} = 100+\displaystyle \frac {15}{2}+\displaystyle \frac {25 \times 3}{2}+\displaystyle \frac {10 \times 5}{2} +\displaystyle \frac {20 \times 7}{2}= 240 [/math]
[math] C_{3,8} = 100+\displaystyle \frac {20}{2}+\displaystyle \frac {15 \times 3}{2}+\displaystyle \frac {25 \times 5}{2} +\displaystyle \frac {10 \times 7}{2} +\displaystyle \frac {20 \times 9}{2} = 320[/math]

Et donc
[math] Z_{9} = Min \left(357.5+135; 295+177.5; 232.5+240; 162.5+ 320 \right)= 472.5 [/math]

Calcul de [math] Z_{10}[/math]


[math] Z_9 = Min\left( Z_9+C_(9,10);Z_8+C_{8,10}; Z_7+C_{7,10}; Z_6+C_{6,10};Z_5+C_{5,10}; Z_4+C_{4,10}; Z_3+C_{3,10}; Z_2+C_{2,9};C_{1,10} \right) [/math]
Nous pouvons nous limiter à
[math] Z_7 = Min\left(Z_8+C_{8,10}; Z_7+C_{7,10}; Z_6+C_{6,10};Z_5+C_{5,10}\right) [/math]
avec
[math] C_{8,10} = 100+\displaystyle \frac {10}{2}+\displaystyle \frac {20 \times 3}{2}=117.5[/math]
[math] C_{5,8} = 100+\displaystyle \frac {10}{2}+\displaystyle \frac {20 \times 3}{2}+\displaystyle \frac {5 \times 5}{2}= 147.5[/math]
[math] C_{4,8} = 100+\displaystyle \frac {25}{2}+\displaystyle \frac {10 \times 3}{2}+\displaystyle \frac {20 \times 5}{2} +\displaystyle \frac {5 \times 7}{2}= 195 [/math]
[math] C_{3,8} = 100+\displaystyle \frac {15}{2}+\displaystyle \frac {25 \times 3}{2}+\displaystyle \frac {10 \times 5}{2} +\displaystyle \frac {20 \times 7}{2} +\displaystyle \frac {5 \times 9}{2} = 262.5[/math]

Et donc
[math] Z_{10} = Min \left(392.5+117.5;357.5+147.5; 295+195; 232.5+262.5 \right)= 490 [/math]

Calcul de [math] Z_{11}, Z_12 et Z_13[/math]


On peut calculer de la même manière

[math] Z_{11} = C_{8,11} + Z_8= 392.5+142.5= 535 [/math]
[math] Z_{12} = C_{8,12} + Z_8= 392.5 + 160 = 552.5 [/math]
[math] Z_{13} = C_{8,13} + Z_8= 392.5 + 250 = 642.5 [/math]

Synthése


Finalement, la meilleure solution est donc de faire 3 ordres de fabrication, l'un en semaine 1, le suivant en semaine 4 et le dernier en semaine 8.

[math] Z_{13} = C_{8,13} + Z_8= 392.5 + 250 = 642.5 [/math]
[math] Z_{8} = C_{4,8} + Z_4= 162.5 + 230 = 392.5 [/math]
[math] Z_{4} = C_{1,4} =162.5 [/math]
Donc la solution optimale est obtenue en commençant en semaine 1 à faire 45 produits, puis en semaine 4, faire 70 produits, et finalement faire en semaine 8 les 60 produits restants, couvrant les 5 périodes suivantes.

Mais que ce serait-il passé si la demande en semaine 13 avait été de 30 au lieu de 20 :

[math] Z_{13} = C_{9,13} + Z_9= 472.5 + 185 = 657.5 [/math]
[math] Z_{9} = C_{5,9} + Z_5= 232.5 + 240 = 472.5 [/math]
[math] Z_{4} = C_{1,5} =232.5 [/math]

Il faut donc faire non plus 45 produits cette semaine, mais bien 65, alors qu'en fait, personne ne sait exactement ce que sera la demande en période 13. Cet algorithme est donc très peu robuste.

ordonnancement

Ordonancement, algorithme de Johnson

Contexte

L'algorithme de Johnson est un paradoxe de l'ordonnancement. La référence de Johnson 54 est sans aucun doute la référence la plus citée du monde de l'ordonnancement. Pratiquement personne ne l'a lu, elle n'a pratiquement aucun intérêt industriel, mais l'originalité de son approche et sa simplicité en font un "objet culte".

Domaine d'application

L'algorithme de Johnson s'applique à un problème de Flow Shop à deux machines, et le critère à optimiser est le Cmax.
Les hypothèses sont donc :

  • Tous les jobs ont deux opérations, la première sur la machine 1, la seconde sur la machine 2,
  • les machines ne travaillent que sur un job à la fois,
  • En début d'ordonnancement, les deux machines sont libres et l'atelier est vide,
  • Les deux tâches d'un job ne peuvent pas se chevaucher (on doit attendre la fin de la première pour pouvoir commencer la seconde)
  • Il n'y a aucun temps de réglage, ou bien ceux-ci sont inclus dans les processing time, ce qui revient au même.

Notation :
[math] i[/math] Indice des jobs
[math] A_i[/math]: processing time (durée) du job [math]i[/math] sur la première machine.
[math] B_i[/math]: processing time (durée) du job [math]i[/math] sur la seconde machine

Approche mathématique

Johnson a prouvé que pour trouver l'ordonnancement qui minimise le Cmax (date de fin de dernier job sur la dernière machine), il suffit de classer i avant j si :

[math] min \left( A_i,B_j \right) < min \left( A_j, B_i \right) [/math]

Cette remarque n'est pas d'une grande utilité "constructive", mais c'est cette propriété de base qui permettra de développer les algorithmes subséquents.

Approche algorithmique 1

À partir de la propriété précédente, on peut développer l'algorithme suivant:

  • Classer les jobs en deux groupes:
  • Dans le premier groupe, G1, mettre tous les jobs tels que [math] A_i < B_i[/math]
  • Dans le second groupe, G2, mettre tous les jobs tels que [math] B_i <= A_i[/math]
  • Classer G1 par SPT (shortest processing time) sur la machine M1 (par [math] A_i [/math] croissants
  • Classer G2 par LPT (Longest Processing time) sur la machine M2 (par [math] B_i [/math] décroissants
  • Considérer la séquence obtenue par concaténation de G1-G2
  • Cette séquence est optimale.

Pour s'en convaincre, il suffit de comparer deux éléments i et j, i classés avant j.
  • si i et j sont dans G1, alors [math] A_i< B_i [/math]et[math] A_j< B_j [/math] et [math] A_i< A_j [/math] puisque G1 est classé par SPT sur M1. Donc [math] A_i< A_j < B_j [/math] et donc [math] min \left( A_i,B_j \right)=A_i < min \left( A_j, B_i \right) [/math].
  • si i et j sont dans G2, alors [math] B_i<= A_i [/math]et[math] B_j<=A_j [/math] et [math] B_j<= B_i [/math] puisque G2 est classé par LPT sur M2. Donc [math] B_j< B_i < A_i [/math] et donc [math] min \left( A_i,B_j \right)=B_j < min \left( A_j, B_i \right) [/math].
  • si i est dans G1 et j dans G2, alors [math] A_i<= B_i [/math]et[math] B_j<=A_j [/math]. Donc [math] min \left( A_i,B_j \right)< min \left( A_j, B_i \right) [/math].

Les deux formulations sont équivalentes

Approche algorithmique 2


Cette approche consiste à remplir la séquence par les deux extrémités. On va trier les jobs puis les placer.
  • Initier deux listes DEBUT et FIN, vides
  • Classer les jobs par [math] min \left(A_i, B_i\right) [/math] croissant
  • prendre chacun des jobs
    • Si la tache la plus courte est sur M1, placer le job en début d'ordonnancement, donc en fin de liste DEBUT
    • Si la tache la plus courte est sur M2, placer le job en fin d'ordonnancement, donc en début de liste FIN
  • concaténer les listes DEBUT et FIN

Il est facile de montrer que cette formulation est équivalente à la précédente.

Approche EXCEL

Pour travailler avec Excel, il est facile de faire un seul tri. Les étapes sont les suivantes:

  • Créer une colonne supplémentaire indicateur.
  • Calculer l'indicateur comme étant si[math](A_i < B_i; A_i; K-B_i)[/math] ou [math]K[/math] est un grand nombre.
  • classer les Jobs par indicateur croissant.
  • l'ordre résultant est le bon.

En effet en choisissant [math]K[/math] suffisamment grand, le plus grand des [math] A_i [/math] est inférieur au plus petit des [math] K-B_i[/math]. Ainsi les Jobs tels que [math] A_i < B_i [/math]sont en tête, classés par [math]A_i[/math] croissants, et ceux tels que [math]B_i<=A_i[/math]sont classés ensuite, par [math]K-B_i[/math]croissants, et donc par [math]B_i[/math]décroissants.

Cela montre d'ailleurs que la complexité de l'algorithme est en [math]n \times log(n)[/math].

Référence

Johnson, 1954 S.M. Johnson, Optimal two- and three-stage production schedules with setup times included, Nav. Res. Logist. Quart. 1 (1954), pp. 61–68.

Cas particulier du flow shop à 3 machines

Contexte

Curieusement, si le cas de la minimisation du Cmax dans un flow-shop à 2 machines se traite bien par l'algorithme de Johnson, il n'existe aucun algorithme polynomial pour le cas du flow-shop à 3 machines.

En revanche, Johnson a montré que si la seconde machine (étage intermédiaire) était dominée, alors la solution optimale était obtenue par son algorithme initial légèrement modifié.

Condition

La seconde machine est dite dominée si :
[math] max \left(B_j \right)<=min \left(A_i \right) [/math] ou [math] max \left(B_j \right)<=min \left(D_i \right) [/math]

Algorithme


Dans ce cas, l'algorithme de Johnson appliqué au problème virtuel à deux machines pour lequel les jobs ont un processing time de [math]A_i+B_i[/math] sur la première machine virtuelle et un processing time de [math]B_i+D_i[/math] sur la seconde machine virtuelle donne la solution minimisant le Cmax.

Évidemment, pour calculer le Cmax de problème réel, une fois la séquence obtenue sur le problème virtuel, il faut se replonger dans le problème réel.

Exemple

Soit le problème suivant:




job 1 2 3 4 5 6
M16487105
M2421323
M34671058

Dans ce problème, la machine 2 est dominée, en l'occurrence par la 1 et par la 3. Le problème virtuel à résoudre est :



job 1 2 3 4 5 6
machine virtuelle 1106910128
machine virtuelle 288813711

L'ordonnancement optimal est donc : 2,6,4,1,3,5.
Le Cmax du problème virtuel est : 62
Le Cmax du problème réel est de : 47

Flow-Shop à N machines, Cmax

Contexte

La minimisation du Cmax dans le cas du flow-shop général est un problème NP-difficile au sens fort (voir Garey et al.). Plusieurs heuristiques ont été proposées pour le résoudre, et en particulier celle de Campell Dudek et Smith (CDS) et celle de Nawaz, Enscore et Ham (NEH).
Chacune de ces heuristique donne de bons résultats, mais aucune ne garantie la solution optimale.
Souvent, on va compléter ces algorithmes avec un 2-opt ou un 3-opt.

Notation :
[math] n [/math]: nombre de jobs.
[math] m [/math]: nombre de machines.
[math] p_{i,j} [/math]: processing time du job [math]i[/math] sur la machine [math]j [/math].

CDS

Cette heuristique consiste simplement générer [math]m-1[/math] sous problèmes de type Flow-shop à 2 machines, à les résoudre et à sélectionner la meilleure solution.
Le sous problème k est défini par :
processing time sur la machine virtuelle 1 : [math]p_{i,1}= \displaystyle \sum_{j=1}^{k}{p_{i,j}}[/math]
processing time sur la machine virtuelle 2 : [math]p_{i,2}= \displaystyle \sum_{j=k+1}^{m}{p_{i,j}}[/math]
Pour chacun de ces problèmes, on calcule l'ordre optimal avec l'algorithme de Johnson et on applique alors cet ordre sur le problème de base pour obtenir le [math] Cmax(k)[/math].
Ensuite, il suffit de choisir le meilleur sur l'ensemble des [math] Cmax(k)[/math].

NEH


NEH est une heuristique "générique" qui peut s'adapter à de nombreux problème : la meilleure insertion. Lorsque l'on cherche une séquence (un cycle dans le cas du voyageur de commerce), on classe les objets à trier selon un critère donné, puis on les prend les uns après les autres et on les insère à la meilleure place possible dans la séquence en construction.
La complexité de cet algorithme est en [math]O(n^2)[/math] puisque à chaque insertion [math]k[/math](il y en a n) il y a de l'ordre de [math]k[/math]insertions à essayer.
Pour le Flow shop, l'algorithme est le suivant:
  • Classer les jobs par ordre de [math] \displaystyle \sum_{j=1}^{m}{p_{i,j}}[/math]décroissants.
  • Considérer une séquence initiale avec le premier.
  • Tant qu'il reste des jobs, prendre le premier et le placer à la meilleure place possible dans la séquence courante.
  • fin

Cet algorithme est simple, facile à programmer et donne souvent de bon résultats.

2-opt ou 3-opt

Rien n'est plus vexant que de proposer en "expert" une solution qu'un non-expert va améliorer rien qu'en la regardant. Malheureusement, les heuristiques sont souvent aveugles et ne voient pas des évidences que n'importe quel humain verra. Pour pallier ce problème, on utilise souvent un algorithme extrêmement simple d'amélioration locale (Croes 58 par exemple).
Une solution est dite 2-opt si aucune permutation locale de 2 éléments ne permet de l'améliorer.
Pour obtenir une solution 2-opt (respectivement 3-opt) à partir d'une solution obtenue par heuristique, on va simplement appliquer l'algorithme suivant:

  • 1) passer toutes les permutations de 2 éléments jusqu'à en trouver une qui améliore la solution.
  • 2) si on en trouve une, effectuer la permutation et recommencer 1) au départ.
  • 3) si on n'en trouve aucune, fin.

Cet algorithme n'est pas à proprement parler l'algorithme du gradient discret. En effet, dans l'algorithme du gradient discret, on passerait toutes les permutations à chaque étape pour choisir la meilleure. Dans l'algorithme 2-opt de base, on cesse la recherche dès qu'une amélioration est obtenue.

Références

H.G. Campbell, R.A. Dudek and M.L. Smith, A heuristic algorithm for the n job m machine sequencing problem. Management Science 16 (1970), pp. 630–637.
G. A. Croes (1958). A method for solving traveling salesman problems. Operations Res. 6 (1958) , pp., 791-812.
M.R. Garey, D.S. Johnson, R. Sethi, The complexity of flowshop and jobshop scheduling, Math. Oper. Res. 1 (1976) 117–129.
M. Nawaz, E.E. Enscore, Jr. and I. Ham, A heuristic algorithm for the m-machine, n-job flow shop sequencing problem. OMEGA, International Journal of Management Science 11 (1983).

Fiches techniques concernant la gestion scientifique des stocks

Cas de gestion de stock sous contrainte

Objectif

Souvent, la gestion de stock est soumise à des contraintes externes qui font que les solutions calculées par des méthodes scientifiques ne sont pas applicables: il y a des contraintes globales. C'est le cas par exemple :

  • Lorsque l'on souhaite limiter le coût moyen du stock (pour des raisons comptables essentiellement)
  • Lorsque le volume total de stockage est limité

    Modélisation

    Dans ce cas, la recherche d'une solution locale, produit par produit n'est plus possible. On doit prendre l'ensemble des produits en considération, ainsi que les contraintes globales.

    Exemple: Si on se limite au modèle de Wilson, mais que l'on introduit une contrainte de volume total et une contrainte de coût moyen immobilisé, on peut définir le modèle suivant:

    Pour chaque produit:
    [math] d_i [/math] demande par unité de temps
    [math] CL_i [/math] coût de lancement
    [math] Ts_i [/math] taux de stockage par période
    [math] C_i [/math] prix du produit
    [math] Cs_i=C_i*Ts_i [/math] coût de stockage d'un produit en une période
    [math] V_i [/math] volume du produit
    Globalement
    [math] V [/math] volume maximal du stockage
    [math] A [/math] coût moyen de stockage souhaité.
    Variables de décision
    [math] Q_i [/math]

    Le problème à résoudre devient

    [math] Min \left( \displaystyle\sum _{i=1}^{n}{\left( \displaystyle\frac {Q_i \times Cs_i}{2}+\displaystyle\frac {d_i\times Cl_i}{Q_i } \right)}\right)[/math]
    Sous contraintes
    [math] \left(\displaystyle\sum _{i=1}^{n}{ V_i \times Q_i }\right) <= V [/math]
    [math] \displaystyle\frac{1}{2}\times \left(\displaystyle\sum _{i=1}^{n}{ C_i \times Q_i }\right) <= A [/math]
    [math] Q_i>=0 [/math]
    Ce problème est un problème d'optimisation non linéaire (fonction de coût non linéaire) et demande l'utilisation d'un solveur.

    Résolution avec Excel

    Soit un problème simple avec 4 produits:






    produit demande Coût commande prix coût stockage taux stockage volume
    1 100 20 2 20% prix / an 0.00111 0.02
    2 1000 50 0.5 30% prix / an 0.00041667 0.01
    3 10 50 5 40% prix / an 0.005555 0.03

    Le volume total disponible est [math] V=140 m^3 [/math] et la limite du coût du stock moyen est de [math] A=5000$ [/math]

    Étape 1:
    Ouvrir Excel et vérifier que le solver est installé (onglet Données, à droite du bandeau) sinon l'installer (voir documentation)
    Faire un tableau excel avec : Produit, D, %stockage, prix, taux stockage, volume,[math] Q^* [/math], volume utilisé, coût moyen.
    Rentrer les valeurs du problème. La colonne taux de stockage peut être calculée à partir du prix et du pourcentage, avec 360 jours par an, ou prise dans les données (ce doit être la même chose!). La colonne [math] Q^* [/math] est à calculer avec la formule de la quantité économique.
    À partir de là, sommer les volumes utilisés et le coût moyen si on choisit les [math] Q^*_i [/math]. Si les contraintes sont respectées, on s'arrête là....
    Sinon....
    Créer 4 nouvelles colonnes : Q, coût, volume, prix immobilisé.
    Initialiser la colonne Q avec les [math] Q^*_i [/math], calculer la colonne Coût à partir de [math] \left( \displaystyle\frac {Q_i \times Cs_i}{2}+\displaystyle\frac {d_i\times Cl_i}{Q_i } \right)[/math], le volume à partir de [math] Q_i [/math] et de [math] V_i [/math], le prix immobilisé à partir de [math] Q_i [/math] et du coût [math] C_i [/math].
    Faire les sommes des coûts, des volumes et la demi somme des prix immobilisés (prix moyen, pas maximum)
    Se positionner sur la cellule de la somme des coûts (donc du coût de la politique) et ouvrir le solveur.
    Rentrer le fait que l'on minimise cette valeur, rentrer les 3 contraintes (les [math] Q_i [/math] positif, la somme des volumes inférieure à 140 et le coût moyen immobilisé inférieur à 5000/$. Résoudre...

    Voir le fichier donnant la solution

    Coût de réglage en gestion de stock

    Lorsqu'une entreprise travaille en Make to Stock, elle doit calculer la quantité de produits à fabriquer lors du lancement de la commande. Le coût de passation de commande (ou coût de lancement, ou coût de réglage en cas de production interne) correspond alors au coût administratif d'établissement de l'ordre de fabrication, mais surtout au coût de réglage des différentes machines utilisée pour fabriquer la pièce.

    Dans le cas d'une fabrication interne, le coût de passation est le coût administratif de lancement et de la somme de tous les coûts de réglage des machines utilisées pour les différentes opérations.

    Le calcul d'un coût de réglage pour une opération donnée est souvent difficile. Il comporte les éléments suivants:

    • Le coût du temps d'immobilisation de la machine elle-même,
    • Le coût du temps des régleurs qui travaillent durant l'immobilisation de la machine,
    • Le cout des matières premières "gâchées" lors des pièces d'essai.

    Dans la gamme de production, le temps de réglage est le temps qui est nécessaire à un (ou plusieurs) opérateur(s) pour effectuer le réglage proprement dit. Ce temps est donc souvent le temps "opérateur de réglage". Ce temps peut être valorisé par le coût horaire des régleurs.
    Mais si les régleurs ne sont pas immédiatement disponibles, la machine peut-être immobilisée beaucoup plus longtemps. Le temps d'immobilisation de la machine peut être valorisé par le taux horaire de la machine. Mais quel taux horaire utiliser ???
    Souvent, on utiliser la seule information dont on dispose, soit le taux horaire d'une machine utilisée pour calculer les prix de revient d'une production. Ce taux horaire inclut le plus souvent :

    • L'amortissement de la machine,
    • Les coûts de fonctionnement (consommable, maintenance, nettoyage, entretient)de la machine,
    • Le du personnel opérant la machine.

    Par exemple, une machine achetée 1M\$, prévue pour travailler environ 20 000H (soit environ 7 heures par jour, 285 jours par an, pendant 10 ans), nécessitant 0.5 heure de nettoyage (à 20\$ de l'heure) tout les 8 heures, une maintenance de 3 jours (24 \$, 40 \$/h) tout les 300 heures, utilisant un opérateur (40\$/h), un peu de consommable (huile, fluide de coupe, électricité, etc.) pour travailler coûtera de l'ordre de 100\$ de l'heure en frais direct, soit de l'ordre de 130 $ incluant les frais indirects (chauffage du bâtiment, personnels administratif, etc.).
    Si on utilise ce taux horaire pour une machine demandant 2 heures de réglage (50 dollars de l'heure) mais restant immobilisée pendant en moyenne 8 heures pour seulement 2 heures de travail, le coût de réglage sera de :

    50*2 + 130*8 = 1140 $


    La question est: cela a-t-il du bon sens ????
    • Si l'entreprise est certaine de pouvoir faire fonctionne à 100 % sa machine (donc cette machine est le goulot d'étranglement de l'entreprise)on peut effectivement considérer que les 8 heures d'immobilisation sont 8 heures perdues. Mais alors est-ce 8 heures de perdues sur cette machine, ou 8 heures de perdues en Chiffre d'affaire pour toute l'entreprise ? À la lecture du livre de Goldratt, la question mérite d'être posée.
    • Si cette machine n'est pas goulot, alors pourquoi considérer tous ces coûts, puisqu'elle n'aurait rien fait durant ce temps ? Pourquoi ne pas considérer seulement les deux heures du régleur ??

    La question est donc de juger si le coût de réglage est bien 100\$, 1140\$ ou beaucoup plus si on considère le chiffre d'affaire. Le reste n'est qu'une question de calcul, mais c'est au moment du choix de la valeur que la décision est prise.

    Gestion des stocks : synchronisation

    Objectif:


    Réfléchir à l'intérêt de commander simultanément plusieurs produits en même temps lorsque le coût de commande est indépendant du nombre de références de produits commandés.
    On trouve cette situation lorsque :
    • Le coût de transport est lié au passage d'un camion, indépendamment de son taux de remplissage,
    • Le coût de commande est un coût de réglage et le même réglage peut être utilisé pour toute une famille de références,
    • Le coût de passation de commande se résume aux coûts administratifs qui ne dépendent pas du nombre d'items commandés

    Dans ce cas, on parle d'une famille de produit indicés par [math] i [/math].

    L'étude est faite avec le modèle de base conduisant aux formules de Wilson de la quantités économiques de commande.

    Cas de commandes séparées


    Si les commandes sont séparées, chaque produit est traité à part, avec sa propre période [math] T^*_i [/math] et sa propre quantité économique de commande [math] Q^*_i [/math] et le coût total de la politique est :

    [math] C=\displaystyle\sum _{i=1}^{n}{C(Q_i^*)}= \displaystyle\sum _{i=1}^{n}\sqrt{2\times d_i \times Cs_i\times Cl}[/math]
    Puisque le coût de lancement Cl est supposé le même, quel que soit le nombre de références commandées.

    Cas de commandes groupées


    Si on groupe les commandes, il n'y a plus qu'une seule variable, T. Tous les produits sont commandés avec cette période, en quantité [math] T\times d_i [/math].

    Le coût de la politique devient:

    [math] C(T)=\displaystyle\frac{Cl}{T} +\displaystyle\sum _{i=1}^{n}{\left(\displaystyle\frac{d_i\times T\times Cs_i}{2} \right)}[/math]

    [math] C(T)=\displaystyle\frac{Cl}{T} +\displaystyle\frac{T}{2}\times \displaystyle\sum _{i=1}^{n}{Cs_i \times d_i}[/math]

    Qui après un calcul simple de la période [math]T^*[/math] aboutira à une politique optimale de :

    [math] C= \displaystyle \sqrt {2 \times Cl \times \displaystyle\sum _{i=1}^{n}{ d_i \times Cs_i}}[/math]

    Conclusion


    Comme la racine de la somme est toujours inférieure à la somme des racines, il vient que la politique consistant à grouper les commandes est TOUJOURS plus intéressante que la politique consistant à commander séparément.
    [math] \displaystyle \sqrt {\displaystyle \sum _{i=1}^{n}{ d_i \times Cs_i}} < \displaystyle\sum _{i=1}^{n}\sqrt{ d_i \times Cs_i}[/math]

    Gestion scientifique des stock, multi-période, modèle général

    Hypothèses:


    Ce cas concerne un problème de gestion de stock dans lequel on tolère la rupture (mais elle a un coût) et dans lequel les approvisionnements se font en continu pendant une période de temps (le taux d'arrivé doit être supérieur à la demande).
    L'hypothèse de taux d'arrivée continu est par exemple vérifiée si l'on produit les pièces localement et que l'on peut donc commencer à en recevoir dès que la production commence.
    On gère un produit indépendamment des autres
    La demande est constante dans le temps d
    Le prix du produit est : C
    Les ruptures sont autorisées, les demandes non satisfaites sont reportées, et le coût de rupture par produit et période est un taux de rupture par période fois le prix du produit Cr=Tr*C
    La livraison des produits se fait à un taux constant p
    Le coût de passation de commande est constant CL
    Le coût de stockage par produit et période est un taux de stockage par période fois le prix du produit Cs=Ts*C
    L’horizon de gestion est infini

    Ainsi, les produits sont consommés à un taux de "d" produits par unité de temps, et lorsqu'ils sont livrés, ils arrivent à un taux de "p" produits par unité de temps.

    Le niveau de stock dans l'entreprise évolue de la manière suivante :

    Dans les deux premières zones [math](t_1)[/math] et [math](t_2)[/math], le taux apparent d'augmentation du stock est de [math](p-d)[/math] produits par unité de temps (on reçoit et on consomme).
    Dans les deux dernière zones [math](t_3)[/math] et [math](t_4)[/math], le taux apparent de diminution du stock est de [math]d[/math] produits par unité de temps (on consomme seulement).
    Dans les deux zones [math](t_1)[/math] et [math](t_4)[/math], on est en rupture de stock (stock négatif). Le coût de rupture est proportionnel au niveau moyen de rupture, [math](a/2)[/math].
    Dans les deux zones [math](t_2)[/math] et [math](t_3)[/math], le stock est positif. Le coût de stockage est proportionnel au niveau moyen de stock, [math](b/2)[/math].
    Ce modèle est un modèle a deux variables: la période [math]T[/math] et le niveau de rupture toléré (pour une même valeur de [math]T[/math], on peut tolérer ou non un niveau de rupture).

    Développement mathématique


    Étant donné les pentes [math](p-d)[/math] et [math]d[/math], nous avons les relations suivantes :
    [math]b=(p-d)\times t_2=d\times t_3[/math]
    [math]a=(p-d)\times t_1=d\times t_4[/math]
    [math](a+b)=(t_1 + t_2)\times (p-d)=(t_3 + t_4)\times d[/math]
    [math](t_1 + t_2)\times d=T \times d[/math]

    Et finalement en utilisant la troisième équation, et le fait que [math](t_1+t_2+t_3+t_4=T)[/math]:
    [math]T=\frac{(a+b)}{(p-d)}+ \frac{(a+b)}{(d)}=(a+b)\times \frac {p}{d \times (p-d)}[/math]

    Notons [math] K= \frac {p}{d \times (p-d)}[/math]
    Puisqu'une équation lie a, b et T, on peut travailler indifféremment avec 2 de ces variables. Le coût d'une politique (a, b) est donc:

    [math]C(a,b)=\frac{1}{T}\times \left(Cl+Cr \times \frac {t_1+t_4}{2}\times a + Cs \times \frac {t_2+t_3}{2}\times b \right)[/math]
    [math]C(a,b)=\frac{1}{K\times (a+b)}\times \left(Cl+ \frac {Cr}{2}\times K \times a^2 + \frac {Cs}{2}\times K \times b^2 \right)[/math]
    [math]C(a,b)=\frac{1}{(a+b)}\times \left( \frac {Cl}{K}+ \frac {Cr}{2}\times a^2 + \frac {Cs}{2}\times b^2 \right)[/math]

    Les dérivées partielles sont :

    [math]\displaystyle\frac{ \partial (C(a,b)) }{\partial(a)}= \displaystyle \frac{1}{(a+b)}\times Cr \times a - \displaystyle \frac{1}{(a+b)^2}\times \left( \frac {Cl}{K}+ \frac {Cr}{2}\times a^2 + \frac {Cs}{2}\times b^2 \right)[/math]
    et
    [math]\displaystyle\frac{ \partial (C(a,b)) }{\partial(b)}= \displaystyle \frac{1}{(a+b)}\times Cs \times b - \displaystyle \frac{1}{(a+b)^2}\times \left( \frac {Cl}{K}+ \frac {Cr}{2}\times a^2 + \frac {Cs}{2}\times b^2 \right)[/math]
    Les deux s'annulent simultanément si

    [math] Cs \times b = Cr \times a[/math]

    À partir de là, on peut réécrire la coût de la politique avec une seule variable :
    [math] C(a)=\displaystyle\frac{Cs \times Cl}{K\times (Cr+Cs) \times a}+ \displaystyle\frac {Cr \times a}{2}[/math]
    Dont la dérivé par rapport à [math]a [/math] s'annule pour
    [math] a= \sqrt {\displaystyle \frac {2 \times Cs \times Cl}{Cr \times K \times (Cr+Cs)} }[/math]

    Solution générale

    On a donc une période et une quantité économique :

    [math] T^*= (a+b)\times K = a\times (1+\displaystyle \frac{Cr}{Cs})=\sqrt {\displaystyle \frac {2 \times Cl \times (Cr+Cs)\times p}{Cs \times Cr \times d \times (p-d)} }[/math]
    [math] Q^*= d\times T = a\times (1+\displaystyle \frac{Cr}{Cs})=\sqrt {\displaystyle \frac {2 \times Cl \times (Cr+Cs)\times p\times d }{Cs \times Cr \times (p-d)} }[/math]

    Conditions limites


    On peut alors travailler sur les conditions limites suivantes :

    Si les ruptures sont interdites, alors [math]Tr[/math] tend vers l'infini et [math]\displaystyle \frac{Cs+Cr}{Cr}[/math] tend vers 1, donc :

    [math] Q^*=\sqrt {\displaystyle \frac {2 \times Cl \times p\times d }{Ts \times (p-d)} }[/math]

    Si l'approvisionnement se fait instantanément, alors [math]p[/math] tend vers l'infini, et [math]\displaystyle \frac{p}{(p-d)}[/math] tend vers 1, donc :

    [math] Q^*= \sqrt {\displaystyle \frac {2 \times Cl \times (Cr+Cs)\times d }{Cs \times cr } }[/math]

    Si simultanément l'approvisionnement est instantané et la rupture interdite, simultanément [math]\displaystyle \frac{p}{(p-d)}[/math] et [math]\displaystyle \frac{Cs+Cr}{Cr}[/math] tendent vers 1 et

    [math] Q^*= \sqrt {\displaystyle \frac {2 \times Cl \times d }{Cs } }[/math]

    On retombe sur les formules de Wilson.

    Le problème des ristournes

    Contexte


    En gestion de stock, les ristournes viennent perturber le calcul des quantités économiques. En effet, elles perturbent deux choses:
    • Lorsque le coût de stockage dépend du prix moyen du produit, si le prix d'achat varie, il faut en tenir compte

    • Si le prix d'achat dépend de la quantité approvisionnée, il devient différentiel et il doit apparaitre dans la formule du coût de la politique

    De fait, la fonction de coût devient :
    [math] C(Q)=\displaystyle\frac {Q }{2}\times Ts \times P(Q)+\displaystyle\frac {d\times Cl}{Q} +\displaystyle\ P(Q)\times d [/math]
    Avec
    [math] P(Q) [/math] est le coût moyen d'achat d'un produit si on les achète par quantité Q
    [math] Ts [/math] est le taux de stockage à appliquer sur le prix moyen du produit pour obtenir le coût de stockage.

    En effet, dans le modèle classique, [math] Cs=Ts \times C [/math], [math] Ts [/math] étant le pourcentage du prix du produit que coûte le stockage par an. Le coût de stockage est alors une constante. Le prix devenant variable, le coût est lui-même variable.

    Cas des prix par palier

    Si le fournisseur annonce plusieurs prix, C1, C2, C3 en fonction des quantités commandées, alors le problème est simple.

    Dans chaque "zone", le prix est constant [math]C(Q)=C_j [/math] ou [math]j[/math] est l'indice de la zone. Le principe consiste donc :

    • pour chaque zone considérée:
      • calculer la quantité économique,
      • si la quantité économique n'est pas dans la zone prendre le point frontière,
      • calculer le coût de la politique en ajoutant le prix d'achat.
    • choisir la meilleure zone.

    Exemple :
    demande =30 par jour, CL= 50\$, Ts=20% prix du produit par an, C=10 si Q<1000, C=9 au delà. Notons qu'il est idiot d'acheter 900 produits (9000\$) alors que si on en achète 1000, cela coûte aussi 900\$. Avec ce modèle, personne n'achète entre 900 et 999 produits.
    Zone 1:

    [math] C(Q)=\displaystyle\frac {Q }{2}\times 0.2 \times 10 +\displaystyle\frac {30\times 50}{Q} +\displaystyle\ 10\times 30 [/math]
    Le calcul de la quantité économique donne 734 produits (dans la zone) et le coût de la politique (par période) est de 301.29\$

    Zone 2
    [math] C(Q)=\displaystyle\frac {Q }{2}\times 0.2 \times 9 +\displaystyle\frac {30\times 50}{Q} +\displaystyle\ 9\times 30 [/math]
    Le calcul de la quantité économique donne 734 produits (hors de la zone). On prend donc la frontière, 1000. Le coût de la politique (par période) en commandant 1000 produits est de de 274\$

    Remarque : Dans ce cas, le coût de la politique est tellement plus faible que le coût d'achat qu'il est pratiquement toujours plus intéressant d'aller vers les grandes quantités (d'un point de vue comptable).

    Cas des prix différenciés


    Dans ce modèle de négociation entre donneur d'ordres et fournisseurs, les prix des produits dépendent du rang du produit:
    • Les [math]K_1[/math] premiers produits sont à [math]C_1[/math]
    • Les produits de [math]K_1+1[/math]à [math]K_2[/math] sont à [math]C_2[/math]
    • etc...

    Dans ce cas, le prix pour acheter Q produits entre [math] [ K_{j-1}, K_j] [/math] est :[math] C_j \times Q +\displaystyle\sum_{i=1}^{j-1}{K_i\times(C_i-C_{i+1})}[/math]
    Et le coût moyen d'un produit devient: [math] P(Q)= \displaystyle\frac{1}{Q} \times \left( C_j \times Q +\displaystyle\sum_{i=1}^{j-1}{K_i\times(C_i-C_{i+1})}\right)[/math]

    Le coût de la politique devient :
    [math] C(Q)=\displaystyle\frac {Q }{2}\times Ts \times \displaystyle\frac{1}{Q} \times \left( C_j \times Q +\displaystyle\sum_{i=1}^{j-1}{K_i\times(C_i-C_{i+1})}\right)+\displaystyle\frac {d\times Cl}{Q} +\displaystyle\ \displaystyle\frac{1}{Q} \times \left( C_j \times Q +\displaystyle\sum_{i=1}^{j-1}{K_i\times(C_i-C_{i+1})}\right)\times d [/math]

    [math] C(Q)=\displaystyle\frac {Ts \times C_j}{2} \times Q+ \displaystyle\frac{d}{Q}\times
    \left( Cl+\displaystyle\sum_{i=1}^{j-1}{K_i\times(C_i-C_{i+1})} \right)+\left( C_j \times d +\displaystyle\frac {Ts }{2} \times \displaystyle\sum_{i=1}^{j-1}{K_i\times(C_i-C_{i+1})} \right)[/math]
    Le traitement est alors identique au cas précédent car la fonction est exactement du type de celle conduisant aux formules de Wilson, avec simplement des coefficients plus complexes. Le dernier terme s'annule lors de la dérivé, mais doit être utilisé pour le calcul du coût de l apolitique. On doit de la même manière :

    • pour chaque zone considérée:
      • calculer la quantité économique,
      • si la quantité économique n'est pas dans la zone prendre le point frontière,
      • calculer le coût de la politique incluant le prix d'achat,
    • choisir la meilleure zone.

    Exemple

    Cette entreprise achète les produits à C1=10\$ dans l'intervalle [0,100], à C2=9\$ dans l'intervalle [101,1000] et C3=8\$ au delà. Ainsi, acheter 2000 produits coute [math]100 \times C1+(1000-100) \times C2 + (1500-1000) \times 8 = 1000 + 8100 + 4000 = 13100\$[/math]
    La demande est de 30 produits par unité de temps, le coût de passation de commande de 40\$ et le coût de possession est de 30% du prix du produit par an.

    Selon la zone, le prix moyen d'un produit sera :
    Zone 1: [math]P(Q)=10[/math]
    Zone 2: [math]P(Q)=\displaystyle\frac{1}{Q}\times (9 \times Q + 100)=9+\displaystyle\frac{100}{Q}[/math]
    Zone 3: [math]P(Q)=\displaystyle\frac{1}{Q}\times (8 \times Q + 1100)=8+\displaystyle\frac{1100}{Q}[/math]
    Selon la zone, le coût de la politique optimale sera:
    Zone 1:

    [math] C(Q)=\displaystyle\frac {Q }{2}\times Ts \times 10+\displaystyle\frac {d\times Cl}{Q} +\displaystyle\ 10\times d [/math]
    [math] Q^*=\displaystyle\sqrt {\displaystyle\frac {2 \times Cl \times d}{10 \times Ts}} =536[/math]

    La solution optimale n'est pas dans la zone, donc dans cette zone, l'optimum est la frontière, soit Q=100 pour un coût par jour de 312.5\$ environ.

    Zone 2:

    [math] C(Q)=\displaystyle\frac {Q }{2}\times Ts \times \left( 9+\displaystyle\frac{100}{Q}\right)+\displaystyle\frac {d\times Cl}{Q} +\displaystyle\ \left( 9+\displaystyle\frac{100}{Q}\right)\times d [/math]

    [math] C(Q)= 4.5 \times Ts \times Q + \displaystyle\frac{d}{Q}\times (Cl+100)+ 50 \times K + 9 \times d [/math]
    [math] Q^*= \displaystyle\sqrt {\displaystyle\frac {d \times (Cl+100)}{4.5 \times Ts}}= 1058[/math]

    La solution optimale n'est pas dans la zone, donc dans cette zone, l'optimum est la frontière, soit Q=1000 pour un coût par jour de 278\$ environ.

    Zone 3:

    [math] C(Q)=\displaystyle\frac {Q }{2}\times Ts \times \left( 8+\displaystyle\frac{1100}{Q}\right)+\displaystyle\frac {d\times Cl}{Q} +\displaystyle\ \left( 8+\displaystyle\frac{1100}{Q}\right)\times d [/math]
    [math] C(Q)= 4 \times Ts \times Q + \displaystyle\frac{d}{Q}\times (Cl+1100)+ 4050\times Ts + 9 \times d [/math]
    [math] Q^*= \displaystyle\sqrt {\displaystyle\frac {d \times (Cl+8100)}{4 \times Ts}}= 3203[/math]

    La solution optimale est dans la zone, donc dans cette zone, l'optimum est 3203 produits, pour un coût par jour de 262\$ environ.
    Conclusion
    Dans ce cas, avec ces hypothèses, on préconise une politique avec un achat de 3200 produits, pour bénéficier des meilleurs prix.
    Remarque
    Avec une commande de 2000 produits par jour, la politique coûte 264\$ par jour, et avec 1500 le coût est de 268\$. Cela mérite sans doute réflexion, tenant compte du fait qu'il peut y avoir un coût de péremption.

    Remarques sur le coût de la politique

    La principale méthode est celle de Wilson, universellement utilisée. Le but de cette note est d'explorer le calcul du coût de la politique.

    Rappel sur les limites des formules de Wilson (EOQ)

    Données :

    Demande par unité de temps (supposée constante) d
    Le coût de passation de commande est constant CL
    Prix d'achat du produit C
    Coût du stockage par unité de temps et par produit (taux de stockage) Cs= Ts*C

    On dit généralement que Cs est de l'ordre de 20 à 30% du prix du produit par an (donc Ts est entre 0.2 et 0.3 si l'unité est l'année)

    Hypothèses :

    On gère un produit indépendamment des autres
    La demande est constante dans le temps
    Les ruptures ne sont pas autorisées
    La livraison des produits est instantanée
    Le coût de stockage par unité de temps est proportionnel à la quantité entreposée durant cette unité (taux de stockage)

    Coût de la politique consistant à commander Q produits

    Sous ces hypothèses, le coût d’une politique est donc caractérisé par T ou par Q qui sont TOUJOURS liés par la relation : [math]Q=d*T[/math].
    Le coût de l apolitique consistant à commander Q produit (notée C(Q)) peut s'exprimer dans trois unités différente :

    • coût par période
    • coût par unité de temps
    • coût par produit

    Coût par période

    Durant une période, il y a un seul approvisionnement et le stock moyen est de [math]\displaystyle\frac{Q}{2}[/math] durant toute la période (donc [math]T[/math]).
    [math]C(Q)=Cl + C\times Ts \times \displaystyle\frac{Q}{2} \times T = Cl + Cs \times \displaystyle\frac{Q^2}{2\times d } [/math]

    Coût par unité de temps

    Par unité de temps, c'est simplement la formule précédente divisée par [math]T[/math].
    [math]C(Q)=\displaystyle\frac{Cl}{T}+ Cs \times \displaystyle\frac{Q}{2}=\displaystyle\frac{Cl\times d}{Q}+ Cs \times \displaystyle\frac{Q}{2}[/math]

    Coût par produit

    Pour calculer le coût par produit, on peut partir du coût par période et diviser par [math]Q[/math] ou partir de la seconde et diviser par [math]d[/math]

    [math]C(Q)=\displaystyle\frac{Cl}{Q}+ Cs \times \displaystyle\frac{Q}{2\times d}[/math]

    Politique optimale(EOQ)

    Le calcul de la politique optimale peut se faire indiféremment avec les formules 2 et 3 (par unité de temps ou par produit) en dérivant par rapport à [math]Q [/math] ou [math]T [/math] selon que l'on exprime l'équation en [math]Q [/math] ou [math]T [/math]. En revanche, on ne peut pas utiliser l'équation 1, car la période dépend de Q.
    Comme vu dans le cours, la politique optimale est pour :
    [math]Q^\star= \sqrt{\displaystyle\frac{2\times Cl \times d}{Cs }}[/math] ou [math]T^\star= \sqrt{\displaystyle\frac{2\times Cl }{Cs \times d}}[/math]
    Et pour cette valeur de [math]Q^* [/math] ou [math]T^\star [/math] on a
    [math]C(Q^\star)= \sqrt{2\times Cl \times d \times Cs} [/math]
    Mais cette valeur n'est bonne que pour la quantité économique.

    Exemple

    Soit un produit acheté 100\$, avec un coût de commande de 50\$, une demande de 250 par jour et un coût de stockage de 20% du prix du produit par an. Le coût de passation de commande est de 250 $.
    Le coût par produit d'en commander 2000 à la fois est :
    [math]C(2000)=\displaystyle\frac{250}{2000}+ \displaystyle\frac{100\times 0.2}{360} \times \displaystyle\frac{2000}{2\times 200}=0.403[/math]
    Le coût par période est de :
    [math]C(2000)=250+ \displaystyle\frac{100\times 0.2}{360} \times \displaystyle\frac{2000^2}{2\times 200}=805.6[/math]

    Soit une valeur de :[math]\displaystyle\frac{805.6}{2000}=0.403[/math] par produit.
    Le coût par unité de temps est de
    [math]C(2000)=\displaystyle\frac{250 \times 100}{2000}+ \displaystyle \frac{100 \times 0.2}{360} \times \frac{2000}{2}=80.56[/math]
    Soit une demande par produit de [math]\displaystyle\frac{80.56}{200}=0.403[/math]
    LE tout se tient.

    Sensibilité de la quantité éconnomique de commande

    Contexte


    Les formules de Wilson donnent les valeurs suivantes :

    La formule du calcul du coût d'une politique consistant à commander "Q" produits est :
    [math] C(Q)=Cs\times \displaystyle\frac{Q}{2}+ \displaystyle\frac{Cl\times d}{Q} = Cs\times\displaystyle\frac{d\times T}{2} + \displaystyle\frac{Cl}{T}[/math]

    Et la solution optimale est :

    [math]Q^\star= \sqrt{\displaystyle\frac{2 \times Cl \times d}{Cs}}[/math] et[math]T^\star= \sqrt{\displaystyle\frac{2*Cl}{Cs*d}}[/math]

    Pour un coût de :

    [math]C(Q^\star)= \sqrt{2\times Cl\times d \times Cs}[/math]

    On peut s'intéresser à lier d'une augmentation de x% de la quantité commandée à une augmentation de y% du coût de la politique optimale.

    Développement mathématiques


    Il faut donc résoudre l'équation :

    [math]C(Q^\star \times(1+x))= (1+y)\times C(Q^\star)[/math]

    [math]C(Q^\star \times(1+x))= \displaystyle\frac{Ts\times (1 +x) \times \sqrt{\displaystyle\frac{2 \times Cl \times d}{Cs}}}{2}+ \displaystyle\frac{Cl\times d}{(1 +x)\times \sqrt{\displaystyle\frac{2 \times Cl \times d}{Cs}}} [/math]

    [math]C(Q^\star \times(1+x))= (1+x) \times \sqrt{\displaystyle\frac{Cs\times Cl \times d}{2}} + \displaystyle\frac{1}{(1+x)} \times \sqrt{\displaystyle\frac{Cs\times Cl \times d}{2}}[/math]
    Soit :
    [math]C(Q^\star \times(1+x))= ((1+x)+ \displaystyle\frac{1}{(1+x)}) \times \displaystyle\frac{C(Q^\star)}{2}[/math]

    D'ou la nouvelle équation :

    [math] \left( 1+x+ \displaystyle\frac{1}{(1+x)} \right)= 2 \times (1+y)[/math]

    Soit
    [math] x^2-2\times y-2\times x \times y=0[/math]
    Clairement, cette équation a deux solutions, données par:
    [math]x=y+\sqrt{y^2+2\times y}[/math]
    et
    [math]x=y-\sqrt{y^2+2\times y}[/math]

    Exemple :

    Si on tolère une variation de 5% (soit y=0.05) du coût de la politique, on peut tolérer une variation de x de -0.27 et +0.37, soit une plage pour Q de [math][-0.83\times Q^*; +1.37\times Q^*][/math]. On devrait donc plutôt parler de fenêtre optimale que de quantité économique de commande. Car s'écarter de 5% du coût de la politique optimale, lorsque l'on sait les approximations de modélisation faites, cela ne semble pas énorme, mais si on l'accepte, la fenêtre sur Q est déjà large.

    Stock de sécurité

    Contexte


    Le stock de sécurité est rendu nécessaire par l'aspect stochastique du délai d'approvisionnement et de la demande durant ce délai.
    On ne peut jamais se prémunir complètement contre les ruptures de stock. Un stock de sécurité permet d'atteindre un certain niveau de service. Le niveau de service peut se définir de plusieurs manière. Par exemple :
    • Le nombre probable de clients non servis par cycle de commande ou par an,
    • Le nombre probable de produits non livrés par cycle ou par an,
    • La probabilité de ne pas avoir de rupture sur un cycle ou une année
    • Le probabilité d'avoir K cycles avec rupture dans une année.

    Les indicateurs du niveau de service les plus souvent utilisés sont les deux derniers. Ils sont liés par la relation suivante:
    [math]Prup(K,N)=C^K_N \times Pr^k(1-Pr)^{N-k}[/math].

    Avec [math]Prup[/math] qui est la probabilité de rupture sur un cycle et [math]Prup(k,N)[/math]la probabilité d'avoir exactement K cycles avec rupture sur une séquence de N cycles:
    À partir de cet indicateur, on peut facilement calculer la probabilité d'avoir moins de k ruptures sur une séquence de N cycles de commande.
    Le calcul du stock de sécurité dépend du type de politique (Q, SA) ou (T, R)

    Cas de la politique [math](Q,SA)[/math]


    La politique [math](Q,SA)[/math] consiste à commander la quantité Q (dite EOQ ou quantité économique de commande) dès que le niveau de stock atteint le niveau [math]SA[/math], calculé comme :
    [math]SA=d\times DA[/math]
    Avec [math]d[/math] est la demande moyenne durant le délai d'approvisionnement [math]DA[/math].

    Cas général

    Si l'on note [math]Di[/math] la variable aléatoire (continue) représentant la loi de distribution de la demande sur une période de [math]i[/math] unités de temps et [math]DA[/math] la loi de distribution (discrète) du délai d'approvisionnement, pour un stock de sécurité [math]SS[/math], la probabilité d'avoir une rupture de stock est:
    [math]Prupt(SS+SA)= \displaystyle \sum_{i=0}^{+infini}{P(DA=i)\times P(Di>SS+SA)}[/math]

    Exemple:
    Soit un produit dont la demande journalière suit une loi normale de moyenne 100 et d'écart type 30, et un délai d'approvisionnement pouvant aller de 3 à 5 jours avec les probabilités (0,7; 0,2; 0.1). Sous l'hypothèse que les demandes journalières sont indépendantes, avec [math]SS+SA=380[/math], la probabilité de rupture est :
    [math]Prup(380)= 0,7*PR(N(300, \sqrt{3} \times 30)>380) + 0,2*PR(N(400, \sqrt{4} \times 30)>380) + 0,1*PR(N(500, \sqrt{5} \times 30)>380) [/math]
    [math]Prup(380)= 0,26 [/math]
    [math]Prup(510)= 0,05 [/math]

    Calculer le modèle inverse analytiquement n'est en général pas facile. Soit on procède par simulation (il est facile de tracer [math]Prup(X)[/math] et de choisir la valeur adéquate), soit on passe par une approche plus pragmatique.

    Approche approchée


    Dans la majeure partie des cas, on peut approximer l'équation de la probabilité de rupture par son dernier terme :
    [math]Prupt(SS+SA)= \displaystyle \sum_{i=0}^{+infini}{P(DA=i)\times P(Di>SS+SA)}= P(DA=DAMAX)\times P(D_{DAMAX}>SS+SA)[/math]

    [math]Prupt(SS+SA)= P(DA=DAMAX)\times \left( 1-F_{D_{DAMAX}} \left( SS+DA \right)\right)[/math]
    Ou [math]F_{D_{DAMAX}} [/math] est la fonction de répartition de la demande durant le délais [math]DAMAX[/math]

    Sous ces hypothèses, on peut calculer analytiquement le stock de sécurité à acquérir pour obtenir une probabilité de rupture [math]Prupt = P [/math] déterminée à priori:
    [math] SS+SA= F^{-1}_{D_{DAMAX}} \left( 1-
    \displaystyle \frac {P}{P(DA=DAMAX)} \right) [/math]

    Pour cela, il faut évidement, entre autre, que [math] \displaystyle \frac {P}{P(DA=DAMAX)} < 1 [/math]. Sinon cela n'a pas de sens.

    Exemple
    Dans l'exemple précédent, [math]DAMAX=5 [/math], [math]P(DA=DAMAX)=0.1[/math], et la loi de probabilité suivi par la demande en 5 jours est une loi normale de moyenne 500 et d'écart type [math]\sqrt{5} \times 30 [/math].
    Pour un taux de service de 0.95, l'approximation est de 500 (Prupt(500)=0,06)
    Pour un taux de service de 0.93, l'approximation est de 535 (Prupt(535)=0,032)

    Exception
    Il y a donc deux cas ou cette approximation est fausse :


    • Si [math]SS+SA[/math] est très petit, alors Prupt(SS+SA) est très grand et les termes inférieurs à [math]DAMAX[/math] ne sont plus négligeables

    • P(DA=DAMAX) est très petit si bien que le terme en [math]P(Da=DAMAX-1)/[math] devient non négligeable.

    Dans le premier cas, il est rare que l'on s'intéresse à un stock de sécurité offrant un taux de service très bas. Pour le second cas, si [math]P(Da=DAMAX)[/math] est très petit, c'est que l'on doit changer de [math]DAMAX[/math].

    Approche pragmatique

    Si la demande journalière est telle que l'on puisse considérer qu'elle est entre [math][d-\triangle (d), d+\triangle (d)] [/math] et que le délai d'approvisionnement est compris entre [math][DA-\triangle (DA), DA+\triangle (DA)] [/math], alors il est raisonnable (et même presque trop prudent) d'utiliser un stock de sécurité de : [math]d \times \triangle (DA)+ DA \times \triangle (d) [/math]

    En effet, la demande maximale est de

    [math] Max= d \times DA + d \times \triangle (DA)+ DA \times \triangle (d)+ \triangle (DA) \times \triangle (d)[/math]
    [math] Max= SA + d \times \triangle (DA)+ DA \times \triangle (d)+ \triangle (DA) \times \triangle (d)[/math]

    Or
    [math] \triangle (DA) \times \triangle (d)[/math] est une incertitude du second ordre, négligeable.

    Exemple
    Dans l'exemple précédent, si on considère que la demande est comprise entre [math][100-40, 100+40][/math] (donc une probabilité d'environ 0.9 d'être inférieur à 140), et le délai entre [math][3, 4][/math] (soit encore une probabilité de 0.9), alors
    [math]d \times \triangle (DA)+ d \times \triangle (d) = 220 [/math] et commander [math]SA+220 = 520 [/math] induit une probabilité de rupture de :[math]Prup(520)= 0,04 [/math], ce qui peut sembler raisonnable.

    Cas de la politique (T,R)

    Cette politique consiste à faire venir à date fixe une quantité variable de produit qui ramène un inventaire à un niveau de réapprovisionnement constant R.
    Concrètement, le niveau de réapprovisionnement [math] R = Q*+SS [/math]

    Dans ce cas, comme le cycle d'approvisionnement est régulier (T = constante) l'incertitude sur la largeur de la période est nul.

    La probabilité de rupture avec un stock SS est donc [math] Prup(SS)= Pr (D_T > Q^*+SS)[/math] ou [math] D_T [/math] est la loi de distribution de la demande durant la période de T jours.

    Le stock de sécurité permettant d'obtenir un niveau donné de service (probabilité de rupture sur un cycle) est alors assez facile à calculer:

    Utilisation du stock de sécurité


    Le stock de sécurité est là pour être consommé. Curieusement, certaines entreprises le considèrent comme un stock de guerre, préférant ne pas livrer plutôt que de consommer le stock de sécurité. C'est une erreur.En moyenne, le stock de sécurité doit être attaqué un cycle sur deux.