Programme de Doctorat en informatique

Département d’informatique et de génie logiciel

Faculté des sciences et de génie

Présentation de la proposition de projet de thèse de

De

Yanick Ouellet

Jeudi 16 décembre 2021 de 10h00 à 12h00

Par vidéoconférence (voir lien ci-dessous)

https://ulaval.zoom.us/j/62832918161?pwd=R2NIODAvVW5yV3c1Z3FucFNGYmllZz09

« Algorithmes de vérification et de filtrage pour des contraintes d’ordonnancement. »

Verification and filtering algorithms for scheduling constraints.

Membres du comité d’encadrement

Pr. Claude-Guy Quimper
(Directeur de recherche)
Département d’informatique et de génie logiciel

Pr. Pascal Tesson
Département d’informatique et de génie logiciel

Pr. Pascal Germain
Département d’informatique et de génie logiciel

 

Résumé

Les problèmes d’ordonnancement, où il faut céduler 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 de biscuits.

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 proposition de 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. La deuxième contrainte, la Cumulative Souple, est une variation de la Cumulative où il est possible de dépasser la capacité maximale, moyennant un coût.

La troisième, la contrainte MinCumulative, force une utilisation minimale, plutôt que maximale, de la ressource.

 

Abstract

Scheduling problems, where tasks must be scheduled on a timeline within different constraints, are present in a wide variety of industries. They range from scheduling a hospital to planning the production of biscuits.

Unfortunately, most of these problems are NP-hard. Constraint programming has proven to be very effective in solving these problems. In this thesis proposal, we will present verification and filtering algorithms for three scheduling constraints. The first, the Cumulative constraint, limits the use of a resource to a maximum capacity. The second constraint, the Flexible Cumulative, is a variation of the Cumulative where it is possible to exceed the maximum capacity, at a cost.

The third, the MinCumulative constraint, forces a minimum, rather than maximum, use of the resource.

 

Note: La présentation sera donnée en français.

 

Bienvenue à tous!