Approche intégrée pour des problèmes à plusieurs niveau

Approche intégrée pour des problèmes à
plusieurs niveau

 Évolution du modèle

Description du problème

Nous nous intéressons à la résolution du problème intégré de planification et d’ordonnancement de la production dans des ateliers multi-ressources de type job-shop. Cependant, nous considérons ici des structures de nomenclature établissant des liens ou des besoins de production entre les produits, c’est-à-dire des problèmes multi-niveaux. De manière plus générale, ceci peut correspondre à des chaînes logistiques comprenant différents sites de production, chaque site fabricant des composants différents pour satisfaire les demandes internes d’autres sites, ainsi que les demandes externes. De manière similaire à l’approche pour des problème mono-niveau, le but est de planifier la production de N produits sur R machines et T périodes en déterminant les dates de début et de fin des O opérations nécessaires pour la fabrication des produits. Les hypothèses considérées pour l’approche du chapitre précédent restent valables. Néanmoins, nous considérons que les produits peuvent avoir besoin de certains composants (d’autres produits) dans leur processus de fabrication. Le problème d’ordonnancement est à nouveau représenté par un graphe disjonctif, où les opérations sont liées par des contraintes de précédence associées aux gammes de fabrication et à l’utilisation des ressources. Ce graphe reste inchangé par rapport au graphe d’un problème mono-niveau puisqu’il n’y a pas d’arcs de précédence entre les couples composant-composé. En plus des données décrites dans le chapitre précédent, nous utilisons par la suite les données suivantes : – dil : demande externe du produit i à la fin de la période l, – Dil : demande totale du produit i à la fin de la période l, – ei : coût unitaire d’échelon stock du produit i, – DS(i) : ensemble des successeurs directs du produit i dans la nomenclature, – AS(i) : ensemble de tous les successeurs du produit i dans la nomenclature, – DP(i) : ensemble des prédécesseurs directs du produit i dans la nomenclature, – AP(i) : ensemble de tous les prédécesseurs du produit i dans la nomenclature, – gij : nombre d’unités du produit i requises pour produire une unité du produit j (gij = 0 si j /∈ DS(i)), – nij : nombre de chemins liant les produits i et j dans la nomenclature, – p n ij : quantité totale du produit i nécessaire pour produire une unité du produit j, en suivant le chemin n dans la nomenclature, – P n (i, j) : n ème chemin reliant le produit i et son successeur j, – Kn (i, j) : somme des délais d’obtention entre les produits i et j ∈ AS(i) à travers le chemin P n (i, j) dans la nomenclature, – Mi : somme maximale des délais d’obtention du produit i, – Ti + Li : période de production au plus tard du produit i, – B : nombre de niveaux de la nomenclature, – BL(b) : ensemble des produits appartenant au niveau b de la nomenclature. Les variables de décision du problème intégré restent les mêmes (tailles des lots Xil et setups Yil), mais nous utilisons en plus les variables dépendantes suivantes : – Eil : échelon stock du produit i à la fin de la période l. Ces notations ont été également utilisées par Afentakis et al. [8], sans prise en compte des délais d’obtention, et par Afentakis et Gavish [7], Clark et Armentano [39, 40] et Berretta et al. [30], avec des délais d’obtention non nuls, pour l’implémentation d’une formulation basée sur l’échelon stock. Ce concept a été introduit par Clark et Scarf [38] et nous l’expliquons plus tard dans cette section. Une différence importante entre la formulation des travaux précédents et la notre est que nous comptabilisons la production Xil à la période où le produit est terminé (la production de i peut commencer au plus tôt au début de la période l − Li + 1 et doit se terminer à la période l). Dans les autres travaux, la production Xil démarre à la période l et est disponible pour consommation à la période l + Li . Définissons d’abord les notions de bases dans un contexte multi-niveaux. Suivant une nomenclature, les différents produits d’un système de production sont organisés par niveau, selon leurs liens de dépendance. Ainsi par exemple, il peut y avoir une nomenclature avec un nombre de niveaux B = 5, les produits appartenant au niveau 1 (BL(1)) étant les produits finis (sans successeurs), les produits appartenant au niveau 5 (BL(5)) étant les composants basiques (produits sans prédécesseurs) et, BL(b) ∀ 1 < b < 5 représentant les composants intermédiaires. Les produits peuvent être liés à travers de multiples chemins, nij étant le nombre de chemins entre les produits i et j ∈ AS(i). Nous pouvons donc calculer le nombre total d’unités p n ij du produit i nécessaire pour fabriquer une unité du produit j, en suivant le chemin P n (i, j), avec l’expression suivante : p n ij = Y k∈P n(i,j)−j gk,sn(k) (4.1) Un facteur important à prendre en compte dans un problème multi-niveaux est le délai d’obtention. En fait, pour fabriquer le composant i à la période l, nous devons garantir que tous les prédécesseurs directs (DP(i)) de i sont disponibles dès le début de la période l−Li + 1. Nous commençons par calculer la somme des délais Kn (i, j) pour obtenir les composants du produit j à partir du produit i, en suivant le chemin P n (i, j).

Modèle intégré avec notation classique

Le modèle mathématique que nous considérons pour le problème multi-niveaux intégré est celui proposé par Dauzère-Pérès et Lasserre [48], avec la différence que nous ne considérons pas la rupture de stocks. La différence entre cette formulation et celle que nous avons employée pour la modélisation du problème mono-niveau réside dans les contraintes d’équilibre des stocks. Pour tenir compte des liens de production entre les produits, le paramètre gij permettant de calculer la demande interne de chaque produit est introduit. La formulation du problème intégré est la suivante De nombreuses contraintes du modèle sont les mêmes que pour le problème à un seul niveau (voir Section 3.2 du Chapitre 3). Nous avons uniquement modifié les contraintes d’équilibre des stocks (4.12), pour tenir compte de l’aspect multi-niveaux, et ajouté les contraintes (4.13), qui garantissent qu’il n’est pas possible de déclencher la production d’un produit i à une période l si la somme maximale des délais d’obtention du produit i n’est pas supérieure à l. Comme dans le cas des problèmes à un seul niveau, il est très compliqué de résoudre un tel modèle. De plus, les nouvelles variables de décision (Xjl ∀ j ∈ DS(i), ∀ l) introduisent une difficulté supplémentaire, car elles empêchent d’utiliser la propriété de Wagner et Whitin pour la décomposition du problème en plusieurs sous-problèmes mono-produit. 

Modèle intégré avec échelon stock

 Pour réduire le nombre de variables de décision et rendre le problème décomposable par produit, nous utilisons les variables d’échelon stock et de demande d’échelon, qui permettent de remplacer les variables d’inventaire et les tailles de lot des produits successeurs respectivement. Pour garantir l’approvisionnement en composants, des contraintes de nomenclature liant l’échelon stock de chaque produit avec ceux des ses successeurs sont aussi ajoutées La fonction objectif du modèle est représentée par (4.14), qui correspond à la minimisation du coût total, i.e. la somme des coûts de production, d’échelon stock et de setup. Les contraintes d’équilibre des stocks sont modélisées par (4.15). Les contraintes (4.16) correspondent aux contraintes de nomenclature ou de type BOM (Bill Of Materials). Les contraintes (4.17) forcent les variables de tailles de lots et d’échelon stock à prendre des valeurs strictement positives. Les autres contraintes sont identiques à celles du modèle utilisant les notations classiques de la Section 3.2 du Chapitre 3