Staff assignment using network flow techniques

Varone, Sacha ; Schindl, David

La détermination des horaires du personnel est une tâche à faire dans toute organisation de plusieurs employés. Dans cette recherche, nous revisitons sa modélisation comme un problème de coût minimum à débit maximal dans un réseau. Cette modélisation possède l'avantage de permettre une résolution par un algorithme s'exécutant en temps polynomial. Outre les contraintes de... Plus

Ajouter à la liste personnelle
    Résumé
    La détermination des horaires du personnel est une tâche à faire dans toute organisation de plusieurs employés. Dans cette recherche, nous revisitons sa modélisation comme un problème de coût minimum à débit maximal dans un réseau. Cette modélisation possède l'avantage de permettre une résolution par un algorithme s'exécutant en temps polynomial. Outre les contraintes de disponibilité et de compétences, nous considérons comme un ensemble de contraintes supplémentaires : la charge contractuelle de travail, la satisfaction des employés traitée sous l'angle de contraintes de rotation, les tâches nécessitant plusieurs employés, des incompatibilités de tandems, ne pouvant être affectés à une même tâche. Nous considérons plusieurs type de coûts à minimiser : les heures supplémentaires, les catégories d'employés, les retards dans l'accomplissement des tâches, les profits associés à l'exécution des tâches. Nous analysons aussi les limites de notre modèle, en montrant différents types de contraintes qui transforment le problème en un problème NP-dur.
    Summary
    Staff scheduling, also known as timetabling, is a task to be done in any organization with several employees. In this paper, we revisit its modeling as a minimum cost maximum flow problem in a network, which has the decisive advantage to be solvable with a polynomial time algorithm. Besides the usual availability and skills constraints, we consider additional constraints : targeted workload, satisfaction of employees seen as rotation constraints, tasks requiring several employees, pairs of employees which can not be assigned to a same task. We consider several cost specifications : types of employees, overtime, delayed tasks, profit associated with the execution of a task. We also analyze the limits of our model, showing types of constraints that transform the problem into an NP-hard problem.