Résumé technique : Prédiction du temps d'attente par apprentissage automatique pour les files d'attente à priorité

Énoncé du problème

L'article traite du défi que représente la prédiction des temps d'attente transitoires dans les systèmes de files d'attente à priorités multiclasses opérant sous des conditions variables dans le temps. Alors que la théorie classique des files d'attente fournit des résultats analytiques exacts pour les systèmes simples et stationnaires, les applications réelles (par exemple, la santé, les centres d'appels, la logistique) impliquent souvent des taux d'arrivée non stationnaires, des distributions de temps de service complexes et des règles de préemption. Dans de tels environnements, le temps d'attente d'un client dépend non seulement de l'état actuel de la file, mais aussi des arrivées futures de haute priorité, ce qui rend la prédiction analytique difficile.

L'étude examine spécifiquement si les modèles d'apprentissage automatique (ML) peuvent prédire avec précision les temps d'attente en utilisant des données limitées et opérationnellement observables — spécifiquement la longueur de la file au moment de l'arrivée et la classe de priorité du client — sans nécessiter une connaissance détaillée des fonctions de taux d'arrivée sous-jacentes ou des distributions de temps de service.

Méthodologie

Génération de données

Les auteurs ont généré un ensemble de données synthétiques simulant 200 jours indépendants d'une file d'attente à deux classes ($G(t)/G/1$) sous un environnement variable dans le temps.

• Processus d'arrivée : Les arrivées non stationnaires ont été modélisées à l'aide d'intervalles homogènes par morceaux avec des distributions de type PH (Phase-Type) pour capturer la variabilité au-delà des simples hypothèses exponentielles.
• Discipline de service : Trois règles de service distinctes ont été simulées :
  1. Non-préemptive : Le service se poursuit sans interruption une fois commencé.
  2. Préemptive-avec-recommencement (Preemptive-Repeat) : Une arrivée de priorité supérieure interrompt un travail de priorité inférieure, qui doit recommencer depuis le début lors de la reprise.
  3. Préemptive-avec-reprise (Preemptive-Resume) : Une arrivée de priorité supérieure interrompt un travail de priorité inférieure, qui reprend à l'endroit où il a été interrompu.
• Caractéristiques (Features) : Deux configurations de caractéristiques ont été testées :
  1. Ensemble de quatre caractéristiques : Temps d'arrivée, temps inter-arrivée, classe de priorité et longueur de la file à l'arrivée.
  2. Ensemble de deux caractéristiques : Classe de priorité et longueur de la file à l'arrivée uniquement.

Modèles évalués

Cinq modèles d'apprentissage automatique ont été comparés :

1. Gradient Boosting Machine (GBM) : Un ensemble standard d'arbres de décision.
2. Forced Priority-Split GBM (FS-GBM) : Une variante où l'ensemble de données est divisé de manière stricte par classe de priorité avant l'entraînement de modèles GBM distincts.
3. Random Forest (RF) : Un ensemble standard d'arbres de décision décorrélés.
4. Forced Priority-Split RF (FS-RF) : Une variante avec des modèles RF distincts entraînés pour chaque classe de priorité.
5. Réseau de neurones récurrents (RNN) : Une architecture basée sur LSTM conçue pour capturer les dépendances temporelles dans la séquence des arrivées de clients au cours d'une journée.

La performance a été évaluée à l'aide de l'erreur absolue moyenne (MAE), de l'erreur quadratique moyenne (MSE), de la racine de l'erreur quadratique moyenne (RMSE) et du coefficient de détermination ($R^2$).

Principales contributions

• Cadre unifié : L'étude fournit un cadre de simulation unifié pour générer des données transitoires à travers les disciplines non préemptives, préemptives-avec-recommencement et préemptives-avec-reprise avec des arrivées variables dans le temps.
• Évaluation des structures respectant la priorité : L'article teste explicitement si la division stricte des données par classe de priorité (FS-GBM, FS-RF) améliore la prédiction par rapport aux modèles standards qui traitent la priorité comme une caractéristique.
• Faisabilité avec des informations minimales : La recherche démontre qu'une prédiction précise du temps d'attente est réalisable en utilisant seulement deux entrées (longueur de la file et priorité), remettant en question l'hypothèse selon laquelle des paramètres détaillés du système sont nécessaires pour les approches fondées sur les données.
• Analyse comparative : Elle offre une comparaison complète entre les ensembles basés sur les arbres et les modèles de deep learning basés sur les séquences dans le contexte des files d'attente à priorité.

Résultats

Performance des modèles

• Supériorité du RNN : Le réseau de neurones récurrents (LSTM) a systématiquement obtenu la plus haute précision à travers les trois disciplines de service et les deux configurations de caractéristiques. Il a démontré sa capacité à modéliser des dynamiques temporelles complexes, particulièrement dans les contextes préemptifs où les interruptions de service créent des dépendances complexes.
  • Dans le cadre non préemptif (4 caractéristiques), le RNN a atteint un $R^2$ de 0,987, contre environ 0,94 pour les modèles basés sur les arbres.
  • Dans le cadre préemptif-avec-reprise (le scénario le plus complexe), le RNN a maintenu un $R^2$ de 0,987, tandis que les modèles basés sur les arbres sont tombés à environ 0,927.
• Stabilité des modèles basés sur les arbres : Les modèles GBM et Random Forest ont fourni des performances stables et compétitives, particulièrement dans les contextes non préemptifs. Cependant, ils ont montré une précision réduite dans les scénarios préemptifs par rapport au RNN.
• Inefficacité de la division forcée : Les variantes "Forced Priority-Split" (FS-GBM et FS-RF) n'ont offert que des améliorations marginales et incohérentes par rapport à leurs homologues standards. Les auteurs concluent que les modèles d'arbres standards sont déjà capables d'apprendre implicitement les non-linéarités spécifiques à la priorité lorsque celle-ci est incluse comme caractéristique d'entrée, rendant la division stricte explicite inutile.

Réduction des caractéristiques

La réduction des caractéristiques d'entrée de quatre à deux (suppression du temps d'arrivée et du temps inter-arrivée) n'a entraîné qu'une diminution modérée des performances.

• Le RNN a conservé un fort pouvoir prédictif même avec des entrées minimales, atteignant un $R^2$ de 0,974 dans le cas non préemptif et de 0,972 dans le cas préemptif-avec-reprise avec seulement deux caractéristiques.
• Les modèles basés sur les arbres sont également restés stables, suggérant que la longueur de la file et la priorité encodent la majeure partie de l'information prédictive requise.

Signification et affirmations

L'article affirme que l'apprentissage automatique, en particulier les modèles basés sur les séquences comme les RNN, offre une alternative pratique et puissante aux méthodes analytiques traditionnelles pour la prédiction du temps d'attente en temps réel dans les systèmes de service à priorité.

• Déployabilité pratique : La conclusion selon laquelle des prédictions précises sont possibles en utilisant uniquement la longueur de la file et la priorité est soulignée comme un avantage pratique majeur. Dans de nombreux systèmes réels (par exemple, hôpitaux, centres d'appels), les fonctions de taux d'arrivée détaillées ou les distributions de service sont inconnues ou difficiles à estimer, mais la longueur de la file et la priorité sont facilement observables.
• Gestion de la préemption : L'étude démontre que les modèles de ML peuvent capturer efficacement les effets complexes de la préemption (tant le recommencement que la reprise) sans modélisation explicite de la logique d'interruption, une tâche analytiquement difficile.
• Sélection de modèle : Bien que les RNN soient identifiés comme les plus efficaces pour capturer les dynamiques temporelles dans les systèmes préemptifs, les modèles basés sur les arbres sont présentés comme des alternatives fiables, stables et efficaces sur le plan computationnel, surtout si l'interprétabilité ou une architecture plus simple est préférée.
• Limites des modifications structurelles : L'article conclut modestement que forcer explicitement les divisions de priorité n'améliore pas significativement la performance, suggérant que les méthodes d'ensemble modernes sont suffisamment robustes pour gérer l'hétérogénéité des priorités via l'inclusion standard de caractéristiques.

Les auteurs soulignent que leur travail fait le pont entre la théorie classique des files d'attente et la prédiction moderne basée sur les données, offrant un cadre adapté aux systèmes disposant de données limitées et de conditions de fonctionnement dynamiques.