Machine Learning For Large-Scale Personnel Scheduling Problems

Les problèmes de planification d’horaires du personnel consistent à établir les horaires de travail des employés de manière à garantir que les besoins en main-d’oeuvre soient satisfaits sur un horizon de planification donné. Ces problèmes font l’objet de nombreuses études dans divers secteurs et revêtent une importance particulière dans les industries de services telles que le commerce de détail, où la demande en main-d’oeuvre varie considérablement au cours de la journée, ce qui rend les coûts de main-d’oeuvre cruciaux. Dans de tels environnements, les horaires sont généralement élaborés à partir d’un grand nombre de quarts de travail potentiels, caractérisés par des heures de début, des heures de fin et des durées flexibles. Lorsque l’énumération explicite de ces quarts de travail est requise pour des modèles de programmation linéaire en nombres entiers mixtes, ceux-ci peuvent contenir un très grand nombre de variables et devenir difficiles à résoudre à l’aide de solveurs d’optimisation génériques. Par conséquent, réduire la taille de ces modèles tout en préservant la qualité de la solution constitue un défi majeur pour les problèmes de planification du personnel de grande taille. Dans cette thèse, nous étudions comment des techniques de la science des données, notamment l’apprentissage machine et l’exploration de données, peuvent être utilisées pour guider le processus d’énumération des quarts de travail et améliorer l’évolutivité des modèles d’optimisation pour la planification du personnel dans le secteur de la vente au détail. Tout d’abord, nous proposons un cadre assisté par l’apprentissage pour guider l’énumération des quarts de travail dans les problèmes de planification flexible du personnel avec des quarts de travail mono-tâche. L’approche s’appuie sur des modèles d’apprentissage profond entraînés sur des instances de planification précédemment résolues afin d’identifier des plages horaires prometteuses pour les heures de début et de fin des quarts de travail. Au lieu d’énumérer tous les quarts de travail possibles, la méthode limite le processus d’énumération à ceux qui commencent ou se terminent aux moments prédits, réduisant ainsi considérablement le nombre de quarts de travail potentiels pris en compte dans le modèle d’optimisation. Des expériences numériques menées sur des cas concrets du secteur de la vente au détail, comportant jusqu’à 10 tâches et 50 employés, ont démontré que l’approche proposée peut accélérer le processus de résolution d’un facteur moyen de 47, tout en limitant l’augmentation moyenne du coût à 1.28%. Deuxièmement, nous étudions comment les décisions de planification historiques peuvent être exploitées à l’aide de techniques d’exploration de données afin d’améliorer à nouveau l’efficacité de la résolution de problèmes de planification du personnel de grande taille. Étant donné que les cas de planification dans les environnements de vente au détail sont résolus de manière répétée au fil du temps et présentent souvent des modèles de demande similaires, nous proposons une méthode basée sur l’algorithme des k plus proches voisins pour identifier les cas historiques similaires à un nouveau cas. Les modèles de quarts de travail apparaissant dans les solutions de ces instances historiques sont ensuite utilisés pour restreindre l’énumération des quarts de travail candidats dans le nouveau problème. Cette approche permet au processus d’optimisation de tirer parti des structures de solution observées précédemment. Des expériences numériques menées sur des instances impliquant jusqu’à 12 types de tâches et 252 employés montrent que la méthode proposée peut éliminer en moyenne plus de 85% des variables de décision, ce qui conduit à un facteur d’accélération moyen supérieur à 15 tout en maintenant les coûts de solution à environ 1% des coûts des solutions de référence. Enfin, nous étendons le cadre assisté par l’apprentissage machine au contexte plus complexe de la planification des horaires avec quarts multi-tâches. Dans de nombreux environnements de vente au détail, les employés peuvent effectuer plusieurs tâches différentes au cours d’un même quart de travail, ce qui augmente considérablement le nombre de configurations d’horaires possibles. Nous développons une formulation explicite de couverture d’ensembles qui intègre à la fois les quarts mono-tâche et multi-tâches, chaque quart pouvant se composer de plusieurs segments de tâche. Pour maîtriser la croissance combinatoire du nombre de variables qui en résulte, nous utilisons un modèle d’apprentissage machine qui prédit les périodes de début et de fin prometteuses pour les segments de tâche et filtre les limites de segments peu probables avant l’énumération des quarts de travail. Des expériences numériques menées sur des ensembles de données réels et synthétiques démontrent que la méthode proposée produit des solutions de haute qualité dans des délais de calcul raisonnables. De plus, l’intégration de quarts de travail à tâches multiples permet de réduire les coûts moyens jusqu’à 4.24% par rapport aux horaires limités aux quarts de travail à tâche unique. Dans l’ensemble, cette thèse démontre que l’intégration de techniques d’apprentissage machine et d’exploration de données à l’optimisation mathématique peut améliorer considérablement l’évolutivité des modèles explicites de planification du personnel basés sur les quarts de travail. Les approches proposées permettent de résoudre efficacement des problèmes de planification à grande échelle dans le secteur de la vente au détail tout en préservant la qualité des solutions, fournissant ainsi des outils pratiques d’aide à la décision pour la gestion des effectifs dans les industries de services.