Problèmes d’équilibrage des lignes de production

Pour répondre concrètement aux problèmes qui se posent dans la production d’une façon générale et dans l’usinage en particulier, il est indispensable d’admettre des hypothèses de travail. Ces hypothèses restreignent la part de réalité du problème traité dans le but de réduire sa complexité. Elles sont nécessaires pour apporter des réponses précises à des problèmes difficiles à aborder. Une bonne illustration de cette approche est le problème de l’équilibrage des lignes d’assemblage (ALB) qui a été largement étudié dans la littérature. Il en dérive plusieurs problèmes : le simple, noté SALBP, pour Simple Assembly Line Balancing Problem, et les généralisés notés GALBP, pour Generalized Assembly Line Balancing Problem. Ces problèmes sont moins complexes que celui que nous traitons, néanmoins nous avons fait le choix de les aborder car ils ont de nombreux points en commun avec les problèmes de configuration de lignes d’usinage que nous étudions dans ce mémoire. Nous les décrivons de façon formelle indiquons leurs hypothèses dans cette section. Nous présentons également quelques méthodes d’optimisation qui ont été employées pour les résoudre.Une ligne d’assemblage consiste en une série de stations, chacune effectuant un ensemble d’opérations1. Les opérations sont caractérisées par leur temps d’exécution et elles sont le plus souvent reliées par des contraintes de précédence. Les opérations d’une même station sont exécutées de façon séquentielle. Il en résulte que le temps de travail d’une station est égal à la somme des temps d’exécution de ses opérations. Le temps de cycle impose une cadence aux stations car celles-ci ne doivent pas avoir un temps de travail qui lui est supérieur. Le temps mort d’une station est défini comme étant la différence entre le temps de cycle et son temps de travail. L’équilibrage d’une ligne d’assemblage revient à trouver une affectation de l’ensemble des opérations telle que les contraintes de précédence entre les opérations soient respectées et que le temps mort total de la ligne soit minimal.

Le tableau 3.1 [SB06] synthétise les différentes variantes du SALBP. Le problème SALBP- F est un problème de décision (le F désignant faisabilité). Dans ce cas, le problème revient à trouver une solution réalisable qui respecte les données, en l’occurrence le temps de cycle et le nombre de stations. Contrairement au SALBP-F, les variantes SALBP1 et SLABP2 sont des problèmes d’optimisation. Le premier problème a comme objectif de minimiser le nombre de stations en respectant un temps de cycle donné et fixe, alors que le second, à l’inverse, doit minimiser le temps de cycle en respectant un nombre de stations donné et fixe. Le SALBP-E est plus général car il a pour objectif de maximiser l’efficacité E = 1 et SALBP-2, le sont également, car ces derniers peuvent être résolus en parcourant les solutions du SALBP-F [Kar72, WM86, SB06]. La forte combinatoire du problème a conduit à la recherche de bornes inférieures afin de réduire l’espace de recherche. Comme le montrent les travaux faits dans ce sens que nous citons ci-dessous, les bornes inférieures sont essen- tiellement obtenues en résolvant des relaxations du problème original en un problème plus facile. Dans ce qui suit, nous rapportons les différentes bornes inférieures proposées pour le SALBP-1, c’est-à-dire pour le nombre de stations (minimiser le temps mort pour le SALBP-1 est équivalent à la minimisation du nombre de stations).

Différentes bornes ont été proposées pour la fonction objectif du SALBP-1. Elles se dis- tinguent par leur complexité, celles qui ont une complexité linéaire permettent d’obtenir une estimation rapide mais souvent imprécise. Comme nous l’avons déjà évoqué précédemment, plus d’efforts sont déployés dans les calculs, meilleure est la qualité de la borne. Ce prin- cipe est confirmé dans le cas du SALBP-1 ainsi les bornes les plus élaborées fournissent une meilleure approximation de l’objectif, contre-partie d’un plus grand temps de calcul. Une deuxième borne est proposée par Johnson [Joh88], elle est obtenue en considérant les opérations avec un certain temps d’exécution. Plus exactement, si on considère la proportion de temps correspondant à l’occupation d’une opération dans une station, i.e. pi = ti/T0, alors il est possible de déduire que les opérations ayant une proportion supérieure à 0,5 ne peuvent pas partager une même station, elles définissent alors une borne inférieure sur le nombre de stations. Celles qui ont une proportion égale à 0,5 se voient attribuer la moitié d’une station.