Dans cette thèse, notre objectif est de présenter une nouvelle approche de résolution pour des problèmes d'ordonnancement de type job-shop. Les problèmes traités sont de grande taille, ce qui, du fait de la complexité du problème, ne permet d'envisager que l'utilisation d'heuristiques. Cette approche propose une alternative aux algorithmes basés sur des règles de priorité, généralement utilisés. Le principe de l'approche est de construire une succession d'ordonnancements partiels, en agrégeant les jobs les uns après les autres. L'agrégation consiste à insérer toutes les opérations du job à agréger sans changer l'ordre des opérations dans l'ordonnancement partiel précédent. Dans un premier temps, des méthodes issues de l'approche sont proposées pour résoudre le problème classique du job-shop. Ensuite, ces méthodes sont étendues pour traiter des problèmes de job-shop généralisé, ou l'affectation des opérations aux machines n'est pas fixée au départ. Pour finir, des problèmes de job-shop dynamiques et réactifs sont abordés. Dans ceux-ci, l'arrivée aléatoire de jobs et l'arrêt de machines sont pris en compte. Les méthodes agrégatives sont particulièrement bien adaptées à la résolution de ce type de problème.

La conception architecturale de systèmes mécaniques et énergétiques permet d'étudier la faisabilité de concepts préalablement choisis pendant la phase de recherche de concepts. Elle fait partie de la phase de conception préliminaire et son achèvement vise à définir l'architecture globale qui sera étudiée pendant la phase de conception détaillée d'un produit. Les principales caractéristiques d'un produit (dimensions, choix de composants, de formes, de topologies ou de matériaux) sont alors fondamentales à ce stade de la conception. La conception architecturale nécessite aussi la prise en compte des comportements physiques et des interactions du produit, de ses composants et des milieux extérieurs, de critères économiques, environnementaux, etc. suivant les exigences du cahier des charges fonctionnel. Le concepteur définit un modèle mathématique exprimant cette connaissance liée au produit. Ce modèle peut être traité à l'aide d'un solveur de Problèmes de Satisfaction de Contraintes numériques (CSP). Ce type de solveur traite de manière générique des problèmes formulés à l'aide de contraintes, de variables et de domaines. Nous proposons de nouveaux algorithmes et de nouvelles heuristiques qui prennent en compte des besoins spécifiques au concepteur en conception préliminaire, comme : la classification des variables, les précisions relatives aux valeurs de certaines variables, les contraintes par morceaux. Les études de faisabilité de plusieurs systèmes mécaniques et énergétiques ont été réalisées avec succès. Les nouveaux algorithmes ont permis de diminuer significativement les temps de calculs, mais ils ont aussi permis d'améliorer la qualité des solutions calculées au regard des besoins du concepteur.

Nous nous intéressons dans cette thèse aux possibilités d'hybridation entre les méthodes exactes et les méthodes heuristiques afin de pouvoir tirer avantage de chacune des deux approches : optimalité de la résolution exacte, caractère moins déterministe et rapidité de la composante heuristique. Dans l'objectif de résoudre des problèmes NPdifficiles de taille relativement importante tels que les problèmes de transports, nous nous intéressons dans les deux dernières parties de ce mémoire à la conception de méthodes incomplètes basées sur ces hybridations. Dans la première partie, nous allons nous intéresser aux méthodes de résolution par recherche arborescente. Nous introduisons une nouvelle approche pour la gestion des décisions de branchement, que nous appelons Dynamic Learning Search (DLS). Cette méthode définit de manière dynamique des règles de priorité pour la sélection des variables à chaque noeud et l'ordre des valeurs sur lesquelles brancher. Ces règles sont conçues dans une optique de généricité, de manière à pouvoir utiliser la méthode indépendamment du problème traité. Le principe général est de tenir compte par une technique d'apprentissage de l'impact qu'ont eu les décisions de branchement dans les parties déjà explorées de l'arbre. Nous évaluons l'efficacité de la méthode proposée sur deux problèmes classiques : un problème d'optimisation combinatoire et un problème à satisfaction de contraintes. La deuxième partie de ce mémoire traite des recherches à grand voisinage. Nous présentons un nouvel opérateur de voisinage, qui détermine par un algorithme de programmation dynamique la sous-séquence optimale d'un chemin dans un graphe. Nous montrons que cet opérateur est tout particulièrement destiné à des problèmes de tournées pour lesquels tous les noeuds ne nécessitent pas d'être visités. Nous appelons cette classe de problème les Problèmes de Tournées avec Couverture Partielle et présentons quelques problèmes faisant partie de cette classe. Les chapitres 3 et 4 montrent, à travers des tests expérimentaux conséquents, l'efficacité de l'opérateur que nous proposons en appliquant cette recherche à voisinage large sur deux problèmes, respectivement le Problème de l'Acheteur Itinérant (TPP) et le Problème de Voyageur de Commerce Généralisé (GTSP). Nous montrons alors que cet opérateur peut être combiné de manière efficace avec des métaheuristiques classiques, telles que des algorithmes génétiques ou des algorithmes d'Optimisation par Colonies de Fourmis. Enfin, la troisième partie présente des méthodes heuristiques basées sur un algorithme de Génération de Colonnes. Ces méthodes sont appliquées sur un problème complexe : le problème de Tournées de Véhicules avec Contraintes de Chargement à Deux Dimensions (2L-VRP). Nous montrons une partie des possibilités qu'il existe afin de modifier une méthode a priori exacte en une méthode heuristique et nous évaluons ces possibilités à l'aide de tests expérimentaux

Le rôle de l'imaginaire ne semble pas - a priori - fondamental pour la dynamique de la motivation dans le contexte scolaire, c'est à dire dans un cadre envisagé en vue d'apprentissages par l'élève, de connaissances conformes à des programmes bien définis. Cependant on peut inverser cette perspective en concevant la motivation dans le cadre d'une réalisation de soi - dans le groupe et en fonction d'apprentissages répondant à des besoins créatifs spontanés. Les travaux effectués par Gilbert Durand sur l'Imaginaire - et en particulier sa conception des "structures anthropologiques de l'Imaginaire" - nous ont servi de fil conducteur théorique à partir duquel nous avons élaboré une méthodologie et réalisé une expérimentation dans différentes classes. Nous avons recueilli des données et analysé l'évolution de certaines situations scolaires individuelles et collectives. Au terme de cette recherche, nous constatons que si les contenus liés à une pédagogie de l'imaginaire restent importants, il apparaît surtout que c'est dans la régulation de l'espace-temps éducatif que se construit ou non la raison simultanée d'apprendre et de vivre ensemble Pour qu'une activité prenne du sens il faut en effet que soit combinées harmonieusement trois directions pédagogiques : la mise à l'épreuve individuelle, la participation au sein d'un groupe et la circulation de toute information dans le système apprenant qu'est la classe. Or cela correspond justement aux trois modes durandiens des structures de l'imaginaire : mode "héroïque", mode "mystique" et mode synthétique ou cyclique, trilogie constitutive des bases anthropologiques de la psyché, préfigurant dans son équilibre une éducation à visée socialisante et démocratique. L'hégémonie d'un modèle pédagogique - trop "héroïque par exemple - pourrait alors être envisagé comme facteur de séparation, d'échec scolaire, de fracture sociale...

L'alignement de séquences biologiques est une technique fondamentale en bioinformatique, et consiste à identifier des séries de caractères similaires (conservés) qui apparaissent dans le même ordre dans les deux séquences, et à inférer un ensemble de modifications (substitutions, insertions et suppressions) impliquées dans la transformation d'une séquence en l'autre. Cette technique permet de déduire, sur la base de la similarité de séquence, si deux ou plusieurs séquences biologiques sont potentiellement homologues, donc si elles partagent un ancêtre commun, permettant ainsi de mieux comprendre l'évolution des séquences. Cette thèse aborde les problèmes de comparaison de séquences dans deux cadres différents: la détection d'homologies et le séquençage à haut débit. L'objectif de ce travail est de développer des méthodes d'alignement qui peuvent apporter des solutions aux deux problèmes suivants: i) la détection d'homologies cachées entre des protéines par comparaison de séquences protéiques, lorsque la source de leur divergence sont les mutations qui changent le cadre de lecture, et ii) le mapping de reads SOLiD (séquences de di-nucléotides chevauchantes codés par des couleurs) sur un génome de référence. Dans les deux cas, la même idée générale est appliquée: comparer implicitement les séquences d'ADN pour la détection de changements qui se produisent à ce niveau, en manipulant, en pratique, d'autres représentations (séquences de protéines, séquences de codes di-nucléotides) qui fournissent des informations supplémentaires et qui aident à améliorer la recherche de similarités. Le but est de concevoir et d'appliquer des méthodes exactes et heuristiques d'alignement, ainsi que des systemes de scores, adaptés à ces scénarios.

Reproduction de : Thèse de doctorat : Informatique : Lille 1 : 2004. / N° d'ordre (Lille 1) : 3514. Résumé en français et en anglais. Titre provenant de la page de titre du document numérisé. Bibliogr. p. [149]-160.

Reproduction de : Thèse de doctorat : Informatique : Lille 1 : 2004. / N° d'ordre (Lille 1) : 3467. Résumé en français et en anglais. Titre provenant de la page de titre du document numérisé. Bibliogr. 9 p.

Thèse (M.A.) -- Université du Québec à Chicoutimi, [2003]. / Ce travail de recherche a été réalisé à l'UQAC dans le cadre du programme de la maîtrise en art, concentration Création, pour l'obtention du grade maître ès arts (M.A.). CaQCU Bibliogr.: f. 54-55. Document électronique également accessible en format PDF. CaQCU

Dans cette thèse, nous étudions l’optimisation des problèmes de planification et d’ordonnancement des flux, dans une stratégie d’intégration des décisions, pour planifier la chaîne logistique au niveau tactique avec prise en compte de contraintes opérationnelles. Le but de ce travail est de répondre au besoin de cohérence entre les décisions de planification et d’ordonnancement, qui sont souvent prises de manière séquentielle ne garantissant pas la faisabilité des plans de production. Nous proposons une approche intégrée pour résoudre des problèmes mono-niveau et multi-niveaux, dans des systèmes multi-produits et multi-ressources dans des ateliers de type job-shop.Les problèmes de planification avec contraintes de capacité et les problèmes d’ordonnancement dans des systèmes complexes sont des problèmes NP-difficiles. Intégrer les contraintes propres aux deux problèmes engendre un nouveau problème qui est d’autant plus complexe. Nous proposons une décomposition du problème intégré en un ensemble de sous-problèmes de planification avec séquence fixée, résolus par relaxation Lagrangienne. L’amélioration de la séquence est guidée par une recherche taboue. L’efficacité de l’approche intégrée, par rapport à un solveur commercial, a été prouvée en termes de qualité des solutions et d’effort de calcul. Pour les problèmes multi-niveaux, nous proposons une nouvelle formulation basée sur la notion d’échelon stock, ainsi que de nouveaux algorithmes et stratégies de lissage de la production, pour construire des plans de production respectant les contraintes de capacité détaillées et de nomenclature / In this thesis, we study the optimization of flow planning and scheduling, within a strategy to integrate decisions for supply chain planning at tactical level, taking into account operational constraints. The goal of this work is to address the need for consistency between decisions arising from production planning and scheduling. These decisions are often taken in a sequential order, leading most of the time to unfeasible production plans. We propose an integrated approach to solve single-level and multi-level problems in multi-item multi-resource systems configured as job-shops.Both capacitated production planning and scheduling problems, in complex manufacturing systems, are NP-hard. Therefore, integrating constraints of both problems generates a new problem which is even more difficult to solve. We propose a decomposition of the integrated problem into a set of several sub-problems with fixed sequence, solved by Lagrangian Relaxation. The sequence improvement is guided by a Tabu Search. The efficiency of the integrated approach comparing to a standard solver is proved in terms of solution quality and computational effort. In case of multi-level problems, we propose a new mathematical model based on the concept of echelon stock, as well as new algorithms and smoothing strategies to build production plans respecting detailed capacity and bill-of-materials constraints.

Dès qu’on manipule des ordres partiels (des hiérarchies), il est naturel de se demander comment les représenter dans un système informatique. Parmi les solutions proposées dans la littérature, on retrouve le codage par vecteur de bits. Dans cette thèse, nous nous intéressons au problème de calcul d’un codage des ordres par vecteur de bits de taille minimale, aussi connu par le problème de calcul de la 2-dimension des ordres, qui est NP-complet. Nous proposons des solutions du problème de nature heuristique, pour le cas général et pour des classes d’ordres particulières.Cette thèse présente également des résultats sur des conjectures autour de la 2-dimension des arbres. Notamment celle de Habib et al. à propos de la 2-approximabilité de la 2-dimension des arbres. Nous proposons quelques pistes de preuve de cette conjecture puis une reformulation, permettant d’apporter un nouveau regard sur le problème en question et d’espérer trouver des codages des ordres par vecteur de bits efficaces et de taille inférieure à leur 2-dimension. Nous apportons une réponse négative à deux autres conjectures. / The main question asked when manipulating partial orders (hierarchies), is how to represent them in computer. Among solutions proposed in literature, there is the bit-vector encoding. In this thesis, we consider the problem of computing a bit-vector encoding of orders with minimal size, which is also known as the problem of computing the2-dimension of orders that is NP-complete. We propose heuristics solutions of the problem for the general case and for some particular order classes. In addition, this thesis presents some results about conjectures on the 2-dimension of trees. Especially, the conjecture of Habib et al. about the 2-approximability of the 2-dimension of trees. We propose some ideas of a proof of this conjecture then give a reformulation of it that brings new perspectives on the problem that are finding efficient bits-vector encodings of orders of size less than their 2-dimension. We disprove two other conjectures.