1 Files d’attente ∗

La théorie des files d’attente a été développée en 1917 par l’ingénieur danois ERLANG. Ce
formalisme permet essentiellement de modéliser le phénomène de partage de ressources. Il peut
s’appliquer à différentes situations comme : l’attente des malades dans un cabinet médical, la gestion
des abonnés dans une centrale téléphonique, des pièces à traiter dans un atelier de fabrication, des
feux lumineux dans un réseau routier, etc.

1.1 Processus de Poisson :

Le processus de Poisson est un processus stochastique à espace d’état discret et à temps continu,
tel que les variables aléatoires décrivant les temps d’inter-arrivées U1 = X(t1 ) − X(t0 ), U2 =
X(t2 ) − X(t1 ) ,..., Un = X(tn ) − X(tn−1 ) sont des variables indépendantes et identiquement dis-
tribuées selon une loi exponentielle.

Propriété :
Soit X un processus de Poisson et An la variable aléatoire mesurant l’instant d’arrivée du nième
client dans le système. Les variables aléatoires {Tn }n=1,2,... mesurant le temps séparant l’arrivée du
n − 1 ième client et celle du nième client : Tn = An − An−1 sont des variables aléatoires exponentielles
indépendantes et identiquement distribuées de paramètre λ.

Interprétation : Si les arrivées dans un système suivent un processus de Poisson de taux λ,

alors les inter-arrivées ont une distribution exponentielle de paramètre λ.

Propriété caractéristique du processus de Poisson :

Si les arrivées de clients dans un système suivent un processus de Poisson de paramètre λ, alors la
probabilité qu’un client arrive entre t et t + ∆t (∆t très petit) est égale à λ∆t, quel que soit le temps
t considéré et la probabilité qu’il arrive plus d’un client est négligeable.

1.2 Processus de Naissance et de Mort :

Ces processus ont de nombreuses applications en dynamique des populations et dans la théorie
des files d’attente. Ils se caractérisent par ce qui suit :
— Un processus de naissance et de mort est une chaı̂ne de Markov à temps continu, dont les
seules transitions possibles, à partir d’un état i, sont vers ses états voisins i − 1 et i + 1.
— Ce processus est spécifié par les taux de naissance qi,i+1 = λi et les taux de mortalité qi,i−1 = µi .
— Une transition d’un état i à un état i + 1 s’appelle une naissance et λi représente le taux de
naissance, qui correspond au nombre de naissances par unité de temps ∆t.
— Une transition d’un état i à un état i − 1 s’appelle une mort et µi représente le taux de
mortalité, qui correspond au nombre de morts par unité de temps ∆t.
— Lorsque le système à un instant donné t est dans un état i, on dit que la population à
l’instant t notée N (t) est de taille i (N (t) = i).

1.3 Description du modèle des files d’attente

Un système de file d’attente est un système dans lequel les clients (demandeurs de service) arrivent
suivant une loi probabiliste (le plus généralement poissonnienne) pour recevoir un service auprès d’une
station de service qui peut être constituée de un ou plusieurs serveurs (ressources). Ainsi, une file
d’attente est constituée d’un espace d’attente appelé buffer et d’une station de service mono ou
multi-serveurs.
∗. Pr. N. GHARBI, Faculté d’Informatique - USTHB

1
 Fig. 1: Processus de naissance et de mort

Arrivées des Serveur(s) Départ des

clients clients
Buffer
Station de service

Fig. 2: Système de file d’attente

Un client qui arrive de l’extérieur et trouve un serveur disponible est immédiatement servi puis
quitte le système dès la fin du service. Par conte, si tous les serveurs sont occupés, il patientera dans
l’espace d’attente jusqu’à ce qu’un serveur soit disponible pour que son service puisse commencer.
Une représentation graphique du modèle de file d’attente est donnée dans Figure ??.

Caractéristiques : †
Un système de file d’attente est caractérisé par :
— Le processus d’arrivée des clients : qui est généralement le processus de Poisson.
— Le processus de service.
— Le nombre de serveurs.
— La capacité maximale de la file d’attente (= espace du buffer + nombre de serveurs). Une FA
peut avoir une capacité finie ou infinie. Lorsqu’elle est finie et qu’un client trouve le buffer
plein et tous les serveurs occupés, il est perdu.
— La taille de la source de clients.
— La discipline de service : elle determine l’ordre dans lequel les clients sont retirés du buffer
pour être servis. Les disciplines les plus courantes sont :
— FIFO (First In First Out) : cela correspond à la file standard.
— LIFO (Last In First Out) : cela correspond à une pile.
— Random (aléatoire) : le prochain client qui sera servi est choisi aléatoirement.
— Round Robin (cyclique), etc.

Remarque : La distribution du temps de service la plus simple à étudier et la plus couram-

ment utilisée est la distribution exponentielle. Cependant, la propriété de perte de mémoire de la
loi exponentielle fait que celle-ci n’est généralement pas très réaliste pour modéliser des phénomènes
réels. On est donc souvent obligé de recourir à d’autres distributions de service : Constante, Hyper-
exponentielle, Cox, Erlang, PH, etc.

Notation de KENDALL : Elle normalise la description des files d’attente. Elle est de la forme
†. Pr. N. GHARBI, Faculté d’Informatique - USTHB

2
 Fig. 3: Le Processus sous-jacent à la file d’attente M/M/1

A/B/s/K/N/D où :
— A et B : désignent respectivement la loi du processus d’arrivée et la loi de service. La loi peut
être : Exponentielle ou markovienne (M), déterministe (D), générale (G), Cox, etc ;
— s : nombre de serveurs ;
— K : capacité ou taille de la file d’attente ;
— N : taille de la source de clients (population)
— D : discipline de service.
Lorsque les trois derniers éléments de la notation ne sont pas précisés, il est sous-entendu que
K = ∞, N = ∞ et D = F IF O.

1.4 Système de file d’attente M/M/1 ‡

Un système de file d’attente M/M/1 est équivalent au système M/M/1/∞/∞/F IF O. Ce modèle
est caractérisé par un processus d’arrivée Poisonnien, un processus de service exponentiel, une station
de service monoserveur (un seul serveur), une capacité infinie, une source infinie et une discipline de
service FIFO.

Supposons que le processus d’arrivée des clients suit un loi de Poisson de taux λ et la durée
du service est distribuée selon la loi exponentielle de taux µ. Ainsi, λ représente le nombre moyen
d’arrivées par unité de temps ∆t et µ représente le nombre moyen de services par unité de temps ∆t.

Le processus {N (t), t ≥ 0} sous-jacent à la file d’attente M/M/1 est un processus de naissance

et de mort dans lequel une transition de l’état i vers l’état i + 1 correspond à l’arrivée d’un nouveau
client et une transition de l’état i vers l’état i − 1 correspond à une fin de service et par conséquent au
départ du client. N (t) représente le nombre de clients présents dans le système à l’instant
t.
Ce processus est représenté dans la Figure ??.

1.5 Condition d’ergodicité

Comme le processus sous-jacent à la file M/M/1 est une chaine de Markov à temps continu et à
espace d’état infini, la condition de stabilité est donnée par : λ < µ ou bien : ρ < 1 où : ρ = λ/µ

1.6 Calcul de la distribution stationnaire

On note πi la probabilité que le système contient i clients en régime permanent. Ceci peut être
calculé en résolvant le système infini des équations d’état en régime stationnaire :
(0) : λπ0 = µπ1
(1) : (λ + µ)π1 = λπ0 + µπ2
‡. Pr. N. GHARBI, Faculté d’Informatique - USTHB

3
 (2) : (λ + µ)π2 = λπ1 + µπ3
......
......
(i) : (λ + µ)πi = λπi−1 + µπi+1 , ∀i ≥ 1
.....
.....
En remplaçant la 1ère équation dans la 2ème, la 2ème dans la 3ième et ainsi de suite, et en notant
ρ = λ/µ, on obtient :

(0) : λπ0 = µπ1 ⇒ π1 = (λ/µ).π0 ⇒ π1 = ρ.π0

(1) : λπ1 = µπ2 ⇒ π2 = (λ/µ).π1 = ρ.π1 ⇒ π2 = ρ2 .π0
(2) : λπ2 = µπ3 ⇒ π3 = (λ/µ).π2 = ρ.π2 ⇒ π3 = ρ3 .π0
......
......
(i) : λπi−1 = µπi , ∀i ≥ 1 ⇒ πi = (λ/µ).πi−1 = ρ.πi−1 ⇒ πi = ρi .π0
.....
.....
Ainsi, πi = ρi .π0 , ∀i ≥ 0
∑∞
En utilisant l’équation de normalisation : i=0 πi = 1

π0 + π1 + π2 + .... = 1

π0 + ρ.π0 + ρ2 .π0 + .... = 1

π0 [1 + ρ + ρ2 + ....] = 1
∑∞
π0 . i=0 ρi = 1

1
π0 . 1−ρ =1

Donc : π0 = 1 − ρ et πi = (1 − ρ).ρi , ∀i ≥ 0

1.7 Calcul des paramètres de performance en régime stationnaire §

1. Nombre moyen
∑ de clients dans la file (N ) : D’une manière générale, ce paramètre est
défini par : N = ∞i=0 i.π i

Dans le cas de la file M/M/1 :

N = 0.π0 + 1.π1 + 2.π2 + 3.π3 + ....

N = 0 + (1 − ρ).ρ + 2.(1 − ρ).ρ2 + 3.(1 − ρ).ρ3 + ....

N = ρ.(1 − ρ)[1 + 2.ρ + 3.ρ2 + ....]

∑∞
N = ρ.(1 − ρ). i=1 i.ρi−1

N = ρ.(1 − ρ). (1−ρ)

1
2

§. Pr. N. GHARBI, Faculté d’Informatique - USTHB

4
 ρ
Donc : N = 1−ρ

2. Débit moyen (X) :

En régime stationnaire, le débit moyen d’entrée Xe et égal au débit moyen de sortie Xs.
X = Xe = Xs

D’une manière générale, les arrivées se font suivant la loi exponentielle de taux λ, dans chaque
état où le système peut encore accueilir un nouveau client. Ainsi : Xe = λ.P rob{File non pleine}

De la même manière, le service s’effectue avec un taux µ dans chaque état où le système contient
au moins un client. Ainsi : Xs = µ.P rob{File non vide}.

Dans le cas de la file M/M/1 :

Xe = λ.P rob{File non pleine}

Xe = λ.(1 − P rob{File pleine})

Xe = λ.(1 − 0) = λ

Xs = µ.P rob{File non vide}

Xs = µ.(1 − P rob{File vide})

Xs = µ.(1 − π0 )

Xs = µ.[1 − (1 − ρ)]

Xs = µ.ρ = λ = Xe

3. Temps de réponse moyen (R) :

Le temps de réponse moyen appelé aussi temps moyen de séjour. Ce paramètre est obtenu en
utilisant la loi de Little qui est une relation générale appliquée à une grande classe de systèmes. Elle
ne concerne que le régime permanent d’un système (à condition qu’il soit stable). Cette loi est définie
de la façon suivante :

R = N /X

Dans le cas de la file M/M/1 :

ρ
R= . 1
1−ρ µ.ρ
= 1
µ.(1−ρ)

4. Temps d’attente moyen (W ) : ¶

Sachant que le temps de réponse moyen correspond à la somme du temps d’attente et du temps
nécessaire pour le service. Ainsi, le temps d’attente moyen peut être calculé comme suit :

W =R− 1
µ

5. Taux d’utilisation du serveur (U ) : Il correspond à la probabilité que le serveur soit occupé.

¶. Pr. N. GHARBI, Faculté d’Informatique - USTHB

5
 ∑∞
U= i=1 πi

U = 1 − π0

U = 1 − (1 − ρ) = ρ = λ
µ

Ainsi, quand λ augmente, la charge du serveur augmente, jusqu’à tendre vers 100% lorsque
λ −→ µ.

6. Probabilité qu’il y ait k clients au moins dans la file (Pk ) :

∑∞
Pk = i=k πi

Pk = πk + πk+1 + πk+2 + ...

Pk = (1 − ρ).ρk + (1 − ρ).ρk+1 + (1 − ρ).ρk+2 + ....

Pk = (1 − ρ).ρk .[1 + ρ + ρ2 + ....]

Pk = (1 − ρ).ρk . 1−ρ
1

Pk = ρ k

1.8 Système de file d’attente M/M/1/K ∥

Un système de file d’attente M/M/1/K est caractérisé par un processus d’arrivée Poisonnien,
un processus de service exponentiel, une station de service monoserveur, un buffer à capacité limitée
à K − 1, une source infinie et une discipline de service FIFO. Ainsi, le paramètre K représente le
nombre maximal de clients qui peuvent être présents dans le système (soit en attente ou en service).
Par conséquent, un client qui arrive alors qu’il y a K clients dans le système, est automatiquement
perdu.

On décrit l’évolution d’une file d’attente M/M/1/K par la CMTC donnée dans la Figure ??.
Le processus décrivant cette file est : {N (t), t ≥ 0} où : N (t) représente le nombre de clients
présents dans le système à l’instant t. Ainsi, l’espace d’état de cette chaı̂ne est fini : E =
{0, 1, 2, ..., K}.

1.9 Condition d’ergodicité

Comme le processus sous-jacent à la file M/M/1/K est une chaine de Markov à temps continu, à
espace d’état fini et irréductible. Ainsi, elle est ergodique pour toutes les valeurs de λ > 0 et µ > 0.

1.10 Calcul de la distribution stationnaire

Soit πi la probabilité que le système contient i clients en régime permanent. Les équations d’état
à l’équilibre sont données par :

(0) : λπ0 = µπ1

(1) : (λ + µ)π1 = λπ0 + µπ2
......
∥. Pr. N. GHARBI, Faculté d’Informatique - USTHB

6
 Fig. 4: Le Processus sous-jacent à la file d’attente M/M/1/K

......
(k − 1) : (λ + µ)πk−1 = λπk−2 + µπk
(k) : λπk−1 = µπk

En remplaçant la 1ère équation dans la 2ème, la 2ème dans la 3ième et ainsi de suite, et en notant
ρ = λ/µ, on obtient :

(0) : λπ0 = µπ1 ⇒ π1 = (λ/µ).π0 ⇒ π1 = ρ.π0

(1) : λπ1 = µπ2 ⇒ π2 = (λ/µ).π1 = ρ.π1 ⇒ π2 = ρ2 .π0
......
......
Ainsi de suite, jusqu’à k − 1 :

(k − 1) : λπk−1 = µπk ⇒ πk = (λ/µ).πk−1 = ρ.πk−1 ⇒ πk = ρk .π0

Ainsi, πi = ρi .π0 , ∀i, 0 ≤ i ≤ k

∑k
En appliquant l’équation de normalisation : i=0 πi = 1, on obtient : ∗∗

π0 + π1 + π2 + .... + πk = 1

π0 + ρ.π0 + ρ2 .π0 + .... + ρk .π0 = 1

π0 [1 + ρ + ρ2 + .... + ρk ] = 1
∑k
π0 . i=0 ρi = 1

⇒ π0 = ∑k
1
ρi
i=0

∑k ∑∞ ∑∞
i=0 ρi = i=0 ρi − i=k+1 ρi ... (1)
∑∞ 1
D’une part, i=0 ρi = 1−ρ
... (2)
∑∞
D’autre part, i=k+1 ρi = ρk+1 + ρk+2 + ρk+3 + .... = ρk+1 .[1 + ρ + ρ2 + ....]
∑∞ ρk+1
⇒ i=k+1
1
ρi = ρk+1 . 1−ρ = 1−ρ
... (3)

En remplaçant (2) et (3) dans (1), on obtient :

∗∗. Pr. N. GHARBI, Faculté d’Informatique - USTHB

7
 ∑k ρk+1 1−ρk+1
i=0 ρi = 1
1−ρ
− 1−ρ
= 1−ρ

1−ρ
Donc : π0 = 1−ρk+1

Finalement : πi = 1−ρ
1−ρk+1
.ρi , ∀i, 0 ≤i≤k

1.11 Calcul des paramètres de performance en régime stationnaire ††

1. Nombre moyen de clients dans la file (N ) :
∑k
Ce paramètre est défini par : N = i=0 i.πi

N = 0.π0 + 1.π1 + 2.π2 + 3.π3 + .... + k.πk

Sachant que πi = ρi .π0 , ∀i, 0 ≤ i ≤ k

N = 0 + ρ.π0 + 2.ρ2 .π0 + 3.ρ3 .π0 + .... + k.ρk .π0

N = ρ.π0 .[1 + 2.ρ + 3.ρ2 + .... + k.ρk−1 ]

∑k
N = ρ.π0 . i=1 i.ρi−1
∑k ∑∞ ∑∞
i=1 i.ρ
i−1
= i=1 i.ρ
i−1
− i=k+1 i.ρi−1 ... (1)
∑∞ 1
D’une part, i=1 i.ρi−1 = (1−ρ)2
... (2)

D’autre part,
∑∞
i=k+1 i.ρi−1 = (k + 1).ρk + (k + 2).ρk+1 + (k + 3).ρk+2 + ....

= k.ρk + k.ρk+1 + k.ρk+2 + .... + ρk + 2.ρk+1 + 3.ρk+2 + ....

= k.ρk [1 + ρ + ρ2 + ....] + ρk .[1 + 2.ρ + 3.ρ2 + ....]

1 1
= k.ρk . 1−ρ + ρk . (1−ρ)2

k.ρk .(1−ρ)+ρk
= (1−ρ)2

= ρk . k(1−ρ)+1
(1−ρ)2

= ρk . k−kρ+1
(1−ρ)2
... (3)

En remplaçant (2) et (3) dans (1), on obtient :

∑k 1−ρk .(k−kρ+1)
i=1 i.ρi−1 = 1
(1−ρ)2
− ρk . k−kρ+1
(1−ρ)2
= (1−ρ)2

k
Donc : N = ρ.π0 . 1−ρ (1−ρ)
.(k−kρ+1)
2

1−ρ
Sachant que : π0 = 1−ρk+1

††. Pr. N. GHARBI, Faculté d’Informatique - USTHB

8
 ρ(1−ρ) 1−ρk .(k−kρ+1)
N= 1−ρk+1
. (1−ρ)2

ρ 1−ρk .(k−kρ+1)
N= 1−ρ
. 1−ρk+1

ρ 1−k.ρk −ρk +k.ρ.ρk

N= 1−ρ
. 1−ρk+1

ρ 1−(k+1).ρk +k.ρk+1
Ainsi, N = 1−ρ
. 1−ρk+1

2. Débit moyen (X) : ‡‡

En régime stationnaire, le débit moyen d’entrée Xe et égal au débit moyen de sortie Xs.
X = Xe = Xs

Débit moyen entrant :

Xe = λ.P rob{File non pleine}

Xe = λ.(1 − P rob{File pleine})

Xe = λ.(1 − πk )

Xe = λ.[1 − 1−ρ
1−ρk+1
.ρk ]
k+1 −ρk +ρk+1
Xe = λ.[ 1−ρ 1−ρk+1
]

1−ρ k
Xe = λ. 1−ρk+1

Débit moyen sortant :

Xs = µ.P rob{File non vide}

Xs = µ.(1 − P rob{File vide})

Xs = µ.(1 − π0 )

Xs = µ.[1 − 1−ρ
1−ρk+1
]

−1+ρ
k+1
Xs = µ.[ 1−ρ1−ρk+1 ]
k+1
Xs = µ.[ ρ−ρ
1−ρk+1
]

1−ρ k 1−ρ k
Xs = µ.ρ.[ 1−ρ k+1 ] = λ.[ 1−ρk+1 ] = Xe

3. Temps de réponse moyen (R) :

Ce paramètre est obtenu en utilisant la loi de Little : R = N /X

ρ 1−ρk .(k−kρ+1) 1−ρk+1

R= 1−ρ
. 1−ρk+1 . λ.(1−ρk )

ρ 1−ρk .(k−kρ+1)
Donc, R = 1−ρ
. λ.(1−ρk )

4. Temps d’attente moyen (W ) :

‡‡. Pr. N. GHARBI, Faculté d’Informatique - USTHB

9
 Le temps d’attente moyen peut être calculé comme suit : W = R − 1
µ

5. Taux d’utilisation du serveur (U ) : Il correspond à la probabilité que le serveur soit occupé.

∑k
U= i=1 πi = 1 − π0

U =1− 1−ρ
1−ρk+1

1−ρk+1 −1+ρ
U= 1−ρk+1

ρ−ρk+1
U= 1−ρk+1

6. Taux de perte (T P ) : Il correspond à la probabilité qu’un client ne soit pas admis par le
système.
1−ρ
T P = πk = ρk . 1−ρk+1

10