Programme de doctorat
Département d’informatique et de génie logiciel
Faculté des sciences et de génie
SOUTENANCE DE THÈSE
de
Yanick Ouellet
Le vendredi 16 février 2024 à 9 h
Local 1211, Pavillon Ferdinand-Vandry
Lien Zoom:
https://ulaval.zoom.us/j/3054862029
« Algorithmes de vérification et de filtrage pour
la contrainte Cumulative et ses variantes »
Président
Monsieur Brahim Chaib-draa, Ph.D.
Directeur des programmes de 2e et 3e cycles
Département d’informatique et de génie logiciel
Université Laval
Examinateurs
Monsieur Claude-Guy Quimper, Ph.D. (Directeur de recherche)
Département d’informatique et de génie logiciel
Université Laval
Monsieur Pascal Germain, Ph.D. (Examinateur)
Département d’informatique et de génie logiciel
Université Laval
Monsieur Pascal Tesson, Ph.D. (Examinateur)
Département d’informatique et de génie logiciel
Université Laval
Monsieur Charles Prud’homme, Ph.D. (Examinateur externe)
Département Automatique, Productique et Informatique
IMT Atlantique, Nantes, France
Les problèmes d’ordonnancement, où il faut planifier des tâches sur une ligne du temps en respectant différentes contraintes, sont présents dans une grande variété d’industries. Cela va de la conception d’horaire pour un hôpital jusqu’à la planification de la production en usine. Malheureusement, la plupart de ces problèmes sont NP-Difficiles. La programmation par contraintes s’est montrée très efficace pour résoudre ces problèmes. Dans cette thèse, nous présenterons des algorithmes de vérification et de filtrage pour trois contraintes d’ordonnancement. La première, la contrainte Cumulative limite l’utilisation d’une ressource à une capacité maximale. Pour cette contrainte, nous améliorons la complexité d’algorithmes de vérification et de filtrage existants. La deuxième contrainte, la SoftCumulative, est une variation de la Cumulative où il est possible de dépasser la capacité maximale, moyennant une pénalité. La troisième, la contrainte MinCumulative, force une utilisation minimale, plutôt que maximale, de la ressource. Pour ces deux dernières contraintes, nous introduisons de nouveaux algorithmes qui sont inspirés par les algorithmes classiques de la contrainte Cumulative.
Abstract
Scheduling problems occur in various industries. Examples of these problems include, among others, nurse rostering, production planning in a factory, and airline crew scheduling. In such problems, one needs to schedule tasks on a time line while satisfying several constraints. Unfortunately, most of these problems are NP-Hard. Constraint programming has been shown to be an effective technique to solve NP-Hard scheduling problems. In this thesis, we introduce checker and filtering algorithms for three scheduling constraints. The Cumulative constraint limits the resource consumption to a max- imal capacity. For that constraint, we present faster checker and filtering algorithms. The SoftCumulative constraint is a variant of the Cumulative where it is possible to exceed the capacity, but doing so incurs a penalty. The MinCumulative constraint enforces a minimum resource usage, rather than limiting it. For those two constraints, we introduce new filtering algorithms that are inspired by classical algorithms for the Cumulative constraint.
Note: La présentation sera donnée en français.
Bienvenue à tous !
