<  Retour au portail Polytechnique Montréal

A Divide-and-Conquer Approach to Employee Scheduling

Nicolas Heutte

Mémoire de maîtrise (2020)

Document en libre accès dans PolyPublie
[img]
Affichage préliminaire
Libre accès au plein texte de ce document
Conditions d'utilisation: Tous droits réservés
Télécharger (441kB)
Afficher le résumé
Cacher le résumé

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 disastrous

Département: Département de génie informatique et génie logiciel
Programme: Génie informatique
Directeurs ou directrices: Daniel Aloise et Guy Desaulniers
URL de PolyPublie: https://publications.polymtl.ca/5362/
Université/École: Polytechnique Montréal
Date du dépôt: 20 oct. 2020 13:28
Dernière modification: 02 oct. 2024 01:54
Citer en APA 7: Heutte, N. (2020). A Divide-and-Conquer Approach to Employee Scheduling [Mémoire de maîtrise, Polytechnique Montréal]. PolyPublie. https://publications.polymtl.ca/5362/

Statistiques

Total des téléchargements à partir de PolyPublie

Téléchargements par année

Provenance des téléchargements

Actions réservées au personnel

Afficher document Afficher document