Théorie des files d'attente

La loi de Little énonce que le nombre moyen ${\displaystyle \langle N\rangle }$ de clients dans un système stable est égal à leur fréquence moyenne d'arrivée ${\displaystyle \lambda }$ multipliée par leur temps moyen ${\displaystyle \tau }$ passé dans le système : ${\displaystyle \langle N\rangle =\lambda \cdot \tau }$.

Quoique cet énoncé paraisse évident intuitivement, il n'en est pas moins remarquable, puisqu'il ne dépend ni du processus d'arrivée, ni de la discipline de service[6]. Il s'applique également à des serveurs à l'intérieur d'un serveur[7] ; la seule exigence est que le système soit stable et non-préemptif, ce qui exclut des états de transition comme la mise en route ou l'arrêt d'un serveur.

Dans certains cas, il est possible non seulement de relier la taille moyenne de la file d'attente au temps moyen d'attente, mais même de relier la loi de probabilité (et ses moments) de la taille de la file d'attente à celle du temps moyen d'attente[8].

Dans son article original de 1954, Little énonçait cette relation sans la démontrer[9] - [10]. Il en donna une première démonstration en 1961[11], simplifiée depuis par Jewell[12] et Eilon[13].

Il existe 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[14] - [15].

• 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 de Poisson ou 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 C de serveurs + 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 FIFO (first in, first out), LIFO (Last in, first out), Nearest neighbour, etc.

Très souvent, K est infini, m est infini, et Z en FIFO (encore dénoté par peps). Dans ce cas, les trois derniers symboles de la notation sont omis.

Avec :

• ${\displaystyle \lambda =}$ fréquence moyenne d'arrivées ;

• ${\displaystyle {\tfrac {1}{\mu }}=}$ temps moyen de service ;

• ${\displaystyle A=\rho ={\frac {\lambda }{\mu }}=}$ trafic offert (nombre moyen d'arrivées pendant le temps moyen de service). Attention à ne pas oublier S, le nombre de serveurs.

	File M/M/1	File M/M/S
Probabilité système vide (P0)	${\displaystyle 1-A}$	${\displaystyle {\frac {1}{\sum _{k=0}^{S-1}{\frac {A^{k}}{k!}}+{\frac {A^{S}}{S!}}{\frac {1}{1-A/S}}}}}$
Probabilité d'attente (Pa)	${\displaystyle A}$	${\displaystyle P0\cdot {\frac {A^{S}}{(S-1)!(S-A)}}}$
Nombre moyen de clients dans le système (<N>)	${\displaystyle {\frac {A}{1-A}}}$	${\displaystyle A\left(1+{\frac {Pa}{S-A}}\right)}$
Nombre moyen de clients en attente (<Na>)	${\displaystyle {\frac {A^{2}}{1-A}}}$	${\displaystyle A\cdot {\frac {Pa}{S-A}}}$
Nombre moyen de clients en service (au guichet) (<Ns>)	${\displaystyle A}$	${\displaystyle A}$
Temps moyen de séjour dans le système (${\displaystyle \tau }$)	${\displaystyle {\frac {1}{\mu }}\cdot {\frac {1}{1-A}}}$	${\displaystyle {\frac {1}{\mu }}\cdot \left(1+{\frac {Pa}{S-A}}\right)}$
Temps moyen d'attente (${\displaystyle \tau _{a}}$)	${\displaystyle {\frac {A}{\mu (1-A)}}}$	${\displaystyle {\frac {Pa}{\mu (S-A)}}}$
Condition d'atteinte de l'équilibre (« pas d'engorgement »)	${\displaystyle {\frac {\lambda }{\mu }}<1}$	${\displaystyle {\frac {\lambda }{S\mu }}<1}$