Notification Timing for On-Demand Personnel Scheduling - Complexity and an Imitation Learning Approach

Les systèmes de service modernes s’appuient de plus en plus sur un large bassin d’employés occasionnels avec des horaires flexibles, payés à la pièce, pour répondre à la demande de travail sur appel dans des secteurs tels que le covoiturage, les livraisons et les plateformes de microtâches. Cependant, maintenir une prestation de service de haute qualité reste un défi, car les employés occasionnels ont souvent une implication peu fréquente et une expérience limitée. Cette étude présente un système de planification avancé, basé sur les données, qui donne la priorité aux employés occasionnels expérimentés, dans le but d’optimiser les opérations de service tout en minimisant les perturbations. Similaire aux systèmes de service sur appel traditionnels, notre approche contacte les employés par ordre d’ancienneté pour offrir des opportunités de quarts, ce qui permet aux travailleurs de choisir les quarts disponibles et même de « supplanter » les employés juniors si les quarts préférés ne sont pas disponibles. Bien que le supplantage soit autorisé, il peut entraîner une insatisfaction parmi les employés et une instabilité des horaires, créant un besoin de stratégies qui réduisent à la fois le supplantage et garantissent que les quarts sont pourvus rapidement. Nous formalisons ce défi de planification comme un problème de synchronisation des notifications (NTP) et établissons qu’il est NP-complet, même sous des hypothèses d’information parfaite. Pour remédier à l’incertitude des temps de réponse des employés, nous proposons un modèle stochastique en deux étapes pour la synchronisation dynamique des notifications, en développant une politique heuristique avec une structure basée sur des seuils. Cette politique est calibrée à l’aide de solutions hors ligne où toutes les incertitudes sont supposées connues, ce qui nous permet d’affiner les règles de décision pour les applications en temps réel. En optimisant le timing des notifications, notre approche réduit la probabilité de remplacements inutiles tout en garantissant l’affectation rapide des équipes. De plus, nous appliquons une approche d’apprentissage par imitation en utilisant DAgger pour former de manière itérative un modèle prédictif qui capture la prise de décision des experts dans des scénarios d’affectation séquentielle des équipes. L’algorithme DAgger permet à la politique d’apprendre à partir de scénarios d’experts déterministes, créant ainsi un cadre de prise de décision efficace en temps réel. Cette intégration de l’optimisation et de l’apprentissage automatique s’ajuste dynamiquement aux états actuels du système, en équilibrant les notifications précoces et différées pour minimiser les perturbations du planning. Notre approche s’appuie sur un ensemble de modèles experts, notamment Hindsight, Aggregated Hindsight et un expert stochastique en deux étapes, pour informer l’algorithme d’apprentissage avec diverses perspectives. En définissant ces multiples modèles experts, nous offrons une base flexible et personnalisable pour divers contextes opérationnels, permettant à l’algorithme d’apprentissage d’intégrer différentes perspectives d’experts pour améliorer la précision et l’adaptabilité des décisions. Les résultats empiriques utilisant des données réelles de notre partenaire industriel démontrent la robustesse des politiques proposées, qui surpassent les méthodes heuristiques existantes en améliorant considérablement l’efficacité de la planification et la satisfaction des employés. Cette étude met en évidence le potentiel de la combinaison de la modélisation stochastique et de l’apprentissage par imitation pour relever les défis complexes de la planification induits par l’incertitude dans les systèmes de services à la demande, en apportant des méthodologies précieuses pour la prise de décision dynamique et en offrant une gamme d’options pilotées par des experts pour améliorer les performances du modèle dans diverses applications.

Abstract

Modern service systems increasingly rely on a large pool of casual employees with flexible hours, paid on a piece-rate basis, to meet the demand for on-call work in sectors such as ride-sharing, deliveries, and microtask platforms. However, maintaining high-quality service delivery remains a challenge, as casual employees often have infrequent engagement and limited experience. This study introduces an advanced, data-driven scheduling system that prioritizes experienced casual employees, aiming to optimize service operations while minimizing disruptions. Similarly to traditional on-call systems, our approach contacts employees in order of seniority to offer shift opportunities, allowing flexibility for workers to choose available shifts and even "bump" junior employees if preferred shifts are unavailable. Although bumping is allowed, it can lead to dissatisfaction among employees and scheduling instability, creating a need for strategies that both reduce bumps and ensure shifts are filled promptly. We formalize this scheduling challenge as a Notification Timing Problem (NTP) and establish that it is NP complete, even under the assumptions of perfect information. To address the uncertainty in employee response times, we propose a two-stage stochastic model for dynamic notification timing, developing a heuristic policy with a threshold-based structure. This policy is calibrated using offline solutions, where all uncertainties are assumed to be known, allowing us to refine decision rules for real-time applications. By optimizing notification timing, our approach reduces the probability of unnecessary replacements while ensuring the timely assignment of shifts. Additionally, we apply an imitation learning approach using DAgger to iteratively train a predictive model that captures expert decision-making in sequential shift assignment scenarios. The DAgger algorithm enables the policy to learn from deterministic expert scenarios, creating an effective real-time decision-making framework. This integration of optimization and machine learning dynamically adjusts to current system states, balancing early and delayed notifications to minimize schedule disruptions. Our approach leverages an array of expert models, including Full-Information, Deterministic, Aggregated Deterministic, and a Two-Stage Stochastic expert, to inform the learning algorithm with diverse perspectives. By defining these multiple expert models, we offer a flexible, customizable foundation for various operational contexts, enabling the learning algorithm to incorporate different expert perspectives to improve the accuracy and adaptability of the decisions. Empirical results using real-world data from our industry partner demonstrate the robustness of the proposed policies, which outperform existing heuristic methods by significantly improving both scheduling efficiency and employee satisfaction. This study highlights the potential of combining stochastic modelling and imitation learning to tackle complex uncertaintydriven scheduling challenges in on-demand service systems, contributing valuable methodologies for dynamic decision-making and offering a range of expert-driven options to enhance model performance across diverse applications.