A Divide-and-Conquer Approach to Employee Scheduling

De nos jours, les grandes entreprises ont trop d'employés pour se permettre de déterminer leurs emplois du temps à la main. Par conséquent, ces entreprises sont contraintes d'utiliser des méthodes informatiques pour créer un horaire satisfaisant. De nombreux algorithmes ont été proposés pour générer les meilleurs horaires possibles. Cependant, leur complexité temporelle rend la résolution de gros problèmes de génération d'horaire très lente. On cherche donc un moyen de réduire cette complexité lorsque l'on est confronté à des problèmes de grande taille.La piste qui sera explorée dans ce mémoire est l'application du principe de "diviser pour régner" au problème de génération d'horaire. Si l'on parvient à diviser un exemplaire de grande taille en plusieurs sous-exemplaires plus petits, on peut résoudre chaque sous-exemplaire séparément et déduire des solutions obtenues une solution à l'exemplaire de grande taille que l'on souhaitait traiter en premier lieu. Cependant, la structure du problème de génération d'horaire fait que la manière de séparer l'exemplaire de grande taille en sous-exemlaires peut très fortement dégrader la qualité des solutions obtenues. On souhaite donc trouver un moyen de partitionner un exemplaire de grande taille sans que la qualité de la solution obtenue ne diminue trop.