Mode d’activation mixte des unités d’usinage : TLBP/B-M

À présent, nous nous intéressons à la généralisation de notre approche au problème consi- dérant un mode d’activation mixte dans le sens série-parallèle (voir formulation générique du problème dans [DIB05]). Dans ce type de lignes, une station correspond à plusieurs étages dont le fonctionnement est séquentiel de sorte que l’étage suivant ne peut être enclenché avant que le précédent n’ait terminé. Chaque étage peut contenir lui-même un sous-ensemble d’uni- tés d’usinage qui sont activées en parallèle. Ainsi, lorsqu’il n’existe qu’un seul étage dans une station le problème se ramène au cas de l’activation parallèle, que nous avons étudié dans la seconde partie de ce mémoire. Par ailleurs, en présence d’une seule unité d’usinage par étage, le problème se ramène au cas séquentiel. Le cas mixte (TLBP/B-M) est donc une généralisation du cas parallèle (TLBP/B-P) et du cas séquentiel. Le coût moyen de l’ouverture d’une station est toujours noté C et chaque station peut contenir au maximum q0 étages. Il est important de noter que le coût d’ouverture d’une station ne dépend pas du nombre d’étages qui seront effectivement utilisés. La valeur T0 est le temps de cycle maximum à ne pas dépasser. Le temps de cycle effectif de la ligne est déterminé par la station goulot1. Le temps de travail d’une station est égal au cumul des temps d’exécution des étages qui la composent en raison de leur exécution séquentielle. Par conséquent, la contrainte de temps de cycle T0 doit être directement intégrée dans le modèle. Contrairement au cas parallèle, où il suffisait d’éliminer les unités d’usinage ayant un temps supérieur à T0, pour le cas mixte l’activation séquentielle des étages rend ce pré-traitement nécessaire mais plus suffisant.

Les contraintes de précédence entre les opérations sont définies de la même façon que pour le TLBP/B-P. Nous utilisons toujours Dor pour désigner les couples d’opérations qui sont reliées par une relation d’antériorité. À la différence du cas précédent, un couple d’opé- rations appartenant à Dor peut être affecté à la même station à condition que l’opération prédécesseur soit affectée à un étage antérieur à celui de l’opération successeur. Seulement, comme les unités d’usinage qui équipent le même étage sont activés en pa- rallèle, il faut également considérer l’incompatibilité qui peut exister entre elles. Il faut par conséquent prendre en compte les interdictions d’affectation de certaines unités au même étage. Afin d’éviter toute confusion avec les contraintes d’incompatibilité aux stations, nous considérons les possibilités des blocs d’être mis en parallèle dans un même étage en les dési- gnant par contraintes de parallélisme. Nous utilisons ainsi la collection Dpb dont les éléments sont des sous-ensembles de blocs, c’est-à-dire que si p ∈ Dpb, alors p ⊆ B, tel que les blocs appartenant à p peuvent être placés sur le même étage.

De la même manière que pour le cas parallèle, une analyse préalable se basant sur les contraintes peut être faite afin de déduire les étages d’affectation dans lesquels, chaque bloc b, pourra être placé. Nous pouvons utiliser l’Algorithme 2 (voir section 5.4.2) pour obtenir l’étage au plus tôt et l’étage au plus tard afin de réduire le nombre d’affectations possibles. Le premier terme de l’expression (7.1) fournit le coût engendré par la mise en place des stations supplémentaires à m∗. Du fait que les m∗ premières stations participent systéma- tiquement à la construction de toute solution réalisable et que leur coût est fixe, l’objectif (7.1) peut être alors exprimé uniquement en fonction du coût dû aux stations additionnelles qui seront ouvertes. Ainsi, pour retrouver le coût global de la ligne, il suffit de rajouter à la valeur de l’objectif le coût de l’ouverture des m∗ premières stations. Quant au second terme de l’objectif, il correspond au coût des unités sélectionnées. Les contraintes (7.11) permettent d’inférer les décisions prises concernant l’ouverture des stations dans la fonction objectif. Autrement dit, dés qu’un bloc est affecté à la station courante la variable de décision yk correspondante est positionnée à 1, ce qui permet de répercuter le coût de la nouvelle station créée dans l’objectif. Nous avons implémenté ce modèle et entamé une phase expérimentale qui a permis de relever des premiers résultats [BDDI06]. Près de 200 instances ont été testées pour évaluer les performances de la formulation, toutefois nous avons fait le choix de ne pas rapporter ces résultats car il sont à compléter. Il a été notamment intéressant de constater que les ins- tances du TLBP/B-M requièrent un temps de calcul plus important par rapport à celles de TLBP/B-P. En effet, la présence des étages multiplie le nombre d’affectations pour chacun des blocs par rapport au TLBP/B-P où il n’y qu’une affectation possible par station. De plus, l’introduction des nouvelles contraintes de parallélisme rend le problème plus difficile ralentissant globalement la résolution des instances. C’est pour améliorer ces performances que nous suggérons d’intégrer des coupes pour réduire le domaine des solutions réalisables. En particulier, nous pensons réduire davantage le nombre de solutions symétriques en in- troduisant des coupes pour favoriser l’affectation des blocs aux premiers étages. Ainsi, il ne faut autoriser l’ouverture d’un étage ultérieure que lorsque l’ensemble des étages qui le pré- cèdent ont été utilisés. De plus, des coupes développées pour le problème de set partitioning peuvent être intéressantes à tester. De la même façon que pour le cas du TLBP/B-P, une étude de l’influence des paramètres considérant la densité du graphe de parallélisme et le nombre d’étages par stations est à envisager.