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.