Télécom 2A module Evaluation de Performances

Aide mémoire sur la file M/GI/1

Le processus de Poisson joue un rôle fondamental dans la modélisation d’arrivée de clients
dans des files d’attente. L’objectif de ce chapitre est d’étudier une file d’attente avec un seul
serveur et des temps de service indépendants identiquement distribués de loi générale. On notera
F la fonction de répartition de cette loi et, lorsqu’elle est bien définie f sa fonction de densité.
On supposera que la discipline de service est FIFO.
Le processus d’arrivée de clients, noté At , est un processus de Poisson d’intensité λ. On se
donne comme variable d’état le couple (Nt , Rt ) où Nt est le nombre de clients présents dans la
file à l’instant t et Dt le temps de service déjà effectué pour le client en service (age du client).
Le processus (Nt , Rt ) est un processus de Markov à valeur dans N × R+ . L’espace d’état est
continu, il est par conséquent difficile à analyser directement. On sait cependant que la condition
de stabilité du système est
∆
ρ = λES < 1,

ρ est appelé charge de la file d’attente. Cela correspond au taux d’utilisation du serveur.
Pour simplifier l’analyse, on étudie le processus à des instants spécifiés (les instants de fin
de service). Notons 0 < t1 < · · · < tn < · · · les instants de départ des clients 1, 2, · · · , n, · · · .
Le processus {Nn }n∈N défini par

Nn = Nt+n ,

nombre de clients dans la file juste après le départ du nième client, est un processus de Markov
en temps discret et à valeur dans N. En effet, les équations d’évolution s’écrivent

Nn + Yn+1 − 1 si Nn > 1,
Nn+1 =
Yn+1 si Nn = 0,

où Yn+1 = Atn+1 − Atn est le nombre de clients arrivés pendant le (n + 1)ième service. Comme
les intervalles de temps ]ti , ti+1 ] sont disjoints et que le processus d’arrivée est un processus
de Poisson, les variables aléatoires Yn sont indépendantes. Comme les temps de service sont
indépendants de même loi, les variables aléatoires Yn sont iid. {Nn }n∈N est donc une chaîne de
Markov homogène..
Les probabilités de transition de cette chaîne sont définies par la distribution des variables
Yn . On note

aj = P(Yn = j).

En conditionnant par la durée du service et en utilisant les propriétés du processus de Poisson,

on obtient
Z +∞
(λs)j −λs
aj = e f (s)ds.
0 j!
On notera GA (z) = Ez Y la fonction génératrice associée aux Yn .

INPG 2005 1/ 4
Télécom 2A module Evaluation de Performances
a3 a4 a4

a2 a3 a3

a1 a2 a2 a2

a0 a0 a0 a0
a0 a1 a1 a1

F IG . 1 – Graphe de la chaîne de Markov incluse {Nn }n∈N

La matrice de transition de {Nn } est donc

 
a0 a1 a2 · · · · · · · · · · · · · · ·
 a0 a1 a2 · · · · · · · · · · · · · · · 
 
 0 a0 a1 a2 · · · · · · · · · · · · 
 
 0 0 a0 a1 a2 · · · · · · · · · 
.
 .. . . . . . .

 . . . .


 . 
 .. 
 
..
.
Comme ai > 0 car le processus d’arrivée est un processus de Poisson, la chaîne de Markov est
apériodique et irréductible. Soit π = (π0 , · · · , πn , · · · ) le vecteur de probabilité stationnaire.
Les équations de Chapman-Kolmogorov s’écrivent :
k+1
X
π k = π 0 ak + πj ak+1−j k > 0.
j=1

πk z k . En multipliant
P
Pour résoudre ces équations, on passe par la série génératrice G(z) =
k
l’équation ci-dessus par z et en faisant la somme de tous les équations on obtient :
1
G(z) = π0 GA (z) + (G(z) − π0 )GA (z).
z
Ceci se réécrit
GA (z)
G(z) = π0 GA (z)−1
.
1− z−1

Le calcul de π0 est obtenu en utilisant le fait que G(1) = 1. Donc en faisant tendre z vers 1 dans
l’expression précédente et en utilisant le fait que G0A (1) = λES on tire
GA (z)
G(z) = (1 − ρ) GA (z)−1
.
1− z−1

En utilisant l’expression de la série génératrice par la transformée de Laplace du temps de

service
GA (z) = LS (λ(1 − z)),

INPG 2005 2/ 4
Télécom 2A module Evaluation de Performances
on obtient

Théorème 1 (Formule de Pollaczek-Khintchine) La serie génératrice du nombre de clients

à l’état stationnaire, aux instants de départ des clients d’une file d’attente M/GI/1 est donnée
par la formule :
LS (λ(1 − z))
G(z) = (1 − ρ) LS (λ(1−z))−1
.
1− z−1

La difficulté est de passer de la distribution stationnaire de Nn à la distribution stationnaire

de Nt . Une propriété importante de la file d’attente M/GI/1 est que les clients qui arrivent
voient le système à l’état stationnaire. Cette propriété, notée P AST A (Poisson Arrival see Time
Average), peut être démontrée dans un cadre beaucoup plus général [1] page 54, [2] page 293.
Comme conséquence de cette propriété, G est la fonction génératrice de Nt à l’état stationnaire.
Cette formulation de la fonction génératrice permet de calculer le nombre moyen de clients
dans la file à l’état stationnaire :

Corollaire 1
Le nombre moyen de clients dans une file M/GI/1 à l’état stationnaire est donné par
ρ2 (1 + CS2 )
EN = ρ + ,
2(1 − ρ)
avec ρ = λES et CS2 le coefficient de variation du temps de service
V ar(S)
CS2 = .
(ES)2
On calcule alors pour différentes distributions en utilisant la valeur de la variance du temps de
service.
File M/D/1 Dans ce cas la variance du temps de service est nulle, CS2 = 0 et
ρ ρ
EN = (1 − ).
1−ρ 2
File M/M/1 Dans le cas d’une loi exponentielle, CS2 = 1 et
ρ
EN = .
1−ρ
On retrouve les résultats obtenus par l’approche markovienne.
File M/Ek /1 La loi du temps de service est une loi d’Erlang de paramètre k, de temps moyen
de service 1 et de CS2 = k1 .
 
ρ ρ 1
EN = 1 − (1 − ) .
1−ρ 2 k
La figure suivante montre les écarts lorsque l’on fait varier le coefficient de varaition de 0 à 1
pour des lois d’Erlang de moyenne 1 (c’est à dire des lois γ(n, n)).

INPG 2005 3/ 4
Télécom 2A module Evaluation de Performances
Densité EN
1 5
E(1) Constant
Erlang(2)
Erlang(3) E(1)
Erlang(4)
0.8 4 Erlang(2)
Erlang(3)
Erlang(4)
0.6 3

0.4 2

0.2 1

0 0
0 1 2 3 4 x 0 0.2 0.4 0.6 0.8 1
Charge

F IG . 2 – Densité des temps de service et courbes du nombre moyen de clients fonction de la

charge.

Il faut noter que le nombre moyen de clients est minimum pour la file à temps de service
constant (voir le chapitre sur la comparaison de performances). De plus, lorsque le coefficient
de variation est inférieur à 1 le modèle markovien donne une borne supérieure sur le nombre
moyen de clients. On se place donc dans un cas “pessimiste” pour l’évaluation de performances.
De plus, ces courbes donnent une indication sur l’erreur faite entre un modèle markovien et un
modèle déterministe. Cette erreur n’est souvent pas significative par rapport aux erreurs de
modélisation et d’estimation des paramètres.

Références
[1] F. Baccelli and P. Brémaud. Elements of Queuing Theory. Springer-Verlag, 1994.
[2] R.W. Wolff. Stochastic Modelling and the Theory of Queues. Prentice-Hall, Englewood
Cliff, 1989.

INPG 2005 4/ 4