PROBLÈMES COMBINATOIRES EN CONFIGURATION DES LIGNES DE FABRICATION

Systèmes de production

   L’ensemble des moyens et des ressources utilisés pour fabriquer des produits finis à partir de produits bruts forme un système de production. Notons qu’un produit fini ne signifie pas forcément un produit qui est prêt pour l’utilisation par des consommateurs finaux. Il y a des producteurs qui fabriquent des composants pour d’autres producteurs. À leur tour, ceux-ci reçoivent (souvent via les centres logistiques) les composants comme les produits bruts pour fabriquer leur propre produit fini ayant une plus grande valeur ajoutée. Par exemple, dans la construction automobile, les producteurs de boîtes de vitesses transmettent leurs produits finis au producteur final qui assemble les produits prêts à vendre aux consommateurs, c’est-à-dire les voitures. Les boîtes de vitesses ne servent à rien sans voiture. Cependant, pour un producteur de boîtes de vitesses ses produits représentent des produits finis. Les producteurs peuvent être associés à deux types d’interactions économiques : B2B (Business to Business) – entreprise aux entreprises et B2C (Business to Customer) – entreprise aux particuliers. La différenciation se fait selon les clients ciblés. L’ensemble de ces producteurs et leurs interactions constitue une chaîne d’approvisionnement, connue dans la littérature anglo-saxonne sous le terme supply chain. Afin d’obtenir des produits finis il faut effectuer un ensemble d’opérations ordonné sur des produits bruts. Ces opérations sont exécutées par des ressources de production : soit par des opérateurs humains, soit par des machines automatiques. Il est évident que, s’agissant de production industrielle, même si des opérateurs participent au processus de production, de toute façon, ils emploient certains outils ou machines. De même, un processus de production entièrement automatisé doit être supervisé par des spécialistes. Les ressources de production sont habituellement affectées à des postes de travail, plus souvent appelés des stations. Chaque station est caractérisée par des opérations qui lui sont affectées et qu’y sont exécutées de façon répétitive. Les produits bruts sont déplacés entre des stations où ils subissent des opérations. On obtient un produit fini lorsque la dernière opération sur la dernière station est finie. Un cheminement de production signifie une séquence de stations prédefinie pour un produit. On peut distinguer trois types principaux de système de production, à savoir : les systèmes d’ateliers à cheminement multiple (job-shop), les systèmes d’ateliers à cheminement unique (flow-line) et les systèmes hybrides :
• Un système d’ateliers à cheminement multiple implique des cheminements de production différents pour chaque type de produit. La production est donc discontinue et flexible. Ce type de système de production est mis en œuvre pour la fabrication de produits dont les caractéristiques sont hétérogènes et pour lesquels la demande est petite. Compte tenu de l’utilisation de mêmes ressources pour la fabrication d’un ensemble de produits qui diffèrent parfois fortement les uns des autres, il est nécessaire d’ordonnancer les tâches pour utiliser les ressources au maximum et réduire le temps total de production. Vu la faible quantité et la très haute diversité de produits fabriqués, le niveau d’automatisation de ce type de système reste faible. Les ateliers flexibles (FMS – flexible manufacturing systems) qui devaient pallier à ce défaut coûtent très cher. Ils sont relativement complexes et demandent une certaine organisation du flux pour automatiser le transport des produits.
• Un système d’ateliers à cheminement unique signifie une séquence linéaire de stations auxquels des opérations sont affectées. Toutes les unités de produits de tous les types (s’il y a plusieurs types) ont un seul cheminement de production. Ainsi, la production a une haute cadence mais avec un degré de flexibilité plus faible que celui d’un système d’ateliers à cheminement multiple. Le flux de produits dans ce système suit la même direction. C’està-dire, l’entrée et la sortie de système sont toujours les mêmes. Ce système permet d’obtenir une productivité élevée et de satisfaire une forte demande. Le niveau d’automatisation est souvent élevé.
• Un système de production hybride réunit à la fois des caractéristiques d’ateliers à cheminement multiple et unique. Cette symbiose est par exemple possible grâce aux stations parallèles qui permettent d’avoir plusieurs cheminements de production en gardant la même direction du flux de produits.

La conception préliminaire des lignes de fabrication

   Il y a des entreprises dont la spécialité est la conception et la production de lignes de fabrication. Normalement, un fabricant de lignes (équipementier) reçoit de son client l’information à propos des produits que ce dernier souhaite fabriquer : les formes géométriques, les matériaux constitutifs, les types de produits avec leurs spécifications et les volumes annuels de production souhaités. Ensuite l’équipementier doit fournir une ou plusieurs solutions préliminaires concernant l’architecture de la ligne, le nombre de stations, les ressources utilisées et naturellement une estimation du coût de la ligne. Vu la grande concurrence dans ce secteur et les exigences accrues de la part des clients, la solution doit d’un côté être fournie au plus vite et d’un autre côté être de la meilleure qualité possible. Par une bonne qualité on sous-entend la satisfaction de critères imposés par le client, notamment le coût, la productivité de la ligne et sa fiabilité. L’optimisation à cette étape est très importante car la signature ou non d’un contrat de fabrication d’une telle ligne en dépend et les valeurs de contrat se chiffrent parfois en millions d’euros [Delorme et al., 2009]. Donc avant qu’une ligne de fabrication soit produite et assemblée, une procedure scrupuleuse de conception préliminaire s’impose. La conception préliminaire est un processus qui a pour but de définir une configuration de la ligne de fabrication et de conduire à sa mise en œuvre [Dolgui and Proth, 2006]. Le problème de conception préliminaire se divise en plusieurs étapes qui doivent être effectuées dans l’ordre chronologique suivant :
1. Analyse de produit. Cette étape consiste en l’examen méticuleux des produits qui seront fabriqués afin de déterminer l’ensemble des opérations que la ligne doit effectuer. Chaque opération doit être bien précisée et décrite. Les outils de la Conception Assisté par Ordinateur (CAO), plus connue sous le terme anglais Computer Aided Design ou CAD, représente une technologie efficace qui aide à développer un prototype de produit avec ses propriétés : les composants, les dimensions géométriques et la typologie.
2. Planification de processus ou choix de gammes. À ce stade les gammes possibles de fabrication sont choisies définissant les contraintes technologiques. Cela inclut, par exemple, l’ordre partiel entre les opérations, les contraintes d’inclusion et d’exclusion entre les opérations, etc. En plus, une sélection d’architecture de ligne doit être effectuée. Le résultat de cette sélection définit les cheminements de production.
3. Configuration. Cette phase consiste au choix des ressources et à leur affectation à des stations afin de remplir les objectifs donnés par le client, par exemple, assurer la productivité de ligne souhaitée. Les ressources sont affectées aux stations tout en respectant les contraintes technologiques et en tenant compte de l’architecture de ligne qui sont établies à l’étape précédente.
4. Analyse de flux. Cette étape s’intéresse à la simulation utilisée pour l’examen de flux de produits le long de la ligne en tenant compte de la variabilité de produits et des événements aléatoires. L’objectif est de dimensionner un dispositif de transfert et de trouver le placement optimal des ressources qui ont été affectées aux stations lors des étapes précédentes.
5. Ordonnancement. À ce stade l’ordre d’entrée des produits sur la ligne de fabrication est défini. Le but de l’ordonnancement est d’utiliser au mieux les ressources affectées. Si nécessaire, le concepteur revient aux étapes précédentes afin de corriger ou réviser les decisions déjà prises. Dans le cas de la conception d’une ligne reconfigurable, le processus de conception peut recommencer dès le début après une décision de fabriquer un nouveau produit. Cette méthodologie a déjà été mise en œuvre dans un logiciel d’aide à la décision développé pour la conception préliminaire de lignes dédiées [Battaïa et al., 2012]. Cette thèse est consacrée à une étape importante de la conception préliminaire : la configuration de lignes de fabrication. Les décisions prises lors de cette étape influencent fortement les objectifs définis par le client, c’est-à-dire, le coût d’installation et de fonctionnement, le taux de production et la fiabilité de la ligne.

Les problèmes d’équilibrage de lignes de fabrication

   Les industries utilisant des lignes de fabrication peuvent profiter de leur équilibrage optimal. Cela se manifeste par la réduction des coûts, l’accroissement de la productivité et l’augmentation de leur rentabilité. Par conséquent, la compétitivité des industries qui recourent aux méthodes d’optimisation s’accroît. L’équilibrage optimal favorise non seulement les producteurs en augmentant leur compétitivité sur le marché, mais influence aussi positivement la satisfaction de la demande. C’est pourquoi les problèmes d’équilibrage de lignes de fabrication attirent l’attention de nombreux chercheurs qui, dans leurs travaux, utilisent différentes méthodes de recherche opérationnelle afin de trouver une solution optimale ou quasi optimale dans les cas où la taille du problème ou le temps de résolution imparti ne permettraient pas une solution optimale. Plusieurs classifications des problèmes ALB ont été proposées dans la littérature [Baybars, 1986, Rekiek et al., 2002, Boysen et al., 2007, Guschinskaya and Dolgui, 2010]. Nous proposons ici de les classer suivant les six éléments qui permettent de bien définir les problèmes abordés dans cette thèse :
1. La variabilité de ligne. Ici, nous utilisons la classification de lignes de fabrication du chapitre 1, à savoir, nous distinguons des lignes dédiées, flexibles et reconfigurables.
2. Les caractéristiques de ligne. Dans cette catégorie nous incluons l’architecture de ligne, c’est-à-dire, le nombre de cheminements de production et le schéma logique de ligne. Par ailleurs, le cadencement de flux de produits est défini. Cela nous renvoie aux notions de lignes de fabrication cadencées et non-cadencées.
3. Les caractéristiques de temps. Nous décrivons les élements de la ligne de fabrication liés à la dimension du temps : les temps opératoires, les temps de stations, les temps de changements de séries, le temps de cycle, etc.
4. Les caractéristiques de coût. Les élements de la ligne de fabrication sont considérés du point de vue de la dimension de coût. Par exemple, nous distinguons les coûts de ressources, les coûts de changements de séries, les coûts d’installation de stations, etc.
5. Les contraintes technologiques. Les restrictions imposées par des facteurs technologiques sont mathématiquement définies à ce stade.
6. Les critères d’optimisation. Chaque problème d’équilibrage est caractérisé par une ou plusieurs fonctions objectif devant être minimisées ou maximisées.
Ainsi, cette classification nous permet de distinguer des lignes selon leurs fréquences de changements de types de produits fabriqués (notion de variabilité) et selon les temps et les coûts à prendre en compte ainsi que les contraintes technologiques à considérer et les fonctions objectif à optimiser. L’histoire des publications sur l’équilibrage de lignes de fabrication tient son origine dans le travail de Salveson publié en 1955 [Salveson, 1955]. Cette étude est concentré sur l’aspect principal de la configuration de lignes, à savoir, sur l’affectation de ressources et, effectivement, d’opérations à des stations. Plus tard, en 1986, le problème traité par Salveson a été baptisé Simple Assembly Line Balancing Problem (SALBP) par Baybars [Baybars, 1986]. C’est le problème de base qui est devenu le point de départ pour tout un ensemble des problèmes de conception de lignes. En utilisant notre classification, on peut décrire le SALBP de la manière suivante :
1. La variabilité de ligne.
• Un seul type de produit est fabriqué et la ligne est dédiée.
2. Les caractéristiques de ligne.
• Il y a un seul cheminement de production et il n’y a pas de stations parallèles. Les stations k = 1, . . . , m sont alignées de manière sérielle l’une après l’autre.
• La ligne est cadencée. Les produits bruts restent pendant un temps constant sur chaque station qui est égal au temps de cycle c. Ainsi, la ligne fonctionne avec la productivité 1/c fixe.
3. Les caractéristiques de temps.
• Les temps opératoires pi
, i = 1, . . . , n sont déterministes.
• Le temps de cycle fixe est donné.
4. Les caractéristiques de coût.
• La dimension de coût n’est pas considérée. On suppose qu’en minimisant le temps d’inactivité on minimise le coût.
5. Les contraintes technologiques.
• L’exécution de chaque opération doit se passer sur une seule station.
• Chaque station peut être également équipée de sorte qu’elle puisse effectuer n’importe quelle opération et que n’importe quelle opération i = 1, . . . , n puisse être exécutée sur n’importe quelle station.
• Les temps de stations ne doivent pas dépasser le temps de cycle.
• Les contraintes de précédence sont imposées à certaines opérations selon le processus technologique choisi.
• Le mode d’exécution des opérations est séquentiel. Le temps de station est égal à la somme des temps opératoires des opérations affectées à cette station.
6. Les critères d’optimisation.
• L’objectif est de minimiser le nombre de stations.
Plus précisément, le problème initial de Salveson a été désigné SALBP-1. Trois autres formulations basées sur les mêmes hypothèses, mais avec un critère d’optimisation différent ont aussi été définies : SALBP-2, SALBP-E et SALBP-F. Les trois types de contraintes : l’indivisibilité des opérations, la limitation des temps de station par le temps de cycle et les contraintes de précédence, sont inhérentes à toute version du SALBP.
• Le SALBP-F est le problème de faisabilité. Ici, le temps de cycle ainsi que le nombre de stations servent comme des paramètres donnés. La solution de ce problème consiste à répondre à la question : est-il possible de répartir l’ensemble d’opérations N sur m stations en respectant toutes les contraintes du SALBP. Autrement dit, il faut décider si une ligne de fabrication à m stations peut fonctionner avec le temps de cycle c défini.
• Pour le SALBP-1 le temps de cycle est donné comme un paramètre alors que le nombre de stations est variable et doit être minimisé.
• Le SALBP-2 est un problème inverse au SALBP-1. Il consiste à la minimisation du temps de cycle ayant le nombre de stations fixe.
• Le SALBP-E a la fonction objectif non-linéaire qui répresente l’efficacité de la ligne – le produit du nombre de stations et du temps de cycle m · c. En minimisant ce produit, on maximise l’efficacité. Au regard de la théorie de la complexité, le SALBP-1 est un problème NP-difficile. Wee et Magazine [Wee and Magazine, 1982] ont démontré ceci en se basant sur le problème bin packing qui a déjà été prouvé d’être NP-difficile [Garey and Johnson, 1979]. Il s’agit de trouver le rangement le plus efficace pour un ensemble d’objets unidimensionnels de valeurs différentes dans les boîtes de capacités données. Dans ce cas, les objets correspondent à des opérations ayant une seule dimension – le temps opératoire, tandis que les boîtes sont des stations. Si le temps de cycle est la capacité maximale de boîtes, alors le problème consiste à distribuer les opérations entre les stations de sorte qu’aucun temps de station ne dépasse le temps de cycle et que le nombre de stations soit minimisé. En ayant des séquences d’opérations à respecter, c’est-à-dire des contraintes de précédence, le problème bin packing devient SALBP-1. Quant aux autres versions du SALBP, elles ont été également démontré NP-difficiles en utilisant le problème NP-difficile d’ordonnancement sur m machines identiques parallèles pour SALBP-2 ou le problème de partition pour SALBP-F. Le SALBP-E est évidemment NP-difficile lui aussi puisqu’il représente une généralisation des autres problèmes du type SALBP. De nombreuses études bibliographiques ont été faites dont les plus récentes sont [Erel and Sarin, 1998, Rekiek et al., 2002, Becker and Scholl, 2006, Guschinskaya and Dolgui, 2010]. Une description détaillée de règles de dominance permettant de réduire l’effort calculatoire ainsi que de calculs de bornes inférieures et supérieures visant à la réduction de l’espace de recherche et à l’estimation de la qualité des solutions approchées pour les SALBP est donnée dans [Scholl, 1999]. Même si la majorité écrasante des travaux de recherche dans le domaine de l’équilibrage de lignes est consacrée aux SALBP, les problèmes traités ont intégré d’autres aspects plus complexes nous amenant à différentes généralisations. Cela a rapproché des travaux académiques avec les situations pratiques que l’on trouve dans l’industrie. Au fil du temps, en essayant d’approcher les problèmes initiaux à des conditions réelles, les chercheurs ont enlevé certaines hypothèses simplificatrices du SALBP en introduisant de nouvelles hypothèses plus réalistes. Le terme GALBP (pour Generalized Assembly Line Balancing Problem) a été proposé par Baybars [Baybars, 1986] pour distinguer les problèmes ayant au moins une hypothèse plus générale par rapport au SALBP. Des études montrant la diversité d’hypothèses et de méthodes de résolution pour les GALBP ont été présentées par [Ghosh and Gagnon, 1989, Rekiek et al., 2002, Becker and Scholl, 2006].

Table des matières

Introduction générale
1 Conception de lignes de fabrication 
1.1 Systèmes de production
1.2 Lignes de fabrication : définition et classification
1.3 La conception préliminaire des lignes de fabrication
1.4 Conclusion
2 État de l’art sur les problèmes de configuration de lignes de fabrication
2.1 Choix de ressources et équilibrage de lignes de fabrication 
2.2 Les problèmes d’équilibrage de lignes de fabrication 
2.3 Principales caractéristiques des problèmes d’équilibrage de lignes de fabrication
2.3.1 Variabilité de lignes
2.3.2 Caractéristiques de lignes
2.3.3 Caractéristiques de temps
2.3.4 Caractéristiques de coût
2.3.5 Contraintes technologiques
2.3.6 Critères d’optimisation
2.4 Méthodes de résolution pour les problèmes de configuration de lignes de fabrication 
2.5 Conclusion
3 Problème d’équilibrage et de choix d’équipement pour des lignes dédiées 
3.1 Introduction
3.2 Définition du problème 
3.3 Origine du problème
3.4 Réduction du problème P au problème de partition d’ensemble
3.5 Prétraitement des données 
3.6 Heuristiques gloutonnes 
3.7 Algorithme de génération de contraintes
3.8 Exemple du problème P
3.9 Résultats numériques 
3.10 Conclusion 
4 Minimisation des coûts de changements de séries pour des lignes multiproduits : cas d’exécution parallèle des opérations 
4.1 Introduction 
4.2 Définition du problème 
4.3 Origine du problème
4.4 Exemple d’une solution
4.5 Minimisation du nombre de stations 
4.5.1 Cas avec des contraintes de précédence et des tailles unitaires sans contraintes d’exclusion
4.5.2 Cas avec des tailles d’opérations arbitraires sans contraintes d’exclusion et de précédence
4.5.3 Cas avec des contraintes d’exclusion et sans contraintes de précédence
4.5.4 Heuristiques pour le problème Ppar(prec, excl, si| k)
4.5.5 Formulation en un programme linéaire en nombres entiers du problème Ppar(prec, excl, si| k)
4.6 Minimisation du coût total de changements de séries 
4.6.1 Heuristique pour le problème Ppar(prec, excl, si| k, cost)
4.6.2 Formulation en un programme linéaire en nombres entiers du problème Ppar(prec, excl, si| k, cost)
4.7 Résultats numériques
4.8 Conclusion
5 Minimisation des coûts de changements de séries pour des lignes multiproduits : cas d’exécution séquentielle des opérations 
5.1 Introduction 
5.2 Définition du problème 
5.3 Origine du problème
5.4 Exemple d’une solution 
5.5 Minimisation du nombre de stations
5.5.1 Temps opératoires et tailles d’opérations unitaires
5.5.2 Heuristique pour le cas général du Pseq(prec | k)
5.5.3 Formulation en un programme linéaire en nombres entiers du problème général Pseq(prec | k)
5.6 Minimisation du coût total de changements de séries 
5.7 Résultats numériques 
5.8 Conclusion
Conclusion générale
Bibliographie

Télécharger le rapport complet