Files d'attente markoviennes

Une file d'attente markovienne est caractérisée par des arrivées de Poisson et des temps de service exponentiels, ce qui fait du nombre de clients une chaîne de Markov en temps continu dont l'équilibre peut être résolu explicitement.

Definition

Une file d'attente markovienne est un système de service dans lequel les clients arrivent selon un processus de Poisson et nécessitent des temps de service exponentiels indépendants, de sorte que le nombre d'éléments dans le système évolue comme une chaîne de Markov en temps continu de naissance et de mort avec des distributions explicites d'état stationnaire et de temps d'attente.

Scope

Ce sujet couvre la notation de Kendall pour les systèmes de files d'attente, la file d'attente M/M/1 à serveur unique et sa distribution stationnaire géométrique, les systèmes M/M/c à serveurs multiples et les systèmes à perte, les formules d'Erlang B et C, la stabilité et l'intensité du trafic, ainsi que la dérivation de la longueur moyenne de la file d'attente, du temps d'attente et des quantités de période d'occupation à partir du processus sous-jacent de naissance et de mort.

Core questions

• Comment la file d'attente M/M/1 apparaît-elle comme un processus de naissance et de mort et quelle est sa distribution stationnaire ?
• Quelle condition sur l'intensité du trafic assure la stabilité de la file d'attente ?
• Comment la longueur moyenne de la file d'attente et le temps d'attente sont-ils obtenus, et comment la loi de Little est-elle appliquée ?
• Comment les serveurs multiples et la capacité finie modifient-ils les formules d'Erlang ?

Key theories

Distribution stationnaire et stabilité M/M/1

Le nombre d'éléments dans une file d'attente M/M/1 suit une distribution stationnaire géométrique avec un paramètre égal à l'intensité du trafic, le rapport du taux d'arrivée au taux de service, et la file d'attente est stable précisément lorsque ce rapport est inférieur à un.

Formules de perte et de délai d'Erlang

Pour les systèmes multi-serveurs, la formule d'Erlang B donne la probabilité de blocage dans un système à perte et la formule d'Erlang C donne la probabilité d'attente dans un système à délai, toutes deux dérivées des équations d'équilibre de naissance et de mort et centrales pour la planification de la capacité.

Clinical relevance

Les files d'attente markoviennes constituent les modèles fondamentaux pour le dimensionnement des groupes de lignes téléphoniques, la dotation en personnel des centres d'appels, les fermes de serveurs et les guichets de service, où les formules d'Erlang traduisent la charge offerte et les niveaux de service cibles en nombre de serveurs requis.

History

Erlang a dérivé les formules de perte et de délai pour le trafic téléphonique entre 1909 et 1917, Kendall a introduit la notation systématique arrivée/service/serveur et l'analyse des chaînes imbriquées en 1953, et le traité de Kleinrock dans les années 1970 a appliqué la théorie aux réseaux informatiques et de communication.

Key figures

• Agner Krarup Erlang
• David Kendall
• Leonard Kleinrock

Seminal works

• kleinrock1975

Frequently asked questions

Que signifie M/M/1 ?

Dans la notation de Kendall, le premier M désigne des arrivées markoviennes (Poisson), le second M désigne des temps de service exponentiels, et le 1 désigne un serveur unique.

Quand une file d'attente markovienne est-elle stable ?

Lorsque l'intensité du trafic, le taux d'arrivée divisé par le taux de service total, est inférieure à un ; sinon, la file d'attente croît sans limite et aucune distribution stationnaire n'existe.