Soutenance mémoire
La conception des lignes de fabrication est un problème industriel important dont les enjeux sont la réussite de la mise sur le marché de nouveaux produits et la bonne santé de l’entreprise. Par conséquent, la prise de décisions à cette étape ne peut être faite à la légère et doit être bien argumentée. Dans l’idéal, les méthodes de la recherche opérationnelle doivent être utilisées pour modéliser les problèmes stratégiques qui en relèvent. Comme en pratique les concepteurs ne disposent que d’estimations pour les données de départ, les modèles utilisés doivent tenir compte du fait que certaines données peuvent avoir, au moment de la mise en œuvre du système, des valeurs différentes de celles prévues au point de remettre en cause la solution retenue à l’étape de résolution. Même si la modélisation de l’incertitude est un sujet bien développé en recherche opérationnelle, très peu de travaux ont été consacrés à la conception des lignes de fabrication.
Prise en compte de l’incertitude en recherche opérationnelle
Modélisation de l’incertitude
Lors de la résolution d’un problème d’optimisation, les décideurs sont souvent confrontés à l’incertitude des données concernant un système réel ou son comportement. Intégrer cette information incertaine dans un modèle mathématique du problème ne fait qu’augmenter sa complexité, mais la négliger peut faire perdre toute crédibilité au modèle. L’information imparfaite dans les applications réelles peut être présente, selon Sanlaville, sous les trois formes suivantes [Sanlaville, 2005] :
– incertitude. Une donnée est soumise à une incertitude si sa valeur ne peut être déterminée de façon précise qu’au moment exact où cette donnée intervient. Par exemple, en ordonnancement, la durée d’une tâche ne peut être connue de façon certaine que lorsque celle-ci est réellement exécutée.
– aléa. Une donnée est sujette aux aléas si la valeur qui lui est associée a priori est susceptible d’être modifiée par certains événements. Par exemple, le temps d’exécution d’une tâche peut être allongé par des micro-arrêts de la machine qui la réalise.
– variation. Une donnée est soumise à des variations si sa valeur nominale change durant la phase d’approbation. Par exemple, si une tâche est réalisée par un opérateur, l’effet d’apprentissage peut raccourcir son temps d’exécution. Pour faire face à l’incertitude des données, les approches suivantes peuvent être appliquées selon Mahjoub [Mahjoub, 2004] :
– a priori. Une solution pour le problème d’optimisation initial est préalablement calculée sur la base des données estimées. Une fois cette solution calculée, elle n’est plus remise en cause.
– en-ligne. Le problème ne peut être résolu que lorsque les données sont disponibles complètement ou partiellement.
– partiellement en-ligne. Les deux approches précédentes sont combinées. Ainsi les données disponibles a priori sont utilisées pour calculer une solution préalable, mais cette solution peut évoluer en fonction des perturbations des données. Notons que dans [Davenport and Beck, 2000], les auteurs préfèrent parler d’approches prédictives, réactives, et prédictives réactives, respectivement. Puisque les approches en-ligne se basent sur les données réelles, leur application est impossible pour de nombreux problèmes stratégiques, pour lesquels la prise de décisions ne peut être reportée au moment où toutes les données seront connues. Souvent en pratique, seules les approches a priori peuvent être appliquées dans ce cas. Par conséquent, il est important d’intégrer les perturbations possibles dans la modélisation des données de départ afin d’obtenir des solutions préalables pouvant être efficaces pour plusieurs scénarios possibles du futur. Ainsi dans la littérature, plusieurs approches ont été développées pour modéliser l’incertitude des données ou pour guider le décideur lors de la prise de décisions sous incertitudes :
– Les approches probabilistes considèrent les données incertaines comme variables aléatoires de lois connues.
– Les approches par ensembles flous supposent que chaque donnée incertaine appartient à un sous-ensemble flou A ⊆ X avec le degré d’appartenance qui se mesure par la fonction µA : X → [0, 1], où X est un ensemble universel.
– Les approches robustes associent à une donnée incertaine un ensemble, continu ou discret, de valeurs possibles, sans probabilité attachée.
– L’analyse de sensibilité introduit l’incertitude après la phase de résolution du problème. Ainsi à la différence des approches précédentes, il s’agit d’étudier le comportement des solutions déjà trouvées face aux variations éventuelles des données de départ et non pas de résoudre le problème posé. D’ailleurs, dans le cas général, l’évaluation de l’impact de telles variations sur une solution est possible sans que le problème initial soit résolu.
Notons qu’en pratique l’application des deux premières approches est souvent difficile, puisque les connaissances a priori ne permettent pas toujours de déduire les lois de probabilité ou les degrés d’appartenance associés aux données, surtout si le problème posé est traité pour la première, et peut-être unique, fois. Pour cette raison, l’approche robuste et l’analyse de sensibilité sont de plus en plus utilisées pour intégrer l’incertitude dans les problèmes d’optimisation combinatoire. Dans ce qui suit, nous présentons ces approches de façon plus approfondie.
Approches robustes
Évoquée dès la fin des années 1960 [Gupta and Rosenhead, 1968], l’idée de robustesse suscite un intérêt croissant à la fois de la part des praticiens et des théoriciens en recherche opérationnelle. Reflétant initialement une préoccupation de flexibilité dans un contexte d’incertitude, ce concept paraît aujourd’hui s’adapter à un spectre beaucoup plus large de situations comme l’indique Bernard Roy dans [Billaut et al., 2005, chapitre 2]. Dans la littérature concernant la robustesse, une donnée incertaine est principalement associée à un ensemble, continu ou discret, de valeurs possibles, sans probabilité attachée [Kouvelis and Yu, 1997]. Dans le cas continu, les ensembles sont souvent des intervalles, d’où la notion d’approche par intervalles. Dans le cas discret, quant à lui, on parle du modèle de scénarios. Quel que soit le cas considéré, le produit cartésien de ces ensembles définit les instances possibles d’un problème. Après avoir modélisé les données incertaines sous forme d’instances possibles, le problème est donc de trouver une solution qui soit « bonne » pour toutes ces instances ou robuste. Pour la définition d’une solution robuste, nous utilisons celle donnée dans [Billaut et al., 2005, chapitre 1] :
Définition 1.1. Une solution est robuste si sa performance est peu sensible à l’incertitude des données et aux aléas.
Suivant cette définition, une solution robuste est alors conçue pour limiter ou absorber les effets des données incertaines. En pratique, on considère souvent que la solution robuste est la meilleure solution dans le pire cas. La plupart des travaux concernant la robustesse utilisent le concept de distance entre la solution robuste calculée a priori et la solution optimale de l’instance réalisée effectivement suivant un certain critère (satisfaction de contraintes ou une exigence particulière). Pour la recherche des solutions robustes, la plupart des auteurs utilisent les critères de la robustesse absolue (min-max), du regret maximal (min-max regret) ou bien du regret relatif [Kouvelis and Yu, 1997].
Problème du sac-à-dos. Dans sa version déterministe classique, ce problème consiste à sélectionner, parmi un ensemble fini d’objets, un sous-ensemble d’objets à mettre dans un sac d’une capacité limitée. Chaque objet a un poids et une valeur et on cherche à maximiser la valeur totale des objets choisis. Ce problème, qui est N P-difficile [Garey and Johnson, 1979], peut être résolu en temps pseudo-polynomial à l’aide de la programmation dynamique [Dantzig, 1957]. Supposons que la valeur de chaque objet n’est pas connue de façon certaine. Pour le cas où ces valeurs sont modélisées par un nombre constant de scénarios, Yu [Yu, 1996] a proposé un algorithme pseudo-polynomial et un algorithme de type séparation et évaluation pour la version max-min. Pour le cas où les données sont modélisées par intervalles, Averbakh [Averbakh, 2004] a démontré que la version min-max regret du problème de sac-à-dos est N P-difficile au sens fort.
Problème d’affectation. Étant donné un graphe biparti complet caractérisé par le même nombre n de sommets dans chaque partie et des coûts associés à chaque arête, le problème d’affectation vise à construire une affectation ayant un coût minimum. Une affectation optimale peut être calculée pour le cas déterministe en temps O(n3 ) avec l’algorithme de Balinski [Balinski, 1985]. En utilisant une réduction polynomiale à partir du problème de partition, Kouvelis et Yu [Kouvelis and Yu, 1997] ont démontré que les versions min-max du problème d’affectation sont N P-difficiles, même pour deux scénarios de coûts. Toutefois, l’existence d’algorithmes pseudo polynomiaux pour ces problèmes est une question ouverte. Dans le cas de la modélisation par intervalles, la version min-max regret est N P-difficile au sens fort [Aissi et al., 2005].
|
Table des matières
Introduction générale
1 Prise en compte de l’incertitude en recherche opérationnelle
1.1 Modélisation de l’incertitude
1.2 Approches robustes
1.3 Analyse de sensibilité
1.4 Conclusion
2 Conception de lignes de fabrication
2.1 Lignes de fabrication
2.2 Problématique de l’équilibrage de lignes
2.3 Équilibrage sous incertitudes
2.4 Conclusion
3 Équilibrage de lignes d’assemblage de type SALBP-E : analyse de sensibilité
3.1 Introduction
3.2 Définitions et propriétés de base
3.3 Exemple
3.4 Solutions faisables
3.5 Solutions quasi-faisables
3.6 Solutions optimales
3.7 Recherche du compromis
3.8 Résultats numériques
3.9 Conclusion
4 Équilibrage de lignes d’usinage à boîtiers multibroches : analyse de sensibilité
4.1 Introduction
4.2 Définitions et propriétés de base
4.3 Solutions faisables
4.4 Solutions quasi-faisables
4.5 Solutions optimales
4.6 Recherche du compromis
4.7 Résultats numériques
4.8 Conclusion
Conclusion générale
Télécharger le rapport complet
