Théorie des files d'attente

Flashcards de vocabulaire couvrant les principes théoriques, formules, mesures de performance et modèles (Kendall, Little, M/M/1, M/M/c, Erlang B) de la théorie des files d'attente.

Agner Krarup Erlang

Ingénieur danois de la Copenhagen Telephone Company (KTAS) ayant introduit l'usage de la loi de Poisson pour dimensionner les lignes téléphoniques, à l'origine de l'unité erlang et des formules Erlang B et C (1917).

Notation de Kendall

Notation standardisée sous la forme $A/B/c/K/N/D$ décrivant un modèle de file d'attente selon les lois d'arrivée ($A$), de service ($B$), le nombre de serveurs ($c$), la capacité ($K$), la population ($N$) et la discipline ($D$).

Loi Markovienne ($M$ dans la notation de Kendall)

Loi désignant des arrivées suivant un processus de Poisson ou des durées de service exponentielles, caractérisées par l'absence de mémoire.

FIFO (First In, First Out)

Discipline de service « premier arrivé, premier servi » où les clients sont traités rigoureusement dans leur ordre d'arrivée.

LIFO (Last In, First Out)

Discipline de service « dernier arrivé, premier servi » où le dernier client entré est le premier pris en charge.

SIRO (Service In Random Order)

Discipline de file d'attente où le choix du prochain client à servir s'effectue selon un ordre aléatoire.

Loi d'Erlang d'ordre $k$ ($E_k$)

Loi de probabilité modélisant une somme de $k$ lois exponentielles indépendantes de même taux, où $k$ représente le nombre d'étapes de la chaîne de service.

Propriété sans mémoire

Propriété des lois exponentielle et de Poisson selon laquelle le temps déjà écoulé n'affecte pas la probabilité du temps restant : $P(T > s + t \times (T > s)^{-1}) = P(T > t)$.

Taux d'arrivée ($\lambda$)

Nombre moyen d'éléments ou de clients arrivant dans le système par unité de temps.

Taux de service ($\mu$)

Nombre moyen de clients qu'un serveur individuel est capable de traiter par unité de temps.

Taux d'occupation ($\rho$)

Fraction moyenne du temps pendant laquelle un serveur est occupé, calculée par $\rho = \frac{\lambda}{\mu}$ pour un serveur ou $\rho = \frac{\lambda}{c \times \mu}$ pour $c$ serveurs.

Condition de stabilité

Critère imposant que le taux d'occupation respecte $\rho < 1$ afin d'éviter que la file d'attente ne s'accroisse indéfiniment.

Grandeur $L$

Nombre moyen total de clients présents dans le système complet (somme de ceux qui attendent dans la file et de ceux en cours de service).

Grandeur $L_q$

Nombre moyen de personnes ou de clients en attente uniquement dans la file, sans compter ceux qui se font servir.

Grandeur $W$

Temps moyen passé par un client dans la totalité du système (incluant l'attente en file et le temps de service).

Grandeur $W_q$

Temps moyen qu'un client passe uniquement à attendre dans la file avant le début de son service.

Loi de Little

Relation fondamentale valable pour tout système stable reliant le nombre moyen d'éléments au temps de séjour moyen : $L = \lambda W$ et $L_q = \lambda W_q$.

Modèle $M/M/1$

Modèle fondamental comprenant des arrivées markoviennes, un temps de service exponentiel, un seul serveur ($c = 1$), une capacité infinie et une discipline FIFO.

Probabilité de système vide ($P_0$ dans $M/M/1$)

Probabilité qu'il n'y ait aucun client dans un modèle $M/M/1$, donnée par la formule $P_0 = 1 - \rho$.

Modèle $M/M/c$

Modèle de file d'attente markovienne généralisé comportant $c$ serveurs identiques fonctionnant en parallèle.

Formule d'Erlang C ($C(c, \frac{\lambda}{\mu})$)

Probabilité qu'un client doive attendre dans la file d'attente à son arrivée dans un système multi-serveur $M/M/c$.

Modèle Erlang B ($M/M/c/c$)

Modèle à capacité limitée sans file d'attente comportant $c$ lignes ou serveurs ; tout appel ou client arrivant quand les $c$ serveurs sont occupés est immédiatement rejeté.

Intensité de trafic ($a$)

Rapport $a = \frac{\lambda}{\mu}$ mesuré en erlangs, représentant le nombre moyen de lignes qui seraient occupées si aucun client n'était rejeté.

Formule d'Erlang B ($B(c, a)$)

Formule calculant la probabilité de perte ou de blocage (probabilité que toutes les $c$ lignes soient occupées) : $B(c, a) = \frac{\frac{a^c}{c!}}{\sum_{k=0}^{c} \frac{a^k}{k!}}$.

Principe du rendement décroissant (télécommunication)

Principe observant que chaque ligne téléphonique additionnelle réduit de moins en moins la probabilité de perte $B$, car l'état de saturation totale devient de plus en plus rare.