Résolution d'horaires scolaires

Par Simon Turcotte

Mon projet est la confection d'un horaire scolaire (School Timetables) avec des contraintes telle que le nombre de classes, la capacité des classes, les cours, le nombre d’élèves, les professeurs,...

Mon projet sera hybride, c'est-à-dire moitié théorique et moitié pratique. Pour la partie théorique, j'expliquerai la résolution du problème d'horaire en utilisant trois algorithmes différents : recuit simulé (simulated annealing), génétique et décomposition. Je décrirai le rôle du parallélisme dans chacun de ces algorithmes. Pour la partie pratique, je vais faire une démonstration de l'un des algorithmes présentés en le programmant. Les contraintes de l'horaire seront allégées afin de simplifier le programme et faciliter l'implémentation de l'algorithme.

Références:

David Abramson. "Constructing School Timetables using Simulated Annealing: Sequential and Parallel Algorithms"

David Abramson. "Simulated Annealing Cooling Schedules for the School Timetabling Problem"

David Abramson. "A PARALLEL GENETIC ALGORITHM FOR SOLVING THE SCHOOL TIMETABLING PROBLEM"

Petr Šlechta. "Decomposition and Parallelization of Multi-Resource Timetabling Problems"

Leonardo Jelenković, Josko Poljak. "MULTITHREADED SIMULATED ANNEALING"

Łukasz Antkowiak. "Parallel algorithms of timetable generation"

Zbigniew J. Czech1, Wojciech Mikanik, and Rafal Skinderowicz, "Implementing a Parallel Simulated Annealing Algorithm"