Optimisation d’un modèle de planification tactique d’une chaîne logistique de type Flow Shop Hybride

22/09/2017
Publication e-STA e-STA 2008-1
OAI : oai:www.see.asso.fr:545:2008-1:19873
DOI :

Abstract

Optimisation d’un modèle de planification tactique  d’une chaîne logistique de type Flow Shop Hybride

Metrics

24
8
193.08 KB
 application/pdf
bitcache://7e74846abbec8844c3a3b61a59edf51dd0fd139f

License

Creative Commons None (All Rights Reserved)
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/545:2008-1/19873</identifier><creators><creator><creatorName>Michael Comelli</creatorName></creator><creator><creatorName>David Lemoine</creatorName></creator></creators><titles>
            <title>Optimisation d’un modèle de planification tactique  d’une chaîne logistique de type Flow Shop Hybride</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2017</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Fri 22 Sep 2017</date>
	    <date dateType="Updated">Fri 22 Sep 2017</date>
            <date dateType="Submitted">Mon 15 Oct 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">7e74846abbec8844c3a3b61a59edf51dd0fd139f</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>33780</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

Résumé — Cet article traite de problèmes de planification tactique des chaînes logistiques de type flow shop hybride. Malgré la pertinence des problèmes de planification multi-site, l’étude de la littérature montre l’absence de modèle de planification générique. Nous appuyant sur un cas d’étude industriel, nous proposons un modèle mathématique générique pour la planification tactique de ce type de chaîne logistique. Nous donnons un état de l’art sur le modèle de « Lot-Sizing » dont est issue notre formalisation. Dans celui-ci, nous donnons les principales extensions de ce modèle, ainsi que les méthodes de résolution rencontrées dans la littérature. Devant la complexité de notre problème, nous proposons une méthode d’optimisation à base de recuit simulé. Mots clés — planification, chaîne logistique, nomenclature Linéaire, modèle mathématique, métaheuristique. I. INTRODUCTION ANS cet article, nous nous intéressons aux problèmes de planification tactique de la chaîne logistique. Les problématiques traitées diffèrent principalement selon deux critères : planification mono-niveau (plan directeur de production des produits finis) ou multi-niveau (planification des composants) et planification mono-site ou multi-site. Communément, les problèmes de planification sont formalisés par des modèles mathématiques dits de « lot sizing ». Parmi ceux-ci, le « Capacitated Lot Sizing Problem » (CLSP) est considéré comme un modèle de référence permettant de traiter la problématique de génération de plan directeur de production dans un contexte mono-site. Concernant la planification multi- niveau, le « Multi Level Capacitated Lot Sizing problem » (MLCLSP) est reconnu comme modèle de référence et traite des problématiques MRP et MRPII. Si les problématiques mono-site ont été largement étudiées dans la littérature, Comelli et al. [1] soulignent l’absence de modèle de référence pour les problématiques multi-site. Ceci s’explique notamment par la diversité des chaînes logistiques et des problématiques traitées. Néanmoins, de par la nature multi-niveau de la production multi-site, les modèles de la littérature (Rizk et al. [3], Thierry et al. [4] …) sont dérivés du modèle du MLCLSP. Partie intégrante de la problématique de planification multi- site, la synchronisation des plans de production des divers sites de production représente depuis plusieurs années un enjeu majeur de l’optimisation des chaînes logistiques. Dans le cas d’une chaîne logistique externe, comprenant donc plusieurs entités indépendantes, proposer une synchronisation des sites suppose une collaboration forte et un partage de l’information entre les différents acteurs. Pour réaliser celle-ci, deux approches peuvent être adoptées : une approche centralisée ou décentralisée (Thierry et al. [4]). L’adoption d’une approche centralisée, supposant donc une très forte (mais hypothétique) collaboration des différents acteurs de la chaîne logistique, permet de concevoir des plans de production apportant une solution globalement meilleure que celle obtenue par une approche décentralisée. Mais il est évident qu’une telle approche ne devient totalement pertinente que dans le cas d’une chaîne logistique interne, où le partage de l’information s’il n’est pas total est pour le moins très fort. Cet article se focalise donc sur l’étude de la planification tactique d’une chaîne logistique par une approche centralisée. Une classification des problèmes de planification de chaînes logistiques peut être également établie en fonction de la typologie de la nomenclature des produits qu’elle fournit. En se limitant aux nomenclatures convergentes, nous pouvons distinguer trois types : les nomenclatures linéaires, d’assemblages et générales. Cet article s’intéresse aux chaînes logistiques dites à nomenclature linéaire : la gamme des produits est réalisée successivement sur plusieurs sites. Ces dernières sont typiques des industries de métallurgie où les produits peuvent être transformés, puis usinés sur plusieurs sites. Cet article est articulé de la manière suivante : dans une première partie, nous présentons le cas d’étude industriel et ses spécificités sur lequel s’appuie notre étude. Dans une seconde partie, un état de l’art sur le modèle de référence de planification multi-niveau, le MLCLSP, sera donné. Un état de l’art traitant de problèmes à nomenclature linéaire permettant de situer notre problématique sera ensuite donné. Dans une troisième partie, un modèle générique de planification tactique pour les chaînes logistiques de type flow shop hybride sera donné. Enfin une méthode de résolution, basée sur un recuit simulé, sera détaillée dans une quatrième partie. II. CAS D’ETUDE INDUSTRIEL L’étude de cas concerne la planification d’une chaîne logistique interne. Elle est constituée de six usines : U1, U2, U3, U4, U5 et U6. La nomenclature des produits est considérée comme linéaire, bien que des composants soient adjoints à ceux-ci au fur et à mesure de leurs transformations : la problématique de planification se limite au produit principal. La Figure 1 présente le synoptique des flux suivis par les produits au travers de cette chaîne logistique. La chaîne logistique étudiée est constituée de quatre étages. Au second étage, chaque produit peut être transformé indépendamment par les trois usines le composant. A chaque étage est assigné un stock où les produits qui auront été transformés par une usine le composant seront entreposés. Ainsi, à l’instar des structures d’ateliers étudiés par la communauté d’ordonnancement, nous MICHAEL COMELLI1 , DAVID LEMOINE1 1 LIMOS CNRS UMR 6158 Complexe scientifique des Cézeaux, 63177 Aubière Cedex, France comelli@isima.fr, lemoine@moniut.univ-bpclermont.fr Optimisation d’un modèle de planification tactique d’une chaîne logistique de type Flow Shop Hybride D e-STA copyright © 2008 by see Volume 5 (2008), N°1 pp 8-13 appelons cette structure : chaîne logistique de type Flow Shop Hybride. Fig. 1. Cas d’étude industriel L’objectif de l’étude est de proposer une planification tactique pour l’ensemble de la chaîne logistique, consistant à générer pour chaque usine, un plan directeur de production sur un horizon de 12 mois à la maille semaine, ces différents plans devant être synchronisés sur l’ensemble de la chaîne. Au niveau de l’étage 2, la production peut s’effectuer sur n’importe quelle usine ce qui constitue un problème d’allocation de production. Les contraintes de transport entre les différents sites de production ne sont pas prises en compte. Une contrainte dite de périodicité est considérée : un produit obtenu en période t (donc stocké en t) n’est disponible pour un autre site de production ou pour un client qu’au début de la période t+1. Le but de notre formalisation est de fournir un ensemble de plans de production synchronisés minimisant les coûts de mis en œuvre. Traditionnellement, dans les modèles de « lot sizing » deux coûts sont pris en compte : les coûts de stockage et de lancement de campagne. Dans cette étude, la contrainte de périodicité impose à chaque article de rester au moins une période en stock : le coût de stockage engendré est donc peu pertinent en termes d’optimisation. Ainsi un coût de « surplus » est défini et correspond aux articles restant en stock plus d’une période. Par ailleurs, la demande peut ne pas être satisfaite, engendrant ainsi un coût de « demande perdue ». L’objectif est donc de proposer des plans directeurs de production synchronisés minimisant la somme de ces trois coûts : les coûts de lancements, de surplus et de demande perdue. Dans la section suivante, un état de l’art centré sur le MLCLSP, modèle de référence pour les problèmes multi- niveau est présenté. III. ETAT DE L’ART La planification dans le cas d’une coordination centralisée des activités d’une chaîne logistique fait l’objet d’une littérature abondante. Au centre de cette préoccupation, la planification tactique, dont l’un des buts majeurs est l’élaboration de plans de production pour chaque site de fabrication, joue un rôle prépondérant. Dans le contexte d’une chaîne logistique, l’élaboration de tels plans suppose une synchronisation (dite horizontale) de la part de tous les acteurs intervenant dans le processus de fabrication. Dans un cas général, celle-ci vise à assurer la fabrication et la mise à disposition en temps utile des composants nécessaires à l’obtention des produits finis afin de répondre au mieux à la demande client, avec un coût minimum pour la chaîne logistique. Des modèles mathématiques ont été développés pour tenter d’optimiser ces deux critères souvent antagonistes. Ceux-ci sont généralement dérivés des modèles de Lot sizing multi-niveau. La figure 2 (Comelli et al. [1]) montre une classification des extensions proposées dans la littérature pour le MLCLSP (Le MLLP, Multi-Level Lot Sizing Problem étant vu comme un MLCLSP à capacité infinie). Fig. 2. Classification des extensions pour le MLCLSP (Comelli et al. [1]) Cette classification montre que les extensions des modèles multi-niveau sont nombreuses et que chacune d’elles a été finalement étudiée par peu d’auteurs, rendant difficile la comparaison des méthodes de résolution proposées pour l’ensemble des instances. Le tableau 1 est extrait de la classification précédente et fait apparaître les auteurs proposant des résultats pour des nomenclatures linéaires. Il présente les extensions, méthodes et instances étudiées par ceux-ci. TABLEAU 1 LES NOMENCLATURES LINEAIRES Auteurs Modèle Méthodes Instances Blackburn et al. [5] MLLP Heuristiques de construction niveau par niveau 1 produit fini, 5 niveaux, 12 périodes Maes et al. [6] MLCLSP + setup time Heuristique basé sur de la relaxation linéaire 3 produits finis, 3 niveaux, 10 périodes Clark et al. [7] MLCLSP + setup time + lead time Branch and Bound 1 produit fini, 10 niveaux, 12 périodes Vörös [8] MLLP Solveur 1 produit fini, 2 niveaux, 4 périodes Ce tableau montre qu’aucune des formalisations proposées ne traite des spécificités de notre problème. Nous pouvons également remarquer la taille extrêmement réduite des instances traitées. Les modèles multi-niveau permettent de planifier la production des composants nécessaires à la fabrication des U1 U2 U3 U4 U5 U6 Etage 1 Etage 2 Etage 3 Etage 4 I1 I2 I3 I4 Usine Stock Flux physique Etage e-STA copyright © 2008 by see Volume 5 (2008), N°1 pp 8-13 produits finis. Pour cela, ils utilisent une matrice appelée « gozinto » qui permet de lier la demande des produits entre eux. Dans le cas d’une nomenclature linéaire, cette matrice prend une forme particulièrement simple puisqu’il s’agit d’un bloc de Jordan nilpotent. Parmi les auteurs cités dans le tableau 1, la majorité modélise les problématiques linéaires grâce à une telle matrice. Néanmoins, la structure particulière de la matrice « gozinto » a permis à certains de proposer des modèles dédiés à ce type de nomenclature : la formalisation donnée par Vörös [8] illustre les modèles multi-niveau dédiés aux nomenclatures linéaires : ( ) ( )( ) [ ] [ ] [ ] 1 1 1, , 1 1, 0 (1) 1, (2) [1, ], 1, (3) 0 [1, ] (4) , 0 [1, ], 1, (5) T M mt mt mt mt t m M t t m t mt m t mt m mT mt mt Min C Q H I Q D t T I Q Q I m M t T I I m M I Q m M t T = = + − + + = ∈ + = + ∈ ∈ = = ∈ ≥ ∈ ∈ ∑∑ Où Dt représente la demande pour la période t, Qmt la production de l’usine m à la période t, Cmt(Qmt) le coût de production pour l’usine m pour la période t. Imt représente le nombre de produits en stock à l’usine m à la fin de la période t, Hmt(Imt) le coût de stockage pour l’usine m pour la période t. (1) représente la somme des coûts de production et de stockage sur tout l’horizon, pour tous les produits. (2) indique que la production pour la dernière usine couvre exactement la demande. (3) est l’équation d’équilibre des stocks. (4) indique qu’il n’y a ni stock initial, ni stock final (5) représente les contraintes de positivité. Ce modèle ne prenant pas en compte les spécificités de notre cas d’étude, nous présentons dans le paragraphe suivant notre modèle de planification tactique pour une chaîne logistique à nomenclature linéaire. Basé sur le modèle de Vörös [8], il peut donc être considéré comme une extension du MLCLSP à nomenclature linéaire. IV. UN MODELE GENERIQUE DE PLANIFICATION Le problème de planification étudié diffère du modèle précédent par l’ajout des spécificités suivantes : - la présence de plusieurs sites pouvant effectuer la même opération de gamme pour un même niveau de la chaîne (chaîne logistique de type Flow Shop Hybride). - la contrainte de périodicité. Le but de cette dernière est d’assurer qu’une quantité produite à la période t n’est disponible pour un autre site qu’en t+1. - La contrainte de perte de commandes dite de "shortage". Dans ce problème, le coût d’une commande perdue est estimé, il est néanmoins possible de se ramener à un problème sans perte de commande en augmentant celui- ci. - La fonction objectif vise à minimiser la somme des coûts de lancement de campagne, de surplus et de demande perdue. Nous proposons un modèle mathématique issue du MLCLSP pour une chaîne logistique de type Flow Shop Hybride. Les paramètres de ce modèle sont les suivants: T : Longueur (en périodes) de l’horizon de planification, N : Nombre de type de produits finis à planifier, P : Nombre d’étages (et de stocks) de la chaîne logistique, N(k) : Les usines composant l’étage k de la chaîne logistique, Dit : Demande en produit fini i à la fin de la période t, Ii,k,0 : Quantité initiale en produit i dans le stock k, Cjt : Capacité maximale disponible à l’usine j durant la période t, hikt : Coût de surplus pour un produit i entreposé dans le stock k durant la période t, sit : Coût de lancement de campagne pour le produit i durant la période t, rit : Coût de demande perdue pour un produit i durant la période t. Les variables de décision du modèle sont : Qijt : Quantité de produit i fabriqué par l’usine j durant la période t, Xijt : Variable binaire qui prend la valeur 1 s’il y a un lancement de campagne pour le produit i dans l’usine j à la période t, Iikt : Quantité de produit i entreposée dans le stock k durant la période t, Yikt : Quantité de produit i en surplus dans le stock k durant la période t, DPit : Demande perdue en produit i durant la période t, DSit : Demande servie en produit i durant la période t. L’objectif (6) de notre modèle est donc : 1 1 1 ( ) 1 Minimiser (6) N T P P it ijt ikt ikt it it i t k j N k k s X h Y r DP = = = ∈ =      + +          ∑∑ ∑ ∑ ∑ La contrainte (7) détermine la quantité de demande perdue : [ ] [ ]( , ) 1, 1,it it itD DS DP i t N T= + ∀ ∈ × (7) La contrainte (8) est la contrainte d’équilibre des stocks concernant les (P-1) premiers stocks de la chaîne logistique : [ ] [ ] [ ] , , 1 , , , , 1 , ', 1 ( ) ' ( 1) ( , , ) 1, 1, 1 0, 1 i k t i k t i j t i j t j N k j N k I I Q Q i k t N P T + + + ∈ ∈ + = + − ∀ ∈ × − × − ∑ ∑ (8) La contrainte (9) représente la contrainte d’équilibre des stocks pour le dernier stock de la chaîne : [ ] [ ] , , 1 , , , , 1 , 1 ( ) ( , ) 1, 0, 1 i P t i P t i j t i t j N P I I Q DS i t N T + + + ∈ = + − ∀ ∈ × − ∑ (9) La contrainte (10) est la contrainte de périodicité pour les P étages de la chaîne: La fabrication d’un produit i à l’étage k+1 durant la période t+1 est limitée par la quantité en stock k à la fin de la période t : e-STA copyright © 2008 by see Volume 5 (2008), N°1 pp 8-13 [ ] [ ] [ ], , 1 , 1, ( ) ( , , ) 1, 2, 1,i j t i k t j N k Q I i k t N P T+ − ∈ ≤ ∀ ∈ × ×∑ (10) La contrainte (11) représente la contrainte de périodicité concernant la demande servie : [ ] [ ], 1 , , ( , ) 1, 1,i t i P tDS I i t N T+ ≤ ∀ ∈ × (11) La suivante (12) détermine les lancements de campagne: ( ) [ ] [ ] [ ] , 1, 1, , ( ) 1, ijt jt ijt ijt ijt Q C X i t N T Q X j N k k P ≤ × ∀ ∈ ×  ≥ ∀ ∈ ∀ ∈ (12) La contrainte (13) est la contrainte de capacité : [ ] [ ] 1 1, , ( ), 1, N ijt jt i Q C t T j N k k P = ≤ ∀ ∈ ∀ ∈ ∀ ∈∑ (13) La contrainte (14) permet de déterminer le niveau de surplus pour chaque produit et chaque période pour les (P-1) premiers stocks : [ ] [ ] [ ] , , , , , ', 1 ( 1) ( , , ) 1, 1, 1 0, 1 i k t i k t i j t j N k Y I Q i k t N P T + ∈ + = − ∀ ∈ × − × − ∑ (14) La contrainte (15) est la contrainte de surplus concernant le dernier étage de la chaîne : [ ] [ ], , , , , 1 ( , , ) 1, 0, 1i P t i P t i tY I DS i k t N T+= − ∀ ∈ × − (15) Les dernières contraintes (16) et (17) sont les contraintes d’intégrité et de positivité : { } [ ] [ ] [ ]0,1 ( , ) 1, 1, , ( ), 1, (16)ijtX i t N T j N k k P∈ ∀ ∈ × ∀ ∈ ∀ ∈ [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] 0 ( , ) 1, 1, , ( ), 1, , 0 ( , , ) 1, 1, 1, (17) , 0 ( , ) 1, 1, ijt ikt ikt it it Q i t N T j N k k P Y I i k t N P T DS DP i t N T ≥ ∀ ∈ × ∀ ∈ ∀ ∈ ≥ ∀ ∈ × × ≥ ∀ ∈ × V. METHODE D’OPTIMISATION Notre problème, basé sur le « MLCLSP » qui est un problème NP-difficile, est donc par extension NP-difficile. Au regard de l’état de l’art donné par Comelli et al. [1], il est possible de souligner la faible utilisation des métaheuristiques pour la résolution de problèmes basés sur le MLCLSP. De façon analogue, Brahimi [2] a dressé un tel constat pour les problèmes de lot sizing (notamment pour le problème mono- niveau à un produit avec capacité). D’après lui, ces méthodes pourraient aboutir à des résultats très intéressants. Cet article propose en réponse à ce constat une métaheuristique à base de recuit simulé dont le but est de pouvoir générer des solutions de bonne qualité pour des instances de taille réelle (20 produits, 100 périodes). Ce type de métaheuristique est basé sur deux éléments : - un codage générique permettant de représenter les solutions du problème, - un système de voisinage (une application permettant de passer d’une solution à une autre -son voisin-). La figure 3 illustre le principe de fonctionnement de notre recuit simulé. Heuristique de construction Voisinage 1 Voisinage 2 Voisinage 3 Réparation 1 Réparation 3 Données Solution admissible Solution non admissible Solution admissible Système de voisinage Recuit simulé Solution admissible Réparation 2 probabilité 1 probabilité 2 probabilité 3 Fig. 3. Fonctionnement du recuit simulé Dans la littérature, deux codages sont proposés (Figure 4). Le premier (le plus courant) consiste à utiliser une matrice A binaire dont les éléments ait représentent les lancements de campagne pour chaque produit i à chaque période t. Un élément ait de cette matrice prendra la valeur 1 si l’article i durant la période t, 0 sinon. Mais il n’est pas possible d’évaluer directement la solution engendrée par la matrice. En effet, cette dernière peut correspondre à plusieurs plans directeurs de production réalisables. C’est pour cela qu’à l’instar de Kuik et al.[9], les différents auteurs utilisant ce codage déterminent un plan directeur de production associé en utilisant un algorithme glouton répartissant la production sur les périodes retenues dans la matrice, permettant ainsi une évaluation de la solution en terme de coût. Mais, les algorithmes utilisés par les auteurs ne garantissent pas l’optimalité du plan construit pour la matrice considérée. Le second type de codage consiste à utiliser une matrice B dont les éléments bit sont les quantités de produit i à fabriquer durant la période t (en fait, B est un plan de production). La combinatoire de cette représentation est évidemment beaucoup plus élevée, mais celle-ci permet de s’affranchir des heuristiques de construction précédentes. 1 0 0 1 0 20 0 0 15 0 1 0 1 0 0 30 0 70 0 0 0 1 0 1 0 0 50 0 30 0                     Codage 1 Codage 2 A= B= Fig. 4. Les deux types de codage e-STA copyright © 2008 by see Volume 5 (2008), N°1 pp 8-13 Ainsi, nous proposons de représenter une solution Q en nous basant sur le second type de codage que nous étendons à l’ensemble de la chaîne logistique sous la forme : ( ) ( ) ( ) (1) ( ) ( ) x x x1 1 1 P étages Q B B B N N k N P x x x= = =    =     ⋯ ⋯ Comme indiqué dans la figure 3, le système de voisinage adopté pour notre recuit simulé garantit l’admissibilité des voisins qu’il génère. Cela signifie que l’espace exploré par notre métaheuristique est celui des solutions réalisables. Ceci nécessite donc l’obtention d’une solution initiale admissible : c’est le rôle de l’heuristique de construction au sein de notre méthode d’optimisation. Pour pouvoir utiliser cette heuristique, nous faisons l’hypothèse que l’étage goulot ne varie pas en fonction du temps. L’heuristique agit de la façon suivante : - Dans une première étape, et comme l’illustre la figure 5, elle agrège chaque étage de la chaîne logistique et ne considère donc plus qu’une seule usine par étage. La capacité de celle-ci est donc la somme des capacités des usines de l’étage correspondant. ∑ ∈ = )1( 1 Ni itt CCa ∑ ∈ = )(kNi itkt CCa ∑ ∈ = )(PNi itPt CCa Fig. 5. Le principe d’agrégation des étages - Dans une seconde étape, elle identifie l’usine agrégée goulot. En tenant compte des contraintes de périodicité, elle lisse la demande sur cette usine. - Dans une troisième étape, le planning de l’usine goulot est reporté sur toutes les usines agrégées, en tenant compte des contraintes de périodicité. - Dans une quatrième et dernière étape, elle répartit le planning de chaque usine agrégée sur les usines composant l’étage considéré. Ce problème d’affectation est résolu de la façon suivante : Pour l’étage k, on commence par affecter le maximum de production sur l’usine 1, en considérant un produit après l’autre. Si celle-ci est saturée, on passe à l’usine 2 et ainsi de suite jusqu’à l’usine N(k). Ainsi, notre heuristique nous assure bien l’obtention d’une solution réalisable, la faisabilité du problème étant assurée par la possibilité d’abandonner tout ou partie d’une demande. Les problèmes de « lot sizing » ont la particularité d’être plus ou moins complexes à résoudre en fonction de la nature et de la structure des instances (hiérarchie des coûts pris en compte et emplacement du goulot au sein de la chaîne logistique). En restreignant l’étude aux trois coûts majeurs : coût de demande perdue (CDP), coût de surplus (CS) et coût de lancement (CL), il est possible de constater l’antagonisme de ces trois critères. Par suite, élaborer une « bonne » solution consiste à trouver un compromis entre un niveau de demande satisfaite, un niveau de stockage et le nombre de lancement de campagne en déterminant des quantités produites à chaque période sur chaque usine. Ce compromis peut être obtenu de deux manières : soit en augmentant ou en diminuant les quantités produites sur une ou plusieurs périodes, soit en regroupant les quantités de périodes consécutives. Aussi, les systèmes de voisinage que nous proposons sont les suivants : ils consistent à choisir aléatoirement une usine x, un produit i et une période t et à appliquer respectivement un des trois stratégies suivantes : - pour le système de voisinage 1, la production d’articles i pour la période t sur l’usine x est augmentée d’une quantité choisie aléatoirement. Cela permet de modifier la demande satisfaite ainsi que les quantités en stock. Celui-ci est illustré par la figure 6. 0 10 0 20 0 15 0 30 10 5 5 14 18 10 6           0 20 0 20 0 15 0 30 10 5 5 14 18 10 6           augmentation Usine x Usine x Fig. 6. Le système de voisinage 1 - pour le système de voisinage 2 (« regroupement à gauche ») nous regroupons la production du produit i des périodes t et t+1 pour l’usine x, la quantité de la période t+1 étant ajoutée à la période t. La figure 7 montre son principe de fonctionnement. 0 10 0 20 0 15 0 30 10 5 5 14 18 10 6           0 20 0 20 0 15 0 30 10 5 5 32 0 10 6           Regroupement à gauche Usine x Usine x Fig. 7. Le système de voisinage 2 - comme décrit dans la figure 8, pour le système de voisinage 3 (« regroupement à droite ») on regroupe la production du produit i des périodes t et t+1 pour l’usine x, la quantité de la période t étant ajoutée à la période t+1. 0 10 0 20 0 15 0 30 10 5 5 14 18 10 6           0 20 0 20 0 15 0 30 10 5 5 32 0 28 6           Regroupement à droite Usine x Usine x Fig. 8. Le système de voisinage 3 En partant d’une solution admissible, appliquer l’un des trois systèmes de voisinage va fréquemment générer une solution non réalisable : en effet, modifier une quantité de production d’un site crée des surplus négatifs si les changements ne sont pas répercutés sur les autres plans de production. Il est donc nécessaire d’adjoindre à chaque système de voisinage une e-STA copyright © 2008 by see Volume 5 (2008), N°1 pp 8-13 procédure de réparation restaurant l’admissibilité de la nouvelle solution générée en rétablissant la positivité des surplus. De plus, la modification d’un plan de production peut créer au niveau des stocks des surplus positifs. Ces quantités ont la particularité de ne pas servir la demande satisfaite. Il peut donc être nécessaire de faire évoluer cette dernière afin de prendre en compte la fabrication de ces nouveaux articles. De plus, afin d’optimiser les coûts, il peut être nécessaire de diminuer ces quantités en surplus. Ainsi chacune des procédures de réparation est enrichie afin de prendre en compte ces considérations. Comelli et al. [10] ont développé un modèle mathématique dédié au cas d’étude industriel. Pour tester l'efficacité de notre démarche, nous nous sommes servis des résultats qu’ils ont obtenus sur des instances de petite taille résolues de manière optimale grâce à un solveur. Ainsi, nous avons pu valider d’une part les résultats obtenus par notre modèle mathématique et d’autre part la performance de notre méthode. Actuellement nous effectuons des campagnes de tests sur des instances de grande taille et les premiers résultats sont encourageants. VI. CONCLUSION ET PERSPECTIVES Les problèmes de planification tactique de la chaîne logistique sont des problèmes complexes et d’actualité. Ils constituent une problématique de recherche très importante. Dans cet article, nous avons proposé un modèle générique pour la planification tactique d’une chaîne logistique de type Flow Shop Hybride à nomenclature linéaire, dans le cadre d’une approche centralisée. Celui-ci, basé sur le modèle de Vörös [8], intègre de nouvelles contraintes dues à la structure particulière de la chaîne considérée. La difficulté algorithmique de cette formalisation nous a amenés à développer une méthode d’optimisation basée sur une métaheuristique à base de recuit simulé. Celle-ci explorant l’espace des solutions réalisables, nous avons été amenés à élaborer une heuristique de construction permettant de trouver une solution initiale admissible pour notre métaheuristique. Comme nous l’avons précisé précédemment, le but de notre formalisation est de minimiser les coûts afférents à la production d’articles pour une demande connue. Or, Comelli et al. [10] ont montré la pertinence d’une optimisation des flux financiers dans le cadre de la chaîne logistique. Une perspective intéressante serait donc de les intégrer dans notre formalisation afin de généraliser leur approche dans le cadre d’une chaîne logistique à nomenclature linéaire de type Flow Shop Hybride. De plus, nous supposons que la demande est connue à l’avance et ne subit donc aucune modification durant l’horizon de planification. Il serait donc intéressant de prendre en compte un aspect plus dynamique de celle-ci afin d’élaborer une solution plus robuste en terme de planification. A l’instar des modèles de « lot sizing », notre formalisation prend en compte, pour chaque usine, une capacité agrégée. La question de l’obtention et surtout de la vraisemblance de celle-ci demeure une question pertinente. Ainsi, il pourrait être intéressant de coupler à notre formalisation, des modèles de simulation ou des modèles mathématiques intégrant des contraintes opérationnelles afin d’estimer plus correctement les capacités réelles de chaque usine, et de prendre en compte les aléas de production (pannes …). REFERENCES [1] M. Comelli, M. Gourgand, D. Lemoine, « A review of tactical planning models », International Conference Service System and Service Management - IEEE/ICSSSM06, Troyes, France, 2006. [2] N. Brahimi, Planification de la production : modèles et algorithmes pour les problèmes de dimensionnement de lots. Thèse de doctorat, Université de Nantes, 2004. [3] N. Rizk, A. Martel, « Supply chain flow planning methods: a review of the lot-sizing literature », Working paper DT-2001-AM-1, Université Laval (Canada), 2001 [4] C. Thierry, N. Chapeaublanc, P. Lepage, G. Bel, « Multi site Planning: A centralized or a distributed approach? », Conference INRIA, Sophia Antipolis, France, 1994 [5] J. Blackburn, R. Millen, « An evaluation of heuristic performance in multi stage lot sizing systems », International Journal of Production Research, Vol. 23, N°5, pp. 857-866, 1985. [6] J. Maes, J.O. McClain, L.N. Van Wassenhove, « Multilevel capacitated lotsizing complexity and LP- based heuristics », European Journal of Operations Research, Vol.53, pp131–148, 1991. [7] A.R. Clark, V.A. Armentano, « The Application of Valid Inequalities to the MultiStage Lot-Sizing Problem », Computers and Operations Research, Vol.22, pp 669-680, 1995. [8] J. Vörös, « On the relaxation of multi-level dynamic lot-sizing models », International Journal of Production Economics, Vol.77, N°1, pp 53-61, 2002. [9] R. Kuik, M. Salomon, « Multi-level lot-sizing problem: Evaluation of a simulated annealing heuristic », European Journal of Operational Research, Vol.45, N° 1, pp 25-37, 1990. [10] M. Comelli, P. Fenies, M. Gourgand, D. Lemoine, « Optimisation des flux physiques versus optimisation des flux financiers pour la planification d'une Supply Chain ». 7ème congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision - ROADEF 2006, Lille, France, 2006. e-STA copyright © 2008 by see Volume 5 (2008), N°1 pp 8-13