Les travaux de ce mémoire traitent du problème d’ordonnancement et d’optimisation de la production dans un environnement de plusieurs machines en présence de contraintes sur les ressources matérielles dans une usine d’extrusion plastique. La minimisation de la somme pondérée des retards est le critère économique autour duquel s’articule cette étude car il représente un critère très important pour le respect des délais. Dans ce mémoire, nous proposons une approche exacte via une formulation mathématique capable des donner des solutions optimales et une approche heuristique qui repose sur deux méthodes de construction de solution sérielle et parallèle et un ensemble de méthodes de recherche dans le voisinage (recuit-simulé, recherche avec tabous, GRASP et algorithme génétique) avec cinq variantes de voisinages. Pour être en totale conformité avec la réalité de l’industrie du plastique, nous avons pris en considération certaines caractéristiques très fréquentes telles que les temps de changement d’outils sur les machines lorsqu’un ordre de fabrication succède à un autre sur une machine donnée. La disponibilité des extrudeuses et des matrices d’extrusion représente le goulot d’étranglement dans ce problème d’ordonnancement. Des séries d’expérimentations basées sur des problèmes tests ont été effectuées pour évaluer la qualité de la solution obtenue avec les différents algorithmes proposés. L’analyse des résultats a démontré que les méthodes de construction de solution ne sont pas suffisantes pour assurer de bons résultats et que les méthodes de recherche dans le voisinage donnent des solutions de très bonne qualité. Le choix du voisinage est important pour raffiner la qualité de la solution obtenue. Mots-clés : ordonnancement, optimisation, extrusion, formulation mathématique, heuristique, recuit-simulé, recherche avec tabous, GRASP, algorithme génétique / The thesis deals with the optimization of the production on a number of machines subject to limited availability of the resources in an extrusion facility. Because of its importance to meet deadlines, the objective is to minimize the sum of weighted tardiness. This work presents a linear formulation of the problem and a number of heuristic solution methods. The proposed heuristic solution methods can be divided into two main groups: construction methods and neighborhood search methods. Also solution construction methods are divided in two sub-groups: parallel construction heuristics and serial construction heuristics. Adaptations of the simulated annealing algorithm (SA), the genetic algorithm (GA), the Tabu search (TS) method and the Greedy randomized adaptive search procedure (GRASP) are developed. Five neighborhood structures are used within the four tested neighborhood search algorithms. In our problem, setup times are sequence dependent. Also, extruders and dies are the bottleneck piece of equipment in this industrial setting. Several problem instances were generated for the evaluation of heuristic scheduling algorithms. The experimental study shows that the construction heuristics are not sufficient to ensure good results, however the proposed neighborhood search methods perform very well. Also, the structure of neighborhoods plays an important role to guarantee better results. Keywords: scheduling, optimization, extrusion, mathematical formulation, heuristic, simulated-annealing, tabu-search, GRASP, genetic algorithm

La tomographie optique diffuse (DOT) se caractérise par l’utilisation de la lumière dans un régime de propagation diffusif pour sonder les tissus biologiques. L’utilisation de marqueurs fluorescents permet de cibler des processus biologiques précis (tomographie optique diffuse en fluorescence - FDOT) et d’améliorer le contraste dans les images obtenues. Les applications typiques de la DOT/FDOT sont la mammographie laser, l’imagerie cérébrale de nouveau-nés et les investigations non-invasives sur petits animaux, notamment pour l’imagerie moléculaire. Le présent projet fait partie du programme de recherche TomOptUS dirigé par le professeur Yves Bérubé-Lauzière. Un scanner optique pour petits animaux y est en cours de développement. Ce scanner possède la particularité de fonctionner avec une prise de mesures sans contact dans le domaine temporel. La première partie du projet a pour point de départ l’algorithme développé en FDOT par Vincent Robichaud qui permet la localisation spatiale d’une seule inclusion fluorescente ponctuelle immergée dans un milieu diffusant homogène ayant une géométrie cylindrique. Une nouvelle approche de localisation pour une pluralité d’inclusions discrètes est ici introduite. Cette dernière exploite l’information contenue dans le temps de vol des premiers photons provenant d’une émission de fluorescence. Chaque mesure permet de définir un lieu géométrique où une inclusion peut se trouver : ces lieux prennent la forme d’ovales en 2D ou d’ovoïdes en 3D. À partir de ces lieux, une carte de probabilité de présence des inclusions est construite : les maxima de la carte correspondent à la position des inclusions. Cette approche géométrique est soutenue par des simulations Monte Carlo en fluorescence dans des milieux reproduisant les propriétés optiques des tissus biologiques. Plusieurs expériences sont ensuite effectuées sur une mire optique homogène répliquant les propriétés optiques des tissus dans lequel des inclusions remplies de vert d’indocyanine (ICG) sont placées. L’approche permet la localisation avec une erreur positionnelle de l’ordre du millimètre. Les résultats démontrent que l’approche est précise, rapide et efficace pour localisation des inclusions fluorescentes dans un milieu hautement diffusant mimant les tissus biologiques. Des simulations Monte Carlo sur un modèle réaliste de souris montrent la faisabilité de la technique pour l’imagerie sur petits animaux. Le second volet de la thèse s’intéresse aux mesures intrinsèques par le développement d’une approche de reconstruction d’une carte des vitesses de propagation des ondes lumineuses diffuses dans un milieu diffusant hétérogène. De telles vitesses constituent un nouveau contraste pour de l’imagerie DOT. La méthode utilise une configuration en faisceaux lumineux analogue aux méthodes utilisées en tomographie par rayons X. Ici, toutefois, les temps d’arrivée des premiers photons sont utilisés plutôt que l’amplitude du signal. Des résultats sont présentés en 2D pour différentes configurations d’inclusions démontrant la validité de l’approche. Des simulations Monte Carlo sont utilisées pour simuler la propagation intrinsèque dans des milieux hétérogènes et pour venir appuyer la démarche.

Afin de garantir et d'optimiser la qualité du café torréfié, il est important de contrôler un grand nombre de facteurs au cours du procédé. Aujourd'hui, des capteurs robustes et des algorithmes permettent d'analyser en temps réel des valeurs essentielles telles que la couleur, la surface, la température, la masse... Dans cette étude de torréfaction, une stratégie de contrôle est appliquée pour estimer la qualité du produit en considérant des capteurs-algorithmes. Pour la mise en place de cette stratégie, une outil expérimental, basé sur l'analyse d'images, l'acquisition de températures et de masse du produit en temps réel est développé. Les grains de café sont torréfiés par un courant d'air chaud. Une base de données expérimentales des grandeurs (température, masse, couleur et surface des grains de café) est réalisée permettant une meilleure compréhension des phénomènes pendant la torréfaction. Un modèle dynamique est obtenu pour prédire l'évolution de la température interne et la teneur en eau des grains de café au cours de la torréfaction en tenant compte de la mesure de la température de l'air d'entrée. Les cinétiques de niveau de gris et de surface des grains sont modélisées par des réseaux de neurones en utilisant comme entrée le temps et la température du grain. Des réseaux de neurones réccurents sont appliqués pour déterminer les cinétiques du niveau de gris au temps suivant (t+1), en considérant le niveau de gris des valeurs précédentes. Les modèles permettent de simuler la température, le niveau de gris et la surface des grains en temps réel. Le niveau de gris estimé par le modèle est le facteur clé pour arrêter le procédé, car le degré de torréfaction est atteint lorsque le niveau de gris est égal à la qualité optimale.

L'optimisation multidisciplinaire fait référence à la conception et l'optimisation de problèmes d'ingénierie nécessitant l'intervention simultanée d'au moins deux disciplines, chacune pouvant avoir plus d'un objectif à optimiser. Les méthodes usuelles n'abordent pas le cas où chaque discipline a un problème d'optimisation multiobjectif à résoudre. Des méthodes ont été récemment proposées, transformant le problème d'optimisation multidisciplinaire en un problème d'optimisation multiobjectif. Ces méthodes reposent sur des algorithmes évolutionnaires multiobjectifs. Cependant, l'ensemble des solutions obtenues ne reflète pas les préférences disciplinaires : des solutions peuvent être globalement efficaces alors qu'elles sont localement dominées. En nous basant sur les propriétés des relations d'ordre, nous proposons quatre définitions de compromis qui tiennent compte du regroupement des objectifs en disciplines. Les propriétés théoriques de ces compromis sont étudiées, et notamment leur capacité à converger vers l'ensemble de solutions attendues, lorsqu'ils sont utilisés avec des algorithmes évolutionnaires. Ces compromis sont intégrés dans un algorithme évolutionnaire multiobjectif. Des analyses expérimentales de cet algorithme sur les quatre compromis proposés sont effectuées. Elles confirment les prédictions théoriques et montrent la pertinence des solutions obtenues.

Cette thèse porte sur un des problèmes majeurs issus du domaine de la Conception Assistée par Ordinateur (CAO) à savoir celui de l'intersection. On aborde cette problèmatique avec une approche novatrice passant par une nouvelle forme de représentation des surfaces dites \og procédurales \fg{}. Cette dernière se base sur des approximants plus fins que les triangles habituellement utilisés, il s'agit de carreaux de surfaces paramétrées polynomiales de bas degré. L'approximation ainsi obtenue possède des caractères intéressants en termes de qualité et de représentation. Cependant, la mise en oeuvre d'une telle stratégie nécessite l'élaboration d'outils adaptés. En particulier, pour le problème d'intersection, il faut savoir intersecter efficacement les approximants. Pour cela, une méthode algorithmique permet de se focaliser uniquement sur des configurations d'intersection \og pertinentes \fg{}. Plusieurs méthodes sur l'intersection des surfaces paramétrées polynomiales sont ensuite exposées de manière effective. Enfin, les aspects d'implémentation sont également abordés à travers l'intégration des algorithmes développés dans un modeleur algébrique géométrique.

Dans la présente thèse nous étudions l'extraction d'arbres dans des graphes arêtes-coloriés.Nous nous concentrons sur la recherche d'arbres couvrants proprement arête-coloriés et faiblement arête-coloriés, notée PST et WST. Nous montrons que les versions d'optimisation de ces problèmes sont NP-Complete dans le cas général des graphes arêtes-coloriés, et nous proposons des algorithmes pour trouver ces arbres dans le cas des graphes arêtes-coloriés sans cycles proprement arêtes-coloriés.Nous donnons également quelques limites de nonapproximabilité. Nous proposons des conditions suffisantes pour l'existence de la PST dans des graphes arêtes-coloriés (pas forcément propre), en fonction de différents paramètres de graphes, tels que : nombre total de couleurs, la connectivité et le nombre d'arêtes incidentes dedifférentes couleurs pour un sommet. Nous nous intéressons aux chemins hamiltoniens proprement arêtes-coloriés dans le casdes multigraphes arêtes-coloriés. Ils présentent de l'intérêt pour notre étude, car ce sontégalement des arbres couvrants proprement arêtes-coloriés. Nous établissons des conditions suffisantes pour qu'un multigraphe contienne un chemin hamiltonien proprement arêtes-coloriés, en fonction de plusieurs paramètres tels que le nombre d'arêtes, le degré d'arêtes, etc. Puisque l'une des conditions suffisantes pour l'existence des arbres couvrants proprement arêtes-coloriés est la connectivité, nous prouvons plusieurs bornes supérieures pour le plus petit nombre de couleurs nécessaires pour la k-connectivité-propre. Nous énonçons plusieurs conjectures pour les graphes généraux et bipartis, et on arrive à les prouver pour k = 1.

Une série de Tchebychev est un développement dans la base des polynômes de Tchebychev. Ces séries sont importantes en théorie de l'approximation. Contrairement aux séries de Taylor, l'algorithmique en calcul formel autour d'elles n'est pas très développée. Cette thèse propose de nouveaux algorithmes pour ces séries. Une première partie présente des algorithmes rapides pour convertir une série de Tchebychev tronquée en une série de Taylor tronquée et réciproquement, et pour multiplier ou diviser deux séries de Tchebychev tronquées. Le reste de la thèse porte sur les séries de Tchebychev solutions d'une équation différentielle linéaire à coefficients polynomiaux. Dans cette classe, les coefficients des séries sont solutions d'une récurrence linéaire. Cette thèse montre comment calculer cette récurrence efficacement, puis comment l'utiliser pour obtenir un calcul approché efficace des coefficients malgré des instabilités numériques. Ces algorithmes mènent au calcul efficace d'une approximation sur un segment par un polynôme de degré fixé d'une fonction solution d'une équation différentielle linéaire. Enfin, le calcul des récurrences pour les coefficients de séries est généralisé au cas des séries de Fourier généralisées. L'ensemble est illustré d'exemples à partir de programmes développés durant cette thèse.

.

Les méthodes d'analyse multivariée permettent d'extraire l'information présente dans les données spectroscopiques expérimentales pour la prédiction d'une propriété d'intérêt. La dimensionnalité des données en spectroscopie proche infrarouge est telle qu'une sélection des variables spectroscopiques et d'échantillons est nécessaire afin d'améliorer les performances, la robustesse des modèles ou de tendre vers une instrumentation simplifiée. L'analyse rapide de la composition chimique des échantillons textiles est fondamentale dans certaines applications. Une première étude concerne la détermination de la teneur en coton dans des mélanges de fibres coton/polyester et coton/viscose par spectroscopie proche infrarouge. Afin d'améliorer les capacités prédictives obtenues sur les spectres complets, deux procédures de sélection de variables, l'information mutuelle et les algorithmes génétiques, ont été appliquées. L'erreur standard de prédiction obtenue pour le lot coton/polyester est de 2,53% sur les 8 variables sélectionnées par l'information mutuelle. Une seconde étude présente l'analyse qualitative pour la classification d'échantillons textiles dans trois classes par rapport à une propriété physico-chimique d'intérêt. La méthode des support vector machine présente des résultats performants avec un taux d'échantillons bien classés en prédiction de 88,8%. La réduction arbitraire du nombre de variables spectroscopiques a permis de montrer que les capacités prédictives obtenues sur les spectres complets ne sont pas dégradées. Ces résultats sont confirmés par l'utilisation d'une instrumentation simplifiée.

Cette thèse est dédiée à l'étude d'une large classe d'algorithmes, appelés algorithmes en arbre. En utilisant une représentation probabiliste appropriée, le comportement asymptotique de tels algorithmes est analysé. L'approche unifie les études faites sur ces algorithmes ainsi que simplifie et généralise certains résultats établis dans le domaine.