A Divide-and-Conquer Approach to Employee Scheduling

RÉSUMÉ: 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. ABSTRACT: As companies grow larger and larger, it becomes necessary to determine the work schedules of a large number of employees. Moreover, laws and labor agreements grow more complex over time, which in turn makes the problem of determining a schedule a difficult one. Of course, many computational methods to solve personnel scheduling problems have been proposed,but most of them have a time complexity which makes them unsuitable for instances that are particularly large. Therefore, there is a demand for an algorithm that is able to quickly handle large instances of schedule generation problems. Since plenty of progress have already been made in making the solving algorithms better, we will attempt to make the problems smaller to decrease the computation times. In other words, we will apply the divide-and-conquer principle to this issue. If we could split a large personnel scheduling instance into multiple subinstances, we could apply any state-of-the-art method of our choosing to the subinstances to compute a solution to the master instance.Since the subinstance's sizes are a fraction of the original instance's, we could expect a sizable reduction of the computation time. On the other hand, if the original instance is split in an inadequate manner, the quality of the final results could be disastrou