Thèse ou mémoire avec insertion d'articles / 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 $\textup{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 $\textup{SoftCumulative}$, est une variation de la $\textup{Cumulative}$ où il est possible de dépasser la capacité maximale, moyennant une pénalité. La troisième, la contrainte $\textup{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 $\textup{Cumulative}$. / 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. $\textup{The Cumulative}$ constraint limits the resource consumption to a maximal capacity. For that constraint, we present faster checker and filtering algorithms. $\textup{The SoftCumulative}$ constraint is a variant of the $\textup{Cumulative}$ where it is possible to exceed the capacity, but doing so incurs a penalty. The $\textup{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 $\textup{Cumulative} constraint.
| Identifer | oai:union.ndltd.org:LAVAL/oai:corpus.ulaval.ca:20.500.11794/138923 |
| Date | 22 March 2024 |
| Creators | Ouellet, Yanick |
| Contributors | Quimper, Claude-Guy |
| Source Sets | Université Laval |
| Language | French |
| Detected Language | French |
| Type | COAR1_1::Texte::Thèse::Thèse de doctorat |
| Format | 1 ressource en ligne (xi, 107 pages), application/pdf |
| Rights | http://purl.org/coar/access_right/c_abf2 |
Page generated in 0.0026 seconds