L’ordonnancement dans l’atelier à cheminement unique hybride et production par lots (« ‘batch »’)

Modélisation mathématique : Modèle avec variables mixtes

Afin de compléter la définition donnée dans la section précédente, nous proposons un modèle mathématique pour résoudre le problème HF SP. Ce modèle est composé de variables binaires pour les décisions de constitution de lots et leur ordonnancement, et de variables entières positives pour les paramètres relatifs aux temps. Sans perte de généralité, nous supposons que les données de chaque instance sont des entiers positifs. Dans un souci de généralisation du problème traité (plannings de permutation et non permutation), les variables de décision permettent l’association produit/lot et l’ordonnancement des lots de manière indifférente pour chaque opération s ∈ S. L’affectation des produits aux lots de traitement est représentée par la variable xi,u : xi,u =    1 Si le produit i fait partie du lot u 0 Sinon (4.6) Les décisions de l’ordonnancement des lots de traitement par opération sont représentées par la variable yu,v,s : yu,v,s =    1 Si le lot u précède le lot v pendant l’opération s 0 Sinon (4.7) Les autres variables utilisées dans le modèle sont : 4.3 Modélisation mathématique : Modèle avec variables mixtes 119 – To ← Retard de la commande o – αu,g ← Variable binaire pour déterminer si le lot u contient des produits de type g – c ′ u,s ← Date de sortie du lot u de l’opération s – M ← Entier suffisamment grand – N + 1 ← Lot supplémentaire pour signaler la fin du planning sur une phase – 0 ← Lot supplémentaire pour signaler le début du planning sur une phase Pour compléter les plannings dans les phases avec plusieurs équipements, les lots de traitement sont affectés à la première machine disponible. Le modèle suivant décrit le problème traité dans ce chapitre.

Méthode de résolution actuelle 

Le problème complet, décrit dans ce chapitre, n’a pas été traité, à notre connaissance, dans aucune référence scientifique. Une étude bibliographique sur les problèmes voisins au HF SP avec traitement par lots, est présenté dans le chapitre 2. Afin de comparer les méthodes présentées dans ce chapitre, avec algorithme complet incluant toutes les contraintes décrites, nous présentons dans cette section la méthode de résolution actuellement utilisée dans le cas industriel du contexte de recherche : le laboratoire physico-chimique (LP C) du centre de recherche du groupe Soufflet. Avec la nomenclature du problème d’ordonnancement traité dans ce chapitre, les échantillons arrivant au laboratoire correspondent aux produits de l’atelier. Ces échantillons arrivent dans des commandes liées au développement d’un nouveau biocatalyseur. Les lots de traitement sont composés d’échantillons suivant une même analyse dans le laboratoire. Les machines multibroches sont des équipements d’analyses avec plusieurs capteurs pour effectuer un total de µ analyses simultanément. Une description plis détaillé du fonctionnement de ce laboratoire est donnée dans le chapitre 5. Le fonctionnement du laboratoire LPC dépend des analyses effectuées sur les différents échantillons envoyés. Lors de sa création, les équipements et l’infrastructure de ce laboratoire ont été conçus selon la conception classique d’un laboratoire de recherche. Les critères utilisés dans la gestion de qualité des temps de mouvements n’ont pas fait partie des critères utilisés dans la prise de décision du positionnement des différents composants du laboratoire.C’est ainsi que la méthode actuelle pour la gestion des échantillons a été fixée. Pour cette méthode, le responsable du laboratoire a défini un paramètre B qui détermine le nombre d’échantillons (produits) faisant partie d’un même lot. Cette valeur est fixée. Dès qu’un lot est complet (un total B produits concernant le même type de produit sont présents), il est autorisé à commencer l’analyse. L’ordonnancement de ces lots de traitement est défini par rapport à la position dans le stock entre opérations : le lot attend dans une file d’attente jusqu’à ce que l’équipement soit libéré. L’ordre suit une loi du type premier arrivé, premier servi pour la première opération («First-In-First-Out» (F IF O)). Pour les opérations restantes, cette loi se conserve, mais nous l’appellerons F CF S («First-Come-First-Served»). Tel qu’il a été décrit en [103], si la méthode F CF S est utilisée pour finir l’ordonnancement dans les opérations, le planning résultat est un ordonnancement à permutation. Un exemple du fonctionnement de cette solution est donné dans la figure 4.2. Dans cette figure, deux commandes arrivent à l’atelier à deux dates différentes R1 et R2. Les Lots sont composés respectant la contrainte d’unicité du type de produit traité. Etant donné que cette méthode fixe une valeur B pour la taille du lot (exemple B = 3), même si des produits sont affectés, le lot ne peut pas être disponible pour son traitement avant de compléter la quantité définie par B. Cela génère des attentes.

Heuristiques à deux niveaux

Afin de résoudre le problème d’ordonnancement décrit dans les sections précédentes, nous avons décomposé le problème en deux niveaux de décision. Dans un premier temps, les décisions relatives à la construction de lots de traitement sont prises afin de réduire les temps de traitement, grâce au traitement simultané des produits contenus dans un même lot. Chaque équipement étant composé de plusieurs broches, les temps de traitement sont identiques pour exécuter l’opération sur un ou plusieurs produits à la fois. Une fois les lots de traitement construits, les dates de disponibilité du lot, et les temps de traitement (liés au type de produit) sont définies. Les équations (4.5) et (4.4) sont utilisées à ces fins. Ces informations conforment les données d’entrée d’un problème d’ordonnancement d’un atelier à cheminement unique de composition hybride (HF SP). Cela correspond au deuxième niveau de décision. Ces deux niveaux de décisions sont représentés dans la figure 4.5. En raison de la complexité du problème et des performances limitées de la méthode de résolution du modèle mathématique linéaire, les méthodes présentées ici sont des métaheuristiques adaptées. L’intégration de ces deux niveaux décisionnels a été effectuée sur une structure de recherche métaheuristique de sélection naturelle. Pour cela, nous avons adapté un algorithme génétique, dont les solutions représentent les décisions relatives à la construction des lots de traitement. L’évaluation de ces solutions est directement liée au deuxième niveau de décision : l’ordonnancement. Nous nous sommes concentrés principalement sur la résolution de ce dernier, car il serait à l’origine de la plus part des retards. L’algorithme 12 montre la structure suivie par les méthodes à deux niveaux.