2.1.2 Analyse mathématique d'un système
de files d'attente
La description mathématique d'une file d'attente se fait
par l'introduction des processus stochastiques suivants :
. {Xt, t = 0} o`u Xt correspond au nombre de clients dans le
système a` la date t; . {Wn, m = 1} o`u Wn
correspond a` la durée d'attente du mieme client;
. {At, t = 0} o`u At est le nombre d'arrivée a` la date
t;
. {Nt, t = 0} o`u Nt est le nombre de clients pouvant être
servis si le serveur travaillait sans interruption durant la période
[0,t];
. {Dt, t = 0} o`u Dt est le nombre d'arrivées a` la date
t.
Ces quantités peuvent être considérées
comme les caractéristiques essentielles du système.
2.2 Files d'attente markoviennes
Les files d'attentes makoviennes sont celles pour lesquelles
les inter-arrivées et les durées de service sont exponentielles.
Leur notation de Kendall sera de la forme M/M/... (M comme markovien).
2.2.1 La file d'attente M/M/1
Pour ce système, le plus simple de la théorie des
files d'attente, le flux des arrivées est poissonnien de
paramètre ë et la durée de service est exponentielle de
paramétre u.
Régime transitoire
Soit le processus stochastique {X(t), t = 0} : »le nombre
de clients dans le système a` l'instant t ». Gràace aux
propriétés fondamentales du processus de Poisson et de la loi
exponentielle suivante :
. P(exactement une arrivée pendant At) = At + o(At);
. P(aucune arrivée pendant At )= 1 - At + o(At); . P(2
arrivées ou plus pendant At)= o(At);
. P(exactement 1 départ pendant At/X(t) = 1 )= ut +
o(At);
. P(aucun départ pendant At/X(t) = 1 )= 1 - ut + o(At);
. P(2 départs ou plus pendant At )= o(At).
Dans ce cas, la matrice des taux de transition P = (Pij)i,j?N
prend la forme suivante :
?
? ? ? ? ? ?
P=
?
??????
-A A 0 . .
-( + A) A 0
0 -( + A) A 0
...
...
0 -( + A) A
... 0 ...
Et le graphe représentatif du processus de naissance et
mort de la file d'attente M/M/1 est donnésous la forme:
FIGURE 2.2 - Graphe représentatif du processus de
naissance et de mort
{
P ' 0(t) = -AP0(t) + P1(t); (2.1)
P '
n(t) = -(A + )Pn(t) + APn_1(t) + Pn+1(t), m =
1, 2, ...
o`u Pn(t) = P(Xt = m).
Si A < , le processus {Xt, t = 0} converge vers une variable
aléatoire X dont la distribution ð est définie par [9] :
ðn = (1 - p)pn,
o`u p = A/ , m = 0,1,...
Caractéristiques de la file M/M/1
La file M/M/1 est stable (A < , c'est-à-dire p <
1).
- Le nombre moyen de clients dans la file Lq :
Le nombre moyen de clients dans la file ne dépend que du
taux de charge p :
|
>
E[m] =
n>0
|
mð(m) = p
1 - p = Lq,
|
- Temps moyen de séjour W est obtenu par:
|
L
W = ë
|
|
1
|
|
|
=
|
|
|
|
u(1 -- ñ),
|
|
qui peut se décomposer en :
|
1
W = u
|
ñ
+ u(1 -- ñ).
|
On déduit alors, le temps moyen passédans la file
d'attente Wq :
ñ
Wq = u(1 -- ñ),
- D'après la formule de Little, le nombre moyen de clients
dans le système de la file d'attente
stable M/M/1 est donnépar le produit de leur taux
d'arrivée ëe et leur temps de séjour moyen W :
L = ëeW = ñ2 .
1 -- ñ
2.2.2 La file d'attente M/M/m
On considère un système identique a` la file M/M/1
exceptéqu'il comporte m serveurs identiques et indépendants les
uns des autres.
On conserve les hypothèses : processus
d'arrivées des clients poissonnien de taux u et temps de service
exponentiel de taux ë (pour chacun des serveurs). Ce système est
connu sous le nom de file M/M/m. L'espace d'états S est, comme pour la
M/M/1 infini, S = {0, 1, 2, ...}. On a un processus de naissance et de mort de
taux :
ën = ë.
0, si n = 0;
nu, si 0 < n < m; (2.2)
mu, si n = m.
La condition de stabilitéici est ë < mu, et
exprime le fait que le nombre moyen de clients qui arrivent a` la file par
unitéde temps doit être inférieur au nombre moyen de
clients que les serveurs de la file sont capables de traiter par unitéde
temps.
On peut donner ðn comme suit [15] :
ðk = ñkmm
{ (mñ)k
m! , k = m, m + 1, ...
k! , k = 0, 1..., m -- 1; (2.3)
avec,
m-1X
k=1
mñ)k k! ].
mñ)m
ð0 = [1 + m!(1 - ñ) +
Le graphe représentatif du processus de naissance et mort
est :
FIGURE 2.3 - Graphe de la file d'attente M/M/m
Caractéristiques de la file M/M/m
La file M/M/m, est plus simple (au niveau des calculs). On
calcule d'abord le temps moyen de séjour et on déduit le nombre
moyen de clients.
- Temps moyen de séjour W :
Le temps moyen de séjour d'un client se
décompose en un temps moyen dans la file d'attente, plus un temps moyen
de service. Il suffit alors d'appliquer la formule de Little a` la seule
file
|
1
W = Wq + u
|
Lq
= ë +
|
1
u
|
,
|
Il reste alors a` calculer le nombre moyen de clients en attente
dans la file, Lq :
Lq = X8 ðn,
n=m+1
Lq = ñ (ë/u)n
(1 - ñ2) m!mn-m ð0.
o`u, ñ = ë/mu.
On en déduit l'expression du temps moyen de
séjour
|
W = ñ
(1 - ñ2)
|
(ë/u)n
ð0 +
m!mn-m
|
1
u
|
,
|
- Nombre moyen de clients L :
Le nombre moyen de clients s'obtient alors par application de la
formule de Little:
L = WA = A( p (A/u)
(1
n 1
ð0 + ).
- p2) m!mn-m u
| 
