Président
Monsieur Brahim Chaib-draa, Ph.D.
Directeur des programmes gradués
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 Richard Khoury, Ph.D. (Examinateur)
Département d’informatique et de génie logiciel
Université Laval
Monsieur Jonathan Gaudreault, Ph.D. (Examinateur)
Département d’informatique et de génie logiciel
Université Laval
Monsieur Thierry Petit, Ph.D. (Examinateur externe)
Worcester Polytechnic Institute, USA
"La programmation par contraintes est une technique puissante pour résoudre des problèmes d’ordonnancement de grande envergure. L’ordonnancement cherche à allouer dans le temps une variété de tâches à des ressources telles que les tâches consomment une certaine quantité de ressource durant leur exécution. Généralement, on cherche à optimiser une fonction « objectif » telle la durée totale d’un ordonnancement. Résoudre un problème d’ordonnancement est équivalent à 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. Particulièrement, nous voulons résoudre plus efficacement des problèmes d’ordonnancement où le critère d’optimalité n’est pas nécessairement la durée de l’ordonnancement. Pour résoudre ces problèmes, nous avons besoin d’algorithmes de filtrage plus rapide pour les problèmes d’ordonnancement conventionnel. De plus, nous devons considérer les propriétés distinctes des problèmes d’ordonnancement industriels. Par exemple, nous considérons des cas où la capacité d’une ressource fluctue dans le temps, où le coût d’exécution d’une ressource évolue dans le temps, où encore lorsque les tâches peuvent être retardées."
Abstract:
"Constraint programming is a powerful methodology to solve large scale and practical scheduling problems. Resource-constrained scheduling deals with temporal allocation of a variety of tasks to a set of resources, where the tasks consume a certain amount of resource during their execution. Ordinarily, a desired objective function such as the total length of a feasible schedule, called the makespan, is optimized in scheduling problems. Solving the scheduling problem is equivalent to finding out when each task starts and which resource executes it. In general, the scheduling problems are NP-Hard.
Consequently, there exists no known algorithm that can solve the problem by executing a polynomial number of instructions. Nonetheless, there exist specializations for scheduling problems that are not NP-Complete. Such problems can be solved in polynomial time using dedicated algorithms. Our objective is to tackle such algorithms for scheduling problems in a variety of contexts. Filtering techniques are being developed and improved over the past years in constraint-based scheduling. The prominency of filtering algorithms lies on their power to shrink the search tree by excluding values from the domains which do not yield a feasible solution. We also aim at solving more efficiently scheduling problems whose optimization criteria is not necessarily the makespan. To solve these problems, we need faster filtering algorithms for conventional scheduling. Furthermore, we consider distinct properties of industrial scheduling problems. For instance, we consider the cases such as when the amount of available resources fluctuates over time, or when the cost of executing a task at time t is dependent on t, or when the tasks can be delayed."
Bienvenue à tous !
