Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Les travaux présentés dans cette thèse portent sur la conception d'une méthodologie d'ordonnancement/optimisation pour les systèmes de production à grande variété de produits et faible densité de flux appelés systèmes HVLV (High-Variety, LowVolume). Les caractéristiques de ces systèmes nous permettent d'appréhender la représentation des flux y circulant par un modèle discret. Le comportement discontinu des systèmes HVLV peut être caractérisé par la connaissance des dates de début et de fin des activités de production. L'algèbre (max, +) est utilisée pour représenter ce type de systèmes où les relations entre les dates de début des activités nécessitent l'utilisation des opérateurs maximum et addition. Afin d'utiliser l'algèbre (max, +) pour l'ordonnancement des systèmes HVLV, il est indispensable de résoudre un problème de conflit et d'optimisation sous contraintes dans cette algèbre. D'abord, nous avons développé dans ces travaux de recherche un modèle d'ordonnancement (max, +) pour les systèmes HVLV dans lequel des variables de décision ont été introduites afin de résoudre le problème de conflit entre les opérations exécutées sur les machines. Ensuite, nous avons amélioré le modèle proposé pour tenir compte de la maintenance préventive. Deux types de maintenance ont été considérés : Maintenance Périodique Répétitive (MPR) et Maintenance Flexible Périodique (MFP). Dans les deux cas, un problème d'ordonnancement non-linéaire sous contraintes a été résolu afin de minimiser certains critères de performance. Enfin, la méthodologie proposée a été validée par simulation, sur des systèmes HVLV complexes de type job-shop.

La problématique générale de notre travail s'inscrit dans le domaine scientifique de la recherche d'information (RI). Les modèles de RI classiques sont généralement basés sur une définition de la notion de pertinence qui est liée essentiellement à l'adéquation thématique entre le sujet de la requête et le sujet du document. Le concept de pertinence a été revisité selon différents niveaux intégrant ainsi différents facteurs liés à l'utilisateur et à son environnement dans une situation de RI. Dans ce travail, nous abordons spécifiquement le problème lié à la modélisation de la pertinence multidimensionnelle à travers la définition de nouveaux modèles d'agrégation des critères et leur évaluation dans des tâches de recherche de RI. Pour répondre à cette problématique, les travaux de l'état de l'art se basent principalement sur des combinaisons linéaires simples. Cependant, ces méthodes se reposent sur l'hypothèse non réaliste d'additivité ou d'indépendance des dimensions, ce qui rend le modèle non approprié dans plusieurs situations de recherche réelles dans lesquelles les critères étant corrélés ou présentant des interactions entre eux. D'autres techniques issues du domaine de l'apprentissage automatique ont été aussi proposées, permettant ainsi d'apprendre un modèle par l'exemple et de le généraliser dans l'ordonnancement et l'agrégation des critères. Toutefois, ces méthodes ont tendance à offrir un aperçu limité sur la façon de considérer l'importance et l'interaction entre les critères. En plus de la sensibilité des paramètres utilisés dans ces algorithmes, est très difficile de comprendre pourquoi un critère est préféré par rapport à un autre. Pour répondre à cette première direction de recherche, nous avons proposé un modèle de combinaison de pertinence multicritères basé sur un opérateur d'agrégation qui permet de surmonter le problème d'additivité des fonctions de combinaison classiques. Notre modèle se base sur une mesure qui permet de donner une idée plus claire sur les corrélations et interactions entre les critères. Nous avons ainsi adapté ce modèle pour deux scénarios de combinaison de pertinence multicritères : (i) un cadre de recherche d'information multicritères dans un contexte de recherche de tweets et (ii) deux cadres de recherche d'information personnalisée. Le deuxième axe de recherche s'intéresse à l'intégration du facteur temporel dans le processus d'agrégation afin de tenir compte des changements occurrents sur les collection de documents au cours du temps. Pour ce faire, nous avons proposé donc un modèle d'agrégation sensible au temps pour combinant le facteur temporel avec le facteur de pertinence thématique. Dans cet objectif, nous avons effectué une analyse temporelle pour éliciter l'aspect temporel des requêtes, et nous avons proposé une évaluation de ce modèle dans une tâche de recherche sensible au temps. / The main research topic of this document revolve around the information retrieval (IR) field. Traditional IR models rank documents by computing single scores separately with respect to one single objective criterion. Recently, an increasing number of IR studies has triggered a resurgence of interest in redefining the algorithmic estimation of relevance, which implies a shift from topical to multidimensional relevance assessment. In our work, we specifically address the multidimensional relevance assessment and evaluation problems. To tackle this challenge, state-of-the-art approaches are often based on linear combination mechanisms. However, these methods rely on the unrealistic additivity hypothesis and independence of the relevance dimensions, which makes it unsuitable in many real situations where criteria are correlated. Other techniques from the machine learning area have also been proposed. The latter learn a model from example inputs and generalize it to combine the different criteria. Nonetheless, these methods tend to offer only limited insight on how to consider the importance and the interaction between the criteria. In addition to the parameters sensitivity used within these algorithms, it is quite difficult to understand why a criteria is more preferred over another one. To address this problem, we proposed a model based on a multi-criteria aggregation operator that is able to overcome the problem of additivity. Our model is based on a fuzzy measure that offer semantic interpretations of the correlations and interactions between the criteria. We have adapted this model to the multidimensional relevance estimation in two scenarii: (i) a tweet search task and (ii) two personalized IR settings. The second line of research focuses on the integration of the temporal factor in the aggregation process, in order to consider the changes of document collections over time. To do so, we have proposed a time-aware IR model for combining the temporal relavance criterion with the topical relevance one. Then, we performed a time series analysis to identify the temporal query nature, and we proposed an evaluation framework within a time-aware IR setting.

Le domaine de l'embarqué connaît depuis quelques années un essor important avec le développement d'applications de plus en plus exigeantes en calcul auxquels les architectures traditionnelles à base de processeurs (mono/multi cœur) ne peuvent pas toujours répondre en termes de performances. Si les architectures multiprocesseurs ou multi cœurs sont aujourd'hui généralisées, il est souvent nécessaire de leur adjoindre des circuits de traitement dédiés, reposant notamment sur des circuits reconfigurables, permettant de répondre à des besoins spécifiques et à des contraintes fortes particulièrement lorsqu'un traitement temps-réel est requis. Ce travail présente l'étude des problèmes d'ordonnancement dans les architectures hétérogènes reconfigurables basées sur des processeurs généraux (CPUs) et des circuits programmables (FPGAs). L'objectif principal est d'exécuter une application présentée sous la forme d'un graphe de précédence sur une architecture hétérogène CPU/FPGA, afin de minimiser le critère de temps d'exécution total ou makespan (Cmax). Dans cette thèse, nous avons considéré deux cas d'étude : un cas d'ordonnancement qui tient compte des délais d'intercommunication entre les unités de calcul CPU et FPGA, pouvant exécuter une seule tâche à la fois, et un autre cas prenant en compte le parallélisme dans le FPGA, qui peut exécuter plusieurs tâches en parallèle tout en respectant la contrainte surfacique. Dans un premier temps, pour le premier cas d'étude, nous proposons deux nouvelles approches d'optimisation, GAA (Genetic Algorithm Approach) et MGAA (Modified Genetic Algorithm Approach), basées sur des algorithmes génétiques. Nous proposons également de tester un algorithme par séparation et évaluation (méthode Branch & Bound). Les approches GAA et MGAA proposées offrent un très bon compromis entre la qualité des solutions obtenues (critère d'optimisation de makespan) et le temps de calcul nécessaire à leur obtention pour résoudre des problèmes à grande échelle, en comparant à la méthode par séparation et évaluation (Branch & Bound) proposée et l'autre méthode exacte proposée dans la littérature. Dans un second temps, pour le second cas d'étude, nous avons proposé et implémenté une méthode basée sur les algorithmes génétiques pour résoudre le problème du partitionnement temporel dans un circuit FPGA en utilisant la reconfiguration dynamique. Cette méthode fournit de bonnes solutions avec des temps de calcul raisonnables. Nous avons ensuite amélioré notre précédente approche MGAA afin d'obtenir une nouvelle approche intitulée MGA (Multithreaded Genetic Algorithm), permettent d'apporter des solutions au problème de partitionnement. De plus, nous avons également proposé un algorithme basé sur le recuit simulé, appelé MSA (Multithreaded Simulated Annealing). Ces deux approches proposées, basées sur les méthodes métaheuristiques, permettent de fournir des solutions approchées dans un intervalle de temps très raisonnable aux problèmes d'ordonnancement et de partitionnement sur système de calcul hétérogène / The domain of the embedded systems becomes more and more attractive in recent years with the development of increasing computationally demanding applications to which the traditional processor-based architectures (either single or multi-core) cannot always respond in terms of performance. While multiprocessor or multicore architectures have now become generalized, it is often necessary to add to them dedicated processing circuits, based in particular on reconfigurable circuits, to meet specific needs and strong constraints, especially when real-time processing is required. This work presents the study of scheduling problems into the reconfigurable heterogeneous architectures based on general processors (CPUs) and programmable circuits (FPGAs). The main objective is to run an application presented in the form of a Data Flow Graph (DFG) on a heterogeneous CPU/FPGA architecture in order to minimize the total running time or makespan criterion (Cmax). In this thesis, we have considered two case studies: a scheduling case taking into account the intercommunication delays and where the FPGA device can perform a single task at a time, and another case taking into account parallelism in the FPGA, which can perform several tasks in parallel while respecting the constraint surface. First, in the first case, we propose two new optimization approaches GAA (Genetic Algorithm Approach) and MGAA (Modified Genetic Algorithm Approach) based on genetic algorithms. We also propose to compare these algorithms to a Branch & Bound method. The proposed approaches (GAA and MGAA) offer a very good compromise between the quality of the solutions obtained (optimization makespan criterion) and the computational time required to perform large-scale problems, unlike to the proposed Branch & Bound and the other exact methods found in the literature. Second, we first implemented an updated method based on genetic algorithms to solve the temporal partitioning problem in an FPGA circuit using dynamic reconfiguration. This method provides good solutions in a reasonable running time. Then, we improved our previous MGAA approach to obtain a new approach called MGA (Multithreaded Genetic Algorithm), which allows us to provide solutions to the partitioning problem. In addition, we have also proposed an algorithm based on simulated annealing, called MSA (Multithreaded Simulated Annealing). These two proposed approaches which are based on metaheuristic methods provide approximate solutions within a reasonable time period to the scheduling and partitioning problems on a heterogeneous computing system

Aujourd'hui, les applications automobiles sont devenues de plus en plus complexes avec des ressources limitées et plus de contraintes de temps et de safety. La vérification temporelle est effectuée très tard aujourd'hui au cours du processus de développement automobile (après l'implémentation et au cours de la phase d'intégration). Pour apporter des solutions aux problèmes du développement logiciel automobile, plusieurs approches de développement dirigé par les modèles ont été définit. Ces approches donnent des langages, des concepts et des méthodologies pour la description de l'architecture des systèmes automobiles. Cependant, ces approches ne donnent aucun guide méthodologique pour intégrer l'analyse temporelle (notamment l'analyse d'ordonnancement) tout au long du processus de développement. Ce travail de thèse propose de développer une méthodologie décrivant un processus d'analyse temporelle dirigé par les modèles. Cette méthodologie décrit les différentes phases du processus de développement dirigé par les modèles et comment l'analyse temporelle est effectuée durant chaque phase.

Cette thèse porte sur la modélisation et l'apprentissage automatique des préférences, dans le contexte industriel de l'impression en grand format. En particulier, nous nous intéressons à l'automatisation de la configuration d'impression. De par la palette des comportements possibles, cette fonctionnalité n'est triviale, ni à concevoir, ni à utiliser. Nous proposons une nouvelle approche pour en améliorer les deux aspect complémentaires : évolutivité et utilisabilité. Notre réalisation principale est un système de recommandation adaptatif, basé sur trois contributions originales : une modélisation de la configuration d'impression grand format à partir d'un modèle de préférence, sous la forme de problèmes d'optimisation sous contraintes, un modèle des préférences de l'imprimeur, sous la forme de fonctions d'utilité additive linéaires par morceaux, basée sur une famille d'attributs adaptée, un algorithme d'apprentissage automatique d'ordonnancements à partir de données comparatives. Basé sur l'algorithme rankSVM (noyau linéaire), notre méthode d'apprentissage permet d'adapter la complexité de l'espace de description des données, tout en conservant la linéarité

Les moteurs de recherche verticaux, qui se concentrent sur des segments spécifiques du Web, deviennent aujourd'hui de plus en plus présents dans le paysage d'Internet. Les moteurs de recherche thématiques, notamment, peuvent obtenir de très bonnes performances en limitant le corpus indexé à un thème connu. Les ambiguïtés de la langue sont alors d'autant plus contrôlables que le domaine est bien ciblé. De plus, la connaissance des objets et de leurs propriétés rend possible le développement de techniques d'analyse spécifiques afin d'extraire des informations pertinentes.Dans le cadre de cette thèse, nous nous intéressons plus précisément à la procédure de collecte de documents thématiques à partir du Web pour alimenter un moteur de recherche thématique. La procédure de collecte peut être réalisée en s'appuyant sur un moteur de recherche généraliste existant (recherche orientée) ou en parcourant les hyperliens entre les pages Web (exploration orientée).Nous étudions tout d'abord la recherche orientée. Dans ce contexte, l'approche classique consiste à combiner des mot-clés du domaine d'intérêt, à les soumettre à un moteur de recherche et à télécharger les meilleurs résultats retournés par ce dernier.Après avoir évalué empiriquement cette approche sur 340 thèmes issus de l'OpenDirectory, nous proposons de l'améliorer en deux points. En amont du moteur de recherche, nous proposons de formuler des requêtes thématiques plus pertinentes pour le thème afin d'augmenter la précision de la collecte. Nous définissons une métrique fondée sur un graphe de cooccurrences et un algorithme de marche aléatoire, dans le but de prédire la pertinence d'une requête thématique. En aval du moteur de recherche, nous proposons de filtrer les documents téléchargés afin d'améliorer la qualité du corpus produit. Pour ce faire, nous modélisons la procédure de collecte sous la forme d'un graphe triparti et appliquons un algorithme de marche aléatoire biaisé afin d'ordonner par pertinence les documents et termes apparaissant dans ces derniers.Dans la seconde partie de cette thèse, nous nous focalisons sur l'exploration orientée du Web. Au coeur de tout robot d'exploration orientée se trouve une stratégie de crawl qui lui permet de maximiser le rapatriement de pages pertinentes pour un thème, tout en minimisant le nombre de pages visitées qui ne sont pas en rapport avec le thème. En pratique, cette stratégie définit l'ordre de visite des pages. Nous proposons d'apprendre automatiquement une fonction d'ordonnancement indépendante du thème à partir de données existantes annotées automatiquement.

Les machines du domaine du calcul haute performance (HPC) gagnent régulièrement en com- plexité. De nos jours, chaque nœud de calcul peut être constitué de plusieurs puces ou de plusieurs cœurs se partageant divers caches mémoire de façon hiérarchique. Que se soit pour comprendre les performances ob- tenues par une application sur ces architectures ou pour développer de nouveaux algorithmes et valider leur performance, une phase d'expérimentation est souvent nécessaire. Dans cette thèse, nous nous intéressons à deux formes d'analyse expérimentale : l'exécution sur machines réelles et la simulation d'algorithmes sur des jeux de données aléatoires. Dans un cas comme dans l'autre, le contrôle des paramètres de l'environnement (matériel ou données en entrée) permet une meilleure analyse des performances de l'application étudiée. Ainsi, nous proposons deux méthodes pour contrôler l'utilisation par une application des ressources ma- térielles d'une machine : l'une pour le temps processeur alloué et l'autre pour la quantité de cache mémoire disponible. Ces deux méthodes nous permettent notamment d'étudier les changements de comportement d'une application en fonction de la quantité de ressources allouées. Basées sur une modification du compor- tement du système d'exploitation, nous avons implémenté ces méthodes pour un système Linux et démontré leur utilité dans l'analyse de plusieurs applications parallèles. Du point de vue de la simulation, nous avons étudié le problème de la génération aléatoire de graphes orientés acycliques (DAG) pour la simulation d'algorithmes d'ordonnancement. Bien qu'un grand nombre d'algorithmes de génération existent dans ce domaine, la plupart des publications repose sur des implémen- tations ad-hoc et peu validées de ces derniers. Pour pallier ce problème, nous proposons un environnement de génération comprenant la majorité des méthodes rencontrées dans la littérature. Pour valider cet envi- ronnement, nous avons réalisé de grande campagnes d'analyses à l'aide de Grid'5000, notamment du point de vue des propriétés statistiques connues de certaines méthodes. Nous montrons aussi que la performance d'un algorithme est fortement influencée par la méthode de génération des entrées choisie, au point de ren- contrer des phénomènes d'inversion : un changement d'algorithme de génération inverse le résultat d'une comparaison entre deux ordonnanceurs.

Dans cette thèse, nous nous intéressons (a) à l'estimation des paramètres de modèles standards de Recherche d'Information (RI), et (b) à l'apprentissage de nouvelles fonctions de RI. Nous explorons d'abord plusieurs méthodes permettant, a priori, d'estimer le paramètre de collection des modèles d'information (chapitre. Jusqu'à présent, ce paramètre était fixé au nombre moyen de documents dans lesquels un mot donné apparaissait. Nous présentons ici plusieurs méthodes d'estimation de ce paramètre et montrons qu'il est possible d'améliorer les performances du système de recherche d'information lorsque ce paramètre est estimé de façon adéquate. Pour cela, nous proposons une approche basée sur l'apprentissage de transfert qui peut prédire les valeurs de paramètre de n'importe quel modèle de RI. Cette approche utilise des jugements de pertinence d'une collection de source existante pour apprendre une fonction de régression permettant de prédire les paramètres optimaux d'un modèle de RI sur une nouvelle collection cible non-étiquetée. Avec ces paramètres prédits, les modèles de RI sont non-seulement plus performants que les même modèles avec leurs paramètres par défaut mais aussi avec ceux optimisés en utilisant les jugements de pertinence de la collection cible. Nous étudions ensuite une technique de transfert permettant d'induire des pseudo-jugements de pertinence des couples de documents par rapport à une requête donnée d'une collection cible. Ces jugements de pertinence sont obtenus grâce à une grille d'information récapitulant les caractéristiques principale d'une collection. Ces pseudo-jugements de pertinence sont ensuite utilisés pour apprendre une fonction d'ordonnancement en utilisant n'importe quel algorithme d'ordonnancement existant. Dans les nombreuses expériences que nous avons menées, cette technique permet de construire une fonction d'ordonnancement plus performante que d'autres proposées dans l'état de l'art. Dans le dernier chapitre de cette thèse, nous proposons une technique exhaustive pour rechercher des fonctions de RI dans l'espace des fonctions existantes en utilisant un grammaire permettant de restreindre l'espace de recherche et en respectant les contraintes de la RI. Certaines fonctions obtenues sont plus performantes que les modèles de RI standards. / The present study focuses on (a) predicting parameters of already existing standard IR models and (b) learning new IR functions. We first explore various statistical methods to estimate the collection parameter of family of information based models (Chapter 2). This parameter determines the behavior of a term in the collection. In earlier studies, it was set to the average number of documents where the term appears, without full justification. We introduce here a fully formalized estimation method which leads to improved versions of these models over the original ones. But the method developed is applicable only to estimate the collection parameter under the information model framework. To alleviate this we propose a transfer learning approach which can predict values for any parameter for any IR model (Chapter 3). This approach uses relevance judgments on a past collection to learn a regression function which can infer parameter values for each single query on a new unlabeled target collection. The proposed method not only outperforms the standard IR models with their default parameter values, but also yields either better or at par performance with popular parameter tuning methods which use relevance judgments on target collection. We then investigate the application of transfer learning based techniques to directly transfer relevance information from a source collection to derive a "pseudo-relevance" judgment on an unlabeled target collection (Chapter 4). From this derived pseudo-relevance a ranking function is learned using any standard learning algorithm which can rank documents in the target collection. In various experiments the learned function outperformed standard IR models as well as other state-of-the-art transfer learning based algorithms. Though a ranking function learned through a learning algorithm is effective still it has a predefined form based on the learning algorithm used. We thus introduce an exhaustive discovery approach to search ranking functions from a space of simple functions (Chapter 5). Through experimentation we found that some of the discovered functions are highly competitive with respect to standard IR models.