Fabrication d'horaires personnalisés maximisant le nombre d'heures travaillées par ordre de seniorité

En règle générale, une entreprise cherche à minimiser les coûts de gestion du personnel en respectant les normes et les conventions collectives. Néanmoins, il arrive que l'on décide d'ajouter une composante non négligeable aux coûts, à savoir les préférences des employés. Ainsi, on modifie légèrement les objectifs d'optimisation, en donnant de l'importance aux volontés des employés, en donnant la priorité aux employés dont l'ancienneté est la plus importante. En effet, on peut se rendre compte qu'il y a plus de bénéfices à tirer d'employés dont les préférences sont satisfaites, plutôt que d'employés choisis de façon à optimiser les coûts, mais qui sont mécontents de leurs affectations. Ce projet de maîtrise a pour but de répondre à ce problème de fabrication d'horaires de personnel avec priorités. Nous appliquons ce problème à des magasins de vente au détail. L'objectif final est de proposer une méthode heuristique basée sur un modèle de programmation en nombres entiers permettant d'obtenir une solution optimale au problème. Nous résolvons le problème de façon séquentielle en utilisant des groupes d'employés. Par exemple nous prenons les 5 employés les plus seniors et nous optimisons l'horaire. On fixe leur horaire et on passe au groupe suivant. Il faut faire attention à ce que les algorithmes développés pour produire les solutions ne nécessitent pas des temps de calcul trop longs à l'exécution. Dans le cadre de cette étude, une seule préférence est prise en compte. Nous tenons ainsi à ce que les employés travaillent le plus d'heures possible. Par conséquent, nous vérifierons que les employés les plus seniors travaillent plus que leurs homologues plus juniors. Un jeu de données factice permet de constater l'efficacité de notre méthode. Mais dans les instances de la vie réelle, les disponibilités rendent impossible la satisfaction des préférences au sens strict. Nous entendons par là qu'il est impossible pour certains employés seniors de travailler plus que des juniors. D'où le besoin d'établir un évaluateur qui certifie que nous satisfaisons bien les préférences. Nous testons ensuite notre approche sur différents jeux de données et estimons l'impact de la satisfaction des préférences sur les fonctions de coût déjà existantes. Puis deux autres approches sont testées pour les comparer à celle d'origine. La première évite l'utilisation des quarts anonymes en relaxant l'intégrité sur les variables associées aux employés plus juniors. La seconde ajoute une contrainte au problème indiquant le nombre d'heures minimum que les employés seniors doivent faire. Enfin, des stratégies de réduction des temps de calcul sont proposées ainsi qu'une analyse de sensibilité pour la meilleure approche.

Abstract

Traditionally, firms aim to minimize the costs linked to the management of staff while still respecting employment law and collective agreement. However, another factor, the satisfaction of preferences, can also be added to these costs. In so doing optimization is modified by taking into account senior employees wishes. Indeed employees who are happy with their schedules generally benefit the company. This thesis will deal with the problem of staff scheduling which considers preferences and priorities and will adress real-life instances from the retail industry. The final goal is to propose a heuristic method based on integer programming in order to obtain optimal solutions. The problem will be solved sequentially using groups of employees. For instance, we will begin by building the schedule of the five most senior employees and then we will do the same for the next group. The computational time will be restricted to be between 0 and 10 minutes maximum. In this study we will only take into account one preference: employees want to work a maximum of hours in a week. Consequently we will check if senior employees work more than junior employees. An artificial instance will be used to test the efficiency of the proposed method. In real life, employee availability cannot ensure the strict satisfaction of preferences – in other words it is possible that some senior employees work less than juniors. So we need to create a tool that guarantees the satisfaction of preferences. We test the proposed solution approach on different instances and then estimate the impact of préférences on the cost of solutions. We will also test two other approaches and compare them to the first one. The first alternative approach avoids the use of open shifts by relaxing the integrality requirements on the variables associated with the juniors. The second one adds a constraint to the problem, indicating the number of hours that the seniors need to work, which is calculated by the first solution. Finally we propose strategies to reduce the computational times and an analysis of sensitivity for the best approach.