Efficient algorithms to solve scheduling problems with a variety of optimization criteria

La programmation par contraintes est une technique puissante pour résoudre, entre autres, des problèmes d’ordonnancement de grande envergure. L’ordonnancement vise à allouer dans le temps des tâches à des ressources. Lors de son exécution, une tâche consomme une ressource à un taux constant. Généralement, on cherche à optimiser une fonction objectif telle la durée totale d’un ordonnancement. Résoudre un problème d’ordonnancement signifie trouver quand chaque tâche doit débuter et quelle ressource doit l’exécuter. La plupart des problèmes d’ordonnancement sont NP-Difficiles. Conséquemment, il n’existe aucun algorithme connu capable de les résoudre en temps polynomial. Cependant, il existe des spécialisations aux problèmes d’ordonnancement qui ne sont pas NP-Complet. Ces problèmes peuvent être résolus en temps polynomial en utilisant des algorithmes qui leur sont propres. Notre objectif est d’explorer ces algorithmes d’ordonnancement dans plusieurs contextes variés. Les techniques de filtrage ont beaucoup évolué dans les dernières années en ordonnancement basé sur les contraintes. La proéminence des algorithmes de filtrage repose sur leur habilité à réduire l’arbre de recherche en excluant les valeurs des domaines qui ne participent pas à des solutions au problème. Nous proposons des améliorations et présentons des algorithmes de filtrage plus efficaces pour résoudre des problèmes classiques d’ordonnancement. De plus, nous présentons des adaptations de techniques de filtrage pour le cas où les tâches peuvent être retardées. Nous considérons aussi différentes propriétés de problèmes industriels et résolvons plus efficacement des problèmes où le critère d’optimisation n’est pas nécessairement le moment où la dernière tâche se termine. Par exemple, nous présentons des algorithmes à temps polynomial pour le cas où la quantité de ressources fluctue dans le temps, ou quand le coût d’exécuter une tâche au temps t dépend de t.

Jeux de policiers et voleurs, Modèles et applications

Les jeux de policiers et voleurs sont étudiés depuis une trentaine d’années en informatique et en mathématiques. Comme dans les jeux de poursuite en général, des poursuivants (les policiers) cherchent à capturer des évadés (les voleurs), cependant ici les joueurs agissent tour à tour et sont contraints de se déplacer sur une structure discrète. On suppose toujours que les joueurs connaissent les positions exactes de leurs opposants, autrement dit le jeu se déroule à information parfaite. La première définition d’un jeu de policiers-voleurs remonte à celle de Nowakowski et Winkler [39] et, indépendamment, Quilliot [46]. Cette première définition présente un jeu opposant un seul policier et un seul voleur avec des contraintes sur leurs vitesses de déplacement. Des extensions furent graduellement proposées telles que l’ajout de policiers et l’augmentation des vitesses de mouvement. En 2014, Bonato et MacGillivray [6] proposèrent une généralisation des jeux de policiers-voleurs pour permettre l’étude de ceux-ci dans leur globalité. Cependant, leur modèle ne couvre aucunement les jeux possédant des composantes stochastiques tels que ceux dans lesquels les voleurs peuvent bouger de manière aléatoire. Dans ce mémoire est donc présenté un nouveau modèle incluant des aspects stochastiques. En second lieu, on présente dans ce mémoire une application concrète de l’utilisation de ces jeux sous la forme d’une méthode de résolution d’un problème provenant de la théorie de la recherche. Alors que les jeux de policiers et voleurs utilisent l’hypothèse de l’information parfaite, les problèmes de recherches ne peuvent faire cette supposition. Il appert cependant que le jeu de policiers et voleurs peut être analysé comme une relaxation de contraintes d’un problème de recherche. Ce nouvel angle de vue est exploité pour la conception d’une borne supérieure sur la fonction objectif d’un problème de recherche pouvant être mise à contribution dans une méthode dite de branch and bound.

Commande prédictive non linéaire d’un séchoir à lit fluidisé pour granules pharmaceutiques

Avec la disponibilité de capteurs fiables de teneur en eau exploitant la spectroscopie proche infrarouge (NIR pour near-infrared) et les outils chimiométriques, il est maintenant possible d’appliquer des stratégies de commande en ligne sur plusieurs procédés de séchage dans l’industrie pharmaceutique. Dans cet ouvrage, le séchage de granules pharmaceutiques avec un séchoir à lit fluidisé discontinu (FBD pour fluidized bed dryer) de taille pilote est étudié à l’aide d’un capteur d’humidité spectroscopique. Des modifications électriques sont d’abord effectuées sur le séchoir instrumenté afin d’acheminer les signaux mesurés et manipulés à un périphérique d’acquisition. La conception d’une interface homme-machine permet ensuite de contrôler directement le séchoir à l’aide d’un ordinateur portable. Par la suite, un algorithme de commande prédictive (NMPC pour nonlinear model predictive control), basée sur un modèle phénoménologique consolidé du FBD, est exécuté en boucle sur ce même ordinateur. L’objectif est d’atteindre une consigne précise de teneur en eau en fin de séchage tout en contraignant la température des particules ainsi qu’en diminuant le temps de lot. De plus, la consommation énergétique du FBD est explicitement incluse dans la fonction objectif du NMPC. En comparant à une technique d’opération typique en industrie (principalement en boucle ouverte), il est démontré que le temps de séchage et la consommation énergétique peuvent être efficacement gérés sur le procédé pilote tout en limitant plusieurs problèmes d’opération comme le sous-séchage, le surséchage ou le surchauffage des granules.

Fonction et structure des muscles du plancher pelvien de femmes traitées par chirurgie et radiothérapie à la suite d'un cancer de l'endomètre

Ce mémoire porte sur les propriétés fonctionnelles du plancher pelvien à la suite de traitements pour un cancer de l’endomètre. Chez les femmes, le cancer de l’endomètre est le cancer gynécologique ayant la plus forte prévalence. Les traitements oncologiques de ce cancer ont des conséquences néfastes sur la continence urinaire et il est possible que des altérations aux muscles du plancher pelvien à la suite de ces traitements puissent expliquer en partie cette problématique. Ce mémoire est composé de deux études principales. La première étude porte sur la recension des écrits liés aux impacts de la radiothérapie sur la structure anatomique et la fonction musculaire du plancher pelvien chez des adultes atteints d’un cancer pelvien. La deuxième étude compare les propriétés fonctionnelles du plancher pelvien de femmes avec incontinence urinaire à la suite d’un cancer de l’endomètre traité par chirurgie et une radiothérapie adjuvante (groupe à l’étude), à celles de femmes avec hystérectomie sans incontinence (groupe témoin). Cette étude a permis de mettre en évidence une diminution de l’ouverture maximale à l’entrée vaginale, de la longueur vaginale, de la force maximale volontaire du plancher pelvien, du taux de développement de la force dans un test de force maximale et de la coordination lors d’un test de contractions rapides. Ainsi, les deux études de ce mémoire apportent de nouvelles évidences sur les altérations des propriétés fonctionnelles du plancher pelvien à la suite de traitements pour un cancer génital.

Caractérisation des propriétés mécaniques de la pâte de carbone à 150°C dans le but d’optimiser la mise en forme des anodes utilisées dans les cuves Hall-Héroult

Les anodes de carbone sont des éléments consommables servant d’électrode dans la réaction électrochimique d’une cuve Hall-Héroult. Ces dernières sont produites massivement via une chaine de production dont la mise en forme est une des étapes critiques puisqu’elle définit une partie de leur qualité. Le procédé de mise en forme actuel n’est pas pleinement optimisé. Des gradients de densité importants à l’intérieur des anodes diminuent leur performance dans les cuves d’électrolyse. Encore aujourd’hui, les anodes de carbone sont produites avec comme seuls critères de qualité leur densité globale et leurs propriétés mécaniques finales. La manufacture d’anodes est optimisée de façon empirique directement sur la chaine de production. Cependant, la qualité d’une anode se résume en une conductivité électrique uniforme afin de minimiser les concentrations de courant qui ont plusieurs effets néfastes sur leur performance et sur les coûts de production d’aluminium. Cette thèse est basée sur l’hypothèse que la conductivité électrique de l’anode n’est influencée que par sa densité considérant une composition chimique uniforme. L’objectif est de caractériser les paramètres d’un modèle afin de nourrir une loi constitutive qui permettra de modéliser la mise en forme des blocs anodiques. L’utilisation de la modélisation numérique permet d’analyser le comportement de la pâte lors de sa mise en forme. Ainsi, il devient possible de prédire les gradients de densité à l’intérieur des anodes et d’optimiser les paramètres de mise en forme pour en améliorer leur qualité. Le modèle sélectionné est basé sur les propriétés mécaniques et tribologiques réelles de la pâte. La thèse débute avec une étude comportementale qui a pour objectif d’améliorer la compréhension des comportements constitutifs de la pâte observés lors d’essais de pressage préliminaires. Cette étude est basée sur des essais de pressage de pâte de carbone chaude produite dans un moule rigide et sur des essais de pressage d’agrégats secs à l’intérieur du même moule instrumenté d’un piézoélectrique permettant d’enregistrer les émissions acoustiques. Cette analyse a précédé la caractérisation des propriétés de la pâte afin de mieux interpréter son comportement mécanique étant donné la nature complexe de ce matériau carboné dont les propriétés mécaniques sont évolutives en fonction de la masse volumique. Un premier montage expérimental a été spécifiquement développé afin de caractériser le module de Young et le coefficient de Poisson de la pâte. Ce même montage a également servi dans la caractérisation de la viscosité (comportement temporel) de la pâte. Il n’existe aucun essai adapté pour caractériser ces propriétés pour ce type de matériau chauffé à 150°C. Un moule à paroi déformable instrumenté de jauges de déformation a été utilisé pour réaliser les essais. Un second montage a été développé pour caractériser les coefficients de friction statique et cinétique de la pâte aussi chauffée à 150°C. Le modèle a été exploité afin de caractériser les propriétés mécaniques de la pâte par identification inverse et pour simuler la mise en forme d’anodes de laboratoire. Les propriétés mécaniques de la pâte obtenues par la caractérisation expérimentale ont été comparées à celles obtenues par la méthode d’identification inverse. Les cartographies tirées des simulations ont également été comparées aux cartographies des anodes pressées en laboratoire. La tomodensitométrie a été utilisée pour produire ces dernières cartographies de densité. Les résultats des simulations confirment qu’il y a un potentiel majeur à l’utilisation de la modélisation numérique comme outil d’optimisation du procédé de mise en forme de la pâte de carbone. La modélisation numérique permet d’évaluer l’influence de chacun des paramètres de mise en forme sans interrompre la production et/ou d’implanter des changements coûteux dans la ligne de production. Cet outil permet donc d’explorer des avenues telles la modulation des paramètres fréquentiels, la modification de la distribution initiale de la pâte dans le moule, la possibilité de mouler l’anode inversée (upside down), etc. afin d’optimiser le processus de mise en forme et d’augmenter la qualité des anodes.

Automatisation de la fonction de façonnage de deux têtes d’abatteuses-façonneuses : Effets sur la productivité et le taux de conformité des billes façonnées

Pour rester compétitives, les entreprises forestières cherchent à contrôler leurs coûts d’approvisionnement. Les abatteuses-façonneuses sont pourvues d’ordinateurs embarqués qui permettent le contrôle et l’automatisation de certaines fonctions. Or, ces technologies ne sont pas couramment utilisées et sont dans le meilleur des cas sous-utilisées. Tandis que l’industrie manifeste un intérêt grandissant pour l’utilisation de ces ordinateurs, peu de travaux de recherche ont porté sur l’apport en productivité et en conformité aux spécifications de façonnage découlant de l’usage de ces systèmes. L’objectif de l’étude était de mesurer les impacts des trois degrés d’automatisation (manuel, semi-automatique et automatique) sur la productivité (m3/hmp) et le taux de conformité des longueurs et des diamètre d’écimage des billes façonnées (%). La collecte de données s’est déroulée dans les secteurs de récolte de Produits forestiers résolu au nord du Lac St-Jean entre les mois de janvier et d’août 2015. Un dispositif en blocs complets a été mis en place pour chacun des cinq opérateurs ayant participé à l’étude. Un seuil de 5 % a été employé pour la réalisation de l’analyse des variances, après la réalisation de contrastes. Un seul cas a présenté un écart significatif de productivité attribuable au changement du degré d’automatisation employé, tandis qu’aucune différence significative n’a été détectée pour la conformité des diamètres d’écimage; des tendances ont toutefois été constatées. Les conformités de longueur obtenues par deux opérateurs ont présenté des écarts significatifs. Ceux-ci opérant sur deux équipements distincts, cela laisse entrevoir l’impact que peut aussi avoir l’opérateur sur le taux de conformité des longueurs.

Le narrateur-personnage inadéquat : marginalité et posture(s) narrative(s) dans "Un enfant à ma porte" de Ying Chen et "La Trilogie coréenne" d’Ook Chung

Ying Chen et Ook Chung sont deux auteurs québécois d’origine asiatique qui ont fait l’objet d’études comparées en raison de leur statut d’écrivain migrant et de leur appartenance à une aire culturelle commune. Bien que leurs oeuvres mettent fréquemment en scène des narrateurs-personnages marginaux et en situation d’exil, celles-ci s’inscrivent au coeur d’intérêts actuels en littérature contemporaine qui permettent de les aborder au-delà de la culture d’origine des auteurs. S’intéressant à la marginalité du narrateur autodiégétique dans Un enfant à ma porte (2009) et dans La Trilogie coréenne (2012), notre mémoire a pour objectif d’étudier l’altérité des narrateurs et de montrer de quelle façon ceux-ci se retrouvent en décalage par rapport à leur récit. L’analyse de la figure de l’étranger dans le roman de Chung et de la folle dans celui de Chen, plus particulièrement de leur prise de parole respective, conduit à montrer en quoi l’altérité des narrateurs-personnages n’est pas que culturelle. L’altérité dans ces romans témoignerait plutôt d’une posture ontologique beaucoup plus fondamentale et générale, qui se répercute à la fois sur le rôle du personnage dans le récit et sur sa fonction de narrateur. Menée en deux temps (le personnage Autre puis le narrateur Autre), notre étude permet d’établir un lien entre l’inadéquation énoncée et la compétence narrative.

La famille, l'amitié et les relations amoureuses au coeur du traitement des jeunes qui présentent un trouble lié à l'utilisation d'une substance et qui sont placés en mise sous garde dans un centre jeunesse

Ce projet de mémoire, de nature exploratoire, examine la place que pourraient occuper la famille, les amis et les relations amoureuses dans le traitement pour un trouble lié à l’utilisation d’une substance (TUS) chez des jeunes qui participent ou qui ont participé, au cours des deux dernières années, au programme toxico-justice jeunesse. Ce programme est offert par le Centre de réadaptation en dépendance de Québec (CRDQ) et s’adresse aux jeunes qui présentent un TUS et qui sont placés dans une unité de mise sous garde du Centre jeunesse de Québec (CJQ). Pour rencontrer le principal objectif de la recherche, l’importance qu’octroient les jeunes aux relations familiales, amoureuses et d’amitié 1) dans leur parcours de consommation et 2) dans leur processus de rétablissement a été étudiée. Au total, 11 jeunes ont été rencontrés et interviewés par le biais d’entrevues semi-structurées. L’analyse des données qualitatives suggère que les relations familiales, amicales et amoureuses ont une importance considérable dans la compréhension du parcours de consommation et de rétablissement des jeunes consommateurs placés en mise sous garde du CJQ. Donc, nos résultats soutiennent qu’il serait bénéfique de tenir compte de ces relations dans le traitement de cette clientèle. Toutefois, une attention plus particulière devrait, selon nous, être portée à la famille de ces jeunes en cours de traitement. En effet, nos résultats suggèrent que les relations familiales sont celles qui ont le plus de poids dans le parcours de consommation et de rétablissement des jeunes. En fait, plus les jeunes se sentent soutenus par leur famille durant leur placement en mise sous garde, plus ils sont susceptibles de désirer délaisser leurs amis consommateurs et leurs activités illicites. Nous croyons donc qu’il serait important, pour cette clientèle, de traiter les relations familiales en priorité, tout en considérant les relations d’amitié et amoureuses en cours d’intervention. Trois idéaux types familiaux se dégagent de nos travaux. Des modalités de traitement ont donc été développées en fonction de chacun de ces idéaux types. Ces modalités de traitement seront décrites dans la discussion du présent mémoire.

Est-ce que l’aversion au risque cyclique et la richesse immobilière peuvent aider à expliquer les rendements boursiers?

Dans les modèles d’évaluation d’actifs financiers, la stratégie de placement d’un individu est liée à la distribution des rendements des actifs inclus dans son portefeuille. Le modèle intertemporel d’évaluation des actifs financiers basé sur la consommation (C-CAPM) permet d’intégrer la dimension temporelle dans le cadre d’analyse et de comprendre l’arbitrage entre les décisions de consommation et d’épargne d’un individu. La prédiction fondamentale de ce modèle est l’existence d’un lien entre les rendements des actifs financiers et leur covariance avec le taux marginal de substitution intertemporel (TMSI). Dans un cadre théorique, l’énigme de la prime de risque est mise en évidence lorsqu’une fonction d’utilité de type CRRA est utilisée afin de représenter les préférences du consommateur. La rigidité de cette modélisation impose cependant un coefficient d’aversion au risque fixe réconciliant difficilement le modèle avec les données réelles. Ce mémoire a pour objectif de résoudre cette problématique en modifiant les formulations classiques du TMSI. Dans un contexte canadien, nous modifions la forme CRRA afin de déterminer, entre autres, si les variations du produit intérieur brut ont un effet sur le niveau d’aversion au risque d’un agent. Par la suite, nous insérons la richesse immobilière dans une forme d’utilité non-séparable comme proxy du rendement de la richesse. Nos résultats suggèrent qu’il est pertinent, sur une longue période, de tenir compte de la richesse immobilière dans le programme de consommation de l’agent.