.

Après une rapide présentation des systèmes d'assemblage et des différentes représentations des processus d'assemblage, ce travail de recherche présente plus précisément trois grands types de modélisation : les graphes d'assemblage, les graphes de précédence et les ASTD. Les graphes de précédence étant très utilisés avec les méthodes d'équilibrage ou de conception des lignes d'assemblage, l'objectif de ce travail est de proposer une méthode de génération des graphes de précédence simple et efficace à partir d'un ensemble de graphes d'assemblage préalablement établis. Deux méthodes de génération de graphe de précédence sont proposées dans ce travail : une par transformation de graphes et une directement basée sur la logique booléenne. La méthode par transformation de graphes permet d'obtenir un graphe de précédence si l'ensemble des séquences d'enchaînement peut être représenté par un unique graphe de précédence. Dans le cas contraire, avec les améliorations apportées à la méthode, il est possible d'obtenir soit un ensemble de graphes de précédence soit un hypergraphe de précédence. La deuxième de ces méthodes permet d'obtenir directement un ensembl e de graphes de précédence ou d'hypergraphes de précédence selon le niveau de complexité du problème. Un calcul des complexités des algorithmes respectifs montre qu'ils sont polynomiaux.

Dans cette thèse, nous considérons une famille des problèmes d’ordonnancement avec machine parallèle identique et contraintes de précédences. Ce champ de recherche fait l’objet de nombreuses études. Malgré tout, la complexité de ces problèmes varie selon de nombreux paramètres,notamment le type de graphe de précédence ou le critère retenu. De plus, il existe encore de nombreux problèmes ouverts. Nous étudions certains de ces problèmes dans cette thèse. Nous montrons notamment que le problème ouvert avec tâches de durée unitaires et graphe de précédence de type intree est NP-complet. Puis, nous prouvons que le problème avec graphe de précédence de type level order est NP-complet aussi. La preuve est ensuite étendue à des problèmes connexes. Par la suite, on améliore un algorithme exponentiel pour un problème spécifique qui est NP-complet. Enfin, nous proposons un modèle linéaire pour le problème avec contraintes de précédence quelconque, améliorant aussi les résultats de littérature. / The main problem studied in this thesis is that of parallel machine scheduling with precedence constraints. The complexity depends on the shape that the precedence graph takes and the objective function. We prove that one minimum-open problem of scheduling equal-processing-time jobs which subject to in-tree precedence constrains is NP complete while minimizing the total competition time.Then, we prove that the open problem of scheduling level-order precedence constrains is NP-complete too. We adapted the second proof to other scheduling problems as well.On the other hand, we improved an exponential algorithm designed for a specific NP-hard problem. At the end, we propose a linear programming model for the general scheduling problem with arbitrary precedence constraints and processing-time. We adapt the existing models which are originally designed for other scheduling problems to parallel scheduling problem and compare these models with ours.

Cette thèse est une contribution à une démarche globale de conception rationnelle des systèmes d'assemblage. Elle concerne plus précisément le problème de génération des graphes de précédence, en vue de leur utilisation par les méthodes d'équilibrage des systèmes d'assemblage. Le premier chapitre de ce travail est consacré à la description de la problématique des systèmes d'assemblage. Le deuxième chapitre présente un état de l'art des approches de génération des graphes de précédence pour l'assemblage. Les propriétés de ceux-ci sont listées et comparées à celles des autres modèles des processus d'assemblage. L'objectif du troisième chapitre est l'élaboration d'une méthode systématique d'obtention des graphes de précédence à partir d'un ensemble de gammes d'assemblage. Dans ce but, deux algorithmes sont proposés. Ils sont basés sur la vérification d'une propriété structurelle – la propriété ? – qui est nécessaire et suffisante pour assurer l'équivalence d'un ensemble de gammes à un seul graphe de précédence. Un état de l'art des méthodes de conception des systèmes d'assemblage issues de l'équilibrage des lignes d'assemblage est présenté dans le quatrième chapitre. Le problème d'équilibrage consiste à trouver l'affectation des tâches aux postes, telle qu'elle assure la minimisation du temps de cycle total. Une approche systémique est proposée par la formulation de ce problème comme problème d'optimisation discrète, en vue de la résolution par la programmation dynamique. Le dernier chapitre est dédié à l'analyse des systèmes d'assemblage avec auto-équilibrage, dont la conception évite la résolution d'un problème d'équilibrage classique. Il est suffisant qu'un tel système satisfasse une contrainte technologique simple de placement des opérateurs (humains) sur la ligne – du plus lent au plus rapide – pour qu'il atteigne spontanément un comportement optimal du point de vue de l'équilibrage. Une analyse par simulation de tels systèmes est présentée. Ils peuvent être traités comme systèmes dynamiques hybrides à commutations et sauts autonomes. La condition suffisante de l'autoéquilibrage – le "bon ordre" – est démontrée en utilisant les critères de stabilité des systèmes dynamiques discrets.

L'objet de cette thèse est l'étude de la parallélisation d'algorithmes du calcul scientifique et<br />leur implémentation sur des ordinateurs parallèles à mémoire partagée et sur des réseaux systoliques.<br /> Un accent particulier est mis sur l'obtention de résultats de complexité. La thèse est organisée autour<br /> d'articles et textes de conférences qui sont analysés et discutés dans une première partie de façon à <br />permettre de replacer les problèmes traités dans leur contexte.<br />Dans le premier chapitre, nous présentons les principaux résultats théoriques concernant <br />l'étude de complexité des algorithmes parallèles, ainsi qu'une description critique de l'architecture <br />de référence, qui est une machine de type MIMD à mémoire partagée. Le chapitre suivant est dédie" à <br />l'ensemble des résultats de complexité concernant les algorithmes de diagonalisation et <br />l'élimination de Gauss, il a pour but d'illustrer la méthodologie. Il existe en tout dix écritures possibles de la méthode de Gauss, qui conduisent principalement à deux grandes classes de graphes de précédente, conceptuellement différents : les graphes de type "glouton" et ceux du type "2 pas".<br />Ces types de graphes se rencontrent d'une manière plus générale dans d'autres problèmes <br />d'algèbre linéaire et même dans certaines méthodes non numériques de la théorie des graphes. <br />Nous développons les résultats de complexité concernant ces deux types de graphes sur les exemples<br /> les plus courant (versions kji et kij de Gauss en parallèle), puis nous montrons comment adapter<br /> l'étude en prenant en compte t'es temps de communication entre tes processeurs, ce qui rend le modèle<br /> théorique plus réaliste.<br />Le chapitre 6 est consacré aux architectures systoliques. Le problème du chemin algébrique permet <br />d'unifier plusieurs problèmes informatiques. Nous présentons un réseau résolvant ce problème en Sn-2 <br />pas sur un réseau de taille n(n+l ). De plus, quelques modifications permettent de calculer des projections<br /> en filtrage adaptatif en vu d'obtenir une solution en temps réel pour le traitement numérique des signaux.<br />Avant de conclure, nous présentons des résultats complémentaires de parallélisation effective sur d'autres<br /> types d'architectures : l'étude de l'algorithme du gradient conjugué sur des super calculateurs <br />(CRAY-XMP et IBM 3090-VF).

Le contexte général de ce travail est l'étude du comportement d'applications parallèles, représentées par un graphe de précédence. La programmation de telles applications dépend fortement des supports d'exécution. Nous présentons et discutons les principaux modèles d'exécution et leur influence sur les problèmes d'ordonnancement des tâches du programme parallèle. Nous étudions en détail quatre problèmes d'ordonnancement sur des modèles d'exécution où le coût de communication est pris en compte. Nous proposons une solution pour un problème à grain très fin, le problème du sac à dos, sur hypercube dans un modèle d'exécution synchrone où le coût de communication est implicite. Nous étudions l'ordonnancement de chaînes sur un modèle à gros grain de communication, le modèle BSP. Nous démontrons qu'ici la recherche d'un ordonnancement optimal est un problème NP-difficile. Nous proposons des solutions avec un compromis entre le nombre de phases de communication/synchronisation et le temps d'inactivité dans chaque processeur. Les deux derniers problèmes étudiés concernent des techniques qui permettent de réduire l'impact du coût des communications inter processeurs. La première technique considère la duplication des tâches. Nous proposons un algorithme de liste avec garantie de performance 2 pour les problèmes à petit temps de communication sur un nombre limité de processeurs. Le deuxième méthode consiste à optimiser les phases de communication en ordonnançant les transmissions de messages. La recherche de la solution optimale étant NP-difficile, nous proposons plusieurs heuristiques.

Dans des contextes de post-urgence tels que le vit la partie occidentale de la République Démocratique du Congo (RDC), l’un des défis cruciaux auxquels font face les hôpitaux ruraux est de maintenir un niveau de médicaments essentiels dans la pharmacie. Sans ces médicaments pour traiter les maladies graves, l’impact sur la santé de la population est significatif. Les hôpitaux encourent également des pertes financières dues à la péremption lorsque trop de médicaments sont commandés. De plus, les coûts du transport des médicaments ainsi que du superviseur sont très élevés pour les hôpitaux isolés ; les coûts du transport peuvent à eux seuls dépasser ceux des médicaments. En utilisant la province du Bandundu, RDC pour une étude de cas, notre recherche tente de déterminer la faisabilité (en termes et de la complexité du problème et des économies potentielles) d’un problème de routage synchronisé pour la livraison de médicaments et pour les visites de supervision. Nous proposons une formulation du problème de tournées de véhicules avec capacité limitée qui gère plusieurs exigences nouvelles, soit la synchronisation des activités, la préséance et deux fréquences d’activités. Nous mettons en œuvre une heuristique « cluster first, route second » avec une base de données géospatiales qui permet de résoudre le problème. Nous présentons également un outil Internet qui permet de visualiser les solutions sur des cartes. Les résultats préliminaires de notre étude suggèrent qu’une solution synchronisée pourrait offrir la possibilité aux hôpitaux ruraux d’augmenter l’accessibilité des services médicaux aux populations rurales avec une augmentation modique du coût de transport actuel. / In post-emergency contexts such as in Western Democratic Republic of the Congo, also known as DR Congo, one of the crucial challenges that rural hospitals face is maintaining a pharmacy with essential medications and supplies. There is significant negative humanitarian impact when hospitals do not have essential medications for treatable life-threatening diseases; hospitals also incur financial losses when too much medication is ordered and it expires. Moreover, the cost of transporting medications and providing onsite supervision to remote hospitals is an extremely expensive endeavour. In some cases the transportation costs alone can surpass the cost of the medications. Using the province of Bandundu, DR Congo as a case study, we attempt to determine the feasibility (in terms of both problem complexity and potential savings) of a synchronized routing problem for medication delivery and on-site supervision visits. We propose a Capacitated Vehicle Routing Problem formulation that handles several novel requirements including activity-wise synchronization, precedence, and two activity frequencies. We implement a novel cluster-first, route-second heuristic with a geospatially-enabled database to solve the problem. We also present a Web-based tool to visualize the solutions in a map. The preliminary results of the research suggest that a synchronized solution could allow rural hospitals to increase the accessibility of medical services to rural populations with only a modest increase in transportation costs.

La réduction des informations redondantes et/ou non-pertinentes dans la description de données est une étape importante dans plusieurs domaines scientifiques comme les statistiques, la vision par ordinateur, la fouille de données ou l’apprentissage automatique. Dans ce manuscrit, nous abordons la réduction de la taille des signatures des images par une méthode issue de l’Analyse Formelle de Concepts (AFC), qui repose sur la structure du treillis des concepts et la théorie des treillis. Les modèles de sac de mots visuels consistent à décrire une image sous forme d’un ensemble de mots visuels obtenus par clustering. La réduction de la taille des signatures des images consiste donc à sélectionner certains de ces mots visuels. Dans cette thèse, nous proposons deux algorithmes de sélection d’attributs (mots visuels) qui sont utilisables pour l’apprentissage supervisé ou non. Le premier algorithme, RedAttSansPerte, ne retient que les attributs qui correspondent aux irréductibles du treillis. En effet, le théorème fondamental de la théorie des treillis garantit que la structure du treillis des concepts est maintenue en ne conservant que les irréductibles. Notre algorithme utilise un graphe d’attributs, le graphe de précédence, où deux attributs sont en relation lorsque les ensembles d’objets à qui ils appartiennent sont inclus l’un dans l’autre. Nous montrons par des expérimentations que la réduction par l’algorithme RedAttsSansPerte permet de diminuer le nombre d’attributs tout en conservant de bonnes performances de classification. Le deuxième algorithme, RedAttsFloue, est une extension de l’algorithme RedAttsSansPerte. Il repose sur une version approximative du graphe de précédence. Il s’agit de supprimer les attributs selon le même principe que l’algorithme précédent, mais en utilisant ce graphe flou. Un seuil de flexibilité élevé du graphe flou entraîne mécaniquement une perte d’information et de ce fait une baisse de performance de la classification. Nous montrons par des expérimentations que la réduction par l’algorithme RedAttsFloue permet de diminuer davantage l’ensemble des attributs sans diminuer de manière significative les performances de classification. / In several scientific fields such as statistics, computer vision and machine learning, redundant and/or irrelevant information reduction in the data description (dimension reduction) is an important step. This process contains two different categories : feature extraction and feature selection, of which feature selection in unsupervised learning is hitherto an open question. In this manuscript, we discussed about feature selection on image datasets using the Formal Concept Analysis (FCA), with focus on lattice structure and lattice theory. The images in a dataset were described as a set of visual words by the bag of visual words model. Two algorithms were proposed in this thesis to select relevant features and they can be used in both unsupervised learning and supervised learning. The first algorithm was the RedAttSansPerte, which based on lattice structure and lattice theory, to ensure its ability to remove redundant features using the precedence graph. The formal definition of precedence graph was given in this thesis. We also demonstrated their properties and the relationship between this graph and the AC-poset. Results from experiments indicated that the RedAttsSansPerte algorithm reduced the size of feature set while maintaining their performance against the evaluation by classification. Secondly, the RedAttsFloue algorithm, an extension of the RedAttsSansPerte algorithm, was also proposed. This extension used the fuzzy precedence graph. The formal definition and the properties of this graph were demonstrated in this manuscript. The RedAttsFloue algorithm removed redundant and irrelevant features while retaining relevant information according to the flexibility threshold of the fuzzy precedence graph. The quality of relevant information was evaluated by the classification. The RedAttsFloue algorithm is suggested to be more robust than the RedAttsSansPerte algorithm in terms of reduction.

La logistique inverse des déchets techniques encombrants de type blanc ou brun se développe de nos jours afin de répondre aux contraintes législatives fortes qui n'autorisent à partir de juillet 2002 que la mise en décharge des déchets dits « ultimes ». Le recyclage noble apparaît comme une solution prometteuse, économiquement viable et écologique, où la collecte, approvisionneuse exclusive du processus de récupération des déchets, doit être appréhendée et planifiée dans l'objectif de maîtrise des coûts. Après avoir identifié les caractéristiques principales des systèmes de collecte existants, nous nous attardons sur le ramassage à domicile des produits usagés de la population. Afin de pouvoir établir une planification opérationnelle, ce mode de collecte est modélisé comme un problème de routage de véhicules : le problème de chargement et de déchargement avec contraintes de fenêtres temporelles, de précédence et de capacité. Ce problème d'Optimisation Combinatoire est ensuite résolu de manière algorithmique, en considérant successivement le cas d'un véhicule, puis de plusieurs véhicules. La résolution du problème se base sur la recherche tabou et la recherche tabou probabiliste, et fournit des résultats très satisfaisants sur le plan qualitatif et en temps d'exécution. Finalement, nous décrivons, grâce au langage de modélisation unifié orienté objet UML, une manière d'intégrer nos résultats algorithmiques dans un module d'aide à la décision pour la planification opérationnelle de la collecte, où l'opérateur humain est chargé de définir le plan de collecte à exécuter.