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

Théorie des files d'attente est l'étude mathématique de la file d'attente ou de l'attente en ligne. Files d'attente contenir les clients (ou «éléments») tels que des personnes, des objets ou des informations. Les files d'attente se forment lorsque les ressources sont limitées pour fournir un 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.

Un basique système de file d'attente consiste en un processus d'arrivée (comment les clients arrivent à la file d'attente, combien de clients sont 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ématique modèles de file 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 en ligne? Quel est le temps d'attente moyen par client?

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

• Faire la queue dans une banque ou un magasin
• Attendre qu'un représentant du service client réponde à un appel une fois que l'appel a été mis en attente
• En attendant l'arrivée d'un train
• En attente d'un ordinateur pour effectuer une tâche ou répondre
• En attente d'un lave-auto automatisé pour nettoyer une ligne de voitures

Les modèles de file d'attente analysent la façon dont les clients (y compris les personnes, les objets et les informations) reçoivent un service. Un système de mise en 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 groupes, et ils peuvent arriver à certains intervalles ou au hasard.
• Comportement. Comment les clients se comportent-ils lorsqu'ils sont en ligne? Certains pourraient vouloir attendre leur place dans la file d'attente; d'autres peuvent s'impatienter et partir. D'autres encore pourraient décider de rejoindre la file d'attente plus tard, comme lorsqu'ils sont mis en attente avec le service client et décider de rappeler dans l'espoir de recevoir un service plus rapide.
• Comment les clients sont servis. Cela comprend la durée de la maintenance d'un client, le nombre de serveurs disponibles pour aider les clients, si les clients sont servis un par un ou par lots, et 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 prochain client 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 service. Par exemple, les clients peuvent être servis par ordre de priorité ou en fonction du nombre d'articles dont ils ont besoin (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 du 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.

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

• Le terme A décrit quand les clients arrivent à la file d'attente - en particulier, le temps entre les arrivées, ou temps interarrivales. Mathématiquement, ce paramètre spécifie le distribution de probabilité que les temps interarrivaux suivent. Une distribution de probabilité commune utilisée pour le terme A est la Distribution de Poisson.
• Le terme S décrit le temps qu'il faut pour qu'un client soit réparé après avoir quitté la file d'attente. Mathématiquement, ce paramètre spécifie la distribution de probabilité que ces temps de service suivre. La distribution de Poisson est également couramment utilisée pour le terme S.
• Le terme c spécifie 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, ils peuvent donc tous être décrits par le terme S ci-dessus.
• Le terme B spécifie le nombre total d'éléments qui peuvent être dans le système et inclut les éléments qui sont toujours dans la file d'attente et ceux qui sont en cours de maintenance. 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 grande, le système est généralement supposé infini.
• Le terme N spécifie le nombre total de clients potentiels - c'est-à-dire le nombre de clients qui pourraient jamais entrer dans le système de file d'attente - qui peut être considéré comme fini ou infini.
• Le terme D spécifie la discipline de service du système de mise en file d'attente, comme le premier arrivé, premier servi ou le dernier entré, premier sorti.

La loi de Little, qui a été prouvé pour la première fois par le mathématicien John Little, déclare que le nombre moyen d'éléments 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 pendant lequel ils dépenser en elle.

• En notation mathématique, la loi de Little est: L = λW
• L est le nombre moyen d'articles, λ est le taux d'arrivée moyen 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 mise en file d'attente, quels que soient les types d'éléments dans la file d'attente ou la façon dont les éléments sont traités dans le queue. La loi de Little peut être utile pour analyser les performances d'une file d'attente au fil du temps ou pour évaluer rapidement les performances actuelles d'une file d'attente.

Par exemple: une entreprise de boîtes à chaussures veut déterminer 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 qu'elles passent dans l'entrepôt est d'environ 3 mois, soit ¼ d'année. Ainsi, le nombre moyen de boîtes à chaussures dans l'entrepôt est donné par (1000 boîtes à chaussures / an) x (¼ an), ou 250 boîtes à chaussures.

• 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 sont limitées pour fournir un service.
• La théorie de la file d'attente peut être appliquée à des situations allant de l'attente en ligne à l'épicerie à l'attente d'un ordinateur pour effectuer une tâche. Il est souvent utilisé 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 mise en 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'éléments dans une file d'attente.

• Beasley, J. E. "Théorie des files d'attente."
• Boxma, O. J. "Modélisation des performances stochastiques." 2008.
• Lilja, D. Mesure des performances informatiques: guide du praticien, 2005.
• Little, J. et Graves, S. "Chapitre 5: La loi de Little." Dans Renforcer l'intuition: aperçu des modèles et principes de base de la gestion des opérations. Springer Science + Business Media, 2008.
• Mulholland, B. "La loi de Little: comment analyser vos processus (avec des bombardiers furtifs)."Process.st, 2017.