Une introduction à la théorie des files d’attente

La théorie des files d’attente est l’étude mathématique de la file d’attente, ou de l’attente en ligne. Les files d’attente contiennent clients (ou « objets ») tels que des personnes, des objets ou des informations. Des files d’attente se forment lorsque les ressources disponibles pour fournir un service. Par exemple, s’il y a 5 caisses enregistreuses dans une épicerie, des files d’attente se formeront si plus de 5 clients souhaitent payer leurs articles en même temps.

Une système de file d’attente consiste en un processus d’arrivée (comment les clients arrivent dans la file d’attente, combien de clients sont présents au total), la file d’attente elle-même, le processus de service pour s’occuper de ces clients et les départs du système.

Mathématiques modèles de files d’attente sont souvent utilisés dans les logiciels et les entreprises pour déterminer la meilleure façon d’utiliser des ressources limitées. Les modèles de file d’attente peuvent répondre à des questions telles que Quelle est la probabilité qu’un client attende 10 minutes dans la file d’attente ? Quel est le temps d’attente moyen par client ?

Les situations suivantes sont des exemples d’application de la théorie de la file d’attente :

• Faire la queue dans une banque ou un magasin
• Attendre qu’un représentant du service clientèle réponde à un appel après que l’appel ait été mis en attente
• Attendre l’arrivée d’un train
• Attendre qu’un ordinateur exécute une tâche ou réponde
• Attendre un lavage automatique pour nettoyer une file de voitures

Caractérisation d’un système de file d’attente

Les modèles de file d’attente analysent la manière dont les clients (y compris les personnes, les objets et les informations) reçoivent un service. Un système de file d’attente contient :

• Processus d’arrivée. Le processus d’arrivée est simplement la façon dont les clients arrivent. Ils peuvent entrer dans une file d’attente seuls ou en groupe, et ils peuvent arriver à certains intervalles ou de manière aléatoire.
• Comportement. Comment les clients se comportent-ils lorsqu’ils font la queue ? Certains peuvent être prêts à attendre leur place dans la file d’attente ; d’autres peuvent s’impatienter et partir. D’autres encore peuvent décider de rejoindre la file d’attente plus tard, par exemple lorsqu’ils sont mis en attente avec le service clientèle et décident de rappeler dans l’espoir de recevoir un service plus rapide.
• Comment les clients sont-ils servis ?. Il s’agit notamment de la durée de service d’un client, du nombre de serveurs disponibles pour aider les clients, du fait que les clients sont servis un par un ou par lots, et de l’ordre dans lequel les clients sont servis, également appelé discipline de service.
• Discipline de service fait référence à la règle selon laquelle le client suivant est sélectionné. Bien que de nombreux scénarios de vente au détail utilisent la règle du « premier arrivé, premier servi », d’autres situations peuvent nécessiter d’autres types de services. Par exemple, les clients peuvent être servis par ordre de priorité ou en fonction du nombre d’articles à servir (comme dans une voie express d’une épicerie). Parfois, le dernier client arrivé sera servi en premier (comme dans le cas d’une pile de vaisselle sale, où celui qui se trouve au-dessus sera le premier à être lavé).
• Salle d’attente. Le nombre de clients autorisés à attendre dans la file d’attente peut être limité en fonction de l’espace disponible.

Mathématiques de la théorie des files d’attente

La notation de Kendall est une notation sténographique qui spécifie les paramètres d’un modèle de base de file d’attente. La notation de Kendall est écrite sous la forme A/S/c/B/N/D, où chacune des lettres représente des paramètres différents.

• Le terme A décrit le moment où les clients arrivent dans la file d’attente – en particulier, le temps entre les arrivées, ou temps d’attente entre deux arrivées. Mathématiquement, ce paramètre spécifie la distribution de probabilité que suivent les temps d’attente entre deux arrivées. Une distribution de probabilité couramment utilisée pour le terme A est la distribution de Poisson.
• Le terme « S » décrit le temps qu’il faut à un client pour être servi après avoir quitté la file d’attente. Mathématiquement, ce paramètre spécifie la distribution de probabilité que ces horaires de service suivre. La distribution de Poisson est également couramment utilisée pour le terme S.
• Le terme c précise le nombre de serveurs dans le système de mise en file d’attente. Le modèle suppose que tous les serveurs du système sont identiques, de sorte qu’ils peuvent tous être décrits par le terme S ci-dessus.
• Le terme B précise le nombre total d’articles qui peuvent être dans le système, et comprend les articles qui sont encore dans la file d’attente et ceux qui sont en cours de traitement. Bien que de nombreux systèmes dans le monde réel aient une capacité limitée, le modèle est plus facile à analyser si cette capacité est considérée comme infinie. Par conséquent, si la capacité d’un système est suffisamment importante, le système est généralement considéré comme infini.
• Le terme N précise le nombre total de clients potentiels – c’est-à-dire le nombre de clients qui pourraient entrer dans le système de file d’attente – qui peut être considéré comme fini ou infini.
• Le terme D précise la discipline de service du système de file d’attente, comme le premier arrivé premier servi ou le dernier entré premier sorti.

La loi de Littlequi a été prouvée pour la première fois par le mathématicien John Little, indique que le nombre moyen d’articles dans une file d’attente peut être calculé en multipliant le taux moyen auquel les articles arrivent dans le système par le temps moyen qu’ils y passent.

• En notation mathématique, la loi de Little est : L = λW
• L est le nombre moyen d’articles, λ est le taux moyen d’arrivée des articles dans le système de file d’attente, et W est le temps moyen que les articles passent dans le système de file d’attente.
• La loi de Little suppose que le système est dans un « état stable » – les variables mathématiques caractérisant le système ne changent pas avec le temps.

Bien que la loi de Little ne nécessite que trois entrées, elle est assez générale et peut être appliquée à de nombreux systèmes de file d’attente, quels que soient les types d’articles dans la file ou la manière dont ils sont traités dans la file. La loi de Little peut être utile pour analyser les performances d’une file d’attente pendant un certain temps ou pour évaluer rapidement les performances actuelles d’une file d’attente.

Par exemple : une entreprise de boîtes à chaussures veut connaître le nombre moyen de boîtes à chaussures qui sont stockées dans un entrepôt. L’entreprise sait que le taux moyen d’arrivée des boîtes dans l’entrepôt est de 1 000 boîtes à chaussures/an, et que le temps moyen passé dans l’entrepôt est d’environ 3 mois, soit ¼ d’une année. Ainsi, le nombre moyen de boîtes à chaussures dans l’entrepôt est donné par (1000 boîtes à chaussures/an) x (¼ an), soit 250 boîtes à chaussures.

Points clés à retenir

• La théorie de la file d’attente est l’étude mathématique de la file d’attente, ou de l’attente en ligne.
• Les files d’attente contiennent des « clients » tels que des personnes, des objets ou des informations. Les files d’attente se forment lorsque les ressources disponibles pour fournir un service sont limitées.
• La théorie des files d’attente peut être appliquée à des situations allant de l’attente dans une file d’attente à l’épicerie à l’attente d’un ordinateur pour effectuer une tâche. Elle est souvent utilisée dans les logiciels et les applications commerciales pour déterminer la meilleure façon d’utiliser des ressources limitées.
• La notation de Kendall peut être utilisée pour spécifier les paramètres d’un système de file d’attente.
• La loi de Little est une expression simple mais générale qui peut fournir une estimation rapide du nombre moyen d’articles dans une file d’attente.

Sources

• Beasley, J. E. « Queuing theory ».
• Boxma, O. J. « Stochastic performance modelling. » 2008.
• Lilja, D. Mesure de la performance des ordinateurs : A Practitioner’s Guide, 2005.
• Little, J., et Graves, S. « Chapitre 5 : La loi de Little ». Dans Building Intuition : Insights from Basic Operations Management Models and Principles. Springer Science+Business Media, 2008.
• Mulholland, B. « La loi de Little : Comment analyser vos processus (avec des bombardiers furtifs) ». Process.st, 2017.