5.

FILES D’ATTENTE :

5.1. Classification et notation de Kendall

La théorie des files d’attente (“queueing theory” en anglais) permet de modéliser

des situations où des clients arrivent à des temps aléatoires `a un serveur. Le serveur
peut être le guichet d’une banque, d’un bureau de poste, la caisse d’un
supermarché, une station-service par exemple, mais également un serveur
informatique dont les clients sont des tâches que le serveur doit traiter. Le temps
nécessaire à servir chaque client est également supposé aléatoire.
Les questions auxquelles l’on voudrait répondre sont par exemple :
• Quelle est la durée d’attente moyenne d’un client arrivant dans la file ?
• Pendant quelle fraction du temps le serveur est-il occupé ?
• Quelle est la distribution de probabilité de la longueur de la file ?
• Selon quel processus les clients quittent-ils le système, une fois servis ?
Il existe toute une série de modèles de files d’attente, qui se distinguent par la loi des
temps d’arrivée, la loi des temps de service, le nombre de serveurs, l’éventuelle
longueur maximale de la file, l’ordre de passage des clients.
La notation de Kendall permet de spécifier le modèle de manière compacte. Le
plus souvent, cette notation se compose de trois symboles :
A/B/s ,
où A désigne la loi des intervalles de temps entre arrivées des clients, B désigne la
loi des temps de service, et s est le nombre de serveurs. Les valeurs les plus usuelles
de A et B sont les suivantes :
• M (Markov) : Loi exponentielle. En effet, nous avons vu que cette loi implique la
propriété de Markov. Il s’agit du cas le plus simple à analyser.
• D (Déterministe) : Temps constant, c’est-`a-dire que les arrivées des clients sont
régulièrement espacées, respectivement le temps de service est le même pour tous
les clients.
• E (Erlang) : Loi dite d’Erlang, qui est en fait une loi Gamma (loi d’une somme de
variables exponentielles).
• G (Générale) : Loi arbitraire. Ce symbole s’utilise quand on dérive des propriétés
ne dépendant pas de la loi particulière considérée.
Si la longueur de la file est limitée à une valeur finie N, on utilise la notation
A/B/s/N
Par défaut, on suppose donc que N = ∞.

PROCESSUS ALEATOIRES 32
 Finalement, on peut aussi spécifier en dernier l’ordre dans lequel les clients sont
servis, la valeur par défaut étant FIFO (first in, first out), ce qui signifie que le premier
client arrivé est aussi le premier servi. Une alternative est LIFO (last in, first out). Dans
ce cas, les nouveaux arrivants se placent en tête de la file, et seront donc servis d`es
que le serveur se libère, à moins que d’autres clients n’arrivent entretemps.
5.2. Cas markoviens : Files d’attente M/M/s

Les files M/M/s sont les plus simples à analyser, puisque le caractère markovien des
temps d’arrivée et des temps de service implique que la longueur de la file est un
processus markovien de sauts.
5.2.1. Exemple : File M/M/1
Le cas le plus simple se présente pour un serveur unique, dont les clients arrivent selon
un processus de Poisson de paramètre λ, et dont le temps de service suit une loi
exponentielle de paramètre µ. L’hypothèse de temps d’arrivée poissonniers est
relativement réaliste, dès lors qu’on suppose que les clients proviennent d’un grand
réservoir d’individus indépendants. Celle des temps de service exponentiels est
beaucoup plus discutable. On la fait surtout parce qu’elle permet des calculs plus
explicites.
Soit Nt la longueur de la file au temps t. Elle évolue selon un processus de sauts de
taux de transition
q(n, n + 1) = λ si n ≥ 0 ,
q(n, n − 1) = µ si n ≥ 1 .
En d’autres termes, Nt suit un processus de naissance et de mort, chaque arrivée d’un
nouveau client étant assimilé à une naissance, et chaque départ d’un client servi
étant assimilé à une mort.
Si le processus admet une distribution invariante π, alors celle-ci satisfait
n

  n       0

La constante π(0) se détermine en exigeant que la somme des π(n) soit égale à 1.
Cette somme est une série géométrique, et on obtient
n
    
  n   1    si   
    
La distribution invariante suit donc une loi géométrique (décalée en 0). Si λ ≥ µ, la
série diverge, et il n’existe pas de distribution stationnaire. Dans ce cas, le taux

PROCESSUS ALEATOIRES 33
d’arrivée de nouveaux clients dépasse la capacité de traitement du serveur, et la
longueur de la file croît indéfiniment.
Supposons λ < µ, et que la file d’attente a atteint l’équilibre. On peut alors calculer
différentes quantités d’intérêt.
 La probabilité que le serveur soit occupé est donnée par

Pr ob  Nt  0  1    0  

C’est également la fraction du temps pendant laquelle le serveur est occupé.

Figure 11- Graphe associé à la file d’attente M/M/1.

 La longueur moyenne de la file est donnée par


/
  N t    n  n  
n 0 1  / 
où l’on a utilisé la valeur de l’espérance d’une loi géométrique. On notera
que ce nombre diverge lorsque λ/µ tend vers 1.

 Soit W le temps d’attente d’un client avant d’être servi. Sa loi se calcule en
distinguant deux cas.
o Si la file est vide à son arrivée, alors le temps d’attente est nul, et on
a


Pr ob W  0  Pr ob  Nt  0  1 

o Si par contre la file a une longueur n > 0 à l’arrivée du client, celui-ci
devra attendre que les n clients le précédent dans la file soient servis.
Le temps d’attente est donc la somme de n variables exponentielles
indépendantes de paramètre µ, qui suit une loi Gamma de paramètres
(n, µ). La densité de W est donnée par

 nt n1
f (t )     n  e t
n 1  n  1!
  
 n1t n1
 1   e  t  
  n 1  n  1 !

PROCESSUS ALEATOIRES 34
 
      e     t

En d’autres termes, conditionnellement à W > 0, W suit une loi
exponentielle de paramètre µ − λ.
 Le temps d’attente moyen avant d’être servi est donné par
 
W   0 tf (t )dt 

   
Le temps d’attente total moyen, en comptant le temps de service, vaut donc
1 1
 W   
  
5.2.2. Exemple : File M/M/1/N
Considérons maintenant le cas où la longueur de la file est limitée à N, c’est-
`a-dire que si un client arrive en trouvant une file de longueur N, alors il repart
sans rejoindre la file. Dans ce cas, le système est décrit par un processus
markovien de saut de taux de transition
q(n, n + 1) = λ si 0 ≤ n < N ,
q(n, n − 1) = µ si 0 < n ≤ N

Figure 12- Graphe associé à la file d’attente M/M/1/N.

C’est encore un processus de naissance et de mort, et la relation

n

  n       0

reste valable pour 1 ≤ n ≤ N. La seule différence est la normalisation, et en
effectuant la somme on obtient comme distribution stationnaire

 1   /    n
   si   
1    /   N 1   
  n   
 1
 si   
 N 1
Contrairement au cas d’une file de longueur arbitraire, la distribution
stationnaire existe toujours. Si λ < µ et qu’on fait tendre N vers l’infini, on
retrouve la distribution stationnaire de la file M/M/1.

PROCESSUS ALEATOIRES 35
5.2.3. Exemple : File M/M/s
Supposons que les clients forment une seule file d’attente, mais qu’il existe un
nombre s de serveurs en parallèle. Dès qu’un serveur se libère, le client en tête
de la file le rejoint. Dans ce cas, on a toujours q(n, n + 1) = λ, mais pour les taux
q(n, n − 1) il faut distinguer deux cas. Si la longueur n de la file est inférieure à
s, alors seuls n serveurs sont actifs, et les départs ont lieu au taux nµ. Par contre,
si n est supérieur ou égal à s, tous les serveurs sont occupés, et le taux des
départs est sµ. On a donc

 n si n  s
q (n, n  1)  
 ns si n  s
On a encore affaire à un processus de naissance et de mort, et la distribution
stationnaire, si elle existe, satisfait

 n
   1 
n



 
k 1  k  
   0      0
n!   
si n  s

 n  
 s n
       1 
n

        0      0  si n  s
 k 1  k   k  s 1  s  s !s ns   

Si λ < µs, on peut trouver π(0) tel que π soit une distribution de probabilité, et
alors il existe un état stationnaire. Sinon, la file ne possède pas de distribution
stationnaire.
On peut calculer les mêmes quantités que pour la file M/M/1, qui ont toutefois
des expressions plus compliquées. Une exception est le nombre moyen de
serveurs occupés, qui est donné par
s 

 n  n    s  n 
n 1 n  s 1

En observant sur l’expression de la distribution stationnaire (n) que

 n  n  si n  s

  n  1  
  s  n  si n  s


Figure 13- Graphe associé à la file d’attente M/M/s.

PROCESSUS ALEATOIRES 36
 on peut récrire la somme précédente sous la forme

   

n 1 
  n  1  
 n 0
 n 

Puisqu’il n’existe une distribution stationnaire que sous la condition λ/µ < s, on
obtient bien un nombre moyen de serveurs occupés inférieur à s. La
proportion de serveurs occupés est égale à λ/µs.
5.2.4. Exemple : File M/M/
L’existence d’un nombre infini de serveurs peut sembler fantaisiste, mais en
fait il s’agit d’une bonne approximation de situations dans lesquelles le
nombre de serveurs est grand par rapport au nombre de clients, comme par
exemple pour certaines centrales téléphoniques.
Dans ce cas, les taux de transition sont donnés par
q(n, n + 1) = λ si n ≥ 0 ,
q(n, n − 1) = nµ si n ≥ 1 .
La distribution stationnaire peut être calculée comme dans les cas
précédents, avec le résultat explicite
n

 
  n  e

  
n!
La longueur de la file, qui est dans ce cas égale au nombre de serveurs
occupés, suit donc une loi de Poisson d’espérance λ/µ.

Figure 14- Graphe associé à la file d’attente M/M/ ∞.

5.2.5. Théorème
Si λ < sµ, alors les clients servis quittent la file M/M/s selon un processus de
Poisson d’intensité λ.

Ce résultat caractérise la distribution des clients rejoignant une seconde file

après avoir été servis dans une première file.

PROCESSUS ALEATOIRES 37
5.3. Cas général : Files d’attente G/G/1
Le cas d’une file d’attente générale est sensiblement plus difficile à étudier,
car si les temps entre arrivées de clients et les temps de service ne sont pas
exponentiels, on perd la propriété de Markov. En effet, l’état actuel du
système ne suffit pas à déterminer son évolution future, qui dépend entre
autres du temps que le client actuellement servi a déjà passé au serveur.
Dans certains cas particuliers, on peut se ramener à un système markovien en
introduisant des états supplémentaires.
5.3.1. Exemple : File M/Er/
Supposons que les clients arrivent selon un processus de Poisson d’intensité λ,
mais que le temps de service suit une loi Gamma de paramètres (r, µ) avec
r≥ 2. Une interprétation possible de cette loi est que le service du client requiert
r actions successives, prenant chacune un temps exponentiel de paramètre
µ. Si Nt désigne la somme du nombre de clients dans la file, et du nombre
d’actions encore nécessaires pour finir de servir le client actuel, son évolution
suit un processus markovien de sauts de taux de transition
q(n, n − 1) = µ si n≥ 1 ,
q(n, n + r) = λ si n ≥ 0 .
En effet, le nombre d’actions à accomplir diminue de 1 avec un taux µ, et
augmente de r à l’arrivée de chaque nouveau client. Si λ < µ, on peut montrer
que ce système admet une distribution stationnaire, qui est une combinaison
linéaire de lois géométriques

Figure 15- Graphe associé à la représentation markovienne de la file d’attente M/Er/1.

En règle générale, toutefois, une telle représentation markovienne n’est pas

possible, et on fait appel à la théorie des processus de renouvellement. Un tel
processus est caractérisé par une suite de temps aléatoires 0 < T 1 < T2 < . . . ,
appelés temps de renouvellement, tels que le comportement sur chaque
intervalle de temps [Tn, Tn+1[ soit indépendant et de même loi que sur les autres
intervalles.
PROCESSUS ALEATOIRES 38
5.3.2. Théorème : Loi des grands nombres pour processus de renouvellement
Soit 1/µ l’espérance des intervalles Tn+1 − Tn, et soit Nt = sup {n : Tn ≤ t} la fonction
de comptage des temps de renouvellement. Alors

 1 
Pr ob lim N t     1 (5.3.1)
 t  t

De plus,
1
lim
t  t
 Nt    (5.3.2)

Cette dernière relation affirme que le nombre moyen de temps de

renouvellement converge vers µ en moyenne ergodique. µ peut donc être
considéré comme le taux du processus.
5.3.3. Théorème :
Soit une file d’attente dans laquelle les clients arrivent selon un processus de
renouvellement de taux λ, et dans laquelle ils sont servis pendant une durée
aléatoire de moyenne 1/µ.
Si λ < µ, et si la longueur initiale de la file est finie, alors la longueur de la file
atteindra 0 en un temps fini presque sûrement. De plus, le serveur sera occupé
pendant une fraction de temps λ/µ.
5.3.4. Définitions :
Soit Xt la longueur de la file au temps t, et soit Wn le temps d’attente du nième
client.
o On appelle longueur moyenne de la file la quantité L définie par
1 t
t  t 0
L  lim X s ds .

o la moyenne des temps d’attente est donnée par

1 n
W  lim
n  n
1 Wn
5.3.5. Théorème : Loi de Little
Soit  * le taux des clients qui arrivent et joignent la file. Alors

L  *W (5.3.3)

PROCESSUS ALEATOIRES 39
 5.3.6. Théorème : Propriété PASTA (Poisson arrivals see time averages)
Soit π(n) la proportion du temps pendant laquelle la file a une longueur n, et
soit an la proportion asymptotique des clients trouvant une file de longueur n
à leur arrivée. Alors

an    n  (5.3.4)

Bibliographie

[1] Nils Berglund, Processus aléatoires et applications. DEA. Université d’Orléans,

2010, pp.99. ffel-00439562v2f
[2] Mario Lefebvre, Processus stochastiques appliqués, Editions Hermann, 2006
[3] Sabin Lessard, Processus stochastiques : Cours et exercices corrigés, Editions
Ellipses, 2014
[4] Philippe Robert, Réseaux et files d’attente : méthodes probabilistes, Springer-
Verlag Berlin Heidelberg 2000

[5] Roy L. Streit, Poisson Point Processes: Imaging, Tracking, and Sensing, Springer,
ISBN 978-1-4419-6922-4

[6] Nick T. Thomopoulos, Fundamentals of Queuing Systems: Statistical Methods

for Analyzing Queuing Models, Springer, ISBN 978-1-4614-3712-3

PROCESSUS ALEATOIRES 40