On the use of tasks ordering to solve scheduling problems with constraint programming
Arthur Godet · HAL (Le Centre pour la Communication Scientifique Directe) · 2021
Au cours des deux dernières décennies, la programmation par contraintes s'est illustrée de par son efficacité à résoudre des problèmes d'ordonnancement. Grâce à la grande expressivité permise par le paradigme, différents algorithmes et techniques de résolution provenant d'autres domaines de l'Optimisation Combinatoire ont pu être intégrés au sein des solveurs de contraintes. Toutefois, cette grande expressivité fait que les solveurs ne sont pas des boîtes noires et demandent une expertise pour être paramétrés correctement pour résoudre efficacement les problèmes souhaités. Dans cette thèse, nous explorons l'introduction et l'utilisation d'algorithmes de liste ordonnée en programmation par contraintes pour résoudre des problèmes d'ordonnancement. Nous revisitons également la contrainte AllDiffPrec, définie comme une contrainte Alldifferent et des précédences entre variables, pour laquelle nous proposons également un nouvel algorithme de filtrage.