Théorie des files d'attente

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

La théorie des files d'attente est une théorie mathématique relevant du domaine des probabilités, qui étudie les solutions optimales de gestion des files d’attente, ou queues. Une queue est nécessaire et se créera d'elle même si ce n'est pas anticipé, dans tous les cas où l'offre est inférieure à la demande, même temporairement. Elle peut s’appliquer à différentes situations : gestion des avions au décollage ou à l’atterrissage, attente des clients et des administrés aux guichets, ou bien encore stockage des programmes informatiques avant leur traitement. Ce domaine de recherches, né en 1917, des travaux de l’ingénieur danois Erlang sur la gestion des réseaux téléphoniques de Copenhague entre 1909 et 1920, étudie notamment les systèmes d’arrivée dans une queue, les différentes priorités de chaque nouvel arrivant, ainsi que la modélisation statistique des temps d’exécution. C'est grâce aux apports des mathématiciens Khintchine, Palm, Kendall, Pollaczek et Kolmogorov que la théorie s'est vraiment développée.

Description[modifier | modifier le code]

Une file d'attente se crée pour chaque cas où des clients désirent recevoir un service auprès d'un producteur. En informatique, on parlera de client et de serveur, ailleurs on préférera les termes d'unité et de station.

Aspects mathématiques[modifier | modifier le code]

Loi de Little[modifier | modifier le code]

la loi de Little dit que le nombre moyen \langle N \rangle de clients dans un système stable est égal à leur fréquence moyenne d'arrivée \lambda multipliée par leur temps moyen \tau passé dans le système :

 \langle N \rangle = \lambda \cdot \tau

Notation de Kendall[modifier | modifier le code]

Article détaillé : Notation de Kendall.

Il existe, évidemment, de très nombreux systèmes de files d'attente. La notation de Kendall permet de décrire le système par une suite de 6 symboles a/s/C/K/m/Z.

  • a indique la loi de probabilité des instants d'arrivées, par exemple GI pour la loi générale indépendante et M pour la loi exponentielle.
  • s indique la loi de probabilité de la durée du service (au guichet); on utilise les mêmes symboles que précédemment
  • C indique le nombre de serveurs (nombre de guichets)
  • K, c'est la capacité totale du système, c'est-à-dire le nombre de serveurs (C) + le nombre de places en attente
  • m indique la population totale de clients (par exemple: nombre d'inscrits sur une liste électorale dans le cas d'une file d'attente à un bureau de vote)
  • Z, la discipline de service, par exemple first in, first out (FIFO alias paps : premier arrivé, premier servi), Last in, first out, Nearest neighbour, etc.

Très souvent, les trois derniers symboles de la notation sont omis avec, par défaut, K infini, m infini et Z en paps.

Quelques résultats[modifier | modifier le code]

Avec:

  • \lambda = fréquence moyenne d'arrivées
  • \tfrac{1}{\mu} = temps moyen de service
  • A = \frac{\lambda}{\mu} = trafic offert (nombre moyen d'arrivées pendant le temps moyen de service) /!\ ne pas oublier S le nombre de serveur
File M/M/1 File M/M/S
Probabilité système vide (P0) 1 - A \frac{1}{\sum_{k=0}^{S-1} \frac{A^k}{k!} + \frac {A^S}{S!} \frac {1}{1-A/S} }
Probabilité d'attente (Pa) A P0 \cdot \frac{A^S}{(S-1)!(S-A)}
Nombre moyen de clients dans le système (<N>) \frac{A}{1 - A} A \left(1 + \frac{Pa}{S-A}\right)
Nombre moyen de clients en attente (<Na>) \frac{A^2}{1-A} A \cdot \frac{Pa}{S-A}
Nombre moyen de clients en service (au guichet) (<Ns>) A A
Temps moyen de séjour dans le système (\tau) \frac{1}{\mu} \cdot \frac{1}{1-A} \frac{1}{\mu} \cdot \left(1 + \frac{Pa}{S-A}\right)
Temps moyen d'attente (\tau_a)  \frac{A}{\mu (1-A)}  \frac{Pa}{\mu (S-A)}
Condition d'atteinte de l'équilibre ("pas d'engorgement")  \frac{\lambda}{\mu} < 1  \frac{\lambda}{S\mu} < 1

Voir aussi[modifier | modifier le code]