Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

THÈSE DE DOCTORAT Présentée à L’UNIVERSITÉ PAUL VERLAINE-METZ Pour l’obtention

THÈSE DE DOCTORAT Présentée à L’UNIVERSITÉ PAUL VERLAINE-METZ Pour l’obtention du grade de Docteur de l’Université Paul Verlaine de Metz Spécialité : Automatique par Liya GU Modèles Déterministe, Stochastique et Multicritère pour l’Equilibrage de Lignes d’Assemblage Soutenue le 3 mars 2008 devant le jury composé de : ABDELHAKIM ARTIBA Professeur à Supméca-Paris (rapporteur) LIONEL DUPONT Professeur à l’Ecole des Mines d'Albi Carmaux (rapporteur) JEAN-MICHEL HENRIOUD Professeur à l’Université de Franche-Comté (examinateur) JEAN CHARLES BILLAUT Professeur à l’Ecole Polytechnique de l’Université de Tours (président de soutenance) XIAOLAN XIE Professeur à l’ENSM.SE (directeur de thèse) SOPHIE HENNEQUIN Maître de Conférences à l’ENIM (co-encadrant) ALEXANDRE SAVA Maître de Conférences à l’ENIM (co-encadrant) AVERTISSEMENT Cette thèse est le fruit d'un long travail approuvé par le jury de soutenance et disponible à l'ensemble de la communauté universitaire élargie. Elle est soumise à la propriété intellectuelle de l'auteur au même titre que sa version papier. Ceci implique une obligation de citation, de référencement dans la rédaction de tous vos documents. D'autre part, toutes contrefaçons, plagiats, reproductions illicites entraînent une poursuite pénale. Enfin, l'autorisaton de diffusion a été accordée jusqu' à nouvel ordre. ➢ Contact SCD Metz : daniel.michel@scd.univ-metz.fr Ecrire au doctorant: Code de la Proriété Intellectuelle. articles L 122. 4 Code de la Proriété Intellectuelle. articles L 335.2- L 335.10 http://www.cfcopies.com/V2/leg/leg_droi.php http://www.culture.gouv.fr/culture/infos-pratiques/droits/protection.htm REMERCIEMENTS Les travaux présentés dans ce mémoire ont été effectués à l’ENI de Metz dans l’équipe des systèmes de production (SDP) du laboratoire de Génie Industriel et Production Mécanique (LGIPM). J’exprime mon profond remerciement à mes rapporteurs, Monsieur Abdelhakim ARTIBA et Monsieur Lionel DUPONT qui ont porté un regard critique et pertinent sur mon manuscrit. Je remercie très vivement mes examinateurs, Monsieur Jean-Michel HENRIOUD et Monsieur Jean Charles BILLAUT pour l’honneur qu’ils m’ont fait d’être membres du jury et d’apprécier mon travail. Je voudrais également témoigner de ma reconnaissance à Monsieur Xiaolan XIE, mon directeur de thèse, Responsable du département Génie Industriel Hospitalier à l’école Nationale Supérieure des Mines de Saint-Etienne, pour m’avoir accueilli dans son équipe et pour toute sa confiance durant cette thèse. Je tiens à lui adresser mes vifs remerciements pour toute sa disponibilité et la façon dont il a partagé ses connaissances qui ont permis de faire progresser cette recherche. Je remercie également Madame Sophie HENNEQUIN, Maître de Conférences à l’ENI de Metz, et Monsieur Alexandre SAVA, Maître de Conférences à l’ENI de Metz, mes encadrants, pour l’aide très importante qu’ils m’ont apportée tout au long de cette étude, tant sur les idées scientifiques que sur la vérification de mon travail et également sur ma vie quotidienne en France. Je tiens à remercier l’ENI de Metz, son Directeur Monsieur Pierre PADILLA et le Conseil Régional de Lorraine pour le soutien financier de ma recherche. Je suis très reconnaissant à toutes les personnes du LGIPM et de l’équipe SDP, pour leurs conseils techniques et scientifiques et le temps qu’ils m’ont accordé. J’exprime tous mes remerciements à Mademoiselle Kun YUAN, Messieurs Jie LI et Iyad MOURANI pour m’engager dans la recherche en algorithmique et en optimisation combinatoire. I Enfin, comment ne pas associer à mon parcours, mes parents, ma famille, mes amis qui m’ont toujours entouré de leur profonde affection et qui m’ont soutenu pendant toutes mes études en France ; comment ne pas remercier Guang YANG qui partage ma vie en France depuis 5 ans. II Table des matières Remerciements I Table des matières III Liste des tableaux VI Liste des figures VII Liste des symboles VIII Introduction Générale 1 1 CHAPITRE 1..........................................................................4 Equilibrage de lignes d’assemblage.......................................................................................................4 1.1 Introduction.............................................................................................................................5 1.2 Problèmes d’équilibrage de lignes d’assemblage....................................................................7 1.2.1 Classification et modélisation des lignes d’assemblage................................. 8 1.2.2 Contraintes supplémentaires ........................................................................ 11 1.2.3 Critères d’optimisation................................................................................. 12 1.3 Résolution de problèmes SALBP..........................................................................................14 1.3.1 Formulations mathématiques d’un problème SALBP-2.............................. 15 1.3.2 Méthodes exactes ......................................................................................... 19 1.3.3 Méthodes heuristiques pour SALBP de type II............................................ 22 1.3.4 Optimisation du SALBP de type II par des Méta-heuristiques.................... 27 1.4 Conclusion.............................................................................................................................28 CHAPITRE 2........................................................................31 Optimisation du temps de cycle d’une ligne d’assemblage déterministe.............................................31 2.1 Introduction...........................................................................................................................32 2.2 Une heuristique pour le SALBP type II.................................................................................34 2.2.1 Définition d'une solution initiale.................................................................. 34 2.2.2 Procédure de transfert et d’échange ............................................................. 36 2.3 Méta-heuristiques pour l'équilibrage des lignes déterministes..............................................38 2.3.1 EM pour le problème SALBP-2................................................................... 38 2.3.2 ED pour le SALBP de type II....................................................................... 43 2.3.3 SA pour le SALBP de type II ....................................................................... 48 2.4 Résultats numériques.............................................................................................................50 2.4.1 Résultats numériques obtenus par l’heuristique proposée ........................... 50 2.4.2 Résultats numériques obtenus par nos méta-heuristiques............................ 54 2.5 Conclusion.............................................................................................................................55 CHAPITRE 3........................................................................57 Equilibrage de lignes d’assemblage stochastiques...............................................................................57 3.1 Introduction...........................................................................................................................58 3.2 Equilibrage de lignes stochastiques : cas mono-critère.........................................................60 III 3.2.1 ALBP stochastique....................................................................................... 60 3.2.2 EM pour les ALBP stochastiques................................................................. 62 3.3 Equilibrage de lignes sous plusieurs critères.........................................................................63 3.3.1 Problèmes multi-critère............................................................................... 63 3.3.2 Résolution du problème multi-critère par EM ............................................. 68 3.4 Résultats numériques.............................................................................................................70 3.4.1 Résultats numériques pour les problèmes stochastiques mono critère ........ 70 3.4.2 Résultats numériques pour les problèmes multi-critère............................... 72 3.5 Conclusion.............................................................................................................................76 CHAPITRE 4........................................................................78 Calcul de borne inférieure par la méthode de génération de colonnes.................................................78 4.1 Introduction...........................................................................................................................79 4.2 Génération de colonnes .........................................................................................................79 4.2.1 Formulation de la programmation linéaire en nombres entiers (modélisation mathématique du problème) ........................................................................ 80 4.2.2 Principe de la méthode de génération de colonnes ...................................... 80 4.3 Méthode de génération de colonnes appliquée à notre problème..........................................85 4.3.1 Formulation du problème SALBP-2 ............................................................ 85 4.3.2 Méthode proposée ........................................................................................ 86 4.4 Application............................................................................................................................96 4.3.3 Algorithme ................................................................................................... 96 4.3.4 Résultats numériques.................................................................................... 97 4.5 Conclusion.............................................................................................................................99 Conclusion Générale 101 Bibliographie 104 Annexe 1 112 Annexe 2 114 IV Liste des tableaux Chapitre 1 Tableau 1. 1 Version de SALBP .........................................................................15 Chapitre 2 Tableau 2. 1 Poids de position des opérations.....................................................35 Tableau 2. 2 Seuils des stations...........................................................................36 Tableau 2. 3 Solution initiale...............................................................................36 Tableau 2. 4 Résultats obtenus par l’heuristique proposée .................................53 Tableau 2. 5 Comparaison des temps de calcul...................................................54 Tableau 2. 6 Résoudre les problèmes déterministes par méta-heuristiques........54 Chapitre 3 Tableau 3. 1 Comparaison des résultats donnés par EM et SA pour des ALBP stochastiques.................................................................................................71 Tableau 3. 2 Systèmes étudiés.............................................................................73 Tableau 3. 3 Comparaison des résultats obtenus.................................................76 Chapitre 4 Tableau 4. 1 Bornes inférieures du temps de cycle.............................................99 V Liste des figures Chapitre 1 : Fig. 1. 1 Une ligne d’assemblage..........................................................................5 Fig. 1. 2 Graphe de précédences ...........................................................................6 Fig. 1. 3 Une ligne équilibrée................................................................................7 Fig. 1. 4 Classification des problèmes d’équilibrage des lignes d’assemblage [ARM 99] .......................................................................................................8 Fig. 1. 5 Trois modèles de ligne............................................................................9 Fig. 1. 6 La ligne en forme-U..............................................................................11 Chapitre 2 : Fig. 2. 1 Processus de ED....................................................................................45 Chapitre 3 : Fig. 3. 1 Ensemble des solutions Pareto optimales.............................................73 Fig. 3. 2 Solutions Pareto optimales des deux méthodes basées sur EM ...........75 Chapitre 4 : Fig. 4. 1 Système étudié dans l’exemple............................................................93 Fig. 4. 2 P1 ..........................................................................................................97 Fig. 4. 3 P2 ..........................................................................................................97 Fig. 4. 4 P3 ..........................................................................................................98 Fig. 4. 5 P4 ..........................................................................................................98 VI Liste des notations c Temps de cycle c_best Plus petit temps de cycle obtenu c Borne inférieure du temps de cycle initial c Un temps de cycle maximum 1 − =UC c LC Borne inférieure du temps de cycle LLCμ Borne inférieure du temps de cycle pour un nœud μ utilisé dans les procédures par séparation et évaluation UC Borne supérieure du temps de cycle ti Temps d’opération de l’opération i dans les modèles déterministes ou moyenne du temps d’opération de l’opération i dans les modèles stochastiques tmax Temps d’opération le plus grand tsum Somme des temps d’opération STk Temps de stations pour la station k TMk Temps mort de la station k TML Temps mort de la ligne TR Temps de retard LSTk Limite inférieure du temps de station pour la station k m Nombre de stations n Nombre d’opérations N Ensemble d’opérations Li Station au plus tard pour l’opération i VII VIII Ei Station au plus tôt pour l’opération i SIi Intervalle entier entre Ei et Li Sk Ensemble des opérations pouvant être exécutées sur la station k Fi* Ensemble des successeurs de l’opération i Pi* Ensemble des prédécesseurs de l’opération i PWi, Poids de la position de l’opération i pour l’heuristique proposée TSk Seuil de la station k δ Moyenne des temps d’opération pour les modèles déterministes qi Charge de la particule électrique chargée i dans le mécanisme électromagnétique Fi Force totale du point i dans le mécanisme électromagnétique R Vecteur des clés aléatoires Di ième population de solutions dans la méthode d’estimation de distribution Dse Individus étalon dans la méthode d’estimation de distribution Pi(x) Distribution de probabilité décrivant la répartition de l’ensemble des solutions sélectionnées dans l’itération i pour la méthode d’estimation de distribution Wk Ensemble des opérations assignées à la station k σ2 Variance du temps d’opération FL Fiabilité de la ligne IP Probabilité d’incomplétude des opérations Ωk Ensemble des colonnes de la station k composées des opérations i pour la génération de colonnes Ω Ensemble des colonnes pour la génération de colonnes Introduction Générale Les lignes d’assemblage, appelées aussi chaînes de montage, sont largement utilisées pour assembler rapidement un grand nombre de produits uniformes dans différents secteurs industriels comme par exemple l’industrie automobile, l’aéronautique, l’industrie pharmaceutique, les télécommunications, etc. Les produits concernés sont uploads/Geographie/ salp.pdf